Tema 3 - Parte 2 - Conceitos básicos de cache

Prévia do material em texto

Universidade Federal de Pelotas
Centro de Desenvolvimento Tecnológico
Programa de Pós-Graduação em Computação
Arquiteturas de Computadores
Tema 3: Parte 2
Conceitos básicos de memórias cache
Prof. Marcelo Schiavon porto
porto@inf.ufpel.edu.br
2
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Cache, em inglês: lugar seguro para esconder ou guardar algo
• Cacher, em francês: esconder, guardar
• Nome usado para designar o nível de memória entre o 
processador e a memória principal
• Este nome foi usado pela máquina que introduziu pioneiramente 
(no início dos anos 1960) este nível de memória (entre a 
memória principal e o processador)
• Cache funciona pois explora o princípio da localidade
• Hoje em dia, usa-se este nome para designar qualquer memória 
que explore o princípio da localidade
Memória Cache 
3
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• A princípio, uma hierarquia de memória pode ter 
qualquer número de níveis
• Entretanto, os dados sempre serão copiados entre dois 
níveis adjacentes (i e i+1, onde i está mais próximo do 
processador)
• Podemos concentrar nossa atenção em dois níveis 
quaisquer i e i+1: i, que chamaremos de superior (mais 
próximo do processador) e i+1, que chamaremos de 
inferior
Definições 
4
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Bloco: unidade mínima de informação, contendo um certo 
número de palavras de memória.
• Exemplo, com 8 palavras (de memória)
Definições 
Informação*
XXXXX000
XXXXX001
XXXXX010
XXXXX011
XXXXX100
XXXXX101
XXXXX110
XXXXX111
* informação = instrução ou dado
5
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Se a informação solicitada pelo processador estiver 
presente no nível superior da hierarquia, ocorre um acerto
(hit)
• Se a informação solicitada pelo processador não puder ser 
encontrada no nível superior, a tentativa de encotrá-la 
gera uma falta (fault ou miss)
• Quando ocorre uma falta, o nível imediatamente inferior é 
acessado, na tentativa de se recuperar o bloco com a 
informação solicitada pelo processador
Definições 
6
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Se um bloco está presente no nível i, então ele também está 
presente no nível i+1
Definições 
processador
Cache L2
Memória 
principal
Cache L1 Nível 1
Nível 2
Nível 3
7
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• A taxa de acertos ou razão de acertos (hit ratio) 
corresponde à fração dos acessos à memória encontrados 
no nível superior (com frequência, é usada como medida de 
desempenho do sistema de memória)
• A taxa de faltas (= 1- taxa de acertos), ou miss ratio, é a 
fração de acessos à memória não encontrados no nível 
superior
Definições 
8
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Tempo de acerto (hit time) é o tempo necessário para 
acessar o nível superior da hierarquia, que inclui o tempo 
necessário para determinar se a tentativa de acesso à 
informação vai gerar um acerto ou uma falta
• A penalidade por falta (fault penalty) é o tempo necessário 
para substituir um dos blocos do nível superior pelo bloco 
do nível inferior que contém a informação desejada, mais o 
tempo para enviar a informação ao processador
Definições 
Tempo de acerto Tempo de acesso ao nível 
imediatamente inferior
<<
9
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Tc = tempo de acesso à cache
Tm = tempo de acesso à memória principal
Tce = tempo efetivo de acesso à cache, considerando o efeito dos misses
Impacto no Desempenho
10
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Assumamos as seguintes características de um sistema de 
memória extremamente simples:
• O processador sempre requisita uma única palavra
• Existe apenas um nível de memória cache (L1)
• Os blocos de L1 são constituídos por somente uma palavra
Memória Cache 
11
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
x4
x1
Xn-2
Xn-1
x2
x3
x4
x1
Xn-2
Xn-1
x2
xn
x3
Fazendo referência 
ao dado xn
antes depois
• Como saber se uma informação está na cache?
• Caso ela esteja, como encontrá-la?
Memória Cache 
12
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Um bloco só pode ser colocado em exatamente um lugar
na cache
• “Existe um caminho, mapeado previamente, de qualquer
endereço de bloco da memória principal para uma única
posição da cache”
• A posição da cache é dada por:
(Endereço do bloco) módulo (Número de blocos da cache)
• O mapeamento direto é um dos extremos
Mapeamento Direto
13
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• É o outro extremo, dos tipos de mapeamento
• Um bloco da memória principal pode ser colocado em qualquer
posição da cache
• Um bloco de memória pode ser associado a qualquer “entrada”
(conjunto) da cache
• É preciso pesquisar todas as entradas da cache, a fim de localizar
um determinado bloco (pois ele pode estar em qualquer uma das
entradas)
• Para reduzir o tempo da pesquisa, ela é feita em paralelo, usando
um comparador para cada entrada da cache
• O custo do hardware é alto: tal esquema somente é atrativo para
caches pequenas
Mapeamento Totalmente Associativo
14
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Fica entre os dois tipos de mapeamento anteriores
• Existe um número fixo de posições na cache (no mínimo duas) nas quais 
cada bloco pode ser colocado
• Cache associativa n: é uma cache associativa por conjunto com n posições 
possíveis para guardar um bloco em cada conjunto
• É composta por um certo número de conjuntos, cada conjunto com n
blocos
• Cada bloco da memória principal é mapeado para um dos conjuntos da 
cache, determinado pelo campo de índice do endereço (sendo que o bloco 
pode ser colocado em qualquer dos elementos desse conjunto)
• O conjunto que contém o bloco de memória é dado por
(Número do bloco) módulo (Número de conjuntos da cache)
Mapeamento Associativo por Conjunto
(ou Bloco Associativo)
15
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Política de substituição em caches
• Quando ocorre um perda de leitura (capacidade ou de
conflito) a controladora da cache precisa escolher um bloco
para ser substituído
• Como esta substituição ocorre no mapeamento direto?
• Não existe escolha, apenas uma posição da cache pode
ser substituída
• Como esta substituição ocorre no mapeamento associativo?
• Aleatória
• Uso menos recente (LRU)
• Primeiro a entrar, primeiro a sair (FIFO)
16
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Política de substituição em caches
• Aleatória
• O bloco a ser substituído é simplesmente escolhido
aleatoriamente
• Estratégia simples para implementação em hardware
• Circuitos LFSR (Linear Feedback Shifter Register) são
usados para gerar números pseudo-aleatórios em
hardware
17
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Política de substituição em caches
• Uso menos recente (LRU)
• Os acessos aos blocos devem ser registrados
• O bloco a ser substituído é aquele que está a mais
tempo sem ser solicitado
• Explora o princípio da localidade temporal
• Controle mais complexo
• Complexidade aumenta com o aumento do tamanho dacache
• Geralmente é apenas aproximado
18
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Política de substituição em caches
• Primeiro a entrar, primeiro a sair (FIFO)
• Uma forma simplificada de implementar o LRU
• O bloco “mais antigo” é substituído e não o LRU
• Controle menos complexo
19
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Fontes de Misses (3Cs)
• Compulsórios (cold start ou chaveamento de
processos, primeira referência): primeiro acesso a
uma linha
• De Conflito (ou Colisão)
• De Capacidade
• Invalidação: outro processo (p.ex. I/O) atualiza
memória
20
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Fontes de Misses
• Compulsórios
• É um “fato da vida”: não se pode fazer muito a respeito
• Se o programa vai executar “bilhões” de instruções, misses
compulsórios são insignificantes
• Uma solução para amenizar o problema é a pré-carga da cache
21
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Fontes de Misses
• De conflito (ou colisão)
• Múltiplas linhas de memória acessando o mesmo conjunto da cache
conjunto-associativa ou mesma linha da cache com mapeamento
direto
• Solução 1: aumentar tamanho da cache
• Solução 2: aumentar associatividade
• De capacidade
• Cache não pode conter todas as linhas accessadas pelo programa
• Solução: aumentar tamanho da cache
22
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Fontes de Misses
23
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Quantidade de misses segundo a fonte
24
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• A maior parte dos acessos a memória por parte do
processador são para leituras
• Escritas representam 7% do tráfego geral da memória
• Cerca de 28% se considerarmos apenas uma cache de
dados
• De modo geral, deve-se otimizar o tempo de leitura, para
aumentar o desempenho médio do sistema
• Processadores tradicionalmente esperam o fim das
leituras, mas não das escritas
Escritas na cache
25
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Suponha que na execução de uma instrução store o dado seja
escrito somente na cache
• Que tipo de problema esta operação irá causar?
• Isto causará uma inconsistência: após, a escrita na cache, a
memória principal terá um valor diferente daquele que foi
escrito na cache
Escritas na cache
26
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Duas soluções básicas:
• Esquema Write through
• A informação é escrita no bloco da cache e também
na memória principal (ou cache de nível inferior)
• Esquema Write Back
• A informação é escrita somente no bloco da cache, e
só será escrito na memória principal quando for
substituído
Escritas na cache
27
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Esquema Write Through
• Vantagens
• Fácil de implementar
• Um cache miss nunca resulta em uma escrita na memória
principal
• Memória sempre possui o dado mais recente, mantendo sempre
a coerência dos dados
• Desvantagens
• Escritas são mais lentas
• Cada escrita requer em acesso a memória principal
• Necessita de maior largura de banda de memória
Escritas na cache
28
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Esquema Write Back
• Vantagens
• As escritas ocorrem na velocidade da cache
• Várias escritas em um bloco da cache resultam em apenas uma
escrita na memória principal
• Menor largura de banda e menor consumo de energia
• Desvantagens
• Implementação mais complexa
• Dados na cache e na memória principal podem estar
inconsistentes
• Uma leitura pode gerar uma escrita na memória principal
Escritas na cache
29
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Esquema Write Back
• Dirty bit (bit de sujo)
• Como muitas vezes o bloco armazenado na cache não está
consistente com a memória principal, um “bit se sujo” é usado
para indicar esta inconsistência
• Caso o bit de sujo esteja em “0” (limpo), o dado está consistente
e não será escrito na memória principal em caso de write miss
• Caso o bit de sujo esteja em “1” (sujo), o dado está inconsistente
e deverá ser escrito na memória principal em caso de write miss
Escritas na cache
30
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• O que é um Write Miss (perda de escrita)?
• Quando o processador solicita uma escrita o endereço
solicitado não está armazenado na cache.
• Duas opções em caso de write miss:
• Alocação de escrita
• As perdas de escrita atuam como perdas de leitura
• Alocação sem escrita
• As perdas de escrita não afetam a cache
• O bloco é modificado apenas na memória principal
Escritas na cache
31
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Write Through
• Alocação sem escrita
32
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Write Back
• Alocação de escrita
33
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• O esquema write-through não favorece o desempenho
• Qualquer escrita faz com que a memória principal seja escrita
também
Tratamento das Escritas
34
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Escrita na cache de dados com Buffer de escrita:
• Buffer de escrita armazena o dado enquanto este aguarda para
ser escrito na memória
• Após escrever o dado na cache e no buffer de escrita, o
processador pode continuar a execução das instruções
• Se o buffer de escrita estiver cheio quando o processador tiver
que executar uma instrução de escrita, o processador precisa
parar, até que haja posição disponível no buffer
Esquema Write-Through com Buffer de Escrita
35
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Escrita na cache de dados com Buffer de escrita:
• Se a velocidade da memória para completar as escritas for 
menor que a taxa à qual o processador está gerando as escritas, 
nenhum buffer (por maior que seja) conseguirá resolver o 
problema
• O tamanho do buffer de escrita depende da relação citada no 
item anterior 
Esquema Write-Through com Buffer de Escrita
36
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Write buffer é uma FIFO
• Funciona bem se:
• Frequência de escritas << 1 / ciclo escrita DRAM
• Problema
• Frequência de escritas > 1 / ciclo escrita DRAM
• Saturação do Write Buffer
Esquema Write-Through com Buffer de Escrita
37
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Frequência de escritas > 1 / ciclo escrita DRAM
• Se esta condição existe por um longo período de tempo (porque
tempo de ciclo da CPU é rápido demais e/ou ocorrem muitas
instruções store em sequência):
• Write-Buffer terá overflow, não importa quão grande ele seja
• Solução para saturação do Write Buffer?
• Usar cache com write back
• Instalar uma cache de segundo nível (L2)
Esquema Write-Through com Buffer de Escrita
38
Conceitos básicos de memória cache
Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
PATTERSON, David A.; HENESSY, John L. Organização e 
Projeto de Computadores: a interface hardware/software. 
2a.ed. Rio de Janeiro: Campus, 2005.Bibliografia