Memórias cache
Organização de Computadores
• CPU procura por dados em L1, depois em L2 e finalmente
na memória principal
(L1: dentro da UCP e L2: fora do processador, na placa
mãe)
UCP
registradores
barramento de
cache
L2 cache
L1
cache
interface de
barramento
ULA
barramento barramento de
de sistema
memória
ponte
E/S
memória
principal
Organização geral da memória cache
<valid>: diz se a linha está válida
<tag>: identifica a linha
Organização de Computadores
B: conteúdo da palavra
1bit válido t bits para
B = 2b bytes
por linha tag por linha
por bloco de cache
valid
tag
valid
tag
valid
tag
valid
tag
conj. 0:
S = 2s sets
conj. 1:
0
•••
0
1
•••
B–1
1
•••
B–1
0
•••
0
1
•••
B–1
1
•••
B–1
1
•••
B–1
1
•••
B–1
•••
valid
tag
valid
tag
conj. S-1:
0
•••
0
Tamanho da cache: C = B x E x S bytes
E linhas
por
conjunto
Endereçamento de cache
<ind.conj>: identifica o conjunto
<tag> identifica a linha do conjunto
<offset>: guarda o início da palavra
v
tag
v
tag
v
tag
v
tag
conj.0:
conj 1:
0
•••
0
1
• • • B–1
1
• • • B–1
0
•••
0
1
• • • B–1
1
• • • B–1
1
• • • B–1
1
• • • B–1
•••
conj.
S-1:
v
tag
v
tag
0
•••
0
Organização de Computadores
Endereço A:
t bits
s bits
b bits
m-1
0
<tag>
<índ. conj.> <offset>
A palavra do endereço A está na cache
se: os bits de tag <tag>
em uma das linhas válidas
do conjunto <ind. conj.> são idênticos
aos bits do campo <tag> do endereço.
O conteúdo da palavra começa no
deslocamento de <offset> bytes
a partir do início do bloco
Cache mapeada diretamente
Organização de Computadores
• Forma mais simples
• Caracterizada por ter uma linha por conjunto
conj. 0:
valid
tag
bloco da cache
conj. 1:
valid
tag
bloco da cache
•••
conj. S-1:
valid
tag
bloco da cache
E=1 linha por
conjunto
Acesso a caches mapeadas diretamente
Organização de Computadores
• Seleção do conjunto feita pelos bits de índice de
conjunto
conj. selecionado
conj. 0: valid
tag
bloco da cache
conj. 1: valid
tag
bloco da cache
•••
t bits
m-1
tag
s bits
00 001
ind. conj
b bits
offset
conj. S-1: valid
0
tag
bloco da cache
Acesso a caches mapeadas diretamente
Organização de Computadores
• Verificar se a linha é válida no conjunto
selecionado com campo tag idêntico aos bits de tag
e extrai a palavra desejada
=1? (1) O bit válido tem que ser 1
0
conj. (i)
selecionado:
1
1
2
0110
3
4
w0
5
w1 w2
(2) Os bits de tags na linha
da cache tem que casar = ?
com os bits de tag do
endereço
m-1
t bits
0110
tag
s bits
i
ind. conj.
b bits
100
offset
6
7
w3
(3) Se (1) e (2), então
acerto,
e offset
seleciona
o byte inicial, que é 4
0
Exemplo de cache mapeada
diretamente
t: bits para a tag
b: bytes para o bloco
s: bits para o índice do conjunto
t=1
x
S=2s B=2b
s=2 b=1
xx
x
v
11
M=endereço para 16 células, E=1 linha por conjunto,
S=4 conjuntos, B=2 bytes por bloco
Acessos a endereços (leituras):
0 [00002], 1 [00012], 13 [11012], 8 [10002], 0 [00002]
0 [00002] (miss)
tag
data
0
13 [11012] (miss)
v tag
data
m[1]
m[0]
M[0-1]
(1)
(3)
v
1
(4)
Organização de Computadores
8 [10002] (miss)
tag
data
1
1
m[9] m[8]
1
1
M[12-13]
0
m[1]
m[0]
M[0-1]
1
1
1
m[13]
m[12]
M[12-13]
v
M[8-9]
1
1
1
(5)
0 [00002] (miss)
tag
data
11
0
m[1]
m[0]
M[0-1]
11
1
m[13]
m[12]
M[12-13]
Caches associativas por conjunto
Organização de Computadores
• Caracterizadas por mais de uma linha no conjunto
conj. 0:
conj. 1:
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
•••
conj. S-1:
valid
tag
bloco de cache
valid
tag
bloco de cache
E=2 linhas
por conj.
Acesso a caches associativas por
conjuntos
Organização de Computadores
• Seleção do conjunto é igual à memória mapeada
diretamente
conj. 0:
Conj. selecionado
conj. 1:
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
•••
t bits s bits
00 001
m-1
tag
b bits
ìnd. conj. offset
0
conj. S-1:
valid
tag
bloco de cache
valid
tag
bloco de cache
Acesso a caches associativas por
conjunto
Organização de Computadores
• Compara o tag de cada linha válida do conjunto
selecionado
=1? (1) Bit válido deve ser 1.
0
conj.(i)
selecionado):
1
1001
1
0110
(2) Os bits de tag em
uma das linhas de
cache tem que casar com
bits de tag do
endereço
1
2
3
4
5
w0
w1 w2
m-1
7
w3
(3) Se (1) e (2), então
acerto, e
offset seleciona
byte inicial.
=?
t bits
0110
tag
6
s bits
i
ind. conj.
b bits
100
offset
0
Caches totalmente associativas
Organização de Computadores
• Caracterizadas por um único conjunto que
contém todas as linhas
conj. 0:
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
•••
valid
tag
bloco de cache
valid
tag
bloco de cache
C=tamanho total
da cache
B=tamanho do
bloco de cache
E=C/B linhas
em um
único
conjunto
Acesso a caches totalmente associativas
Organização de Computadores
• Conjunto 0 é sempre selecionado
conj. 0:
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
valid
tag
bloco de cache
•••
t bits
m-1
tag
b bits
offset
0
(não tem informação do conjunto)
valid
tag
bloco de cache
valid
tag
bloco de cache
Acesso a caches totalmente associativas
Organização de Computadores
•
Compara tag do endereço com campo tag da cache
=1? (1) Bit válido deve ser 1.
0
cache
inteira:
0
1001
1
0110
1
1001
=?
0110
0
(2) Os bits de tag em
uma das linhas de
cache tem que casar
com bits de tag do
endereço
1
2
3
4
w0
=?
t bits
1001
m-1
b bits
100
tag
offset
0
5
6
w1 w2
7
w3
(3) Se (1) e (2), então
acerto, e
offset seleciona
byte inicial.
Algoritmo de substituição de dados
Organização de Computadores
• Consiste em determinar qual o bloco da memória
cache deve ser retirado para ceder lugar a outro
por ocasião de uma falta
• No mapeamento direto não há opção, pois só existe
um único lugar possível para um dado bloco
• Nos demais mapeamentos …
– LRU - Least Recently Used
– FIFO - First In First Out
– LFU - Least Frequently Used
– Escolha aleatória (muito simples e com desempenho parecido com
os demais)
Política de escrita I
Organização de Computadores
• A escrita é sempre realizada na cache pela CPU.
Quando deve ser realizada na memória principal?
• Problema: vários processos em várias CPU ou
dispositivos de E/S podem acessar um mesmo
bloco na MP
– Se o valor real não na MP então, valores diferentes para um mesmo
dado!
• Políticas de escrita...
– write through
– write back
– write once
Política de escrita II
Organização de Computadores
• Escrita em ambas (write through)
– Sempre que se escreve na cache, escreve-se na memória principal
– Pode haver queda no desempenho
• Escrita somente no retorno (write back)
– Escreve apenas quando o bloco é substituído: há bit de alteração
– A memória principal pode ficar desatualizada (ex: E/S via DMA)
• Escrita uma vez (write once)
– Utilizando quando tempo múltiplas UCPs
– Escreve apenas uma vez sempre que o bloco da cache for
atualizado (parecido com write trough)
– Seve para alertar os demais componente de que o campo foi
atualizado