Mapeamento da cache

Prévia do material em texto

MAPEAMENTO DA CACHE – RESUMO 
 
Mapeamento Direto 
 
 De acordo com esta técnica, cada bloco da memória principal (MP) tem uma linha da cache 
previamente definida para onde ele pode ser alocado. Como há mais blocos da MP do que linhas da cache, 
muitos blocos serão destinados a uma mesma linha (um de cada vez, em diferentes momentos, é claro). 
 Genericamente, a MP possui N palavras (células) que podem ser divididas em B blocos. Se a cache 
tem M linhas de C células, então B = N/C. Seja, por exemplo, uma memória principal com capacidade de 4M 
palavras (células), o que requer endereços com 22 bits (N = 2
22
 = 4M), e uma cache associada a esta memória 
RAM com um tamanho de 64 Kbytes distribuídos em 1024 (M = 2
10
 = 1K) linhas, com 64 (C) bytes de dados 
cada uma (64 palavras de dados). Uma célula requer 6 bits de endereço (2
6
 = 64). A quantidade de bytes da 
linha da cache tem que ser a mesma do bloco de dados da memória principal (64 bytes). A memória principal 
de 4M é, então, dividida em 64K blocos de 64 bytes cada (B = N/C = 4M/64 = 2
16
 = 65536 blocos), 
numerados de 0 a 65535 (0x0000 a 0xFFFF). 
 Há uma regra para a escolha da linha específica destinada a cada bloco. Para definir quais blocos da 
MP serão alocados em uma determinada linha, pode-se efetuar um cálculo simples, usando-se aritmética de 
módulo (resto da divisão). 
i = j módulo M 
onde 
i = número (endereço) da linha da cache, de 0 a 1023 (0x000 a 0x3FF) no exemplo corrente 
j = número do bloco da memória principal, de 0 a 65535 (0x0000 a 0xFFFF) no exemplo corrente 
M = número de linhas da cache, 1024 no exemplo corrente 
Exemplo: o bloco 65512 (j) será alocado na linha 1000 (i), pois 65512 ÷ 1024 = 63 (tag) com resto 1000 
(linha). 
 A Figura 1 mostra o mapeamento direto correspondente ao exemplo que está sendo descrito. Na 
Figura 2 está a relação entre o endereço e o mapeamento da cache. 
 
Figura 1 – Mapeamento direto. 
 
Ender. do bloco Memória Principal 
0 – 0x0000 64 bytes 
1 – 0x0001 64 bytes 
2 – 0x0002 64 bytes 
... ... 
1022 – 0x03FE 64 bytes Cache 64K 
1023 – 0x03FF 64 bytes ---------------Linha-------------- 
 Tag Células N
o
 da Linha 
1024 – 0x0400 64 bytes 6 bits 64 bytes 0 – 0x000 
1025 – 0x0401 64 bytes 6 bits 64 bytes 1 – 0x001 
1026 – 0x0402 64 bytes 6 bits 64 bytes 2 – 0x002 
... ... ... ... ... 
2046 – 0x07FE 64 bytes 6 bits 64 bytes 1022 – 0x3FE 
2047 – 0x07FF 64 bytes 6 bits 64 bytes 1023 – 0x3FF 
 
... ... 
 
64512 – 0xFC00 64 bytes 
64513 – 0xFC01 64 bytes 
64514 – 0xFC02 64 bytes 
... ... 
65534 – 0xFFFE 64 bytes 
65535 – 0xFFFF 64 bytes 
 
Figura 2 – Subdivisão do endereço da memória em campos da cache. 
Endereço da memória principal – 22 bits 
Endereço do bloco na memória – 16 bits Endereço do byte no bloco – 6 bits 
Tag – 6 bits Número da linha – 10 bits Endereço do byte no bloco – 6 bits 
 No exemplo da Figura 1, M = 1024. Considerando i = j módulo 1024 (0 ≤ j ≤ 65535), tem-se o 
seguinte mapeamento: 
▪ Para a linha 0 poderão ser destinados os blocos 0, 1024, 2048, 3072 e assim por diante (até o bloco 
64512), num total de 64 blocos possíveis. 
▪ Para a linha l poderão ser destinados os blocos l, 1025, 2049, 3073, ..., 64513. 
▪ E assim, sucessivamente, até a linha 1023, que poderá receber o bloco 1023, 2047, ..., até o bloco 
65535. 
 
 Cada endereço da memória principal pode ser dividido nos seguintes elementos (Figura 2): 
▪ Os 6 bits menos significativos apontam para a palavra de dados (byte, célula) desejada pela CPU, 
dentro do bloco endereçado. Como no bloco e na linha há 64 palavras (correspondentes a 64 células 
da memória RAM), então cada endereço de célula terá 6 bits, sendo 2
6
 = 64 combinhações. 
▪ Os 10 bits intermediários indicam o número da linha da cache, porque 2
10
 = 1024, e há 1024 linhas. 
▪ Os 6 bits mais significativos indicam qual bloco é o desejado pela CPU. Isso porque 2
6
 = 64, ou seja 
um dos 64 blocos que podem ser alocados naquela linha. 
 
 Desse modo, cada bloco estará diretamente mapeado a uma linha específica da cache. Na prática, 
uma operação de leitura, pelo exemplo, funciona da seguinte forma (Figura 3); 
1º. A CPU apresenta o endereço de 22 bits ao circuito de controle da cache, que inicia a identificação de 
seus campos para definir primeiramente se a palavra desejada está na cache ou não. Para 
exemplificar, seja o endereço binário 0001000000011001001000(2). Para efeitos de processamento 
pelo sistema de controle da cache, este endereço é dividido em 3 partes, conforme mostrado na 
Figura 2, da esquerda para a direita, a saber: 
a. Parte l (mais à esquerda, com 6 bits, tag) = 000100 = 0x04 = 4 
b. Parte 2 (meio, com 10 bits, linha) = 0000011001 = 0x019 = 25 → Examina primeiro 
c. Parte 3 (mais à direita, com 6 bits, byte no bloco) = 001000 = 0x08 = 8 
2º. Os 10 bits centrais são examinados primeiro e seu valor indica que se trata da linha 110012 = 25. 
Resta verificar se o bloco solicitado é o que se encontra armazenado na linha 25 ou se lá está um 
outro bloco. 
3º. O controlador da cache examina por comparação se o valor do campo tag do endereço – no caso, o 
valor é 4 – é igual ao do campo tag da linha. No exemplo dado, eles são iguais. (Hit!) 
4º. Em seguida, é acessada a palavra 8 (bloco endereçado pelos últimos 6 bits do endereço) e transferida 
para a CPU. 
5º. Se os valores dos campos tag (no endereço e da linha na cache) não fossem iguais, isso significaria 
que o bloco desejado não se encontrava armazenado na cache (Miss!) e, portanto, deveria ser 
transferido da MP para a linha 25, substituindo o atual bloco para, em seguida, a palavra (ou byte) 
requerida – byte 8 – ser transferida para a CPU via barramento de dados. 
 
Figura 3 – Exemplo de operação de leitura em memória cache com mapeamento direto. 
 
Tag Linha Palavra 
000100 0000011001 001000 ← Endereço de leitura enviado pela CPU 
 
 Tag Dados do bloco (64 palavras) Linha 
 25 0 = 0x000 
 ... ... ... ... ... 
 4 24 = 0x018 
 4 = 4 4 Byte 63 ... Byte 8 ... Byte 0 25 = 0x019 
 Hit! ... ... ... ... ... 
 1023 = 0x3FF 
 Miss! 
 
 Byte 8 CPU 
 
 Para transferir da memória principal para a cache (se tivesse ocorrido falha), os 16 bits mais 
significativos do endereço (6 bits do campo tag mais 10 bits do campo linha) seriam utilizados como 
endereço do bloco desejado, pois cada um dos 64K blocos tem um endereço com 16 bits (2
16
 = 64K). 
5 
1 
2 
3 
4 
4 
 A técnica de mapeamento direto é, sem dúvida, simples e de baixo custo de implementação, além de 
não acarretar sensíveis atrasos de processamento dos endereços. A substituição do bloco também é simples. 
O seu problema consiste justamente na fixação da localização para os blocos (no exemplo dado, 64 blocos 
estão destinados a uma linha, o que indica que somente l de cada vez pode estar lá armazenado). 
 Se, por exemplo, durante a execução de um programa um dado código fizer repetidas referências 
(acessos) a palavras situadas em blocos alocados na mesma linha, então haverá necessidade de sucessivas 
idas à MP para substituição de blocos (muitas faltas) e a relação acerto/faltas será baixa, com a consequente 
redução de desempenho do sistema. No exemplo da Figura 1 poder-se-ia ter referências seguidas a uma 
palavra do bloco 0 e a outra palavra do bloco 1024, como também, por coincidência, outro acesso 
subsequente a uma palavra do bloco 2048, todos destinados à mesma linha da cache. Daria sucessivas faltas 
ou falhas (miss). 
 
Mapeamento Associativo 
 
 Nesta técnica os blocos não têm uma linha previamente fixada para seu armazenamento. Se for 
verificado que o bloco não está armazenado em nenhuma linha da cache, então o bloco será transferido para 
a cache, substituindo um bloco já armazenado nela. Que bloco deverá ser substituído é um problemaa ser 
resolvido de acordo com o algoritmo de substituição adotado, descrito mais adiante. O endereço da MP é, 
neste caso, retomando o exemplo, dividido em apenas duas partes (Figura 4): 
▪ Os 16 bits mais significativos, que indicam o endereço do bloco desejado. 
▪ Os 6 bits restantes menos significativos, para indicar a palavra desejada pela UCP dentro do bloco. 
 
Figura 4 – Subdivisão do endereço no mapeamento associativo 
 
Endereço da memória principal – 22 bits 
Tag = Endereço do bloco na memória – 16 bits Endereço do byte no bloco – 6 bits 
 
 A diferença é que o campo tag de cada linha da cache tem agora 16 bits de tamanho, armazenando na 
linha o endereço completo do bloco. 
 Sempre que a CPU realizar um acesso, o controlador da cache deve examinar e comparar os 16 bits 
do endereço de bloco com o valor (também de 16 bits) armazenado no campo tag de todas as 1024 linhas 
para verificar se o bloco desejado está na cache ou não. Caso afirmativo, o byte da palavra desejada é 
transferido para a CPU, caso contrário, o endereço do bloco é usado para chegar à MP e trazer o bloco para a 
cache, substituindo um bloco existente, conforme o algoritmo de substituição escolhido, e entregue à CPU. 
 Esta técnica evita a fixação dos blocos às linhas, mas, por outro lado, acarreta a necessidade de uma 
lógica complexa para, rapidamente, examinar cada campo tag de todas as linhas da cache. 
 
Mapeamento Associativo por Conjuntos 
 
 O mapeamento direto embora econômico em termos de peças utilizadas sofre bastante por conta dos 
conflitos de endereçamento, o que acaba forçando mais buscas na memória principal. O mapeamento 
associativo por sua vez resolve esse problema, mas a custo de um grande conjunto de comparadores. O 
mapeamento associativo por conjuntos tenta resolver o problema de conflito de blocos da mesma linha (da 
técnica de mapeamento direto) e o problema de técnica de mapeamento associativo, de exaustiva busca e 
comparação do campo tag de toda a memória cache. 
 A técnica se resume em organizar as linhas da cache em conjuntos. Dentro do conjunto, as linhas são 
complementarmente associativas. Há vários blocos que compartilham de uma mesma tag, diminuindo-se 
assim o número de conflitos por um endereço. Além disso, para selecionar o bloco que deve ser acessado, 
usa-se apenas um decodificador, o que reduz significativamente o número de comparadores utilizados para 
acessar uma posição de memória. 
 A figura 5 ilustra a arquitetura de uma cache com mapeamento associativo por conjunto. O 
mapeamento neste caso funciona da seguinte forma. Uma parcela dos bits de endereçamento é destinada a 
mostrar qual é o bloco a ser acessado, o restante serve como tag. Por exemplo, em uma memória principal de 
64K e 32 blocos, tem-se um endereçamento de 16 bits, sendo 5 para definir o bloco (2
5
) e 11 para a tag. 
Resta apenas definir o número de linhas da memória cache, que será dado de acordo o seu tamanho. Nas 
condições acima, uma memória cache com 1K de capacidade e 32 linhas. 
 
Figura 5 – Exemplo de mapeamento associativo por conjuntos. 
 
 
 
Algoritmos de Substituição de Dados na Cache 
 
 O problema se resume em definir qual dos blocos atualmente armazenados na cache deve ser retirado 
para dar lugar a um novo bloco que está sendo transferido (é bom lembrar que isto é necessário porque todos 
as linhas da cache estão sempre ocupadas, visto que Q << B). 
 Dependendo de qual técnica de mapeamento se esteja usando, pode-se ter algumas opções de 
algoritmos. Por exemplo, se o método de mapeamento adotado foi o direto, então não há o que definir, pois, 
neste caso, somente há uma única linha possível para um dado bloco (ver descrição do método). No entanto, 
para os outros dois métodos de mapeamento – associativo e associativo por conjunto – pode-se optar por um 
dos seguintes algoritmos. 
▪ LRU (Least Recently Used) – o sistema escolhe para ser substituído o bloco que está há mais tempo 
sem ser utilizado pela CPU. 
▪ FIFO (First-In, First-Out), Fila – o sistema escolhe o bloco que está armazenado há mais tempo na 
cache, independentemente de estar sendo usado ou não com frequência pela CPU. 
▪ LFU (Least Frequently Used) – o sistema escolhe o bloco que tem tido menos acessos por parte da 
CPU (menos referências). 
▪ Escolha aleatória – trata-se de escolher aleatoriamente um bloco para ser substituído, 
independentemente de sua situação no conjunto. 
 Um estudo realizado sobre memórias cache, baseado em diversas simulações, obteve diversas 
conclusões, entre as quais a de que escolher um bloco aleatoriamente (que nem pode ser considerado um 
algoritmo) reduz muito pouco o desempenho do sistema em comparação com os demais algoritmos baseados 
em algum tipo de uso, e é extremamente simples de implementar. 
 
Política de Escrita pela Memória Cache 
 
 Em sistemas com memória cache, toda vez que a CPU realiza uma operação de escrita, esta ocorre 
imediatamente na cache. Como a cache é apenas uma memória intermediária, não a principal, é necessário 
que, em algum momento, a MP seja atualizada, para que o sistema mantenha sua correção e integridade. 
 Antes que um bloco possa ser substituído na cache, é necessário considerar se ele foi ou não alterado 
na cache e se estas alterações também foram realizadas na MP. Caso contrário, isso significa que o bloco da 
cache está diferente do da MP e isso não pode acontecer, pois a MP precisa ser tão corretamente mantida 
quanto a cache. 
 Atualmente podem ser encontradas algumas políticas de escrita, cada uma contendo suas vantagens e 
desvantagens em relação às outras, no que se refere principalmente ao custo e ao desempenho. 
 O problema é complicado levando-se em conta algumas ponderações, tais como: 
▪ A memória principal pode ser acessada tanto pela cache quanto por elementos de Entrada e Saída 
(um dispositivo de acesso direto à memória, DMA, por exemplo). Neste caso, é possível que uma 
palavra da MP tenha sido alterada na cache e ainda não na MP e, assim, esta palavra da MP está 
desatualizada. Ou um elemento de E/S pode ter alterado a palavra da MP e, então, a palavra da cache 
é que estará desatualizada. 
▪ A memória principal pode ser acessada por várias CPUs, cada uma contendo sua memória cache. 
Neste caso, é possível que uma palavra da MP seja alterada para atender à alteração de uma cache 
específica de uma CPU, e as demais caches cujo conteúdo esteja ligado a esta palavra estarão 
desatualizadas. 
 
 Entre as técnicas conhecidas, tem-se: 
▪ Escrita em ambas (write through) – nesta técnica, cada escrita em uma palavra da cache acarreta 
escrita igual na palavra correspondente da MP, assegurando validade permanente e igual ao 
conteúdo de ambas as memórias. Caso haja outros módulos CPU/cache, estes alterarão também suas 
caches correspondentemente. 
▪ Escrita somente no retorno (write back) – esta técnica não realiza atualização simultânea, como a 
anterior, mas somente quando o bloco foi substituído e se ocorreu alteração. Em outras palavras, 
sempre que ocorrer uma alteração da palavra na cache, o quadro (linha) correspondente será marcado 
através de um bit adicional, que pode ser denominado ATUALIZA, por exemplo. Assim, quando o 
bloco armazenado no quadro específico foi substituído, o sistema verifica o valor do bit 
ATUALIZA; caso seja de valor igual a l, então o bloco é escrito na MP, caso contrário, não. 
▪ Escrita uma vez (write once) – é uma técnica apropriada para sistemas multi CPU/cache, que 
compartilhem um mesmo barramento. Por ela, o controlador da cache escreve atualizando o bloco da 
MP sempre que o bloco correspondente na cache foi atualizado pela primeira vez. Este fato não só 
atualiza ao mesmo tempo ambos os blocos (como na técnica write through), mas também alerta os 
demais componentes que compartilham o barramento único. Estes são cientificados de que houve 
alteração daquela palavra específica e impedem seu uso. Outrasalterações (escritas) naquele bloco 
apenas são realizadas, na cache local, pois o bloco somente é atualizado na MP quando foi 
substituído na cache. 
 
 Comparando-se as três políticas, podem ser estabelecidas algumas conclusões: 
▪ Com a política write throngh pode haver uma grande quantidade de escritas desnecessárias na MP, 
com a natural redução de desempenho do sistema. 
▪ A política write back minimiza aquela desvantagem, porém a MP fica potencialmente desatualizada 
para utilização por outros dispositivos a ela ligados, como o módulo de E/S, o que os obriga a 
acessar o dado através da cache, o que é um problema. 
▪ A política write once pode ser conveniente, mas apenas para sistemas com múltiplas CPU, não sendo 
ainda muito usado. 
 O mesmo estudo sobre caches mencionado anteriormente mostra que a percentagem de escritas na 
memória é baixa, da ordem de 15%, o que aponta para uma política simples write through.