Aula 14 HierarquiaDeMemoria

Prévia do material em texto

Organização e Arquitetura de 
Computadores
Hierarquia de MemóriaHierarquia de Memória
Ivan Saraiva Silva
Hierarquia de Memória
• A Organização de Memória em um 
computador é feita de forma hierárquica
– Registradores,– Registradores,
– Cache
– Memória Principal
– Disco Rígido
– CD-Rom, Flexíveis, etc.
Hierarquia de Memória
CPU
memory
memory
Cache Interna
Cache Externa
Menor
Capacidade
Maior
Custo
memory
memory
Memória Principal
Disco
Menor
Custo
Maior
Capacidade
Hierarquia de Memória
Custo, 
Velocidad
eRegistradores
Memória Cache
Tempo de Acesso, 
Capacidade
Memória Cache
Memória Principal
Memória Auxiliar
Hierarquia de Memória
5
Hierarquia de Memória
• Princípio
– Programas são executados dentro da CPU
– Programas geralmente não cabem integralmente – Programas geralmente não cabem integralmente 
na memória interna do chip (registradores + 
Cache interna)
– Em determinado instante dados podem ser 
copiados entre dois níveis adjacentes da 
hierarquia
– Há uma unidade mínima de transferência
• Blocos, páginas
Hierarquia de Memória
• Como funciona?
– Programas geralmente acessam uma pequena 
porção do espaço de endereçamento em um porção do espaço de endereçamento em um 
dado instante
Espaço de endereçamento
0 2^n - 1
Probabilidade
de referência
Hierarquia de Memória
• Como funciona?
– A hierarquia visa manter os dados utilizados 
mais próximos da CPUmais próximos da CPU
– Tipicamente deseja-se reduzidos tempos de 
acesso com elevadas capacidades de 
armazenamento
Hierarquia de Memória
• Como funciona?
– SRAM: tempo de acesso de 2 a 25ns e custo de 
$100 a $250 por Mbyte.$100 a $250 por Mbyte.
– DRAM: tempo de acesso de 60 a 120ns e custo 
de $5 a $10 por Mbyte.
– Disk tempo de acesso de 10 a 20 milhões de ns 
e custo de $0.10 a $0.20 por Mbyte.
Hierarquia de Memória
• A hierarquia de memória explora o 
princípio da localidade
– Localidade de memória é o princípio que diz – Localidade de memória é o princípio que diz 
que próximos acessos ao espaço de 
endereçamento tendem a ser próximos
– Há dois tipos de localidade
• Temporal
• Espacial
Hierarquia de Memória
• Localidade Temporal
– posições de memória, uma vez acessadas, 
tendem a ser acessadas novamente no futuro tendem a ser acessadas novamente no futuro 
próximo
• Localidade Espacial
– endereços em próximos acessos tendem a ser 
próximos de endereços de acessos anteriores
Hierarquia de Memória
CPU
memory
memory
Cache Interna
Cache Externa
Menor
Capacidade
Maior
Custo
memory
memory
Memória Principal
Disco
Menor
Custo
Maior
Capacidade
CACHE - Estrutura
• Armazena uma cópia de parte dos dados 
e/ou instruções armazenadas na memória
• A cahce é organiza da na forma de uma • A cahce é organiza da na forma de uma 
coleção blocos ou linhas
• Guarda somente os itens que serão 
referenciados com freqüência em 
determinado momento
• Explora os conceitos de Localidade 
Temporal e de Localidade Espacial
CACHE - Terminologia
• hit : dado procurado é encontrado na cache
• miss : posição não é encontrada
• Tempo de hit: Tempo de acesso com sucesso a 
cachecache
• Penalidade de miss: Tempo de transferência do 
dado para a cache
• hit ratio h = probabilidade de que posição 
acessada seja encontrada na cache
CACHE - Terminologia
• miss ratio = 1 – h
• Bloco – menor unidade de dados transferidos de 
um nível inferior para a cache
• Sejam dois níveis adjacentes na hierarquia de • Sejam dois níveis adjacentes na hierarquia de 
memória:
– Nível superior – próximo à CPU
– Nível inferior – longe da CPU
• Miss penalty – tempo para determinar se o acesso 
é um miss + tempo para substituir o bloco no nível 
inferior + tempo de entregar o bloco á CPU.
Impacto do Hit
• Tempo de acesso a memória
– Tam = Th + (1 – h)Tm
– Onde Th é o tempo de acesso a cache e Tm é o tempo 
de acesso a memória (considerados dois níveis 
hierarquicos)hierarquicos)
• Dados:
– Th = 10ns,
– Tm = 80ns e h=0,85
– Tam = 22ns
• Se h =1 então Tam = Th = 10ns
• Se não há cache Tam = Tm = 80ns
Questões
• Como saber se o acesso resultou ou não em 
Hit?
• Onde colocar o novo dado, no caso de • Onde colocar o novo dado, no caso de 
Miss?
• Qual dado retirar do cache?
Mapeamento
• O mapeamento entre a memória principal e 
a cache identifica se o dado buscado está na 
cachecache
– Exemplo
• Cache de 64 Kbystes (216)
• Blocos na cache de 4 Bytes
– Cache com 16K (214) linhas (blocos) de 4 bytes
• Memória de 16 Mbytes
– 24 bits de endereço 224 = 16M
Mapeamento
Linha 0 Byte 0 Byte 1 Byte 2 Byte 3
Linha 1 Byte 4 Byte 5 Byte 6 Byte 7Linha 1
Linha 2
Linha j
Byte 4 Byte 5 Byte 6 Byte 7
Byte 8 Byte 9 Byte 10 Byte 11
Byte n-3 Byte n-2 Byte n-1 Byte n
Completamente Associativo
• Qualquer bloco da memória pode ser levado 
para qualquer linha da cache
• O endereço é dividido em uma Tag que • O endereço é dividido em uma Tag que 
identifica a linha e no identificador do byte
– Se a cache tem 2n linhas (blocos) a Tag deve ter 
n bits
– Se o linha (bloco) tem 2m palavras o 
identificador deve ter m bits
– A memória é endereçada com n + m bits
Completamente Associativo
cache
byteTag
endereço word 0
comparação
simultânea
com todos
os endereços
processador
hit
cache organizada em linhas 
com palavras de 4 bytes
w 1 w 2 w 3
seleciona o byte
Completamente Associativo
Exemplo – Completamente 
Associativo
Bloco 0
Bloco 1
MC
Bloco 1
Bloco 2
Bloco 3
Endereço = 0110
Mapeamento Direto
• Cada bloco na memória principal é mapeado em 
uma única linha (bloco) da cache
– Módulo o número de linhas
• Endereço é dividido em duas partes• Endereço é dividido em duas partes
– w bits menos significativos identificam um byte na 
linha
– s bits mais significativos identificam um bloco
• Os s bits são divididos em um campo que 
identifica a linha com r bits e em uma Tag de s-r
bits
Mapeamento
• O mapeamento entre a memória principal e 
a cache identifica se o dado buscado está na 
cachecache
– Exemplo
• Cache de 64 Kbystes (216)
• Blocos na cache de 4 Bytes
– Cache com 16K (214) linhas (blocos) de 4 bytes
• Memória de 16 Mbytes
– 24 bits de endereço 224 = 16M
Mapeamento Direto
• 24 bit de endereço
• 2 bits identificam o byte (4 bytes)
• 22 Identificador do bloco• 22 Identificador do bloco
– 14 bits identificador da linha (214 linhas de 4 
bytes)
– 8 bit Tag (=22-14)
Tag s-r Linha r Byte w
8 14 2
Mapeamento Direto
Exemplo -Direto
Bloco 0
Bloco 1Bloco 1
Bloco 2
Bloco 3
Endereço = 0110
Associativo por Conjunto
(Set Associativity)
• A cache é dividida em um número de 
conjuntos (set)
• Cada conjunto tem um certo número de 
linha (define a associatividade)
• Cada conjunto tem um certo número de 
linha (define a associatividade)
• Um dado bloco da memória pode ser 
carregado em qualquer linha 
(completamente associativo) de um único 
conjunto (diretamente associativo) na cache
– Módulo número de sets
Set Associativo
Bloco 0
Bloco 1
Bloco 2
Bloco 3
Bloco 4
SET 0
SET 1
00000
00011
00100
00111
01000
01011
01100
01111
10000
10011
Endereço = 00110
Bloco 5
Bloco 6
Bloco 7
10011
10100
10111
11000
11011
11100
11111
Mecanismos de Escrita
• Leitura na cache: Não gera discrepância entre cache e 
memória principal 
• Escrita na cache: Cópias da palavra na cache e na memória 
principal podem tornam-se diferentes 
• Valores deveriam ficar iguais em razão de:
– acessos de E/S feitos através damemória principal
– acessos à memória principal por múltiplos processadores
• Tempo médio de acesso à cache é aumentado pela 
necessidade de atualizações da memória principal
• Mecanismos de coerência de escrita
– write-through
– write-back
Mecanismos de Escrita
• write-through
– cada escrita na cache é repetida imediatamente na 
memória principal
– estatisticamente apenas 5% a 34% dos acessos à – estatisticamente apenas 5% a 34% dos acessos à 
memória são escritas
• write-back
– linha da cache só é escrita de volta na memória 
principal quando precisa ser substituída
– estratégia mais simples: escrita é feita mesmo que linha 
não tenha sido alterada
– estratégia alternativa: só escrever de volta se linha foi 
alterada
Mecanismos de Escrita
ProcessadorProcessador
atualizado ao 
mesmo tempo
Write-through Write-back
ProcessadorProcessador
atualizado na 
reposição de 
MemóriaMemória
CacheCache de de 
dadosdados
mesmo tempo
MemóriaMemória
CacheCache dede
dadosdados
reposição de 
bloco
Mecanismos de Escrita
• Write-back
– Palavras individuais podem ser gravadas pelo 
processador na velocidade da cache (mais rápida)
– Múltiplas gravações dentro de um bloco requer somente – Múltiplas gravações dentro de um bloco requer somente 
uma gravação no nível inferior
• Write-Through
– Falhas de leitura consomem menos tempo, pois não 
requer gravação no nível mais baixo
– É mais fácil de ser implementado
Mecanismos de Escrita
• Write-back
– Aumenta a penalidade de falha (miss), pois o 
processador deverá esperar a atualização da memória 
antes de gravar na cache.antes de gravar na cache.
– Mais complexo de implementar.
• Write-Through
– Várias escritas no mesmo bloco implicam em várias 
escritas na memória principal.
– As escritas são feitas à velocidade da memória 
principal e não à da cache.
Substituição de Linhas
• Quando ocorre um miss, uma nova linha precisa ser trazida 
da memória principal para a cache
• Cache com mapeamento direto não precisa escolher qual 
linha da cache será substituída
• Cache completamente associativa: pode-se escolher 
qualquer uma das linhas
• Cache set-associativa: deve-se escolher uma linha dentro 
de um conjunto fixado pelo índice
• Algoritmo de substituição precisa ser implementado em 
hardware
– substituição randômica
– FIRST-IN FIRST-OUT
– LRU – Least Recently Used
Desempenho de cache
• Como já discutido nas aulas sobre desempenho, o tempo 
de execução é a medida mais importante na análise 
sobre desempenho
clockexec TNCT ×=
Desempenho de cache
clockmemCPUexec TNCNCT ×+= )(
• Com novos conhecimentos sobre caches, podemos expandir 
a equação anterior para:
clockmemCPUexec
Onde:
• NCCPU – corresponde ao número de ciclos gastos 
estritamente pela execução das instruções na CPU
• NCmem – corresponde ao número de ciclos gastos 
aguardando-se a correção de falhas (misses) na memória 
cache.
Desempenho de cache
• Em outras palavras, podemos dividir o tempo de 
execução em:
– Ciclos de clock que o processador gasta com as instruções do 
programa (NCCPU)programa (NCCPU)
– Ciclos de clock que o processador gasta aguardando pelo 
sistema de memória (NCmem)
• Consideremos que os acertos (hits) estão incluídos em 
NCCPU e que NCmem computa apenas as falhas de acesso 
(misses).
Desempenho de cache
NCNCNC +=
• O número de ciclos gastos pela CPU aguardando o sistema 
de memória pode ser dividido em:
– Ciclos de parada para leitura (NCread) ou escrita (NCwrite)
writereadmem NCNCNC +=
– Ciclos de parada para dados (NCdados) ou instruções (NCinstr)
instrdadosmem NCNCNC +=
Desempenho de cache
writedadosreadinstrreadmem NCNCNCNC ++= ,,
• Note que os acessos read e write são complementares entre 
si, assim como os acessos dados e instruções .
writedadosreadinstrreadmem NCNCNCNC ++= ,,
Desempenho de cache : Paradas de leitura
readfalhareadfalharead NCNNC ,, ×=
Número Número totaltotal de de 
ciclos gastos com ciclos gastos com 
parada de leituraparada de leitura
Número Número absolutoabsoluto
de falhas de leiturade falhas de leitura
Número de ciclos Número de ciclos 
gastos com gastos com umauma
falha de leiturafalha de leitura
• Normalmente, não se tem disponível o número absoluto 
de falhas de leitura, mas:
– Número total de leituras (Nread)
– Taxa (ou porcentagem) de falha entre leituras (Txfalha,read)
readfalhareadfalhareadread NCTxNNC ,, ××=
parada de leituraparada de leitura de falhas de leiturade falhas de leitura falha de leiturafalha de leitura
(penalidade)(penalidade)
Desempenho de cache : Paradas de escrita
• O mesmo raciocínio se aplica para falhas de escrita:
writefalhawritefalhawritewrite NCTxNNC ,, ××=
• Em muitas implementações de cache, as penalidades de 
leitura e escrita são as mesmas (tempo para buscar o 
bloco da memória de nível inferior), de forma que:
falhaacessofalhaacessosmem NCTxNNC ××= ,