aula06_SistemaMemoria_Cache

Prévia do material em texto

2012/2 MATA48 - Arquitetura de Computadores 1
Instituto de Matemática
Departamento de Ciência da Computação
Arquitetura de Computadores
Sistema de memória
Prof. Marcos E Barreto
2012/2 MATA48 - Arquitetura de Computadores 2
Tópicos
● Conceitos gerais
● Memória cache
● Referências:
● Patterson; Hennessy. Organização e projeto
de computadores. 3ed. Cap. 7.
● Hennessy; Patterson. Arquitetura de computadores:
uma abordagem quantitativa. 4ed. Cap. 5.
● William Stallings. Arquitetura e organização 
de computadores. Cap. 5.
2012/2 MATA48 - Arquitetura de Computadores 3
Conceitos gerais
● Programadores desejam quantidade ilimitada de 
memória de rápido acesso.
● Projetistas aproveitam-se do princípio da 
localidade* para prover a abstração de uma 
memória grande e rápida.
● Localidade temporal: se um item é referenciado, ele 
tende a ser referenciado novamente em breve. Ex.: 
laços.
● Localidade espacial: se um item é referenciado, os 
itens cujos endereços estão próximos também serão 
referenciados. Ex.: vetores e registros.
* Programas acessam uma parte relativamente pequena do seu espaço de 
endereçamento num dado instante de tempo.
2012/2 MATA48 - Arquitetura de Computadores 4
Conceitos gerais (2)
● Hierarquia de memória: múltiplos níveis de 
memória com diferentes tamanhos e velocidades.
2012/2 MATA48 - Arquitetura de Computadores 5
Conceitos gerais (3)
● Hierarquia de memória: relação entre custo X 
capacidade X velocidade.
2012/2 MATA48 - Arquitetura de Computadores 6
Conceitos gerais (4)
● Hierarquia de memória X localidade 
temporal/espacial.
2012/2 MATA48 - Arquitetura de Computadores 7
● Hierarquia de memória: velocidade do 
processador X velocidade da memória principal.
C
on
ce
ito
s 
ge
ra
is
 (
5)
2012/2 MATA48 - Arquitetura de Computadores 8
Conceitos gerais (6)
● Bloco: unidade mínima de informação presente 
na hierarquia de memória de dois níveis.
2012/2 MATA48 - Arquitetura de Computadores 9
Conceitos gerais (7)
● Métricas:
● Taxa de acertos (hit)
● Taxa de falhas (miss): 
1 – taxa de acertos
● Tempo de acerto: determinar se 
● acesso é acerto ou falha.
● Penalidade de falha: tempo para 
transferência de um bloco de 
um nível I + 1 para um nível I.
Tempo de acerto < Penalidade de falha
2012/2 MATA48 - Arquitetura de Computadores 10
Memória cache
● Forma de armazenamento que tira proveito da 
localidade de acesso.
● Localizada no chip da CPU ou módulo, entre a 
CPU e a memória principal.
2012/2 MATA48 - Arquitetura de Computadores 11
Memória cache
● Exemplo de cache simples: requisição da word Xn
2012/2 MATA48 - Arquitetura de Computadores 12
Memória cache
1. CPU gera endereço de leitura 
(RA) da palavra a ser lida.
2. Se a palavra estiver na cache, 
ela é entregue ao processador; 
senão, o bloco contendo a palavra 
é carregado na cache e a palavra 
é entregue à CPU.
2012/2 MATA48 - Arquitetura de Computadores 13
Memória cache
● Embora haja um grande número de implementações de 
memória cache, existem alguns elementos básicos de 
projeto usados para classificar as memória cache.
2012/2 MATA48 - Arquitetura de Computadores 14
Memória cache
● Endereços de 
cache
● lógico/virtual 
X físico
● Emprego
de MMU
(memory 
management
unit)
2012/2 MATA48 - Arquitetura de Computadores 15
Memória cache
● Tamanho da cache
● IDEAL
– Pequeno suficiente para que o custo médio por bit seja 
próximo do custo médio por bit da memória principal.
– Grande suficiente para que o tempo médio de acesso 
seja satisfatório.
● PRÁTICA
– Por quê minimizar o tamanho da cache?
● Caches grandes tendem a ser lentas
● Área disponível no chip e na placa-mãe
● Projetistas preferem aumentar a largura de banda, 
com novas organizações de memória principal do que 
reduzir a latência da memória cache.
2012/2 MATA48 - Arquitetura de Computadores 16
2012/2 MATA48 - Arquitetura de Computadores 17
Memória cache
● Mapeamento de blocos da memória principal para 
a cache
● Como saber se um item de dados (bloco) está na 
cache?
● Se está, como encontrá-lo?
2012/2 MATA48 - Arquitetura de Computadores 18
Memória cache
● Organização cache / MP
● MP tem M = 2n/K blocos
● Cache tem m blocos (linhas)
● Como m < M, deve haver um tag que
que indique qual bloco da MP está 
armazenado na linha da cache.
2012/2 MATA48 - Arquitetura de Computadores 19
Memória cache
● Métodos de mapeamento
● Mapeamento direto
● Mapeamento associativo
● Mapeamento associativo em conjunto
2012/2 MATA48 - Arquitetura de Computadores 20
Memória cache
● Mapeamento direto
● Cada bloco da memória principal é mapeado a 
apenas uma linha possível da cache
● i = j módulo m
– i = número (endereço) da linha da cache
– j = endereço do bloco na memória principal
– m = total de linhas (endereços) da cache
2012/2 MATA48 - Arquitetura de Computadores 21
Memória cache
● Exemplo de mapeamento direto
● Cache com 64 blocos e um tamanho de bloco de 16 
bytes. Para qual bloco o endereço em bytes 1200 deve 
ser mapeado?
● Bloco da cache = (endereço do bloco MP) MOD (total de blocos 
da cache)
● Endereço do bloco MP = endereço em bytes / tamanho do bloco
● 1200 / 16 = 75
● 75 MOD 64 = 11
● Bloco 11 mapeia todos os endereços entre 1200 e 1215.
2012/2 MATA48 - Arquitetura de Computadores 22
● O uso de uma parte do endereço como número da 
linha garante um mapeamento exclusivo de cada 
bloco à uma linha da cache.
Implementação do mapeamento direto
2012/2 MATA48 - Arquitetura de Computadores 23
Implementação 
do mapeamento 
direto
Tamanho do endereço = (s+w) bits
Número de unidades endereçáveis = 2s+w palavras ou bytes
Tamanho do bloco = tamanho da linha = 2w palavras ou bytes
Número de blocos na memória principal = 2s
Número de linhas na cache = 2r
Tamanho da cache = 2r+w palavras ou bytes
Tamanho da tag = (s-r) bits
2012/2 MATA48 - Arquitetura de Computadores 24
Exemplo 
de mapeamento 
direto
2012/2 MATA48 - Arquitetura de Computadores 25
Implementação do mapeamento direto 
(outra perspectiva)
2012/2 MATA48 - Arquitetura de Computadores 26
Exemplo de acesso à memória cache
2012/2 MATA48 - Arquitetura de Computadores 27
Exemplo de acesso à memória cache
● O uso de uma parte do endereço como número da 
linha garante um mapeamento exclusivo de cada 
bloco à uma linha da cache.
● Endereço: 3 bits menos significativos.
2012/2 MATA48 - Arquitetura de Computadores 28
Memória cache
● Problema do mapeamento direto
● Problema: thrashing
– Existe um local fixo na cache para cada bloco.
– Se um programa referenciar repetidamente palavras 
alocadas em dois blocos que são mapeados para a mesma 
linha da cache, haverá muitas trocas de blocos de MP para 
a linha da cache, diminuindo a eficiência e o desempenho.
● Solução: victim cache
– Cache associativa, de tamanho entre 4 e 16 linhas de 
cache, colocada entre a cache e a memória principal
– Armazena dados que foram descartados recentemente e 
que podem ser lidos novamente, com custo baixíssimo.
=> ver material sobre victim cache (Apêndice D Livro Stallings)
2012/2 MATA48 - Arquitetura de Computadores 29
Memória cache
● Mapeamento associativo
● Permite que um bloco da memória principal seja 
mapeado para qualquer linha da cache.
● Compensa a desvantagem do mapeamento direto.
2012/2 MATA48 - Arquitetura de Computadores 30
Implementação 
do mapeamento 
associativo
Tamanho do endereço = (s+w) bits
Número de unidades endereçáveis = 2s+w palavras ou bytes
Tamanho do bloco = tamanho da linha = 2w palavras ou bytes
Número de blocos na memória principal = 2s
Número de linhas na cache= indetermindado
Tamanho da tag = s bits
2012/2 MATA48 - Arquitetura de Computadores 31
Exemplo de
mapeamento
associativo
2012/2 MATA48 - Arquitetura de Computadores 32
Memória cache
● Considerações sobre o mapeamento 
associativo
● Vantagem
– Flexibilidade em relação a qual bloco substituir quando 
um novo bloco for lido para a cache.
● Desvantagem
– Complexidade do circuito necessário para comparar as 
tags em paralelo.
2012/2 MATA48 - Arquitetura de Computadores 33
Memória cache
● Mapeamento associativo em conjunto
● Técnica intermediária entre mapeamento direto e 
associativo, que potencializa as vantagens e reduz 
as desvantagens.
● Cache é uma série de conjuntos, cada um 
consistindo em uma série de linhas.
● Relacionamentos
– m = v * k e i = j módulo v onde
● i = número do conjunto de cache
● j = número de bloco da memória principal
● m = número de linhas na cache
● v = número de conjuntos
● k = número de linhas em cada conjunto
2012/2 MATA48 - Arquitetura de Computadores 34
Elementos de projeto● Mapeamento 
associativo 
em conjunto
2012/2 MATA48 - Arquitetura de Computadores 35
Implementação 
do mapeamento 
associativo em 
conjunto
Tamanho do endereço = (s+w) bits
Número de unidades endereçáveis = 2s+w palavras ou bytes
Tamanho do bloco = tamanho da linha = 2w palavras ou bytes
Número de blocos na memória principal = 2s
Número de conjuntos = v = 2d
Número de linhas na cache = m = kv = k * 2d
Tamanho da cache = k * 2d+w palavras ou bytes
Tamanho da tag = (s-d) bits
2012/2 MATA48 - Arquitetura de Computadores 36
Exemplo de
mapeamento
associativo
em conjunto
2012/2 MATA48 - Arquitetura de Computadores 37
Memória cache
● Considerações sobre o mapeamento 
associativo em conjunto
● Se v = m, k = 1 => mapeamento direto
● Se v = 1, k = m => mapeamento associativo
● Em geral, emprega-se duas linhas por conjunto 
(v = m/2, k = 2) como organização associativa em conjunto.
● O uso de quatro linhas por conjunto (v = m/4, k = 4) provê 
uma melhoria adicional com custo relativamente baixo.
i = número do conjunto de cache
j = número de bloco da memória principal
m = número de linhas na cache
v = número de conjuntos
k = número de linhas em cada conjunto
2012/2 MATA48 - Arquitetura de Computadores 38
Memória cache
● Algoritmos de substituição
● Usados para a substituição de blocos em cache, quando a 
cache estiver cheia e um novo bloco tiver que ser lido.
● Se mapeamento direto, não há substituição!
● Para mapeamentos associativos, existem várias alternativas 
de algoritmos, dentre os quais:
– LRU (least recently used)
– FIFO (first-in, first-out)
– LFU (least frequently used)
– Escolha de uma linha aleatória
2012/2 MATA48 - Arquitetura de Computadores 39
Memória cache
● Política de escrita
● Como atualizar a memória principal com os blocos de dados 
que foram alterados na cache?
● Técnicas
– Write-through
● Escreve na cache e na memória
– Write-back
● Escreve somente na cache, marcando um bit (tag) na 
linha que foi modificada.
2012/2 MATA48 - Arquitetura de Computadores 40
Memória cache
● Tamanho da linha
● Razão de acerto X tamanho do bloco
– Depende do princípio da localidade
2012/2 MATA48 - Arquitetura de Computadores 41
Memória cache
● RAM estática (SRAM)
● Mesmos elementos 
lógicos de um 
processador
● Portas lógicas e 
flip-flops
● Armazena valores 
enquanto houver 
energia
2012/2 MATA48 - Arquitetura de Computadores 42
Memória cache
● Otimizações 
● As otimizações de cache são realizadas com base em três 
métricas: tempo de acerto, taxa de perda e penalidade de 
perda.
● Otimizações objetivam:
– Reduzir o tempo de acerto
– Aumentar a largura de banda da cache
– Reduzir a penalidade de perda
– Reduzir a taxa de perda
– Reduzir a penalidade de perda ou a taxa de perda por meio 
de paralelismo.
2012/2 MATA48 - Arquitetura de Computadores 43
Resumo das otimizações para memória cache
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43