Aula 6 - Memória - Cache

Prévia do material em texto

Memória Cache
1 / 54
José Roberto Garcia
Universidade de Sorocaba – Campus Cidade Universitária
Arquitetura de Computadores
Agradecimentos: Prof. Bruno Aguilar da Cunha
Material baseado nos slides do prof. Diego Passos/Fernanda Passos
Universidade de Sorocaba
Tipos de memórias
Há vários tipos de memórias, cada uma com características distintas em relação a:
 Custo (preço por bit).
 Capacidade para o armazenamento.
 Velocidade de acesso.
A memória ideal seria aquela que é barata, de grande capacidade e acesso rápido.
Infelizmente, a memória rápida é custosa e de pequena capacidade.
E a memória de grande capacidade, embora mais barata, apresenta baixa velocidade de acesso.
Universidade de Sorocaba
2 / 54
Tipos de memórias
A memória de um computador é organizada em uma hierarquia.
Registradores: nível mais alto, são memórias rápidas dentro do processador.
Vários níveis de memória cache: L1, L2, etc.
Memória interna ou principal (RAM).
Memórias externas ou secundárias (discos, fitas).
Outros armazenamento remotos (arquivos distribuidos,
servidores web).
Universidade de Sorocaba
3 / 54
Hierarquia de memória
Universidade de Sorocaba
4 / 54
Motivação: Diferença de Velocidade
Processador precisa ler e escrever dados na memória principal. Mas, tipicamente, o processador é muito mais rápido que a MP. Exemplo (em um computador hipotético):
 Em uma soma, tempo de leitura dos operandos a partir da memória de 60 ns.
 Uma vez nos registradores, o tempo efetivo de soma é 0,3 ns.
Processador precisa aguardar enquanto dados são carregados.
 Tempo chamado de wait state.
Universidade de Sorocaba
5 / 54
Motivação: Princípio da Localidade
6 / 54
Na década de 1960, pesquisadores começaram a estudar a execução de programas.
 Especialmente, os padrões de acesso à memória.
Notaram que o acesso à memória não é totalmente aleatório.
Quando um determinado endereço é acessado, há maior probabilidade de acesso à endereços próximos.
 Princípio da Localidade.
 Em inglês, chamado de locality of reference ou principle of locality.
Foram notados dois tipos de localidade distintos:
 A localidade espacial.
 E a localidade temporal.
Universidade de Sorocaba
Motivação: Localidade Espacial
7 / 54
Princípio da localidade espacial:
 Se um endereço x é acessado, é provável que endereços x + 1, x + 2, x + 3, . . . também sejam em um futuro próximo.
Este princípio se aplica à execução de programas por dois motivos principais:
 A organização do código executável em memória.
 A existência de estruturas de dados na forma de coleções de itens.
Universidade de Sorocaba
8 / 54
Organização do código executável:
 Instruções são ordenadas sequencialmente.
Leia um operando da memória. Ç Leia outro operando da memória. 
Some os dois valores. . .
Processador busca instruções uma após a outra na memória.
 Exceções:
 Repetições, condicionais e chamadas de funções.
Parte 1 do Programa A
Executado em Sequência
Loop 1
Loop 2
Sub-rotina 1
	Outro Programa
	{ 	
	 	
	Call sub-rotina 1
	 	
	 	
Parte 2
MP
Universidade de Sorocaba
Motivação: Localidade Espacial
Motivação: Localidade Espacial (III)
9 / 54
Coleções:
 Exemplo mais comum são os vetores
 Elementos tipicamente organizados sequencialmente
 É comum percorrer os elementos nesta sequência.
 e.g., em repetições. 
	Outras Variáveis
	
	
	
	
	
a[0]
MP
a[1]
a[2]
a[3]
...
Universidade de Sorocaba
Motivação: Localidade Temporal
10 / 54
Princípio da localidade temporal:
 Se um endereço x é acessado, é provável que ele seja acessado novamente num futuro próximo.
Este princípio se aplica à execução de programas por três motivos principais:
 A existência de variáveis que são lidas/modificadas frequentemente em uma mesma região do código.
 A existência de repetições com variáveis acumuladoras.
 A existência de repetições que executam as mesmas instruções várias vezes seguidas.
int a, b, c; a=0;
b=alguma_funcao(c); if (b<3) a=c%10; 
if (a>1) a--; a=outra_funcao(a);
int a[10], b=0, i;
for (i=0; i<10; i++) a[i]=i;
for (i=1; i<10; i++) b+=a[i-1]*i+a[i];
Universidade de Sorocaba
Motivação: O Princípio da Cache
11 / 54
O termo cache é usado em vários contextos em computação.
 Cache de um browser.
 Cache de arquivos em memória.
 Memória cache.
 . . .
Em todos estes contextos, a ideia é armazenar informações de interesse em um local de acesso mais rápido.
 É impossível armazenar tudo.
 Mas se algo é encontrado na cache, ganhamos em desempenho.
Note que a consulta à cache consome algum tempo.
 Mas supõe-se que esse tempo é pequeno em relação ao ganho que ocorre quando achamos o dado.
Universidade de Sorocaba
Funcionamento da Memória Cache
A memória cache explora o princípio da localidade.
 Tanto temporal, quanto espacial.
Ela é uma memória relativamente pequena, mas bastante rápida.
Toda vez que o processador tenta acessar uma posição de memória, ele primeiro verifica a existência do dado na cache.
Quando um dado é acessado na MP, ele é armazenado na cache.
 Princípio da localidade temporal: ele poderá ser usado novamente em breve..
Além do dado em si, armazena-se um bloco de dados próximos.
 Princípio da localidade espacial: dados próximos podem ser usados em breve.
12 / 54
Universidade de Sorocaba
Funcionamento da Memória Cache
13 / 54
Universidade de Sorocaba
Funcionamento da Memória Cache
Quando o processador precisa de um dado, ele pode já estar na cache (cache hit). Se não (cache miss), tem que buscar na memória (ou até no disco).
Quando um dado é acessado na memória, um bloco inteiro (e.g. 64 bytes) contendo o dado é trazido à memória cache. Blocos vizinhos podem também ser acessados (prefetching) para uso futuro.
Na próxima vez o dado (ou algum dado vizinho) é usado, já está na cache cujo acesso é rápido.
14 / 54
Universidade de Sorocaba
Funcionamento da Memória Cache
15 / 54
Universidade de Sorocaba
Operação de Leitura com Memória Cache
16 / 54
Analogia: 
se falta ovo (dado) na cozinha (processador), vai ao supermercado (memória) e compra uma dúzia (prefetching – pré-busca),
deixando na geladeira (cache) para próximo uso.
Universidade de Sorocaba
Operação de Leitura com Memória Cache
17 / 54
A existência da memória cache altera o processo de leitura de dados da MP. Quando a UCP deseja ler uma posição de memória, os seguintes eventos ocorrem:
 Processador escreve o endereço a ser lido no BE de acesso à MP.
 Controlador da cache intercepta pedido e verifica se o dado está em cache.
Se sim, temos um acerto (hit): dado é copiado para o processador.
Se não, temos um falta (miss): cache pede o dado à MP, o armazena e repassa para a UCP.
Note que, no caso de um miss, cache solicita um bloco inteiro à MP.
 Conjunto de dados maior que o dado a ser lido.
Universidade de Sorocaba
Arquitetura com Memória Cache
18 / 54
...
MP
BE
BC
BD
BE
BC
BD
Cache
BC – barramento de controleBD – barramento de dados
BE – barramento de endereços
Universidade de Sorocaba
Desempenho com Memória Cache
19 / 54
O objetivo de inserirmos a memória cache na hierarquia é reduzir o tempo de acesso à memória.
O objetivo é alcançado?
Isso depende de vários fatores:
O tempo de acesso quando há um hit. O tempo de acesso quando há um miss. E a eficiência da cache.
Define-se a eficiência de uma memória cache como o percentual de hits:
Ec = 100 × hits
acessos
Eficiência varia com uma série de fatores, incluindo o programa em execução. Mas espera-se algo em torno de 95% a 98%.
Universidade de Sorocaba
Desempenho com Memória Cache: Tempo Médio de Acesso à Memória
20 / 54
Para medir o desempenho de um sistema que possui memória cache, podemos calcular o tempo médio de acesso à memória (TMAM).
Considera eventos de:
 acerto (cache hit),
 falta (cache miss) e
 taxa de faltas.
Fórmula para cálculo:
TMAM = tempo de acerto + taxa de faltas × penalidade por falta
 Tempo de acerto: tempo de descobrir que ocorreu um acerto mais o tempo de acesso à memória cache.
 Penalidade por falta: tempo de descoberta da ocorrência da falta adicionado ao tempo de cópia de um bloco da memória principal para a cache e o tempo de acesso à cache.
 Taxa de faltas: número de faltas que ocorrem por instrução.
Universidade de Sorocaba
Desempenho com Memória Cache: Tempo Médio de Acesso à Memória
21 / 54
Universidade de Sorocaba
Estrutura de uma Memória Cache
Universidade de Sorocaba
22 / 54
Cache
Memória Principal
	Hierarquia memória 	Latência em ciclos
 _________________________________________________
	registrador 		1
	L1 cache 			4
	L2 cache 			11
	L3 cache 			39
	Memória RAM 		107
	Memória virtual (disco) 	milhões
Estrutura de uma Memória Cache
Universidade de Sorocaba
23 / 54
Tag
Dados
{
		Célula 0	Célula 1		Célula X
					
					
					
					
				...	
	...
...
...				
					
					
Linha 0
Linha 1
Linha 2
Linha 3
Linha 4
Linha 5
Linha (n-1) Linha n
							
							
							
							
							
	...
...						
							
							
							
							
							
...
...
0
1
2
3
4
M bits
}
...
Bloco de X
Células
Cache
Memória Principal
A memória cache é organizada em linhas.
 Cada linha contém X células.
 E um campo tag.
Estrutura de uma Memória Cache
Tag
Dados
{
		Célula 0	Célula 1		Célula X
					
					
					
					
				...	
	...
...
...				
					
					
Linha 0
Linha 1
Linha 2
Linha 3
Linha 4
Linha 5
Linha (n-1) Linha n
							
							
							
							
							
	...
...						
							
							
							
							
							
...
...
0
1
2
3
4
M bits
}
...
Bloco de X
Células
Cache
Memória Principal
Células em uma linha representam células sequenciais na MP.
 Um bloco.
 Quando um dado é copiado da MP para a cache, todo o seu bloco é trazido juntamente.
15 / 54
24 / 54
Universidade de Sorocaba
Estrutura de uma Memória Cache
15 / 54
Tag
Dados
{
		Célula 0	Célula 1		Célula X
					
					
					
					
				...	
	...
...
...				
					
					
Linha 0
Linha 1
Linha 2
Linha 3
Linha 4
Linha 5
Linha (n-1) Linha n
							
							
							
							
							
	...
...						
							
							
							
							
							
...
...
0
1
2
3
4
M bits
}
...
Bloco de X
Células
Cache
Memória Principal
Há ainda o campo tag.
 Indica, de alguma forma, o endereço do bloco na MP.
 Lembre-se: a MP é muito maior que a cache.
Universidade de Sorocaba
Memória Cache vs. MP
16 / 54
A memória cache é muito menor que a MP.
 Não podemos guardar todos o conteúdo da MP na cache.
 Em outras palavras, só podemos armazenar um subconjunto dos blocos da MP.
Por isso, algumas questões fundamentais:
 Quais blocos manter na cache?
 Como determinar, de forma eficiente, se um dado está em cache?
 O que fazer quando um dado em cache é alterado?
Universidade de Sorocaba
O Problema do Mapeamento
17 / 54
Universidade de Sorocaba
O Problema do Mapeamento
18 / 54
Vamos começar pela segunda questão:
 Como determinar se um dado está em cache?
Como a cache guarda um subconjunto pequeno dos blocos da MP, a primeira tarefa é determinar se o dado está na cache.
Sabemos que o campo tag é usado para, de alguma forma, indicar o campo de endereço do bloco na MP.
 Busca tem que ser eficiente.
 Caso contrário, tempo de acesso à cache fica alto.
Universidade de Sorocaba
Uma Primeira Ideia
19 / 54
Se usarmos o campo tag para armazenar o endereço na MP da primeira célula do bloco, podemos fazer uma busca sequencial:
 Começamos pela primeira linha da cache.
 Verificamos se o endereço a ser acessado é maior ou igual a tag e menor que tag + X.
 Se sim, achamos o dado.
 Se não, continuamos na próxima linha.
 Se não há mais linhas, dado não está na cache.
Algum problema?
Universidade de Sorocaba
Uma Primeira Ideia (II)
20 / 54
Sim!
 Por mais que o acesso à memória cache seja rapido, temos (potencialmente) que ler todas as tags para um único acesso a memória.
 Caches pequenas hoje têm centenas de linhas.
 Tempo efetivo de acesso à cache seria impraticável.
Conclusão:
 Precisamos de um método de busca mais eficiente.
Universidade de Sorocaba
Tipos de Mapeamento
21 / 54
Na prática, problema da busca em cache é resolvido através de tipos de mapeamento.
 Maneiras de se determinar em qual linha da cache cada bloco da MP pode ser inserido.
Há três tipos de mapeamento:
 O mapeamento direto.
 O mapeamento associativo.
 O mapeamento associativo por conjunto.
Universidade de Sorocaba
Tipos de Mapeamento
21 / 54
Universidade de Sorocaba
Tipos de Mapeamento
22 / 54
Uma analogia: 
Um bibliotecário cuida de um acervo de 10.000 livros. Ele notou que um livro recentemente consultado tem grande chance de ser buscado de novo.
Ele arrumou um escaninho de 100 posições. Cada vez um livro é acessado, ele deixa um exemplar no escaninho. Às vezes ele tem que remover um livro do escaninho para ter espaço.
Isso evitou ir aos estantes, se o livro desejado já está lá.
Veremos como ele pode organizar o tal escaninho.
Universidade de Sorocaba
Tipos de Mapeamento
22 / 54
Uma analogia - continuação: 
Os 10.000 livros são identificados de 0000 a 9999.
As 100 posições do escaninho são identificadas de 00 a 99.
No mapeamento direto, os dois últimos dígitos do livro são
usados para mapear à posição do escaninho.
Exemplo: livro 8702 é mapeado à posição 02 do escaninho.
Universidade de Sorocaba
Tipos de Mapeamento
22 / 54
Uma analogia - continuação: 
Para buscar o livro 2513, a posição mapeada no escaninho contém o livro desejado. Não precisa ir buscar nos estantes.
Para buscar o livro 5510, ele não está na posição 10. Pega nos estantes e deixa um exemplar na posição 10 do escaninho.
Para buscar o livro 8813, a posição 13 não contém o livro desejado (88 é diferente de 25). Pega o livro desejado nos estantes e coloca na posição 13 do escaninho, removendo o livro que estava lá.
Universidade de Sorocaba
Mapeamento Direto
22 / 54
Logo, a MP tem B × X células.
O mapeamento direto é a solução mais simples. Divide-se a Memória Principal em blocos de X células.
 X é o tamanho de uma linha da cache.
Blocos são numerados de 0 a B-1.
 B é o número de blocos.
Se a cache tem L linhas, o k-ésimo bloco da 
MP só pode ser armazenado na linha (k mod L).
i.e., o resto da divisão de k por L.
Universidade de Sorocaba
Mapeamento Direto (II)
23 / 54
Este esquema resulta no seguinte tipo de mapeamento:
 Bloco 0 → linha 0.
 Bloco 1 → linha 1.
 . . .
 Bloco L-1 → linha L-1.
 Bloco L → linha 0.
 Bloco L+1 → linha 1.
 . . .
Ou de outra forma:
 Blocos 0, L, 2L, 3L, . . . são mapeados para a linha 0.
 Blocos 1, L+1 2L+1, 3L+1, . . . são mapeados para a linha 1.
 Blocos 2, L+2 2L+2, 3L+2, . . . são mapeados para a linha 2.
 . . .
 Blocos L-1, L+(L-1), 2L+(L-1), 3L+(L-1), . . . são mapeados para a linha L-1.
Universidade de Sorocaba
Mapeamento Direto: Exemplo
24 / 54
Tag	Célula 0
Célula 1
M bits
0
1
2
3
4
5
6
7
8
910
11
12
13
14
15
Bloco 0
Bloco 1
Bloco 2
Bloco 3
{
{
{
{
{
Bloco 4
{
Bloco 5
{
Bloco 6
{
Bloco 7
Linha 0
Linha 1
Linha 2
Linha 3
...
...
Universidade de Sorocaba
Mapeamento Direto: Endereços
25 / 54
É fácil calcular para qual linha um bloco de memória deve ser mapeado.
Mas dado um endereço, digamos E, que queremos acessar, como determinar se ele está na cache?
 Note que o endereço E pertence ao bloco b = E div X .
 Por sua vez, se este b estiver na cache, certamente estará na linha l = b mod L.
 Neste caso, ele estará na célula c = E mod X .
Se X e L são potências de 2, podemos facilmente determinar l olhando para os bits de E:
	...	Ei+j	Ei+j-1	...	Ei	Ei-1	...	E1	E0
c
{
{
{
Se X = 2i e L = 2j:
?	l
Com endereço de 4 bits, E = 11(10), X = 2 e L = 4:
E = 1 0 1 1
c = 1
l = 1
? = 1
Universidade de Sorocaba
Mapeamento Direto: Endereços (II)
26 / 54
Mas ainda há um problema: como saber se o bloco que está na cache é o do endereço E ou algum outro bloco alocado para a mesma linha?
 e.g., no exemplo anterior, o endereço 3 resultaria nos mesmos valores de c e l .
 Como diferenciar?
A resposta está no campo tag.
 Dois ou mais endereços podem resultar nos mesmos c e l por terem o mesmo sufixo.
 Mas seus prefixos serão diferentes.
 Matematicamente, o prefixo pode ser definido como ((E div X ) div L).
 Se X e L são potências de 2, basta olhar para os bits mais à esquerda do endereço.
 Note ainda que duas células do mesmo bloco têm o mesmo prefixo.
 Se guardarmos o prefixo no campo tag, poderemos discernir entre enderec¸os de dois blocos diferentes.
Universidade de Sorocaba
Mapeamento Direto: Acesso
27 / 54
Em resumo, quando o processador tenta acessar um endereço de memória E:
 Identifica-se a linha que pode conter o endereço.
 Compara-se o prefixo do endereço com o campo tag da linha.
 Se o valor bate, cache hit.
 Senão, cache miss.
 Determina-se o bloco ao qual pertence o endereço.
 Todo o bloco é trazido para a cache, na linha adequada.
Universidade de Sorocaba
Mapeamento Direto: Endereços (Exemplo)
28 / 54
Tag Célula 0	Célula 1
M bits
0
1
2
3
4
5
6
7
8
9
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
10
11
12
13
14
15
Bloco 0
Bloco 1
Bloco 2
Bloco 3
{
{
{
{
{
Bloco 4
{
Bloco 5
{
Bloco 6
{
Bloco 7
...
...
1
Linha 0
Linha 1	1
Linha 2
Linha 3
1
0
c = 1
l = 1
tag = 1
Exemplos de Busca na Cache:
E = 11 = 1	0	1	1
E = 14 = 1	1	1	0
(Cache hit)
c = 0
l = 3
tag = 1
(Cache miss)
Universidade de Sorocaba
Mapeamento Direto: Vantagens e Desvantagens
29 / 54
O mapeamento direto é de fácil implementação.
 Principalmente se X e L forem potências de 2.
Basta olhar para conjuntos de bits do endereço para determinar se o dado está em cache.
Mas ele traz uma potencial ineficiência:
 Blocos são sempre colocados na mesma linha.
 Se acessamos sucessivamente endereços de blocos diferentes mapeados para a mesma linha, sempre haverá cache miss.
Universidade de Sorocaba
O Mapeamento Associativo
30 / 54
O grande problema do mapeamento direto é o fato de um bloco ter que ser colocado sempre na mesma linha.
 Determinados conjuntos de blocos nunca podem estar simultaneamente em cache.
 Mesmo que eles sejam os únicos acessados.
O ideal seria que pudéssemos mapear cada bloco da MP para qualquer linha da cache.
 Neste caso, poderíamos ter qualquer conjunto de blocos em cache.
 Limitado apenas pelo número de linhas disponíveis.
Universidade de Sorocaba
O Mapeamento Associativo
30 / 54
Universidade de Sorocaba
Voltemos à analogia. No mapeamento associativo, o livro pode ser colocado em qualquer posição do escaninho.
Para buscar o livro 2513, todo o escaninho precisa ser buscado.
A busca fica rápida se todas as posições são buscadas em paralelo (busca associativa).
Se o livro desejado não está no escaninho, então pega nos estantes e depois deixa um exemplar no escaninho. Se o escaninho já está cheio, então escolhe um livro e o remove.
O Mapeamento Associativo
30 / 54
Universidade de Sorocaba
No mampeamento associativo, cada bloco de memória
pode ser carregado em qualquer linha da cache.
Suponha a memória com B = 2s blocos.
O campo tag de uma linha, de s bits, informa qual bloco
está carregado na linha.
Para determinar se um bloco já está na cache, os campos
tag de todas as linhas são examinados simultaneamente.
O acesso é dito associativo.
A desvantagem do mapeamento associativo é a complexidade da circuitaria para possibiltar a comparação
de todos os tags em paralelo.
O Mapeamento Associativo (II)
31 / 54
Já tentamos fazer este mapeamento sem restrição.
 Nossa primeira abordagem.
 Não funcionava por requerer a comparação sequencial das tags com o endereço a ser acessado.
Mas e se pudéssemos fazer a comparação das tags em paralelo?
 i.e., comparar todas as tags na cache ao endereço ao mesmo tempo.
 Neste caso, determinar se um dado está em cache seria tão rápido quanto no mapeamento direto.
Universidade de Sorocaba
O Mapeamento Associativo (III)
32 / 54
De fato, esta comparacão em paralelo é possível em hardware.
 Cada linha da cache estaria ligada a um circuito comparador cuja entrada seria o endereço a ser acessado.
 As saídas dos comparadores seriam combinadas através de uma função lógica OU.
 Se uma das linhas tivesse a tag adequada, a saída seria verdadeira.
Este tipo de solução recebe o nome de mapeamento associativo.
Memoria: Cache
Universidade de Sorocaba
O Mapeamento Associativo: Endereços
33 / 54
{
{
No mapeamento associativo, o campo tag corresponde ao número do bloco correspondente na MP.
Dado um enderec¸o E a ser acessado, podemos obter o número do seu bloco computando
b = E div X .
 E, dentro do bloco, sua célula será c = E mod X .
Particularmente, se X é potência de 2:
X = 2i:
 b (demais bits)	 c (i bits)
	...	...	Ei	Ei-1	...	E1	E0
Universidade de Sorocaba
O Mapeamento Associativo: Vantagens e Desvantagens
34 / 54
O grande benefício do mapeamento associativo é flexibilizar a alocação de blocos em linhas da cache.
 Podemos ter blocos em quaisquer linhas.
 O que tende a aumentar a taxa de cache hit.
Como desvantagem, temos a maior complexidade do circuito da cache.
 Principalmente em termos econômicos.
 Cache associativa é mais cara que a cache com mapeamento direto.
 Principalmente para caches grandes.
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
O mapeamento direto é simples, mas não tão eficiente.
O mapeamento associativo é complexo, caro, mas muito eficiente. A pergunta é: será que não há um meio termo?
 Sim, o mapeamento associativo por conjunto.
 A cache é dividida em N conjuntos de linhas.
 Assim como no mapeamento direto, cada bloco da MP tem um mapeamento fixo para um conjunto específico.
 Mas dentro do seu conjunto, bloco pode ser armazenado em qualquer linha.
Como no mapeamento associativo.
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
Na analogia: são usados 10 escaninhos (numerados de 0 a 9).
O último dígito do livro é usado para mapear a um dos 10
escaninhos. (Mapeamento direto.)
Dentro do escaninho, o livro pode ser colocado em qualquer
posição. (Mapeamento associativo.)
Combina ambos os mapeamentos, unindo as vantagens.
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
É um compromisso entre o mapeamento direto e associativo,
unindo as vantagens de ambos. 
É o mais usado em processadores modernos.
A cache consiste de um número v de conjuntos, cada um
com L linhas.
Suponha i = número do conjunto.
Suponha j = número do bloco na memória.
Temos i = j mod v. I.e. o bloco j é colocado no conjunto
número i.
Dentro do conjunto i, bloco j pode ser introduzido em qualquer linha. Usa-se acesso associativo em cada conjunto para verificar se um dado bloco está ou não presente.
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 /54
A organização comum é usar 4 ou 8 linhas em cada
conjunto: L = 4 ou 8, recebendo o nome de 4-way ou
8-way set-associative cache.
Exemplo de 2-way set-associative cache:
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
Quando a cache já está cheia e um novo bloco precisa ser carregado na cache, então um dos blocos ali existentes deve ser substituído,cedendo o seu lugar ao novo bloco.
No caso de mapeamento direto, há apenas uma possível linha para receber o novo bloco. Não há portanto escolha. No caso de mapeamento associativo e associativo por conjunto, usa-se um algoritmo de substituição para fazer a escolha. Para maior velocidade, tal algoritmo é implementado em hardware.
Dentre os vários algoritmos de substituição, o mais efetivo é o LRU (Least Recently Used): substituir aquele bloco que está na cache há mais tempo sem ser referenciado.
Esse esquema é análogo a substituição de mercadoria na prateleira de um
supermercado. Suponha que todas as prateleiras estão cheias e um novo
produto precisa ser exibido. Escolhe-se para substituição aquele produto
com mais poeira (pois foi pouco acessado.)
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
O algoritmo de substituição LRU substitui aquele bloco que está na
cache há mais tempo sem ser referenciado.
Numa cache associativa, é mantida uma lista de índices a todas as linhas na cache. Quando uma linha é referenciada, ela move à frente da lista.
Para acomodar um novo bloco, a linha no final da lista é substituída.
O algoritmo LRU tem-se mostrado eficaz com um bom hit ratio.
Source: Suponha cache com capacidade para 4 linhas. O índice pequeno denota o “tempo de permanência” na cache. https://www.cs.utah.edu/~mflatt/past-courses/cs5460/lecture10.pdf
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto
35 / 54
Há uma maneira mais rápida de implementar um pseudo-LRU.
Em cada linha da cache, mantém-se um Use bit.
Quando um bloco de memória é carregado numa linha da
cache, o Use bit é inicializado como zero.
Quando a linha é referenciada, o Use bit muda para 1.
Quando um novo bloco precisa ser carregado na cache,
escolhe-se aquela linha cujo Use bit é zero.
Na analogia de escolha de um produto menos procurado no
supermercado para ceder o lugar a outro produto, Use bit = zero denota aquele com poeira.
Universidade de Sorocaba
O Mapeamento Associativo por Conjunto: Exemplo
36 / 54
Tag	Célula 0
Célula 1
M bits
0
1
2
3
4
5
6
7
8
9
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
							
10
11
12
13
14
15
Bloco 0
Bloco 1
Bloco 2
Bloco 3
{
{
{
{
{
Bloco 4
{
Bloco 5
{
Bloco 6
{
Bloco 7
Linha 0
Linha 1
Linha 2
Linha 3
...
...
Conjunto 0
Conjunto 1
			
			
			
			
Mapeamento de Endereços
	Conjunto 0	Conjunto	1
	0000	0010	
	0001	0011	
	0100	0110	
	0101	0111	
	1000	1010	
	1001	1011	
	1100	1110	
	1101	1111	
Universidade de Sorocaba
Mapeamento Associativo por Conjunto: Endereços
37 / 54
Dado um endereço E da MP, como sabemos se o dado está na cache? Como no mapeamento direto, endereço é dividido em três partes:
 Célula do endereço dentro do bloco: dado por c = E mod X .
 Número do conjunto: dado por n = (E div X ) mod N.
) Tag (para diferenciar dois blocos em um mesmo conjunto), dada por: t = (E div X ) div N.
Se X e N são potências de 2, estes cálculos são triviais:
	...	Ei+j	Ei+j-1	...	Ei	Ei-1	...	E1	E0
c
{
{
{
Se X = 2i e N = 2j: t	n
Com endereço de 4 bits, E = 11(10), X = 2 e N = 2:
E = 1 0 1 1
c = 1 n =
t = 2
Universidade de Sorocaba
Nível de Associatividade
38 / 54
O mapeamento direto pode ser visto como um caso especial do mapeamento associativo por conjunto.
 Cada conjunto possui uma única linha.
O mapeamento associativo também.
 Um único conjunto.
O mapeamento associativo por conjunto, portanto, permite balancear os dois aspectos:
Complexidade vs. desempenho.
Universidade de Sorocaba
39 / 54
Universidade de Sorocaba
Nível de Associatividade
O Problema da Substituição de Bloco
40 / 54
Universidade de Sorocaba
O Problema da Substituição de Bloco
Quando há um cache miss, além de delegar o acesso
ao dado à MP, a cache também traz todo o bloco e o
armazena.
 Princípios da localidade temporal e espacial.
Mas geralmente não há uma linha vazia para o novo bloco.
 Ao contrário, outro bloco tem que ser removido.
Nova pergunta: qual bloco remover?
41 / 54
Universidade de Sorocaba
O Problema da Substituição de Bloco (II)
Para o mapeamento direto, a escolha é trivial.
 Só há ma opção, porque cada bloco tem uma alocação fixa de linhas na cache.
Para os mapeamentos associativos (totalmente ou por conjuntos), a escolha é mais difícil.
 Há várias opções de blocos a substituir.
 Se pudéssemos adivinhar o futuro, faríamos a melhor escolha possível.
 Bloco que vai demorar mais tempo para ser usado.
42 / 54
Universidade de Sorocaba
O Problema da Substituição de Bloco (III)
43 / 54
Embora não possamos adivinhar o futuro, podemos prevê-lo ou projetá-lo.
 Usar informações passadas para tentar inferir o que acontecerá no futuro.
Duas abordagens neste sentido:
 Algoritmo FIFO (First In, First Out).
Dentre os blocos candidatos, escolhe para substituição aquele colocado há mais tempo na cache.
 Algoritmo LRU (Least Recently Used).
Dentre os blocos candidatos, escolhe para substituição aquele cujo último acesso foi há mais tempo.
Universidade de Sorocaba
O Problema da Substituição de Bloco (IV)
44 / 54
Note que tanto o FIFO quanto o LRU necessitam do armazenamento de informações sobre os blocos na cache.
 Quando foi colocado lá.
 Qual foi a última utilização.
Ou seja, eles precisam de bookkeeping.
 Torna a cache mais complexa e cara.
Há uma outra alternativa:
 Escolher para remoção um bloco aleatório.
 Mais fácil e barato de implementar.
 Desempenho razoável, muito próximo do LRU para alta associatividade.
Universidade de Sorocaba
O Problema da Escrita
45 / 54
Universidade de Sorocaba
O Problema da Escrita
46 / 54
Caches funcionam muito bem quando o processador precisa ler dados da memória. Mas e quando é necessário escrever?
 Alterar o valor em uma determinada posição de memória.
A operação de escrita traz o seguinte dilema.
 Devemos sempre atualizar os valores na MP para manter a consistência dos dados? [Write Through]
 Ou devemos fazer atualizações só na cache enquanto o bloco estiver lá? [Write Back]
Universidade de Sorocaba
O Problema da Escrita: Write Through
47 / 54
Na técnica de Write Through, sempre que o processador atualiza uma posição de memória, o dado é atualizado tanto na cache, quanto na MP.
Mantém a consistência dos dados da cache e da MP.
i.e., MP não tem dados com valores diferentes daqueles na cache.
Isso é bom porque:
Simplifica substituição de bloco na cache.
Alguns dispositivos de E/S podem ler diretamente da MP, sem passar pela cache.
Por outro lado, escritas à memória são sempre lentas.
Sempre precisam ir à MP.
Universidade de Sorocaba
O Problema da Escrita: Write Back
48 / 54
Nesta técnica, escritas são sempre feitas em cache.
Apenas quando bloco é removido da cache, conteúdo é atualizado na MP.
 Normalmente, há um bit chamado dirty que acusa se o bloco precisa ou não ser atualizado na MP.
Assim como as leituras, escritas também são tipicamente rápidas por acessar apenas a cache.
Por outro lado:
Dispositivos de E/S que acessariam diretamente a memória precisam passar pela cache.
Isso pode sobrecarregá-la.
Há ainda a questão de como lidar com vários processadores/núcleos, cada um com sua própria cache.
Universidade de Sorocaba
O Problema da Escrita: Write Once
Outra técnica é o Write Once.
Apropriada para sistemas multiprocessados.
Na primeira escrita, a cache executa um Write Through.
Dado é atualizado na MP.
Outros componentes são avisados de que dado foi atualizado.
A partir da segunda escrita, cache simplesmente notifica outros componentes (e.g., outros processadores) de que háalterações.
Outros componentes, ao precisar do dado, passam a requisitá-lo à cache com a versão atualizada.
49 / 54
Universidade de Sorocaba
Outros Fatores
50 / 54
Universidade de Sorocaba
Níveis de Cache
51 / 54
Computadores modernos geralmente têm vários níveis de cache.
 e.g., cache L1, L2 e L3.
Os níveis mais baixos correspondem a caches pequenas e rápidas. Quanto mais alto o nível, mais lenta é a cache, mas também maior.
 Embora ainda muito mais rápidas e menores que a MP.
A justificativa dos vários níveis é a mesma para a existência da cache em primeiro lugar.
 Se um nível é muito mais rápido que os níveis acima e conseguimos boas taxas de cache hit, então há ganho de desempenho.
Universidade de Sorocaba
Bits de Controle
52 / 54
Além do campo tag associado a cada linha e dos dados, uma cache pode armazenar certos bits de controle.
Um deles já foi citado antes: o bit dirty.
 Indica que conteúdo do bloco foi alterado e precisa ser atualizado na MP.
Outro bit comum é o de validade.
 Indica se o conteúdo de uma linha da cache é válido.
 Conteúdo pode ser inválido, por exemplo, quando o processador é ligado.
Universidade de Sorocaba
Tamanho da Cache e Largura de Linha
53 / 54
Obviamente queremos sempre a maior cache possível.
 Mas caches muito grandes não são viáveis.
Tamanhos típicos giram em torno de:
 Dezenas de KB na L1.
 Centenas de KB na L2.
 Alguns poucos MB na L3.
Uma questão interessante é como alocar a memória disponível.
 i.e., qual a largura das linhas da cache.
Linhas maiores favorecem a localidade espacial. 
Mas com linhas menores, podemos ter mais linhas.
 Favorece situações em que os acessos são mais distribuídos.
Universidade de Sorocaba
Exercício
54 / 54
Suponha um computador com 4 GB/4294967296bytes de memória RAM.
 Memória é endereçada em células de 1 byte.
 Cache possui linhas com 32 células cada (além do campo tag).
 No total, a cache possui 1024 linhas.
Determine o formato dos endereços de memória (e.g., tag, coluna, etc) nos seguintes tipos de mapeamento:
 Mapeamento direto.
 Mapeamento associativo.
 Mapeamento associativo por conjunto com 16 conjuntos (com o mesmo número de linhas cada).
Universidade de Sorocaba