aspd-slides-memorg

Prévia do material em texto

Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Memórias cache
João Canas Ferreira
Abril de 2004
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 1/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Conceitos básicos
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Princípios de funcionamento
Colocação e identificação
Actualização: substituição e escrita
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 2/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Princípio da proximidade
I Cache: Uma memória rápida que guarda as instruções/dados
usados mais recentemente.
I Princípio da proximidade: Programas tendem a re-utilizar
os dados e as instruções usados recentemente ou mais
próximos (90% do tempo em 10% das instruções?).
Existem 2 tipos de proximidade:
1. proximidade temporal—elementos acedidos recentemente
têm maior probabilidade de ser acedidos a seguir;
2. proximidade espacial—elementos colocados em posições
de memória próximas tendem a ser acedidos em instantes
consecutivos.
I Objectivo: Obter a rapidez de acesso da memória rápida e a
capacidade da memória mais lenta.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 3/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Hierarquia de memória
I Como a memória mais rápida é mais cara, a memória é
geralmente organizada numa hierarquia de vários níveis: cada
nível tem menor capacidade, é mais rápido e mais caro
(¤/bit) que o seguinte.
I Frequentemente cada nível está contido no seguinte (mas nem
sempre).
I A hierarquia de memória também é responsável pela
verificação de endereços (já que tem de mapear endereços nos
níveis correctos).
I A importância da hierarquia de memória tem aumentado com
os avanços de CPU. (Porquê?)
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 4/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Hierarquia de memória: situação típica
(No ano 2000.)
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 5/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Desempenho de CPU vs. memória
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 6/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Características da hierarquia de memória
Nível 1 2 3 4
Nome registos cache memória
principal
memória de
massa
Tamanho
típico
< 1 KB < 16 MB < 16 GB > 100 GB
Tecnologia memória
multi-
porto,
CMOS
CMOS SRAM CMOS
DRAM
disco
magnético
Acesso (ns) 0.25–0.5 0.5–2.5 80–250 5× 106
Largura de
banda
(MB/s)
2× 103 –
105
5000–10000 1000–5000 20–150
Gerido por compilador hardware OS OS/admin
Backup cache memória principal memória de
massa
CD/banda
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 7/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Termos básicos
I cache hit—CPU encontra item na cache (acerto).
I cache miss—CPU não encontra item na cache (falha).
I bloco—conjunto de dados (de tamanho fixo) que é obtido de
memória e colocado em cache (contém o item pedido).
I A proximidade temporal implica que o item será utilizado de novo
dentro de pouco tempo;
a proximidade espacial implica que haja uma probabilidade elevada
de que os outros dados do bloco sejam usados dentro de pouco
tempo.
I O tempo necessário para processar uma falha depende da latência e
da largura de banda da memória.
I A latência determina o tempo necessário para obter o primeiro
elemento do bloco.
I A largura de banda determina o tempo necessário para obter
(transferir) o resto do bloco.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 8/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Aspectos elementares de desempenho
I Tempo de execução (CPU): t
I Ciclos de relógio (CPU): nc
I Período de relógio: T = 1/f
I Ciclos de protelamento no
acesso a memória: nm
I Número de acessos a
memória: na
I Número de falhas: nf
I Taxa de falhas: tf = nf /ni
I Número de instruções: ni
I Penalidade de falha (em
ciclos): pf
Assumindo que: (a) nc inclui o tempo de tratamento de cache hit;
(b) CPU protela durante cache miss.
t = (nc + nm)× T
nm = nf × pf = ni ×
nf
ni
× pf = ni ×
na
ni
× tf × pf
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 9/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Porque são efectivas as memórias cache?
Hierarquias de memória
Caracterização do desempenho
Aspectos elementares de desempenho (cont.)
Os elementos da última equação podem ser medidos com relativa
facilidade.
Taxas de falhas podem ser avaliadas por simulação usando um
address trace (listagem dos endereços ordenados por ordem
temporal de acessos). [Não é constante. . . ] Uma alternativa:
contadores embutidos no CPU.
Assume-se que taxas de falhas e penalidade de acesso são iguais
para leituras e escritas; uma equação mais detalhada deve
distinguir as duas situações.
Formulação alternativa de taxa de falhas (tf ): nf /ni = fi e então
fi =
tf × na
ni
= tf ×
na
ni
fi é frequentemente dada em falhas/1000 instruções.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 10/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Quatro questões sobre hierarquias de memória
As questões mais importantes sobre um nível da hierarquia de
memória são:
1. Onde é colocado um bloco? [colocação]
2. Como determinar se um bloco está presente?
[identificação]
3. Que bloco deve ser substituído quando ocorre uma
falha? [substituição]
4. O que acontece durante a escrita? [estratégia de escrita]
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 11/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Localização dos dados
A localização dos dados em cache permite distinguir 3 categorias
de organização:
1. Um bloco tem apenas um lugar possível: mapeamento directo
[direct mapped cache].
2. Um bloco pode ser colocado em qualquer posição: memória
totalmente associativa.
3. Um bloco pode ser colocado em qualquer posição de num
conjunto restrito: memória associativa por conjuntos. A
associatividade é caracterizada por N, o número de elementos
de um conjunto [n-way set associative cache].
As implementações mais frequentes têm associatividade 1
(mapeamento directo), 2 ou 4.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 12/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Associatividade
c©JCF, 2004 — ASPD(FEUP/LEEC) Memórias cache 13/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Identificação de um bloco em cache
I A cada bloco está associada uma etiqueta (parte do endereço).
I As etiquetas de todas as posições possíveis são verificadas em
paralelo.
I Posições válidas são assinaladas por um bit de validade.
Estrutura de um endereço de memória:
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 14/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Estratégia de substituição
I Mapeamento directo—Não há escolha, já que um bloco
apenas pode residir numa posição.
I Para memórias associativas, a escolha do elemento do
conjunto a ser substituído por ser feita:
I aleatoriamente—a escolha é feita (pseudo-)aleatoriamente.
I least-recentely used (LRU)—Usa o passado para predizer o
futuro: o bloco não usado (acedido) há mais tempo é
substituído (corolário do princípio da proximidade).
I first-in, first-out (FIFO)—Aproximação a LRU: substituir o
bloco mais velho.
I A implementação de LRU é a mais complicada, pelo que se
usa frequentemente um método aproximado (principalmente
FIFO).
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 15/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Influência da estratégia de substituição no desempenho
Exemplo para cache de dados com blocos de 64 bytes (Alpha
21264).
Associatividade
2-way 4-way 8-way
Tam. LRU Aleat. FIFO LRU Aleat. FIFO LRU Aleat. FIFO
16 KB 114.1 117.3 115.5 111.7 115.1 113.3 109.0 111.8 110.1
64 KB 103.4 104.3 103.9 102.4 102.3 103.1 99.7 100.5 100.3
256 KB 92.2 92.1 92.5 92.1 92.1 92.5 92.1 92.1 92.5
Em falhas por milhar de instruções.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 16/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Estratégia de escrita (1/2)
I Leituras são muito mais numerosas que escritas (≈ 21% das
instruções que acedem à cache de dados).
I O ênfase é colocado na leitura, que é a operação mais fácil.
I Existem duas grandes estratégias de escrita:
1. write through—A informação é escrita simultaneamente
em cache e na memória do nível seguinte.
2. write back—A informação é escrita apenas em cache: o
bloco modificado é escrito em memória quando é
substituído.
I É usado um bit para indicar se o bloco em cache foi
modificado: dirty bit. Um bloco não modificado limpo não
precisa de ser escrito em memória aquando da substituição.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 17/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Estratégia de escrita (2/2)
I Vantagens de write back:
1. escritas à velocidade da cache;
2. múltiplas escrita no mesmo bloco requerem apenas um acesso
à memória (reduz consumo de largura de banda e de potência).
I Vantagens de write through:
1. memória cache sempre “limpa” (uma falha de leitura não
resulta em escritas na memória de nível seguinte);
2. o nível seguinte mantém a versão mais recente dos dados.
I Com write through, o CPU pode protelar à espera que uma escrita
termine (write stall)—usar um write buffer.
I Comportamento numa falha de escrita:
1. write allocate—um bloco é alocado para guardar o novo valor;
2. no-write allocate—Apenas a memória de nível seguinte é
actualizada; a cache não é afectada.
I write back + write allocate, write through + no-write allocate
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 18/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Examplo: Cache de dados do Alpha 21264
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 19/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Exemplo: Cache unificada vs. caches separadas
Tamanho (KB) Instruções Dados Unificada
8 8.16 44.0 63.0
16 3.82 40.9 51.0
32 1.36 38.4 43.3
64 0.61 36.9 39.4
128 0.30 35.3 36.2
256 0.02 32.6 32.9
Falhas por 1000 instruções; referências a instruções: 74%; 2-way; blocos
de 64 bytes.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 20/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Colocação e identificação
Actualização: substituição e escrita
Mais aspectos de desempenho de memória cache
I A taxa de falhas não constitui um bom índice de desempenho (o
número de instruções executadas também não).
I O tempo médio de acesso a memória tm é melhor:
tm = th + tf × pf
em que th é o tempo gasta em acesso à cache (h=hit).
I Para CPU com execução em ordem, tm é um bom índice de previsão
do desempenho. (Convenção: o tempo th é incluído no tempo de
execução de instruções.)
I Falhas de acesso têm um efeito duplo sobre o desempenho:
1. Quanto menor for o CPI (de execução), tanto maior é o
impacto relativo de um número fixo de ciclos de penalização
por falha.
2. Para duas hierarquias de memória idêntica, o CPU mais rápido
tem uma penalidade maior (em ciclos).
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 21/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Aumentar o número de níveis
I As equações de desempenho indicam que melhorias da
penalidade de falha são tão benéficas como melhorias da taxa
de falhas.
I A crescente diferença de desempenho entre memórias e CPU
leva a um aumento do custo relativo das penalidades.
I Técnica 1: Acrescentar níveis intermédios de memória cache.
I O tempo médio de acesso é: tm = th1 + tf 1× (th2 + tf 2× pf 2)
I taxa de falhas local—No de falhas a dividir pelo no de acessos.
I taxa de falhas global—No de falhas a dividir pelo no de
acessos gerados pelo CPU.
I Número médio de falhas por instrução é
fi = fi1 × th2 + fi2 × pf 2
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 22/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Medidas empíricas para caches multinível (1/2)
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 23/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Medidas empíricas para caches multinível (2/2)
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 24/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Leitura “inteligente” de blocos
I Técnica 2: Não esperar pela leitura do bloco completo antes
de satisfazer o pedido do CPU.
I Palavra crítica primeiro—Obter a palavra desejada de
memória e enviá-la para o CPU; posteriormente ler as
restantes palavras da linha.
I Early restart—Obter as palavras por ordem normal; assim que
a palavra pretendida estiver disponível, enviá-la para o CPU.
I Estas técnicas só trazem benefícios para memórias caches com
blocos compridos.
I Caso próxima leitura seja do mesmo bloco, pode ocorrer nova
falha.c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 25/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Conceder prioridade às operações de leitura
I Técnica 3: Dar prioridade às operações de leitura sobre as
operações de escrita.
I Para caches write-through, é importante a existência de um
write buffer; mas mesmo memórias write-back beneficiam da
sua existência.
I Contudo: write buffer pode conter valor de uma posição
necessária para satisfazer uma falha de leitura.
I Altenativas:
1. Falha de leitura só é satisfeita depois de o write buffer ser
esvaziado (→ protelamento).
2. O conteúdo do write buffer é verificado (em paralelo)
para se detectarem e resolverem eventuais colisões;
abordagem usada em quase todos os CPUs não
embutidos.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 26/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Combinação de operações de escrita
I Técnica 4: Combinar operações de escrita para posições
próximas.
I Quando o write buffer está cheio e é necessário proceder a
uma escrita, a memória cache (e o CPU) devem esperar que
surja uma vaga.
I Se o write buffer contiver blocos, verifica-se se o novo bloco é
contíguo a algum dos existentes, procedendo-se à sua
combinação (merging write buffer).
I Esta técnica aproveita o facto de ser frequentemente mais
rápido escrever dados “de rajada.”
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 27/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Combinação de escritas: exemplo
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 28/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Usar uma cache de “vítimas”
I Técnica 5: Manter os blocos “descartados.”
I Como os blocos descartados já foram lidos, podem ser
reutilizados a baixo custo.
I Requer uma pequena memória cache adicional,
completamente associativa.
I A cache de vítimas guarda apenas blocos descartados por
causa de falhas (as “vítimas”).
I Esta cache é verificada antes de se proceder ao acesso ao
próximo nível de memória.
I Exemplo: uma cache de vítimas com 4 posições pode evitar
25% das falhas de uma memória cache de dados de 4 KB,
direct-mapped.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 29/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Caches de vítimas: exemplo
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 30/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Classificação de falhas
I Falhas podem ser classificadas segundo os três C’s:
I compulsórias—O primeiro acesso a um bloco não pode
ter sucesso (falhas de arranque a frio).
I capacidade—Falhas causadas pela ausência de blocos que
já estiveram em cache mas foram retirados por falta de
espaço.
I conflito—São falhas causadas pela impossibilidade de
ocupação simultânea de uma posição ou conjunto (falhas
de colisão ou interferência).
I Falhas compulsórias ocorrem mesmo em caches infinitas.
I Falhas compulsórias e de capacidade ocorrem em caches
completamente associativas.
I Memórias associativas por conjuntos também têm falhas de
conflito.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 31/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Repartição de taxas de falhas por categoria (1/2)
Cache de 4 kB:
Assoc. Total Compulsórias Capacidade Conflito
(%) (%) (%)
1 0.098 0.0001 0.1 0.070 72 0.027 28
2 0.098 0.0001 0.1 0.070 93 0.005 7
4 0.098 0.0001 0.1 0.070 99 0.0001 1
8 0.098 0.0001 0.1 0.070 100 0.000 0
Cache de 512 kB:
Assoc. Total Compulsórias Capacidade Conflito
(%) (%) (%)
1 0.008 0.0001 0.8 0.005 66 0.003 33
2 0.007 0.0001 0.9 0.005 71 0.002 28
4 0.006 0.0001 1.1 0.005 91 0.000 8
8 0.006 0.0001 1.1 0.005 95 0.000 4
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 32/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Repartição de taxas de falhas por categoria (2/2)
Associatividade 1 :
Tam. (kB) Total Compulsórias Capacidade Conflito
(%) (%) (%)
4 0.098 0.0001 0.1 0.070 72 0.027 28
8 0.068 0.0001 0.1 0.044 65 0.024 35
16 0.049 0.0001 0.1 0.040 82 0.0009 17
32 0.042 0.0001 0.2 0.037 89 0.005 11
Associatividade 8:
Tam. (kB) Total Compulsórias Capacidade Conflito
(%) (%) (%)
4 0.071 0.0001 0.1 0.070 100 0.000 0
8 0.044 0.0001 0.1 0.044 100 0.000 0
16 0.041 0.0001 0.2 0.040 100 0.000 0
32 0.037 0.0001 0.2 0.037 100 0.000 0
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 33/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Aumentar a dimensão dos blocos
I A maneira mais simples de reduzir a taxa de falhas é
aumentar a dimensão dos blocos (aproveitamento da
proximidade espacial).
I Desvantagens:
I aumenta a penalidade de falhas;
I pode aumentar o número de falhas por conflito;
I pode aumentar as falhas de capacidade (em caches pequenas).
I A escolha da dimensão dos blocos também depende das
características do nível seguinte de memória: baixa latência →
blocos pequenos (p. ex.).
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 34/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Dimensão dos blocos: medidas empíricas
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 35/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Dimensão dos blocos vs. tempo de acesso
Tamanho da cache
Bloco (B) Penal. 4 kB 16 kB 64 kB 256 kB
16 82 8.027 4.231 2.673 1.894
32 84 7.082 3.411 2.134 1.588
64 88 7.160 3.323 1.933 1.449
128 96 8.469 3.659 1.979 1.470
256 112 11.651 4.685 2.288 1.549
I Técnica 2: Aumentar o tamanho da memória cache.
I Aumento de custo e de tempo de acesso.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 36/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Aumentar a associatividade
I Aumentar a associatividade melhora a taxa de falhas mas
aumenta o tempo médio de acesso.
I Regras empíricas:
1. Para efeitos práticos, associatividade 8 = infinito.
2. Uma memória direct mapped de tamanho N tem a
mesma taxa de falhas que uma memória de
associatividade 2 e de tamanho N/2.
Associatividade
Tamanho (kB) 1 2 4 8
4 3.44 3.24 3.22 3.28
8 2.69 2.582.55 2.62
16 2.23 2.40 2.46 2.53
32 2.06 2.30 2.37 2.45
64 1.92 2.14 2.18 2.25
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 37/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Predição de elemento do conjunto
I Objectivo: Reduzir no de falhas de conflito mas manter o
tempo de acesso de memórias direct mapped.
I Manter informação para predizer que elemento de um bloco
vai ser usado no próximo acesso.
I Quando a predição falha, é necessário verificar os outros
blocos do conjunto.
I Alpha 21264 [assoc 2 I-cache]: Cada bloco tem um bit a
indicar qual dos dois blocos (do conjunto que vier a ser
seleccionado) a usar no acesso seguinte. Predição correcta: 1
ciclo; incorrecta: 3 ciclos.
I Taxa de acertos: 85%.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 38/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Optimizações de software
I Técnica 5: Compilador modifica código para aproveitar melhor
as memórias cache. Exemplo: reordenação de subrotinas para
reduzir falhas de conflito [redução de 75% para cache de
8 kB].
Troca de ciclos
/* Pior */ /* Melhor */
for (j=0; j<100; j++) for (i=0; i<5000; i++)
for (i=0; i<5000; i++) for (j=0; j<100;j++)
x[i][j]=2*x[i][j]; x[i][j]=2*x[i][j];
Porquê?
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 39/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Exemplo: Multiplicação de matrizes (1/2)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
r = 0;
for (k=0; k < N; k++)
r = r + y[i][k] * z[k][j];
x[i][j] = r;
}
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 40/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Exemplo: Multiplicação de matrizes (2/2)
for (jj = 0; jj < N; jj=jj+B) /* x[][] a zero, bloco BxB */
for (kk = 0; kk < N; kk = kk+B)
for (i = 0; i < N; i++)
for (j = jj; j < min(jj+B, N); j++) {
r = 0;
for (k = kk; k < min(kk+B,N); k++)
r = r + y[i][k] * z[k][j];
x[i][j] = r;
}
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 41/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Acessos a memória sem protelamento
I Outra abordagem para aumentar o desempenho de sistemas
com caches consiste em sobrepor temporalmente a actividade
da hierarquia de memória e do CPU.
I Técnica 1: Usar uma memória que não protela nas falhas de
leitura (só interessa com execução fora de ordem).
I A memória continua a responder a pedidos que resultem em
acertos enquanto processa uma falha (hit under miss).
I Extensão: Suportar múltiplas falhas simultâneas; o interesse
desta abordagem depende da capacidade do nível seguinte da
hierarquia.
I Desvantagens:
1. Elevada complexidade de implementação.
2. Dificuldade de avaliação de desempenho.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 42/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Non-blocking caches: medidas empíricas
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 43/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Obtenção prévia de instruções e dados
I Técnica 2: A estratégia de obter um bloco antes de ele ser
necessário pode ser aplicada a instruções e dados.
I Os blocos colocados em cache ou num buffer externo.
I Blocos de instruções são geralmente tratados pelo processador
que obtém dois blocos quando existe uma falha. O bloco
pedido é enviado para a cache; o outro é guardado no
instruction stream buffer.
I Um ISB “apanha” cerca de 15%-25% das falhas de uma
cache DM, 4 kB, 16 B/bloco. Se o ISB tiver capacidade para
16 blocos, a taxa sobe para 72%.
I Para acessos a dados, um valor de 25% é típico (4 kB, DM).
I É possível ter múltiplos DSB a fazerem obtenção prévia de
dados de endereços diferentes: 42%.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 44/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Obtenção prévia controlada por software
I Técnica 3: O compilador inclui instruções de prefetch para
“pedir” dados antes de estes serem necessários.
I Register prefetch: carregar valor para um registo;
cache prefetch: carregar valor apenas para cache.
I Estas instruções são geralmente usadas com memórias cache
que não protelem nas falhas de leitura.
I Este técnica é particularmente efectiva no processamento de
ciclos.
I Desvantagem: Overhead de instruções; contudo, os benefícios
são geralmente superiores.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 45/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Redução do tamanho da cache
I O tempo de acesso à cache limita o ciclo de relógio da maioria
dos processadores.
I Técnica 1: Usar caches simples e pequenas.
I Preferir caches do tipo direct access.
I Preferir caches suficientemente pequenas para ficarem on-chip.
I Manter etiquetas de L2 on-chip.
I A dimensão das caches L1 tem vindo a manter-se constante
nas gerações mais recentes de processadores.
I Pentium III (I-cache): 16 k B; Pentium 4: 8 kB.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 46/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Tempo de acesso em caches CMOS: estimativas
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 47/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Evitar conversão de endereços na indexação
I Caches devem lidar com a conversão entre endereços virtuais
e físicos.
I Caches de endereços virtuais (caches virtuais) tornam mais
simples as leituras.
I Desvantagens de caches virtuais:
1. permissões—conversão virtual→real implica verificar
permissões; sol.: copiar informação de TLB.
2. gestão de processos—cada troca de contexto obriga a “limpar”
a cache; sol: incluir etiquetas de processo.
3. aliases—s.o. e programas podem referenciar a mesma posição
física por diferentes endereços virtuais (simultaneamente); sol:
verificar se não existem endereços físicos repetidos.
4. E/S—interacção com periféricos requer uso de endereços
físicos.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 48/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Taxa de falhas para endereços virtuais: medidas
c©JCF,2004 — ASPD (FEUP/LEEC) Memórias cache 49/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Caches com índices virtuais e endereços físicos
I Técnica 3: (solução de compromisso) Usar a parte comum a
endereços reais e virtuais (o deslocamento) para indexar a
cache; a comparação de endereços usa endereços reais
(entretando convertidos) para comparação de etiquetas.
I Limitação: Uma cache DM não pode ser maior que o
tamanho da página. (Porquê?)
I Solução: Aumentar a associatividade.
I Pentium III: páginas de 8 kB, com cache 2-way de 16 kB.
I IBM 3033 (cache): pág. de 4 kB, 64 kB de cache, 16-way.
Pipeline
I Técnica 3: Implementar acesso pipelined à cache; obter um
item demora vários ciclos (não reduz latência).
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 50/51
Índice
Conceitos básicos
Princípios de funcionamento
Técnicas de aumento de desempenho
Redução das penalidades de falha
Redução da taxa de falhas
Aumento da concorrência
Redução do tempo de acesso
Caches de rastos
I Técnica 4: A cache regista sequências dinâmicas de instruções
executadas, incluindo saltos tomados. (trace cache).
I Predição de saltos tem de ser incluída na cache.
I Desvantagens:
1. Complexidade: os endereços não estão alinhados em
potências de 2.
2. A mesma instrução pode estar em várias posições da
cache.
I Vantagem:
Melhor utilização da cache: blocos longos não desperdiçam
partes devido a saltos.
Exemplo: AMD Athlon pode ter 16–24 instruções num bloco
de 64 B; saltos com frequência de 1 em cada 5-10 instruções.
c©JCF, 2004 — ASPD (FEUP/LEEC) Memórias cache 51/51