Memórias cachejca/feup/aspd/slides/aspd-slides-memorg.pdf · ˝ndice Conceitos bÆsicos Princípios de funcionamento TØcnicas de aumento de desempenho Porque sªo efectivas as memórias

ÍndiceConceitos básicos

Princípios de funcionamentoTé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



Conceitos básicosPorque são efectivas as memórias cache?Hierarquias de memóriaCaracterização do desempenho

Princípios de funcionamentoColocação e identificaçãoActualização: substituição e escrita

Técnicas de aumento de desempenhoRedução das penalidades de falhaRedução da taxa de falhasAumento da concorrênciaRedução do tempo de acesso




Porque são efectivas as memórias cache?Hierarquias de memóriaCaracterização do desempenho

Princípio da proximidade

I Cache: Uma memória rápida que guarda as instruções/dadosusados mais recentemente.

I Princípio da proximidade: Programas tendem a re-utilizaros dados e as instruções usados recentemente ou maispróximos (90% do tempo em 10% das instruções?).Existem 2 tipos de proximidade:

1. proximidade temporal—elementos acedidos recentementetêm maior probabilidade de ser acedidos a seguir;

2. proximidade espacial—elementos colocados em posiçõesde memória próximas tendem a ser acedidos em instantesconsecutivos.

I Objectivo: Obter a rapidez de acesso da memória rápida e acapacidade da memória mais lenta.





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: cadanível tem menor capacidade, é mais rápido e mais caro(¤/bit) que o seguinte.

I Frequentemente cada nível está contido no seguinte (mas nemsempre).

I A hierarquia de memória também é responsável pelaverificação de endereços (já que tem de mapear endereços nosníveis correctos).

I A importância da hierarquia de memória tem aumentado comos avanços de CPU. (Porquê?)





Hierarquia de memória: situação típica

(No ano 2000.)





Desempenho de CPU vs. memória





Características da hierarquia de memória

Nível 1 2 3 4

Nome registos cache memóriaprincipal

memória demassa

Tamanhotípico

< 1 KB < 16 MB < 16 GB > 100 GB

Tecnologia memóriamulti-porto,CMOS

CMOS SRAM CMOSDRAM

discomagnético

Acesso (ns) 0.25–0.5 0.5–2.5 80–250 5 × 106

Largura debanda(MB/s)

2 × 103 –105

5000–10000 1000–5000 20–150

Gerido por compilador hardware OS OS/adminBackup cache memória principal memória de

massaCD/banda





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 elevadade que os outros dados do bloco sejam usados dentro de poucotempo.

I O tempo necessário para processar uma falha depende da latência eda largura de banda da memória.

I A latência determina o tempo necessário para obter o primeiroelemento do bloco.

I A largura de banda determina o tempo necessário para obter(transferir) o resto do bloco.





Aspectos elementares de desempenho

I Tempo de execução (CPU): tI Ciclos de relógio (CPU): nc

I Período de relógio: T = 1/fI 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 (emciclos): 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





Aspectos elementares de desempenho (cont.)

Os elementos da última equação podem ser medidos com relativafacilidade.Taxas de falhas podem ser avaliadas por simulação usando umaddress trace (listagem dos endereços ordenados por ordemtemporal de acessos). [Não é constante. . . ] Uma alternativa:contadores embutidos no CPU.Assume-se que taxas de falhas e penalidade de acesso são iguaispara leituras e escritas; uma equação mais detalhada devedistinguir 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.




Colocação e identificaçãoActualização: substituição e escrita

Quatro questões sobre hierarquias de memória

As questões mais importantes sobre um nível da hierarquia dememó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 umafalha? [substituição]

4. O que acontece durante a escrita? [estratégia de escrita]





Localização dos dados

A localização dos dados em cache permite distinguir 3 categoriasde 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óriatotalmente associativa.

3. Um bloco pode ser colocado em qualquer posição de numconjunto restrito: memória associativa por conjuntos. Aassociatividade é caracterizada por N, o número de elementosde um conjunto [n-way set associative cache].

As implementações mais frequentes têm associatividade 1(mapeamento directo), 2 ou 4.





Associatividade





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 emparalelo.

I Posições válidas são assinaladas por um bit de validade.

Estrutura de um endereço de memória:





Estratégia de substituição

I Mapeamento directo—Não há escolha, já que um blocoapenas pode residir numa posição.

I Para memórias associativas, a escolha do elemento doconjunto 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 obloco mais velho.

I A implementação de LRU é a mais complicada, pelo que seusa frequentemente um método aproximado (principalmenteFIFO).





Influência da estratégia de substituição no desempenho

Exemplo para cache de dados com blocos de 64 bytes (Alpha21264).

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.164 KB 103.4 104.3 103.9 102.4 102.3 103.1 99.7 100.5 100.3256 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.





Estratégia de escrita (1/2)

I Leituras são muito mais numerosas que escritas (≈ 21% dasinstruçõ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 foimodificado: dirty bit. Um bloco não modificado limpo nãoprecisa de ser escrito em memória aquando da substituição.





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ãoresulta 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





Examplo: Cache de dados do Alpha 21264





Exemplo: Cache unificada vs. caches separadas

Tamanho (KB) Instruções Dados Unificada

8 8.16 44.0 63.016 3.82 40.9 51.032 1.36 38.4 43.364 0.61 36.9 39.4128 0.30 35.3 36.2256 0.02 32.6 32.9

Falhas por 1000 instruções; referências a instruções: 74%; 2-way; blocosde 64 bytes.





Mais aspectos de desempenho de memória cache

I A taxa de falhas não constitui um bom índice de desempenho (onú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 deexecuçã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çãopor falha.

2. Para duas hierarquias de memória idêntica, o CPU mais rápidotem uma penalidade maior (em ciclos).




Redução das penalidades de falhaRedução da taxa de falhasAumento da concorrênciaRedução do tempo de acesso

Aumentar o número de níveis

I As equações de desempenho indicam que melhorias dapenalidade de falha são tão benéficas como melhorias da taxade falhas.

I A crescente diferença de desempenho entre memórias e CPUleva 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 deacessos gerados pelo CPU.

I Número médio de falhas por instrução éfi = fi1 × th2 + fi2 × pf 2





Medidas empíricas para caches multinível (1/2)





Medidas empíricas para caches multinível (2/2)





Leitura “inteligente” de blocos

I Técnica 2: Não esperar pela leitura do bloco completo antesde satisfazer o pedido do CPU.

I Palavra crítica primeiro—Obter a palavra desejada dememória e enviá-la para o CPU; posteriormente ler asrestantes palavras da linha.

I Early restart—Obter as palavras por ordem normal; assim quea palavra pretendida estiver disponível, enviá-la para o CPU.

I Estas técnicas só trazem benefícios para memórias caches comblocos compridos.

I Caso próxima leitura seja do mesmo bloco, pode ocorrer novafalha.





Conceder prioridade às operações de leitura

I Técnica 3: Dar prioridade às operações de leitura sobre asoperações de escrita.

I Para caches write-through, é importante a existência de umwrite buffer; mas mesmo memórias write-back beneficiam dasua existência.

I Contudo: write buffer pode conter valor de uma posiçãonecessá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ãoembutidos.





Combinação de operações de escrita

I Técnica 4: Combinar operações de escrita para posiçõespróximas.

I Quando o write buffer está cheio e é necessário proceder auma escrita, a memória cache (e o CPU) devem esperar quesurja uma vaga.

I Se o write buffer contiver blocos, verifica-se se o novo bloco écontíguo a algum dos existentes, procedendo-se à suacombinação (merging write buffer).

I Esta técnica aproveita o facto de ser frequentemente maisrápido escrever dados “de rajada.”





Combinação de escritas: exemplo





Usar uma cache de “vítimas”

I Técnica 5: Manter os blocos “descartados.”

I Como os blocos descartados já foram lidos, podem serreutilizados a baixo custo.

I Requer uma pequena memória cache adicional,completamente associativa.

I A cache de vítimas guarda apenas blocos descartados porcausa de falhas (as “vítimas”).

I Esta cache é verificada antes de se proceder ao acesso aopróximo nível de memória.

I Exemplo: uma cache de vítimas com 4 posições pode evitar25% das falhas de uma memória cache de dados de 4 KB,direct-mapped.





Caches de vítimas: exemplo





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 deespaço.

I conflito—São falhas causadas pela impossibilidade deocupação simultânea de uma posição ou conjunto (falhasde 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.





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 282 0.098 0.0001 0.1 0.070 93 0.005 74 0.098 0.0001 0.1 0.070 99 0.0001 18 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 332 0.007 0.0001 0.9 0.005 71 0.002 284 0.006 0.0001 1.1 0.005 91 0.000 88 0.006 0.0001 1.1 0.005 95 0.000 4





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 288 0.068 0.0001 0.1 0.044 65 0.024 3516 0.049 0.0001 0.1 0.040 82 0.0009 1732 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 08 0.044 0.0001 0.1 0.044 100 0.000 016 0.041 0.0001 0.2 0.040 100 0.000 032 0.037 0.0001 0.2 0.037 100 0.000 0





Aumentar a dimensão dos blocos

I A maneira mais simples de reduzir a taxa de falhas éaumentar a dimensão dos blocos (aproveitamento daproximidade 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 dascaracterísticas do nível seguinte de memória: baixa latência →

blocos pequenos (p. ex.).





Dimensão dos blocos: medidas empíricas





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.89432 84 7.082 3.411 2.134 1.58864 88 7.160 3.323 1.933 1.449128 96 8.469 3.659 1.979 1.470256 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.





Aumentar a associatividade

I Aumentar a associatividade melhora a taxa de falhas masaumenta 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 deassociatividade 2 e de tamanho N/2.

AssociatividadeTamanho (kB) 1 2 4 8

4 3.44 3.24 3.22 3.288 2.69 2.58 2.55 2.6216 2.23 2.40 2.46 2.5332 2.06 2.30 2.37 2.4564 1.92 2.14 2.18 2.25





Predição de elemento do conjunto

I Objectivo: Reduzir no de falhas de conflito mas manter otempo de acesso de memórias direct mapped.

I Manter informação para predizer que elemento de um blocovai ser usado no próximo acesso.

I Quando a predição falha, é necessário verificar os outrosblocos do conjunto.

I Alpha 21264 [assoc 2 I-cache]: Cada bloco tem um bit aindicar qual dos dois blocos (do conjunto que vier a serseleccionado) a usar no acesso seguinte. Predição correcta: 1ciclo; incorrecta: 3 ciclos.

I Taxa de acertos: 85%.





Optimizações de software

I Técnica 5: Compilador modifica código para aproveitar melhoras memórias cache. Exemplo: reordenação de subrotinas parareduzir falhas de conflito [redução de 75% para cache de8 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ê?





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;

}





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;

}





Acessos a memória sem protelamento

I Outra abordagem para aumentar o desempenho de sistemascom caches consiste em sobrepor temporalmente a actividadeda hierarquia de memória e do CPU.

I Técnica 1: Usar uma memória que não protela nas falhas deleitura (só interessa com execução fora de ordem).

I A memória continua a responder a pedidos que resultem emacertos enquanto processa uma falha (hit under miss).

I Extensão: Suportar múltiplas falhas simultâneas; o interessedesta abordagem depende da capacidade do nível seguinte dahierarquia.

I Desvantagens:1. Elevada complexidade de implementação.2. Dificuldade de avaliação de desempenho.





Non-blocking caches: medidas empíricas





Obtenção prévia de instruções e dados

I Técnica 2: A estratégia de obter um bloco antes de ele sernecessá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 blocopedido é enviado para a cache; o outro é guardado noinstruction stream buffer.

I Um ISB “apanha” cerca de 15%-25% das falhas de umacache DM, 4 kB, 16 B/bloco. Se o ISB tiver capacidade para16 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%.





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 cacheque não protelem nas falhas de leitura.

I Este técnica é particularmente efectiva no processamento deciclos.

I Desvantagem: Overhead de instruções; contudo, os benefíciossão geralmente superiores.





Redução do tamanho da cache

I O tempo de acesso à cache limita o ciclo de relógio da maioriados 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 constantenas gerações mais recentes de processadores.

I Pentium III (I-cache): 16 k B; Pentium 4: 8 kB.





Tempo de acesso em caches CMOS: estimativas





Evitar conversão de endereços na indexação

I Caches devem lidar com a conversão entre endereços virtuaise físicos.

I Caches de endereços virtuais (caches virtuais) tornam maissimples 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çosfísicos.





Taxa de falhas para endereços virtuais: medidas





Caches com índices virtuais e endereços físicos

I Técnica 3: (solução de compromisso) Usar a parte comum aendereços reais e virtuais (o deslocamento) para indexar acache; 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 otamanho 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 umitem demora vários ciclos (não reduz latência).





Caches de rastos

I Técnica 4: A cache regista sequências dinâmicas de instruçõesexecutadas, 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çampartes devido a saltos.Exemplo: AMD Athlon pode ter 16–24 instruções num blocode 64 B; saltos com frequência de 1 em cada 5-10 instruções.


Documents

Memórias cachejca/feup/aspd/slides/aspd-slides-memorg.pdf · ˝ndice Conceitos bÆsicos Princípios de funcionamento TØcnicas de aumento de desempenho Porque sªo efectivas as memórias