[11 AOC] Hierarquia de Memória

Prévia do material em texto

Arquitetura e Organização de 
Computadores
HIERARQUIA DE MEMÓRIA
PROF. T I AGO BOCK HOLT, M sc
Fatos
• Os programas gastam a maior parte do tempo acessando a memória.
• Programadores gostariam de ter ao ser dispor quantidade ilimitada de memória 
com acesso instantâneo.
• O projeto do sistema de memória segue alguns princípios os quais tentam dar a 
ilusão ao programador de que ele dispõe de uma grande quantidade de memória 
com tempo de acesso pequeno.
Princípio da Localidade
• Vamos supor que uma pesquisa sobre: Avanços no Hardware dos computadores.
• Imagine uma biblioteca. O que você faria:
Princípio da Localidade
• Vamos supor que uma pesquisa sobre: Avanços no Hardware dos computadores.
• Imagine uma biblioteca.
Princípio da Localidade
• Com uma boa seleção de livros sobre a mesa, existe uma boa probabilidade de que 
muitos dos tópicos de que precisa possam ser encontrados neles. Assim, pode-se gastar 
mais tempo apenas usando os livros na mesa sem precisar se deslocar às estantes da 
biblioteca.
• Assim como não se precisa acessar todos os livros da biblioteca ao mesmo tempo, um 
programa não acessa todo o seu código ou dados ao mesmo tempo com igual probabilidade. 
• Princípio da localidade sustenta a maneira como você fez seu trabalho na biblioteca e o 
modo como os programas funcionam. Ou seja, diz que os programas acessam uma parte 
relativamente pequena do seu espaço de endereçamento em qualquer instante do tempo.
Princípio da Localidade
A hierarquia de memória explora o princípio da localidade
– 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
Localidade Temporal
Se um item é referenciado, ele tenderá a ser referenciado novamente 
em breve. 
◦ Ex: Se você trouxe um livro para examiná-lo, é provável que precise examiná-lo 
novamente em breve.
Localidade Espacial
Se um item é referenciado, os itens cujos endereços estão próximos 
tenderão a ser referenciados em breve. 
◦ Ex: Os livros sobre o mesmo assunto são colocados juntos na biblioteca para aumentar a 
localidade.
Princípio da localidade
A localidade nos programas surge de estruturas de programa simples 
e naturais. 
◦ Ex: Programas contém loops e, portanto, as instruções e os dados provavelmente são acessados de modo 
repetitivo, mostrando altas quantidades de localidade temporal.
Os programas executam Instruções de forma sequencial. 
◦ Ex: Acessos aos elementos de um array ou de um registro terão altos índices de localidade espacial.
Hierarquia de memória
Tiramos vantagem do princípio da localidade implementando a 
memória de um computador como uma hierarquia de memória. 
Consiste em múltiplos níveis de memória com diferentes velocidades 
e tamanhos.
◦ As memórias mais rápidas são mais caras por bit do que as memórias mais lentas e, portanto, são 
menores.
Hierarquia de memória
O sistema de memória é organizado como um hierarquia:
◦ Um nível mais próximo do processador em geral é um subconjunto de qualquer nível mais distante, e 
todos os dados são armazenados no nível mais abaixo. 
◦ Ex: Os livros na mesa formam um subconjunto da biblioteca onde você está trabalhando.
Uma hierarquia de memória pode consistir em múltiplos níveis, mas os dados são copiados apenas 
entre dois níveis adjacentes ao mesmo tempo.
◦ O nível superior – Mais perto do processador (menor, mais caro e mais rápido)
A unidade mínima de informação pode estar presente ou ausente na hierarquia de dois níveis é 
denominada de BLOCO.
Hierarquia de memória
Cada par de níveis na hierarquia pode ser 
imaginado como tendo um nível superior 
e um nível inferior.
Em geral, transfere-se um bloco inteiro 
quando copiamos algo entre os níveis.
Hierarquia de memória - Conceitos
Acertos: 
◦ Se os dados requisitados pelo processador 
aparecerem em algum bloco no nível superior. 
Caso contrário, é chamada de Falhas.
Taxa de acertos:
◦ É a fração dos acessos à memória encontrados no nível 
superior. Usado como medida de desempenho da hierarquia 
de memória.
Taxa de falhas (1 – taxa de acertos):
◦ A proporção de acessos à não encontrados em um nível da 
hierarquia de memória.
Hierarquia de memória - Conceitos
Tempo de acerto:
◦ O tempo necessário para acessar um nível da hierarquia 
incluindo o tempo necessário para determinar se o acesso é 
um acerto ou uma falha.
◦ É o tempo para consultar os livros na mesa.
Penalidade de falha:
◦ O tempo necessário para buscar um bloco de um nível inferior 
para um nível superior da hierarquia incluindo o tempo para 
acessar o bloco, transmissão entre os níveis e inseri-lo no nível 
que experimentou a falha. 
◦ O tempo para apanhar outro livro das estantes e coloca-los na 
mesa.
Hierarquia de memória
Hierarquia de memória
Hierarquia de memória
Tecnologias
Cache
Todas as operações de memória do
processador são feitas na cache.
MISS – É uma requisição de palavra que
não está na cache, um bloco de palavras
que contém a memória solicitada é
transferida para a cache, então a palavra
é devolvida ao processador.
HIT– Se a palavra solicitada já estiver na
cache. Não é preciso uma acesso a
memória para completar a requisição.
BLOCK – Quantidade mínima de dados
transferidos entre a cache e a memória.
Processor
Cache
small, fast 
memory
Main memory
large, inexpensive 
(slow)
words
blocks
O inventor da Cache
M. V. Wilkes, “Slave Memories and Dynamic Storage Allocation,”
IEEE Transactions on Electronic Computers, vol. EC-14, no. 2,
pp. 270-271, April 1965.
Princípios básicos de cache
Imagine um lugar seguro para guardar coisas que precisamos examinar.
No nosso exemplo da biblioteca, a cache seria:
Cache foi o nome escolhido para representar o 
nível de hierarquia de memória entre o 
processador e a memória principal.
Também usado para referenciar qualquer 
armazenamento usado para tirar proveito da 
localidade de acesso.
Princípios básicos de cache
Vamos considerar uma cache simples na qual cada requisição do processador é uma 
word e os blocos também consistem em um única word.
Antes de requisitar, a cache contém uma coleção 
de referências recentes, X1, X2 ... e o processador 
requisita uma word Xn que não está na cache. Isso 
resulta em uma falha.
memória principal (Xn) -> cache
Princípios básicos de cache
Como sabemos que o item de dados está na 
cache? Além disso, se estiver, como encontra-
lo?
A maneira mais simples de atribuir um local na 
cache para cada word da memória é atribuir um 
local na cache baseado no endereço da word na 
memória. Mapeamento Direto
Princípios básicos de cache
Exemplo Mapeamento Direto
Como há oito words na cache, um endereço X é 
mapeado para a word de cache X módulo 8. Ou 
seja, os log2(8) = 3 𝑏𝑖𝑡𝑠 menos significativos são 
usados como o índice da cache. 
Princípios básicos de cache
Ok, mas.... Como cada local da cache pode
armazenar o conteúdo de diversos locais da
memória, Como podemos saber se os dados na
cache correspondem a word requisitada pelo
processador?
Incluímos uma Tag: Contém a parte superior (mais
significativa) do endereço.
No nosso exemplos basta ter uma Tag
com os 2 bits mais significativos.
Princípios básicos de cache
Ok, mas.... Como reconhecer se um bloco de cache
não possui informações válidas. Por exemplo,
quando um processador é iniciado?
Precisamos de um bit de validade para indicar se
uma entrada contém um endereço válido.
Se o bit não estiver ligado, não pode haver uma
correspondência para esse bloco.
000
001
010
011
100
101
110
111
00000
00001
00010
0001100100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
Main
memory
Cache of 8 blocks
11 101 → memory address
cache address:
tag
index
3
2
-w
o
rd
 a
d
d
re
s
s
a
b
le
 m
e
m
o
ry
Block size = 1 word
in
d
e
x
 (
lo
c
a
l 
a
d
d
re
s
s
)
ta
g
00
10
11
01
01
00
10
11
Princípios básicos de cache
Arquitetura e Organização de 
Computadores
FUNCIONAMENTO DA CACHE
PROF. T I AGO BOCK HOLT, M sc
Funcionamento da cache
Dinâmica da Cache
Esse comportamento permite que uma cache 
tire proveito do princípio da localidade 
temporal: Words recentemente acessadas 
substitutem words menos referenciadas 
recentemente.
Dinâmica da Cache
Análogo a precisar de um livro da estante e 
não ter mais espaço na mesa para colocá-lo. 
Ou seja: Algum livro precisa ser devolvido à 
estante.
Exemplo
Cache com 1024
(210) linhas e com palavra de 32 bits.
Algoritmo - Mapeamento Direto
Considerações sobre os blocos
Blocos maiores exploram a localidade espacial para diminuir as taxas de falhas.
Porém a taxa de falhas pode subir se o tamanho de blocos que pode ser armazenado na cache se 
tornará pequeno e haverá uma grande competição entre esses blocos. 
Um bloco será retirado da cache antes que muitas de suas words sejam acessadas.
Tratamento de Escritas
Suponha que em uma instrução store, escrevemos os dados apenas na cache de dados.
• Após a operação de escrita, a memória principal teria valores desatualizados.
Uma técnica para manipular escritas é denominada write through, quando uma palavra é escrita de volta na 
memória imediatamente após ter sido escrita no cache (consistência de dados).
Outra técnica é denominada copy back, em que a memória só é atualizada quando a entrada é expurgada do 
cache para permitir que outra entrada tome conta da posição (consistência de dados).
Tratamento de Escritas
Tratamento de Escritas
• A técnica write through causa mais tráfego de barramento.
• A técnica write back pode gerar inconsistência se o processador efetuar uma transferência entre memória e 
disco, enquanto a memória não tiver sido atualizada.
• Mais complexo de ser implementado.
• Se a razão de leituras para escritas for muito alta, pode ser mais simples usar write through.
• Se houver muitas escritas, pode ser melhor usar write back e fazer com que o programa expurgue todo o 
cache antes de uma operação de entrada/saída.
Vantagens Write-back
• As words individuais podem ser escritas pelo processador na velocidade em que a 
cache pode aceitar (e não a memória).
• Diversas escritas dentro de um bloco exigem apenas uma escrita no nível inferior da 
hierarquia.
• Quando blocos são escritor com write-back, o sistema pode fazer uso efetivo de uma 
transferência de alta largura de banda, já que o bloco inteiro é escrito.
Considerações sobre a cache
Total de bits necessário para uma cache varia de acordo com:
1. Qtde. de bits para end. da memória principal (32, 64 bits, etc..).
2. Qtde. de bits para end. dos bloco (pode ser de várias palavras): 𝑚
3. Quantidade de blocos: 𝑛
4. Qtde de bits para end. das linhas: 𝑙
Considerações sobre a cache
Por exemplo, se considerarmos:
1. Endereço de 32 bits (Palavras alinhadas como múltiplos de 4 bytes).
2. Palavras por Bloco: 2𝑚.
3. Qtde. de Blocos: 2𝑛.
4. Qtde de bits para end. das linhas: 𝑙
Tag: Qtde. de bits para endereçamento – (n+m+ 𝑙)
Tag: 32 – (n+m+2) 
Total de bits: 𝑄𝑡𝑑𝑒. 𝑑𝑒 𝐵𝑙𝑜𝑐𝑜𝑠 x (tamanho do bloco + tamanho da tag + tamanho do campo de 
validade)
Total de bits: 2𝑛 x (tamanho do bloco + tamanho da tag + tamanho do campo de validade) 
= 2𝑛 x {(palavras por bloco x 32) + [32 – (n+m+2)] + 1} 
= 2𝑛 x [(palavras por bloco x 32) + (31 - n - m)]
Considerações sobre a cache
i. Divisão de bits do endereço
ii. Aproveitamento efetivo
◦ Dados em cada linha: 8(2^3) palavras de 16 bits = 128 bits
◦ Tamanho total da linha: 1(validade) + 11(tag) + 128(bloco) = 140 bits
◦ Aproveitamento = 128 * 100% / 140 = 91,42%
Considerações sobre a cache
Total de bits necessário para uma cache varia de acordo com:
1. Tamanho do endereçamento da memória principal (32, 64 bits, etc..).
2. Tamanho do bloco (pode ser de várias palavras).
3. Quantidade de blocos.
Por exemplo, se considerarmos:
1. Endereço de 32 bits (Palavras alinhadas como múltiplos de 4 bytes).
2. Palavras por Bloco: 2𝑚.
3. Qtde. de Blocos: 2𝑛.
Tag: 32 – (n+m+2) 
Total de bits: 2𝑛 x (tamanho do bloco + tamanho da tag + tamanho do campo de validade) 
= 2𝑛 x {(palavras por bloco x 32) + [32 – (n+m+2)] + 1} 
= 2𝑛 x [(palavras por bloco x 32) + (31 - n - m)]
Exercício
Quantos bits são necessários para uma cache diretamente mapeada com 16Kb de dados e blocos de 4 
words, considerando um endereço de 32 bits?
Exercício
Quantos bits são necessários para endereçar uma cache diretamente mapeada com 16Kb de dados e 
blocos de 4 words, considerando um barramento de 32 bits?
Resposta:
Total de bits: 2𝑛 x (tamanho do bloco + tamanho da tag + tamanho do campo de validade) 
= 2𝑛 x {(palavras por bloco x 32) + [32 – (n+m+2) ]+ 1}
Sabemos que 16Kb são 4K words = 212 words. 
Com um tamanho de bloco de 4 words (2𝑚=2), 2𝑛=10 blocos. Cada bloco possui 4 x 32, ou seja, 128 bits 
de dados mais uma tag, que é 32- 10 -2 bits, mais um bit de validade. Portanto, o tamanho da cache total 
é:
210 x {(4 * 32) + [32 - ( 10 + 2 +2)] – 1} = 210 x 147 = 147Kbits = 18,4 Kb
Conclusões
Vantagens do Mapeamento Direto:
• Estratégia simples para agilizar buscas.
• Procura simples (posição fixa).
• Simplicidade / Velocidade
Desvantagens do Mapeamento Direto:
• Pode ter mau aproveitamento das posições da cache (dependendo dos endereços gerados)
• Miss rate pode ser alto!
• Usa parte da cache para controle (armazena tags e bit de validade).
Esquemas de cache
Mapeamento Direto:
• Qualquer endereço de bloco na memória torna-se um único local no nível 
superior da hierarquia.
E se posicionarmos um bloco em qualquer local na cache?
Esquema de cache totalmente associativo 
Totalmente Associativa
Para realizar o esquema associativo, precisamos:
1. Todas as entradas da cache precisam ser pesquisada, pois um bloco pode 
estar posicionado em qualquer uma delas.
2. Um comparador associado a cada entrada da cache.
**Apenas viável para caches com pequenos números de blocos.
Associativa por Conjunto
Faixa intermediária de projetos entre o mapeamento direto e a cache 
totalmente associativa.
1. Existe um número fixo (ao menos 2) de locais onde cada bloco pode ser 
colocado.
2. Cada bloco da memória é mapeado para um conjunto único de cache.
1. Utiliza um campo índice.
3. Bloco pode ser colocado em qualquer elemento desse conjunto.
Arquitetura e Organização de 
Computadores
OBRIGADO
PROF. T I AGO BOCK HOLT, M sc