T10

Transcrição

T10

Microcontroladores e Interfaces
3º Ano – Eng. Electrónica Industrial
Carlos A. Silva
2º Semestre de 2005/2006
http://www.dei.uminho.pt/lic/mint
Assunto: Memória Cache
Aula
#10
16 Maio 06
Organização da Cache: n-way Set
Asscociative

Considere os seguintes dados:

Uma cache única com 128 blocos de dados

Cada bloco contém 4 palavras (16 bytes)
A cache deve mapear uma memória de 16 bits de endereço
(64 k bytes de memória ou 4096 blocos de memória).
Mostre a organização/mapeamento da cache e os
campos do endereço na cache para:

Fully associative cache.

Direct memory cache.

2-way set-associative cache.
2 Microcontroladores e Interfaces 2005/2006 – Carlos A. Silva
1
Exemplo: Fully Associative Cache
V
V
Todas as 28 tags tem
que ser verificadas em
paralelo por hardware
próprio para localizar
um bloco de dados
Valid bit
V
Block Address = 12 bits
Tag = 12 bits
Block offset
= 4 bits
Exemplo: Direct Mapped
V
V
V
Only a single tag must
be checked in parallel
to locate a data block
Valid bit
V
Tag = 5 bits
Index = 7 bits
Main Memory
Block offset
= 4 bits
2
Exemplo: 2-Way Set-Associative
Two tags in a set must
be checked in parallel
to locate a data block
Valid bits not shown
Tag = 6 bits
Index = 6 bits
Main Memory
Block offset
= 4 bits
Organização da Cache: Cálculo do
Número de Bits Necessário

Quantos bits no total seriam necessários para uma
direct-mapped cache com 64 K bytes de dados com
blocos de uma palavra, assumindo endereços de 32
bits ?

64 K bytes = 16 K palavras = 214 palavras = 214 blocos

Tamanho do bloco = 4 bytes => tamanho do offset = 2 bits

Número de conjuntos = número de blocos = 214 => tamanho do
índice = 14 bits
Dimensão da tag = (tamanho do endereço) – (tamanho do índice)
– (tamanho do offset) = 32 – 14 – 2 = 16 bits
Número de bits/bloco = (bits de dados) + (bits da tag) + (bit de
validade) = 32 + 16 + 1 = 49 bits
Número de bits na cache = (Número de blocos) x (Número de
bits/bloco) = 214 x 49 = 98 K bytes
3

Quantos bits no total seriam necessários para uma 4way set associative cache para guardar a mesma
quantidade de dados ?

O tamanho do bloco e o número de blocos não variam.
Número de conjuntos = Número de blocos / 4 = (214)/4 = 212 =>
tamanho do índice ? 12 bits
Tamanho da tag = (tamanho do endereço) – (tamanho do índice) –
(tamanho do offset) = 32 – 12 – 2 = 18 bits
Número de bits/bloco = (bits de dados) + (bits da tag) + (bit de
validade) = 32 + 18 + 1 = 51 bits
Número de bits na cache = (Número de blocos) x (Número de
bits/bloco) = 214 x 51 = 102 K bytes
Conclui-se então que ao aumentar o tamanho da
associatividade aumenta-se o tamanho da cache.

Quantos bits no total seriam necessários para uma directmapped cache com 64 Kbytes de dados e 8 palavras por
bloco, assumindo que os endereços são de 32 bits (pode
fazer a cache de 232 bytes na memória)?

64 K bytes = 16 K palavras = 214 palavras = 214/8 = 211 blocos.
Tamanho do bloco = 32 bytes => tamanho do offset = (offset do bloco) +
(offset do byte) = 3 + 2 = 5 bits
Número de conjuntos = Número de blocos = 211 => tamanho do índice =
11 bits
Tamanho da tag = (tamanho do endereço) – (tamanho do índice) –
(tamanho do offset) = 32 – 11 – 5 = 16 bits
Número de bits/bloco = (bits de dados) + (bits da tag) + (bit de validade) =
8x32 + 16 + 1 = 273 bits
Número de bits na cache = (Número de blocos) x (Número de bits/bloco) =
211 x 273 = 68.5 K bytes
Aumento do número de blocos => menor número de bits da
cache
Microcontroladores e Interfaces 2005/2006 – Carlos A. Silva

8
4
Política de Substituição na Cache

Quando um miss ocorre na cache, o controlador da cache
tem que seleccionar um bloco de dados da cache. Este será
removido e substituído pelo bloco pedido pelo processador.
Este bloco por um dos seguintes métodos:

Aleatório:

Um bloco é escolhido aleatoriamente para ser substituído.

Este método é de fácil implementação em hardware.

Esta estratégia é a mais usada em implementações de cache.
Least-Recently Used (LRU):

Neste método todos os acessos aos blocos são registados.
O bloco que é substituído é aquele que foi menos usado para o maior
período de tempo.
A implementação desta estratégia é dispendiosa, uma vez que tem
que contabilizar os blocos que são acedidos.
Operações de Leitura e Escrita na Cache

Dados estatísticos sugerem as leituras (incluindo o
fetch de instruções) dominam os acessos à cache.

Os acessos de escrita representam 25% do tráfico de
dados da cache.
Na leitura da cache, um bloco é lido em simultâneo
com a comparação da tag com o endereço do
endereço do bloco. Se a leitura resulta num hit, o
dado é passado ao CPU, se resulta num miss, a
cache ignora o pedido.
5
Operações de Leitura e Escrita na Cache

Na escrita, a modificação do bloco de dados na
cache não é iniciada até que a comparação com a
tag com o endereço do bloco tenha terminada e
seja um hit.
Por esta razão na escrita da cache, a verificação da
tag não pode ocorrer em paralelo, pois apenas o
dados referido pelo CPU pode ser modificado.
A cache é classificada consoante as estratégias de
escrita e de actualização da memória em: write
through ou write back
Estratégias de Escrita da Cache

Write through: O dado é escrito simultaneamente
no bloco da cache e no bloco da memória principal.

O nível inferior tem sempre a versão mais actualizada
do dado. Esta característica é importante para o subsistema I/O e para multiprocessamento.
É mais fácil de implementar.
Um buffer de escrita é geralmente usado para reduzir o
stall do processador, enquanto os dados são escritos na
memória principal.
6
Estratégias de Escrita da Cache
• Write back: O dado é escrito ou actualizado apenas
no bloco da cache. O bloco modificado é escrito na
memória principal, quando é substituído.
• A escrita é feita à mesma velocidade que a cache.
• Um bit de status, chamado de dirty bit, é usado para
indicar se o bloco foi modificado enquanto esteve na
cache; caso o bloco não tenha sido modificado então
não precisa ser escrito na memória.
• Esta estratégia usa menos largura de banda da
memória, do que a estratégia de write through.
Políticas de Escrita da Cache numa
Cache Miss
• Uma vez que o dado não é geralmente necessário imediatamente
após um cache miss de escrita temos duas opções para resolve-lo:
•
Write allocate:
•
•
O bloco da cache é carregado durante o cache miss de escrita e
prossegue-se com os procedimentos normais a um cache hit.
No-Write Allocate:
•
O bloco é modificado nos níveis inferiores (memória de cache de nível
inferior, ou memória principal) e não é carregado na cache.
• Qualquer uma das duas políticas acima pode ser usada com as
estratégias de write back e write through tempos que:
•
A estratégia de write back geralmente usa a política de write allocate
para capturar as escritas subsequentes num bloco da cache.
•
A estratégia de write through geralmente usa a política de no-write
allocate uma vez que as escritas subsequentes têm que ir para a
memória principal.
7
Taxa de Miss da Cache
• Taxa de Miss para caches com diferentes dimensões,
associatividades e algoritmos de substituição:
Associativity:
2-way
Random
4-way
LRU
8-way
Size
LRU
Random LRU
Random
16 KB
5.18% 5.69%
4.67%
5.29% 4.39% 4.96%
64 KB
1.88% 2.01%
1.54%
1.66% 1.39% 1.53%
256 KB
1.15% 1.17%
1.13%
1.13% 1.12% 1.12%
Taxa de Miss da Cache
• Classificação do tipo de miss:
•
Compulsório (Compulsory):
• O primeiro acesso a um bloco irá falhar porque não está na cache,
por isso o bloco tem que ser trazido para a cache. Também
conhecido por cold start misses e first reference misses.
•
Capacidade (Capacity):
• Se a cache não puder conter todos os blocos necessários durante a
execução de um programa, ocorrerá um miss de capacidade, visto
determinados blocos serem desprezados e terem que ser carregados
mais tarde (ocorre nas cache fully associative).
•
Conflicto (Conflict):
• Estes misses ocorrem porque um bloco pode ser substituído e ser
necessário mais tarde devido vários blocos serem mapeados para a
mesma linha da cache. Também conhecido por collision misses ou
interference misses (ocorre nas caches com mapeamento directo e
nas caches com mapeamento pode conjunto).
8