Tema 4 - Parte 2 - Oimizações em caches

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 4: Parte 2
Memória cache: Otimizações
Prof. Marcelo Schiavon porto
porto@inf.ufpel.edu.br
Memória Cache
2 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Desempenho das caches
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
Tempo de 
processador
=
Ciclos de relógio 
gastos na execução 
normal do programa
+
Tempo do ciclo 
de relógio
x
Memória Cache
3 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Redução da taxa de faltas (miss rate)
– Redução da penalidade da falta (miss penalty)
– Redução do tempo do acerto (hit time)
Memória Cache
4 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Otimização 1: Aumento do tamanho do
bloco para reduzir a taxa de falta
– Ajuda também na redução de faltas
compulsórias
– Explora o princípio da localidade espacial
Memória Cache
5 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Otimização 1: Aumento do tamanho do
bloco para reduzir a taxa de falta
– Desvantagens?
Memória Cache
6 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Índice val. tag informação
0
1
2
…
…
…
…
253
254
255
desl
endereço
31 32 …. 13 12 11 …. 2 1 0
8
=
22
20
acerto
32
informação
Cache mapeada diretamente com blocos maiores
2
Memória Cache
7 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Cache mapeada diretamente com blocos maiores
Como encontrar o bloco de um dado endereço?
(Endereço do bloco) módulo (Número de blocos da cache) 
Memória Cache
8 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Cache mapeada diretamente com blocos maiores
Exemplo:
(Endereço do bloco) módulo (Número de blocos da cache) 
Considere uma cache de 32 blocos de 16 bytes cada.
Em qual bloco desta cache o endereço 1200 será
mapeado?
(1200/16) = 75 -> Endereço do bloco
(75) módulo (32) = 11 -> Bloco onde será armazenado na cache
Memória Cache
9 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
Memória Cache
10 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
Taxa de miss em relação ao tamanho da cache e tamanho do bloco
Memória Cache
11 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
Tempo médio de acesso em relação ao tamanho da cache e tamanho do bloco
Memória Cache
12 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Em geral, uma linha maior aproveita melhor a
localidade espacial MAS
– Linha maior significa maior miss penalty, pois demora
mais tempo para preencher a linha
– Se o tamanho da linha é grande demais em relação ao
tamanho da cache, miss ratio vai aumentar
• Muito poucas linhas
Tamanho da linha vs. taxa de 
miss e miss penalty
Memória Cache
13 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Tamanho da linha vs. taxa de 
miss e miss penalty
Memória Cache
14 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Otimização 2: Caches maiores para reduzir a
taxa de falta
– Otimização óbvia, com o aumento do tamanho
da cache são reduzidas as faltas por conflito (no
caso de caches associativas) e capacidade
– Desvantagens?
Memória Cache
15 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Otimização 3: Aumento da associatividade
para reduzir a taxa de faltas
– Redução das faltas por conflitos
– Regra do 2:1:
• Uma cache mapeada diretamente de tamanho N, tem
a mesma taxa de faltas de uma cache associativa de 2
vias com tamanho N/2
Memória Cache
16 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 3: Aumento da associatividade para
reduzir a taxa de faltas
• Desvantagens?
Memória Cache
17 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
Tempo médio de acesso em relação ao tamanho da cache e nível de associatividade
Memória Cache
18 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 4: Redução da taxa de faltas através
de prefetching de instruções e dados
• Prefetching em hardware
– Carregamento de dados adicionais em caso de falta
– Necessita de um aumento na largura de banda do sistema
• Prefetching em software
– Uma forma de execução especulativa
– O prefetching tem custo, deve ser avaliado o ganho na
redução da taxa de faltas em relação ao custo adicional
Memória Cache
19 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 5: Redução da taxa de faltas através
de otimizações no compilador
• Merging Arrays: melhorar a localidade espacial
através de arrays de structs, ao invés de N arrays
separados
• Loop Interchange: mudar os loops para acessar os
dados na ordem em que estão armazenados
• Loop Fusion: combinar loops que possuem as
mesmas características de controle
Memória Cache
20 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Otimização 5: Redução da taxa de faltas através de otimizações no
compilador
• Merging Arrays: melhorar a localidade espacial através de arrays de
structs, ao invés de N arrays separados
Memória Cache
21 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Desempenho das caches
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
Tempo de 
processador
=
Ciclos de relógio 
gastos na execução 
normal do programa
+
Tempo do ciclo 
de relógio
x
Memória Cache
22 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 6: Prioridade para faltas de leitura
em relação a escritas para reduzir a penalidade
da falta
• Considerando cache write-through a melhoria mais
importante é o tamanho do buffer de escrita bem
dimensionado
• O bufferpode causar conflito, pois pode estar com o
dado atualizado no caso de uma leitura
Memória Cache
23 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 6: Prioridade para faltas de leitura
em relação a escritas para reduzir a penalidade
da falta
• Esperar o buffer escrever na memória pode demorar
muito
– Alternativa: Verificar o buffer em caso de uma falta de
leitura, interrompendo a escrita
• Em caches write-back, caso uma perda de leitura
substitua um bloco sujo:
– Escrever o bloco sujo no buffer, ler a memória e depois
escrever o bloco do buffer na memória
Memória Cache
24 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Desempenho das caches
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
Tempo de 
processador
=
Ciclos de relógio 
gastos na execução 
normal do programa
+
Tempo do ciclo 
de relógio
x
Memória Cache
25 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
• A cache de primeiro nível pode ser pequena, e rápida
o suficiente para trabalhar no tempo de ciclo de clock
do processador
• A cache de segundo nível deve ser grande (muito
maior que a de primeiro nível) para capturar a maior
parte dos acessos a memória principal, reduzindo a
penalidade da falta
Memória Cache
26 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
• Existe melhora na performance do sistema com a
inserção de uma cache de segundo nível?
Memória Cache
27 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
• Exemplo 1: Dado um processador com CPI básica de 1,0,
admitindo que todas as referências a cache primária resultam
em acerto. O clock deste processador é de 500 MHz, e está
ligado a uma memória principal cujo tempo de acesso é de
200 ns, incluindo o tratamento das faltas. A taxa de faltas da
cache primária é de 5%.
– Calcule a melhora obtida no desempenho desta máquina ao
adicionarmos uma cache de segundo nível, com tempo de acesso de
20ns, tanto para acertos quanto para faltas, e taxa de faltas de 2%.
Memória Cache
28 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
• Exemplo: Solução
• Penalidade por falta com um nível de cache:
200 ns = 100 ns
2 ns
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
Tempo de 
processador
=
Ciclos de relógio 
gastos na execução 
normal do programa
+
Tempo do ciclo 
de relógio
x
Memória Cache
29 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Exemplo: Solução
• Penalidade por falta com um nível de cache:
200 ns = 100 ciclos
2 ns
• Tempo de processador com um nível de cache:
Tempo de Proc. = (CPI + 5% * 100) TC = 1 + 5 = 6,0 * TC
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
Tempo de 
processador
=
Ciclos de relógio 
gastos na execução 
normal do programa
+
Tempo do ciclo 
de relógio
x
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Memória Cache
30 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Exemplo: Solução
• Penalidade por falta da cache de segundo nível:
20 ns = 10 ciclos
2 ns
• Tempo de processador com dois níveis de cache:
Tempo de Proc. = (CPI + Paradas devidas à cache primária
+ Paradas devido à cache secundária) * TC
Tempo de Proc. = 1 + (5% * 10 + 2% * 100) = 3,5 * TC
• Diferença de desempenho: 6,0/3,5 = 1,7
Memória Cache
31 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
Tempo médio de acesso a memória = Tempo de acertoL1 + Taxa de faltaL1 * Penalidade de faltaL1
Penalidade de perdaL1 = Tempo de acertoL2 + Taxa de faltaL2 * Penalidade de faltaL2
Memória Cache
32 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
– Otimização 7: Caches multiníveis para reduzir a
penalidade da falta
• Taxa de perda local
– Medida pelo número de faltas dividido pelo número total
de acessos a memória para esta cache
• Taxa de perda global
– Medida pelo número de faltas dividido pelo número total
de acessos a memória gerados pelo processador
Memória Cache
33 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Exemplo 2: Suponha que, em 1000 referências à memória,
existam 40 faltas no cache de primeiro nível e 20 faltas no
cache de segundo nível. Quais são as diversas taxas de
falta? Considere que a penalidade da falta na cache L2 para
a memória seja de 200 ciclos de clock, o tempo de acerto do
cache L2 seja de 10 ciclos, o tempo de acerto do L1 seja de
1 ciclo e exista 1,5 referências de memória por instrução.
Qual é o tempo médio de acesso a memória e a média de
ciclos parados por acesso a memória de instrução?
Memória Cache
34 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Exemplo 2: Solução
• Taxa de falta(local e global) L1:
40/1000 = 4%
• Taxa de falta local L2:
20/40 = 50%
• Taxa de falta global L2:
20/1000 = 2%
Memória Cache
35 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Otimizações básicas em caches
• Exemplo 2: Solução
Tempo médio de acesso a memória = 1 + 4% * (10 + 50% x 200)
= 1 + 4% x 110 = 5,4 ciclos de clock
Tempo médio de acesso a memória = Tempo de acertoL1 + Taxa de faltaL1 * Penalidade de faltaL1
Penalidade de perdaL1 = Tempo de acertoL2 + Taxa de faltaL2 * Penalidade de faltaL2
Memória Cache
36 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• Bibliografia:
– PATTERSON, David A.; HENESSY, John L. Organização e
Projeto de Computadores: a interface hardware/software. 2a.ed.
Rio de Janeiro: Campus, 2005.
– HENNESSY, John L.; PATTERSON, David A. Computer
Architecture: A Quantitative Approach. San Francisco,
California: Morgan Kaufmann Publishers, 1996.