Embed Size (px)
Citation preview
Memória Principal x CacheMemória Principal x Cache Uma das soluções possíveis para diminuir a
perda de tempo envolvida em operações de leitura e escrita na memória principal são as memórias cache
Este é um tipo de memória rápida, isto é, acessos a ela levam muito menos tempo, porém com a desvantagem de serem surrealmente caras
Recordando, de forma simplificada, o modelo de Von Neumann:
1
Memória Processador
Temos as seguintes opções: A que usávamos antes, memória principal, lenta, mas
com um tamanho maior sem um custo alto demais
Uma memória cache, caríssima e, portanto, de tamanho bem limitado, mas muito mais rápida
2
Memória Principal
Processador
Cache Processador
Podemos sonhar quesomos infinitamentericos e simplesmenteaumentar a cache até otamanho que queremos
Ou podemos voltar à realidade...
3
Agora, vem a pergunta “manjada”: será que é possível ter o benefício da rapidez da memória cache sem ter que aumentá-la a ponto de deixar a máquina cara demais, e ao mesmo tempo ter o tamanho de uma memória principal razoável?
Podemos começar com uma constatação básica: utilizando uma memória convencional, gastaremos 100 ciclos (tempo de leitura na memória, como já vimos) pelo menos uma vez por instrução, pois precisamos buscar cada uma delas na memória
Então, já seria um bom começo não precisar buscar uma mesma instrução duas vezes 4
Podemos arrumar nossa máquina da seguinte forma:
Já que a cache tem um tamanho bastante limitado, podemos usá-la pelo menos para armazenar instruções que já tenham sido buscadas. Assim, quando o processador precisar de alguma instrução pela segunda vez, ela será carregada da cache, o que levará muito menos tempo do que carregá-la da memória principal novamente 5
Memória Principal
ProcessadorCache
endereçosendereços
dados dados
Vamos agora supor uma instrução que é executada k vezes ao longo de um programa
Na arquitetura em que só havia processador e memória principal, o tempo médio para buscar essa instrução seria, naturalmente, o tempo gasto em uma operação de busca na memória
Já na arquitetura proposta no slide anterior, sabemos que a instrução só será buscada na memória principal na primeira vez. Nas outras (k - 1) vezes, ela será carregada da cache. Logo, o tempo médio para buscar essa instrução será:
6
Para k muito grande, temos k >> tmem, e k ≈ k - 1. Daí:
7
Ou seja, o tempo médio de busca dessa instrução será o tempo de buscá-la na cache, que era o que queríamos antes
E nem precisamos gastar uma senhora grana com uma cache do tamanho da memória principal; bastou usar uma menor com alguma inteligência
Existe um tipo especial de cache, chamado cache associativa, que recebe da memória principal um conjunto de instruções, em vez de apenas uma por vez. Estes conjuntos são os blocos
Blocos de instruções são divisões feitas tanto na memória principal quanto na cache, de tamanho fixo e pré-determinado
Por exemplo, podemos dividir a memória principal em blocos de tamanho 4 (cada um contém 4 palavras):
8
.
.
.
bloco 0
bloco 1
bloco 2
bloco 3
bloco 4
Sempre que o processador pedir uma instrução, a cache armazenará todo o bloco de onde essa instrução faz parte:
Vamos dar um zoom em parte da memória do slide anterior. Suponha que o processador precisa da palavra no endereço 4:
9
0123456789
1011
Sempre que o processador pedir uma instrução, a cache armazenará todo o bloco de onde essa instrução faz parte:
Vamos dar um zoom em parte da memória do slide anterior. Suponha que o processador precisa da palavra no endereço 4:
10
0123456789
1011
Cache
As palavras nos endereços 5, 6 e 7 também são carregadas para a cache
Se as palavras nos endereços 4, 5, 6 e 7 forem todas instruções e estas forem executadas sequencialmente, apenas uma consulta na memória principal será necessária, em vez de 4
Considerando que, em aplicações reais, o tamanho dos blocos tende a ser muito maior que 4, pode-se dizer que conseguimos uma grande vantagem
Analisaremos mais a fundo a cache associativa para entender melhor suas vantagens
11
Cache associativa para blocos de tamanho 4:
12
1 3 P0 P1 P2 P3
1 5 P0 P1 P2 P3
0 2 P0 P1 P2 P3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
validade(0 ou 1)
nº dobloco
conteúdo do bloco(Pn é a n-ésima palavra do bloco)
entradas(ou linhas)
Validade é o bit que diz se aquele bloco está sendo usado ou é lixo. 1 significa que o bloco está sendo usado, enquanto 0 quer dizer que aquela linha pode ser sobrescrita
Número do bloco é o número (evidentemente binário) que representa onde aquele bloco estava na memória principal. Se o bloco armazena as palavras vindas dos endereços 0, 1, 2 e 3 da memória, então seu número é 0; se armazena as palavras dos endereços 4, 5, 6 e 7, então seu número é 1; etc
Quando o processador pede alguma palavra da memória, todas as linhas de validade 1 são verificadas, e a palavra é buscada na memória principal apenas se não existir na cache
Mas como essa checagem é feita? 13
Antes, precisamos entenderuma certa “mágica”
Seja a memória dividida emblocos de tamanho n
Cortando os log₂n bits menos significativos do endereço de uma palavra, obtemos exatamente o bloco onde ela está
Por exemplo, vimos que, dividindo em blocos de tamanho 4, a instrução no endereço 7 está no bloco 1
7 na base 2, em 8 bits, é igual a:14
00000111
Antes, precisamos entenderuma certa “mágica”
Seja a memória dividida emblocos de tamanho n
Cortando os log₂n bits menos significativos do endereço de uma palavra, obtemos exatamente o bloco onde ela está
Por exemplo, vimos que, dividindo em blocos de tamanho 4, a instrução no endereço 7 está no bloco 1
7 na base 2, em 8 bits, é igual a:15
00000111log₂4 = 2; então, tirando os 2 bits menos significativos, obtemos o valor 1, que é o número do bloco da instrução 7
Na verdade, não é algo tão difícil de aceitar se pensarmos em uma generalização
Vamos pensar na base 10: considere uma memória dividida em blocos de tamanho 100
Os endereços 0 até 99 estão no bloco 0, do 100 até 199, estão no bloco 1, e por aí vai
Para obter o bloco da palavra no endereço 374, precisamos tirar os log₁₀100 bits menos significativos (mudamos para a base 10, então a base do logaritmo passa a ser 10)
16
374
Na verdade, não é algo tão difícil de aceitar se pensarmos em uma generalização
Vamos pensar na base 10: considere uma memória dividida em blocos de tamanho 100
Os endereços 0 até 99 estão no bloco 0, do 100 até 199, estão no bloco 1, e por aí vai
Para obter o bloco da palavra no endereço 374, precisamos tirar os log₁₀100 bits menos significativos (mudamos para a base 10, então a base do logaritmo passa a ser 10)
17
3log₁₀100 = 2, então tiramos os 2 algarismos menos significativos. A palavra está no bloco 3
33
Voltando ao que interessa, vamos supor que o valor 00001001 chegue ao MAR no processador. Isto significa que o processador está pedindo a palavra que está no endereço 9 (bloco 2)
Os 2 bits menos significativos são ignorados, e o valor 000010 é comparado, na cache, a todos os números de bloco pertencentes a linhas de validade 1
Mas como uma consulta na cache pode ser tão rápida, se ainda precisamos fazer uma busca sequencial para saber se o bloco 2 já está de fato armazenado na cache?
18
Na verdade, a busca não é sequencial Em cada uma das linhas da cache, existem portas
lógicas que comparam simultaneamente o número do bloco nela presente ao valor recebido
19
1 3 P0 P1 P2 P3
1 5 P0 P1 P2 P3
1 2 P0 P1 P2 P3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000010
portas
lógicas
3
5
2
os valores são diferentes
os valores são iguais
20
Esse festival de portas lógicas constitui um importante motivo do encarecimento da cache
Isso porque, como vimos desde os primeiros slides, hardware tem uma grande influência no preço final da máquina
O bloco 2 então está na cache. Mas como encontrar a palavra certa (a do endereço 9) em meio às 4 do bloco, que contém as palavras dos endereços 8, 9, 10 e 11?
Recordando: a palavra pedida é a do endereço 00001001, e para obter o bloco ignoramos os 2 bits mais à esquerda, 01
E estes dois bits são exatamente os bits que informam a palavra certa a ser buscada no bloco!
Então, a palavra do endereço 9 é a P₁ do bloco 2Dessa forma, carregamos a palavra direto da
cache, sem consulta à memória principal21
Existe outro tipo de cache, mais barato que a associativa, a cache com mapeamento direto
Nela, cada linha da cache é destinado a blocos específicos da memória
Dessa forma, não é necessário ter circuitos comparativos em cada linha da cache, já que a procura será feita apenas em uma linha específica e não mais em todas elas
Com isso, conseguimos baratear a cache significativamente
Veremos que o esquema é bem parecido com o da cache associativa:
22
Cache com mapeamento direto para blocos de tamanho 4:
23
1 000 P0 P1 P2 P3
1 001 P0 P1 P2 P3
0 101 P0 P1 P2 P3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
validade(0 ou 1) tag
conteúdo do bloco(Pn é a n-ésima palavra do bloco)
entradas(ou linhas)
Antes, armazenávamos blocos vindos da memória enquanto houvesse linhas disponíveis
Agora, as linhas destinam-se a grupos fixos de blocos. Porém, sabemos que cada linha só pode armazenar um bloco
Então, se uma linha é destinada aos blocos X e Y, apenas um deles pode estar na cache ao mesmo tempo. Se na cache já existir o bloco X, e o bloco Y for carregado da memória, este bloco irá para a linha onde já está o bloco X, sobrescrevendo-a
Vamos definir que na nossa cache, cada linha armazena 4 possíveis blocos
24
A arrumação mais óbvia seria:
Porém, perceba que, desta forma, dos blocos 0, 1, 2 e 3, nunca poderíamos ter mais de um na cache ao mesmo tempo. O mesmo vale para os outros quartetos de blocos
Isto significa que, se as palavras nesses blocos fossem buscadas sequencialmente, perderíamos sempre o bloco anterior 25
0
1
2
validade tag conteúdo do bloco
.
.
.
0, 1, 2, 3
4, 5, 6, 7
8, 9, 10, 11
Vamos focar na linha 0 para entender melhor:
26
0
bloco 0
bloco 1
bloco 2
bloco 3
palavras nos endereços 0 a 15,
consultadas sequencialmente
Vamos focar na linha 0 para entender melhor:
27
0
bloco 0
bloco 1
bloco 2
bloco 3
Ao buscar a palavra no endereço 0, o bloco 0 é carregado para a linha 0 da cache
0
Vamos focar na linha 0 para entender melhor:
28
0
bloco 0
bloco 1
bloco 2
bloco 3
Na busca da palavra no endereço 4, o bloco 1 é carregado para a linha 0 da cache. A cache perde, assim, o bloco 0
4
Vamos focar na linha 0 para entender melhor:
29
0
bloco 0
bloco 1
bloco 2
bloco 3
O mesmo acontece para as buscas das palavras nos endereços 8...
8
Vamos focar na linha 0 para entender melhor:
30
0
bloco 0
bloco 1
bloco 2
bloco 3
...e 12!
12
Note que, após todas essas buscas, teríamos os 4 blocos armazenados na cache associativa
Na cache por mapeamento direto, porém, ficamos apenas com o último bloco da sequência
Nesse caso, se as palavras desses 4 blocos fossem instruções internas a um loop, teríamos que consultar a memória a cada mudança de bloco. Já na cache associativa, nenhum acesso à memória teria de ser feito depois que os 4 blocos já estivessem na cache
Mas nem tudo está perdido. Basta fazermos com que cada linha destine-se a blocos distantes uns dos outros: 31
Com isso, o problema do loop que acabamos de ver será mais difícil de acontecer
Agora, quando carregarmos o bloco 0 na cache, ele só será sobrescrito quando os blocos 8, 16 ou 24 forem carregados da memória
Supondo uma execução sem excessivos desvios, isto é, um programa com razoável localidade, é perfeitamente possível que não precisemos mais do bloco 0 quando carregarmos um dos outros 3 32
0
1
2
.
.
.
0, 8, 16, 24
1, 9, 17, 25
2, 10, 18, 26
Outro ganho que temos com este arranjo é a diminuição da largura da cache, substituindo a antiga coluna que guardava o nº do bloco por uma coluna tag
A linha 0 destina-se aos blocos 0 (00000), 8 (01000), 16 (10000) e 24 (11000). A linha 1 destina-se aos blocos 1 (00001), 9 (01001), 17 (10001) e 25 (11001), e assim por diante
Repare na semelhança: para cada linha, os 3 últimos bits dos seus possíveis blocos são iguais
Isto significa que é possível identificar qual bloco aquela linha está armazenando apenas pelos bits que diferem entre os blocos 33
Assim, se o valor da tag na linha 0 for 000, sabemos que nela está o bloco 0; se for 010, sabemos que lá está o bloco 8; já o valor 100 indica que ela guarda o bloco 16; e 110 indica o bloco 24
Na linha 1, estes mesmos valores acusam, respectivamente, os blocos 1, 9, 17 e 25
Resumindo: quando o processador precisa de uma palavra que já está na cache, a consulta é imediatamente direcionada para a linha onde o bloco daquela palavra deveria estar. Por exemplo, se o processador pede uma palavra do bloco 8, a consulta é feita diretamente na linha 0
Porém, se lá estiver o bloco 16, o bloco 8 é carregado da memória e salvo na linha 0, sobrescrevendo o 1634
Supondo uma memória principal com 32 blocos, teríamos a cache disposta dessa forma:
Repare que a altura da cache precisa sempre ser uma potência de 2, para que possamos identificar o bloco armazenado através da tag
35
0 0, 8, 16, 24
1 1, 9, 17, 25
2 2, 10, 18, 26
3 3, 11, 19, 27
4 4, 12, 20, 28
5 5, 13, 21, 29
6 6, 14, 22, 30
7 7, 15, 23, 31
Se tirássemos a última linha da cache, por exemplo, não teria como redistribuir os blocos 7, 15, 23 e 31 sem que todos os blocos destinados a uma mesma linha possuíssem bits em comum. Logo, seria impossível identificá-los através da tag
Esta restrição de tamanho pode ser ruim: suponha que temos dinheiro para construir até 1023 linhas de cache por mapeamento direto
A potência de 2 mais próxima é 1024 (2¹⁰), mas não conseguimos atingir esse número. Logo, nossa cache será forçada a ter apenas 512 linhas
Já a cache associativa poderia sem problemas ter tantas linhas quanto pudéssemos pagar 36
Uma forma de unir os benefícios desses dois tipos de cache é literalmente unir as duas caches
Se “grudarmos” várias caches com mapeamento direto, lado a lado, teremos na horizontal uma espécie de cache associativa
37
.
.
.
.
.
.
.
.
.
.
.
.
V tag cont. do bloco
.
.
.
.
.
.
.
.
.
.
.
.
V tag cont. do bloco
.
.
.
.
.
.
.
.
.
.
.
.
V tag cont. do bloco
. . .
Isso consiste em um terceiro tipo de cache, chamado cache associativa por conjunto
A altura continua sendo necessariamente uma potência de 2, mas a largura é arbitrária
Portanto, se temos dinheiro para 1536 linhas de cache, basta juntar 3 caches com mapeamento direto de 512 linhas cada
Com isso, não precisamos sobrescrever uma linha sempre que um novo bloco destinado a ela for carregado da memória; basta passá-lo para o lado
38
Já que temos mais de um bloco por linha, precisamos de portas lógicas para identificar em qual deles está a palavra pedida pelo processador, exatamente como fazíamos na cache associativa
Só que desta vez, o número de portas lógicas de que precisamos não equivale ao número de linhas da cache, e sim ao número de caches por mapeamento direto unidas lado a lado
Temos com isso uma significativaredução de preço, sem umasignificativa perda de eficiência
39
