Tema 4 - Parte 1 - Medidas de desempenho de 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
Prof. Marcelo Schiavon porto
porto@inf.ufpel.edu.br
Tema 4: Parte 1
Memória cache: Medidas de desempenho
Memória cache
2 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
• O tempo de processador pode ser dividido entre os
ciclos gastos para a execução das instruções e o
tempo gasto à espera da resposta da memória
• Em geral, consideramos que o custo do acesso à
cache, que resulta em hit, faz parte do tempo
normal de execução do processador
Medidas do Desempenho da Cache
Memória cache
3 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Supondo um modelo simplificado de sistema de memória:
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
Inclui os acessos à cache 
que resultam em acerto
Devem-se às faltas 
na cache
Ciclos de relógio gastos à 
espera do acesso ao 
sistema de memória
=
Ciclos de relógio 
para tratar faltas de 
leitura na cache
+
Ciclos de relógio 
para tratar faltas de 
escrita na cache
Memória cache
4 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
=
Ciclos de relógio para tratar 
faltas de leitura na cache
x
Leituras
Programa
Taxa de faltas 
de leitura
x
Penalidade da 
falta de leitura
Nas leituras:
Nas escritas (considerando write-through):
=
Ciclos de relógio 
para tratar faltas de 
escrita na cache
x
Escritas
Programa
Taxa de faltas 
de escrita
x
Penalidade da 
falta de escrita
+
Ciclos parados 
devido ao buffer
Memória cache
5 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
=
Ciclos de relógio para tratar 
faltas de leitura na cache
x
Leituras
Programa
Taxa de faltas 
de leitura
x
Penalidade da 
falta de leitura
Nas leituras:
Nas escritas (considerando write-through):
=
Ciclos de relógio 
para tratar faltas de 
escrita na cache
x
Escritas
Programa
Taxa de faltas 
de escrita
x
Penalidade da 
falta de escrita
+
Ciclos parados 
devido ao buffer
Se o buffer estiver 
bem dimensionado
Memória cache
6 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Então, combinando as duas equações anteriores, vem:
Memória cache
7 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Exemplo:
Na execução do programa gcc, suponha que a taxa de faltas devidas a
instruções seja de 2% e que a taxa de faltas devidas a dados seja de
4%. Se a máquina tem CPI de 2,0, sem qualquer parada, e a
penalidade por faltas é de 40 ciclos de relógio, para qualquer das
faltas, determine quanto a máquina vai rodar mais rápido se a
equiparmos com uma cache perfeita, que nunca gere faltas.
• Considerando as frequências de instruções do gcc, apresentadas no
capítulo 4, Figura 5.54 do livro Organização e Projeto de
Computadores: a interface hardware/software.
Memória cache
8 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Ciclos devido a faltas de instruções = I x 2% x 40 = 0,80 I
Solução:
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Memória cache
9 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
A frequência de loads e stores no gcc é de 36%. Assim, o
número de faltas devidas a referência a dados será:
Ciclos devido a faltas de instruções = I x 2% x 40 = 0,80 I
Solução:
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Memória cache
10 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
A frequência de loads e stores no gcc é de 36%. Assim, o
número de faltas devidas a referência a dados será:
Ciclos devido a faltas de instruções = I x 2% x 40 = 0,80 I
Ciclos devido a faltas de dados = I x 36% x 4% x 40 = 0,56 I
Solução:
=
Ciclos de relógio para tratar 
faltas na cache
x
Acessos à memória
Programa
Taxa de faltas x
Penalidade 
por faltas
Memória cache
11 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução:
O número total de ciclos de relógio referentes à memória parada
é de:
0,80 I + 0,56 I = 1,36 I
Memória cache
12 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução:
O número total de ciclos de relógio referentes à memória parada
é de:
0,80 I + 0,56 I = 1,36 I
Isto significa que estamos gastando mais de um ciclo de relógio
por instrução, devido às faltas geradas na cache. Por este
motivo, a CPI com as paradas devidas às faltas na cache é de:
2,0 + 1,36 = 3,36
Memória cache
13 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Continuação da solução:
Considerando que tanto o número de instruções executadas
quanto o ciclo de relógio não mudam quando consideramos a
cache sem faltas, podemos calcular a razão dos tempos de
execução:
Tempo do processador 
com paradas
Tempo do processador 
com cache perfeita
I x CPI paradas
I x CPI perfeitas
X ciclo de relógio
= =
X ciclo de relógio
I x CPI paradas
I x CPI perfeitas
=
3,36
2
= 1,68 vezes mais rápida
Memória cache
14 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Considerando a mesma máquina, agora sem cache.
Ciclos devido a faltas de instruções = 40
Ciclos devido a faltas de dados = 40 x 36% = 14,4
Memória cache
15 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Considerando a mesma máquina, agora sem cache.
Ciclos devido a faltas de instruções = 40
Ciclos devido a faltas de dados = 40 x 36% = 14,4
CPI sem hierarquia de memória = 2 + (40 + 14,4) = 56,4 
A máquina que utiliza cache com perdas é quase 17
vezes mais rápida que a máquina sem hierarquia de
memória!
Memória cache
16 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
O que acontece se o processador for mais rápido, mas
o sistema de memória permanecer o mesmo?
Memória cache
17 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
O que acontece se o processador for mais rápido, mas
o sistema de memória permanecer o mesmo?
O montante de tempo gasto com as paradas da
memória vai corresponder a uma fração crescente do
tempo de execução.
Memória cache
18 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Considerando a máquina do exemplo anterior, mas
com um CPI de 1,0, sendo que este ganho ocorreu com
apenas com uma melhoria no pipeline.
CPI com falta da cache = 1,0 + 1,36 = 2,36
A cache perfeita é:
2,36
1
= 2,36 vezes mais rápida
Memória cache
19 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
O montante de tempo gasto com as paradas da
memória sobe de:
Para:
1,36
3,36
= 41%
1,36
2,36
= 58%
Memória cache
20 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Performance com Taxa de Clock Maior
Exemplo:
Supondo que a performace da máquina do exemplo
anterior tenha melhorado, em função da velocidade do
clock ter dobrado. Supondo também que o tempo
absoluto para o tratamento de uma falta não tenha
mudado. Qual foi o aumento real de desempenho desta
máquina com o novo clock?
Memória cache21 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Performance com Taxa de Clock Maior
Solução:
Penalidade da falta anterior = 40 ciclos
Penalidade da falta novo clock = ?
• 40 * 1/T = N * 1/(T/2)
• 80 ciclos
Taxa de faltas devido a instruções e dados:
Taxa Int./Dados = (2% * 80) + 36% * 4% *80 = 2,75
Memória cache
22 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Performance com Taxa de Clock Maior
Solução:
A nova máquina, considerando faltas na cache, terá uma CPI de:
CPI nova máquina = 2 + 2,75 = 4,75
O aumento real de desempenho da nova máquina será:
Performance com 
clock rápido
=
Performance com 
clock lento
Tempo de execução 
com clock lento
Tempo de execução 
com clock rápido
I * CPI * (Ciclo de Clock)/2
=
I * CPI * Ciclo de Clock
Memória cache
23 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Performance com Taxa de Clock Maior
Solução:
O aumento real de desempenho da nova máquina será:
A CPI da máquina original é de 3,36.
I * CPI * (Ciclo de Clock)/2
=
I * CPI * Ciclo de Clock
4,75 * 0,5
3,36 * 1
= 1,41
Memória cache
24 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Performance com Taxa de Clock Maior
Solução:
Portanto, o aumento em 2 vezes na velocidade do clock da
máquina resultou em um aumento real da performance de
apenas 1,41 vezes.
Isto ocorre devido ao aumento do efeito do tempo de tratamento
das faltas na cache, em relação ao tempo de processamento das
instruções.
Memória cache
25 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache
•A penalidade relativa da falta aumenta na proporção
em que a máquina se torna mais rápida
•Se a máquina melhorar, tanto no CPI quanto na
velocidade do clock:
•Quanto menor o CPI, maior o impacto causado pelos
ciclos relativos à memória parada
•Uma taxa de clock maior leva a uma penalidade de falta
maior (considerando memórias iguais)
Memória cache
26 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache
•Até agora, não consideramos o custo para um acesso
à cache que resulta em acerto
•No entanto, já discutimos que o tempo de acerto em
uma cache pode aumentar de acordo com:
• Tamanho da cache
• Nível de associatividade
Memória cache
27 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Tempo médio de acesso a memória
•É uma medida de desempenho mais eficiente para o
desempenho da hierarquia de memória
Tempo médio de acesso a memória = Tempo de acerto + Taxa de perda * Penalidade de perda
•Onde, “Tempo de acerto” é o tempo necessário para 
acessar a cache em um acerto (hit)
• Pode ser medido em tempo absoluto ou em número de ciclos 
de clock
Memória cache
28 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Exemplo 1: Aumentando o tamanho da cache:
Supondo uma máquina com dois tamanhos de cache, 16kB e 64kB.
Ao aumentarmos o tamanho da cache a taxa de faltas cai de 3% para
2%. A máquina com a cache maior apresenta um tempo de ciclo de
clock de 2 ns, enquanto a menor 1,6 ns, e ambas utilizam CPI de 1
ciclo. Se a penalidade de falta para acesso a uma cache secundária é
de 20 ns, e considerando 1,5 referência a memória por instrução,
determine:
a) O número de ciclos parados por memória para cada cache
b) O tempo de processador para cada tamanho de cache
c) O tempo médio de acesso a memória para cada tamanho de cache
Memória cache
29 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução Exemplo 1 a):
Cache menor:
Ciclos parados por memória = I * (3% * 1,5) * 20/1,6 = 0,56
Cache maior:
Ciclos parados por memória = I * (2% * 1,5) * 20/2 = 0,3
=
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
Medidas do Desempenho da Cache
Solução Exemplo 1 b):
Cache menor:
Tempo de processador = I * (CPI + 0,56) * 1,6 = 1,56 * 1,6 = 2,496 I
Cache maior:
Tempo de processador = I * (CPI + 0,3) * 2,0 = 1,3 * 2 = 2,6 I 
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
31 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução Exemplo 1 c):
Cache menor:
Tempo médio de acesso a memória = 1,6 + 0,03 * 20 = 2,2ns
Cache maior:
Tempo médio de acesso a memória = 2 + 0,02 * 20 = 2,4ns
Tempo médio de acesso a memória = Tempo de acerto + Taxa de perda * Penalidade de perda
Memória cache
32 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Exemplo 2: Caches com diferentes níveis de
associatividade
Dado um processador que, com uma cache perfeita, tem CPI de 1,6 e ciclo
de clock de 0,35ns, onde existem 1,4 referências a memória por instrução.
Considerando duas configurações de cache, uma com mapeamento direto (ou
de uma via) e taxa de falta de 2,1% e outra com mapeamento associativo por
conjunto de 2 vias com taxa de falta de 1,9%. Para a cache associativa, o
clock deve ser “esticado” 1,35 vezes, devido ao tempo do multiplexador. A
penalidade de falta para as duas caches é de 65ns. Calcule o tempo médio de
acesso a memória e o desempenho do processador, considerando que o
tempo de acerto é de 1 ciclo de clock.
Memória cache
33 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução Exemplo 2:
Cache com mapeamento direto:
Tempo médio de acesso a memória1 via = 0,35 + 0,021 * 65 = 1,72 ns
Cache com mapeamento associativo:
Tempo médio de acesso a memória2 vias = 0,35 * 1,35 + 0,019 * 65 = 1,71 ns
Tempo médio de acesso a memória = Tempo de acerto + Taxa de perda * Penalidade de perda
Memória cache
34 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução Exemplo 2:
Cache com mapeamento direto:
Tempo de processador = I * (CPI + 0,021 * 1,4 * (65/0,35)) * tempo ciclo1 via)
= (1,6 + 5,46) * 0,35 = 2,47 I
Cache com mapeamento associativo:
Tempo de processador = I * (CPI + 0,019 * 1,4 * (65/0,35 * 1,35) * tempo ciclo2
= (1,6 + 3,66) * 0,35 * 1,35 = 2,49 I
Memória cache
35 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Medidas do Desempenho da Cache
Solução Exemplo 2:
Diferença de desempenho do exemplo:
Tempo de processador1 via = 2,49 = 1,01
Tempo de processador2 vias 2,47
Memória cache
36 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
•Caches unificadas (ou mistas) são aquelas que
armazenam tanto dados quanto instruções
• Caches unificadas podem se tornar um gargalo do
sistema
•Um processador em pipeline pode solicitar uma palavra de
instrução e uma de dados ao mesmo tempo
• Solução lógica, dividir a cache em duas, uma para dados e
outra para instruções
Memória cache
37 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
•Caches separadas são encontradas na maioria dos
processadores atuais
•Possibilitam a otimização de cada cache em separado
•Evitam conflitos entre dados e instruções
•Problema:
• Limitam o tamanho individual de cada cache
•O que é melhor para a taxa de perda?
Memória cache
38 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
•Uma comparação justa requer caches de mesmo
tamanho
•Duas caches de 16kB separadas e uma unificada de 32kB,
por exemplo
• A taxa de falta também é influenciada pelo percentual de
referências feito a cada memória
• Podemos assumir que:
• 74% de referências à instruções
• 26% de referências àdados
Memória cache
39 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
• Acessos na cache unificada: 1000 instruções
Cache de dados e instruções
Processador
1000 acessos 
para instruções
% de loads e 
stores para 
acessos à dados
Memória cache
40 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
• Acessos na cache unificada: 1000 instruções
Cache de dados e instruções
Processador
Supondo 36% de 
loads e stores 1360 acessos 
à cache
74% Instruções 
26% dados
Taxa de faltas 
única
Memória cache
41 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
• Acessos nas caches separada: 1000 instruções
Cache de 
instruções
Cache de 
dados
Processador
% de 
loads e 
stores
1000 
acessos
Memória cache
42 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
• Acessos nas caches separada: 1000 instruções
Cache de 
instruções
Cache de 
dados
Processador
360 
acessos
1000 
acessos
Supondo 36% de 
loads e stores 1360 acessos 
à cache
Memória cache
43 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Caches unificadas vs. Caches separadas
• Taxa de faltas para 1000 instruções em caches associativas por
conjunto de 2 vias, com blocos de 64kB
Memória cache
44 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Exemplo 3: Cache unificada vs. Cache separada
Considerando uma cache unificada de 32kB e duas caches separadas
de 16kB, uma para dados e outra para instruções. Considerando que a
taxa de faltas para 1000 instruções é de 3,82 para instruções e 40,9
para dados, na cache de 16kB, e de 43,3 para a cache unificada.
Considere que 36% das instruções são de load/strore e que um acerto
utiliza 1 ciclo de clock e a penalidade de falta é de 100 ciclos. Um
acerto na cache unificada utiliza 1 ciclo extra para acesso a dados.
Calcule o tempo médio de acesso à memória em cada cache,
considerando média de 74% de acessos a instruções e 26% de acessos
a dados.
Memória cache
45 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
Convertendo faltas por 1000 instruções em taxa de faltas:
Taxa de falta =
Perdas
1000 instruções
Acessos à memória
1000 instruções
/1000
Memória cache
46 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
Convertendo faltas por 100 instruções em taxa de faltas:
Taxa de falta16k instruções =
1
3,82/1000
= 0,004
Memória cache
47 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
Convertendo faltas por 100 instruções em taxa de faltas:
Taxa de falta16k dados =
0,36
40,9/1000
= 0,114
Memória cache
48 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
Convertendo faltas por 100 instruções em taxa de faltas:
Taxa de falta32kB unificada=
1 + 0,36
43,3/1000
= 0,0318
Memória cache
49 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
A taxa de miss geral para as caches divididas deve considerar
74% de acessos para instruções e 26% para dados:
Taxa de miss geral16kB divididas= 74% * 0,004 + 26% * 0,114 = 0,0326
Logo, a taxa de miss das caches separadas é ligeiramente
superior ao apresentado pela cache unificada (0,0318).
Memória cache
50 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
A fórmula do tempo médio de acesso a memória pode ser
dividida entre acessos a instruções e acessos a dados:
Tempo médio de acesso a memória =
% instruções (Tempo de acerto + Taxa de falta * Penalidade de falta) 
+ 
% dados (Tempo de acerto + Taxa de falta* Penalidade de falta) 
Tempo médio de acesso a memória = Tempo de acerto + Taxa de perda * Penalidade de perda
Memória cache
51 Prof. Marcelo PortoComputação UFPel: Arquiteturas de Computadores
Desempenho da cache: Caches unificadas vs. Caches separadas
Solução Exemplo 3:
Tempo médio de acesso a memória:
Tempo médio de acesso à memória 16kB divididas
= 74% * (1 + 0,004 * 100) + 26% * (1 + 0,114 * 100) 
= 74% * 1,4 + 26% * 12,4
= 1,036 + 3,224 = 4,26
Tempo médio de acesso à memória 32kB unificada
= 74% * (1 + 0,0318 * 100) + 26% * (1 + 1 + 0,0318 * 100) 
= 74% * 4,18 + 26% * 5,18
= 3,0932 + 1,3468 = 4,44 
Memória cache
52 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.
• HENNESSY, John L.; PATTERSON, David A. Computer
Architecture: A Quantitative Approach. San Francisco,
California: Morgan kaufmann Publishers, 1996.
Bibliografia