MEMÓRIA CACHE

Prévia do material em texto

MEMÓRIA CACHE
CARLOS MÁGNO
CAMPUS GARANHUNS
Roteiro
 Motivação;
 Princípio da Localidade;
 Princípios da Cache;
 Funcionamento;
 Operação de Leitura;
 Níveis de Cache;
 Memória Cache vs. Memória Principal;
 Tipos de Mapeamento;
 Algoritmos de Substituição;
 Políticas de Escrita;
 Cache nos processadores atuais;
 Exercícios de Fixação.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 2
Motivação
 Evolução dos Sistemas Computacionais
Memória RAM x Processador;
Exemplo (computador hipotético): Realizar uma soma, e ir buscar os operando na 
memória gasta de 60 ns e para o processador obter o resultado 0,3 ns.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 3
HENNESY, 2009
Princípio da Localidade (Denning, 1968)
Apenas uma parte relativamente pequena do 
espaço de endereçamento dos programas é 
acessada em um instante qualquer:
◦ Localidade Espacial
◦ Se um item é referenciado, itens cujos endereços sejam próximos ao dele 
tendem a ser logo referenciados
◦ Localidade Temporal
◦ Um item referenciado tende a ser referenciado novamente dentro de um 
espaço de tempo curto
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 4
Princípios da Cache
 O termo cache é usado em vários contextos em computação:
 Cache de um browser;
 Cache de arquivos em memória;
 Memória cache.
 Em todos estes contextos, a ideia é armazenar informações de interesse em 
um local de acesso mais rápido. 
 É impossível armazenar tudo. 
 Mas se algo é encontrado na cache, ganhamos em desempenho. 
 Note que a consulta à cache consome algum tempo.
 Mas supõe-se que esse tempo é pequeno em relação ao ganho que ocorre 
quando achamos o dado.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 5
Princípios da cache
Cada local de cache pode armazenar o conteúdo de 
diversos locais de memória diferentes:
Como saber se dados correspondem a uma palavra requisitada?
Tags (rótulos) incluídos:
Campo que contém informações necessárias para identificar bloco
Contém parte superior do endereço
Precisamos reconhecer se bloco possui informações 
válidas
 Bit de validade
 Indica se bloco contém dados válidos
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 6
Princípios de cache
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 7
Índice V Tag Dados
000 N
001 N
010 N
011 N
100 N
101 N
110 N
111 N
Funcionamento
 Memória cache, que serve como um reservatório temporário de 
dados e instruções com grande possibilidade de serem usados pelo 
processador; 
 Visa Diminuir o gargalo de velocidade existente entre processador e 
memória principal;
 A memória cache explora o princípio da localidade. Temporal e 
espacial.
 Ela é uma memória relativamente pequena, mas bastante rápida.
 Toda vez que o processador tenta acessar uma posição de memória, 
ele primeiro verifica a existência do dado na cache.
 Quando um dado é acessado na MP, ele é armazenado na cache.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 8
Funcionamento
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 9
Stallings,2002
Esquema de uma memória cache
Funcionamento
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 10
Funcionamento da cache
Stallings,2002
Operação de Leitura
A existência da memória cache altera o processo de leitura de dados 
da MP.
Quando a UCP deseja ler uma posição de memória, os seguintes 
eventos ocorrem:
 Processador escreve o endereço a ser lido no BE de acesso à MP.
 Controlador da cache intercepta pedido e verifica se o dado está em cache.
 Se sim, temos um acerto (hit): dado é copiado para o processador.
 Se não, temos um falta (miss): cache pede o dado à MP, o armazena e repassa para a UCP.
Note que, no caso de um miss, cache solicita um bloco inteiro à MP.
 Conjunto de dados maior que o dado a ser lido.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 11
Operação de Leitura – (Miss)
Os Três Cs:
 Falhas Compulsórias: São faltas no acesso à cache, causadas pelo 
primeiro acesso que nunca esteve na cache.
 Falhas devido à Capacidade: São faltas que ocorrem porque a cache 
não pode armazenar todos os blocos necessários à execução de um 
programa.
 Falhas por Conflitos ou Colisão: São faltas que ocorrem no acesso à 
cache quando diversos blocos competem pelo mesmo conjunto. Não 
ocorrem em caches totalmente associativas.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 12
Níveis de Cache
L1 – Level 1 (nível 1)
 Dentro do processador
Mesma velocidade do processador
 L2 – Level 2 (nível 2)
 Dentro do invólucro, fora do chip
Metade da velocidade do processador
 L3 – Level 3 (nível 3)
 Cache externa, situada na placa mãe
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 13
Caches de Dados e Instruções
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 14
A cache L1 é geralmente dividida em cache de dados e cache de 
instruções: processamento mais rápido
Cache Multinível
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 15
[Stallings, 2010]
Cache Multicore
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 16
Cache Multicore
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 17
Cache Multicore
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 18
Memória Cache vs. MP
 A memória cache é muito menor que a MP. 
 Não podemos guardar todos o conteúdo da MP na cache.
 Em outras palavras, só podemos armazenar um subconjunto dos blocos da 
MP. 
 Por isso, algumas questões fundamentais: 
 Quais blocos manter na cache? 
 Como determinar se um dado está em cache de forma eficiente?
 O que fazer quando um dado em cache é alterado? 
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 19
Memória Cache vs. MP
 A memória cache é muito menor que a MP. 
 Não podemos guardar todos o conteúdo da MP na cache.
 Em outras palavras, só podemos armazenar um subconjunto dos blocos da 
MP. 
 Por isso, algumas questões fundamentais: 
 Quais blocos manter na cache? 
 Como determinar se um dado está em cache de forma eficiente?
 O que fazer quando um dado em cache é alterado? 
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 20
Tipos de Mapeamento
A função de mapeamento determina como a cache é 
preenchida, podendo ser: 
Direto: cada bloco da memória principal é mapeado para apenas 
uma linha de cache;
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 21
Xavier, 2011
Tipos de Mapeamento
Mapeamento direto:
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 22
Xavier, 2011Pode ocorrer substituições de blocos, enquanto outros ficam ociosos.
Tipos de Mapeamento
A função de mapeamento determina como a cache é 
preenchida, podendo ser: 
Direto: cada bloco da memória principal é mapeado para apenas 
uma linha de cache;
Associativo: um bloco pode ser alocado em qualquer linha da cache;
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 23
Xavier, 2011
Tipos de Mapeamento
Mapeamento Associativo: 
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 24
Xavier, 2011
Requer memória associativa entre todos os endereços para realizar a busca 
na cache (alto custo).
Tipos de Mapeamento
A função de mapeamento determina como a cache é 
preenchida, podendo ser: 
Direto: cada bloco da memória principal é mapeado para apenas 
uma linha de cache;
Associativo: um bloco pode ser alocado em qualquer linha da cache;
Associativo por conjunto: a cache é dividida em conjuntos, com certo 
número de linhas cada e um bloco pode estar associado a qualquer 
linha de um conjunto já pré-determinado.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 25
Xavier, 2011
Tipos de Mapeamento
Mapeamento Associativo por Conjunto
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 26
Xavier, 2011
Requer memória Associativa somente dentro de cada bloco; 
Melhor utilização dos blocos.
Vantagem e Desvantagens
TIPO DE 
MAPEAMENTO
VANTAGEM DESVANTAGEM
Direto
Simples e de baixo custo Fixação da localização 
para os blocos;
Fenômeno thrashing;
Associativo
flexibilizar a alocação de blocos em
linhas da cache
maior complexidade do 
circuito da cache
Associativo por 
Conjunto
Meio termo: Usa omapeamento direto, onde cada bloco 
da MP tem um mapeamento fixo para um conjunto 
específico. Mas dentro do seu conjunto, o bloco pode ser 
armazenado em qualquer linha, como no mapeamento 
associativo.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 27
Exemplo – Mapeamento
Consideremos: 
Memória principal: 32 bits
Cache de 4 blocos >> 2N >> n sendo o número de blocos, então n = bits de 
index
 Sequencia desejada de endereços: [0;5;4;9;7;4;0;9;0;7]
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 28
Mapeamento Direto
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 29
Endereço do Bloco Bloco da Cache
0 (0 modulo 4) = 0
5 (5 modulo 4) = 1
4 (4 modulo 4) = 0
9 (9 modulo 4) = 1
7 (7 modulo 4) = 3
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Bloco 0 Bloco 1 Bloco 2 Bloco 3
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[4] Memory[5]
9 Miss Memory[4] Memory[9]
7 Miss Memory[4] Memory[9] Memory[7]
4 Hit Memory[4] Memory[9] Memory[7]
0 Miss Memory[0] Memory[9] Memory[7]
9 Hit Memory[0] Memory[9] Memory[7]
0 Hit Memory[0] Memory[9] Memory[7]
7 Hit Memory[0] Memory[9] Memory[7]
Mapeamento Direto
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 30
Endereço do Bloco Bloco da Cache
0 (0 modulo 4) = 0
5 (5 modulo 4) = 1
4 (4 modulo 4) = 0
9 (9 modulo 4) = 1
7 (7 modulo 4) = 3
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Bloco 0 Bloco 1 Bloco 2 Bloco 3
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[4] Memory[5]
9 Miss Memory[4] Memory[9]
7 Miss Memory[4] Memory[9] Memory[7]
4 Hit Memory[4] Memory[9] Memory[7]
0 Miss Memory[0] Memory[9] Memory[7]
9 Hit Memory[0] Memory[9] Memory[7]
0 Hit Memory[0] Memory[9] Memory[7]
7 Hit Memory[0] Memory[9] Memory[7]
Taxa Hit = 4/10 = 40%
Mapeamento Associativo por 2 Conjuntos 
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 31
Endereço do Bloco Bloco da Cache
0 (0 modulo 2) = 0
5 (5 modulo 2) = 1
4 (4 modulo 2) = 0
9 (9 modulo 2) = 1
7 (7 modulo 2) = 1
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Conj 0 Conj 0 Conj 1 Conj 1
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[0] Memory[4] Memory[5]
9 Miss Memory[0] Memory[4] Memory[5] Memory[9]
7 Miss Memory[0] Memory[4] Memory[7] Memory[9]
4 Hit Memory[0] Memory[4] Memory[7] Memory[9]
0 Hit Memory[0] Memory[4] Memory[7] Memory[9]
9 Hit Memory[0] Memory[4] Memory[7] Memory[9]
0 Hit Memory[0] Memory[4] Memory[7] Memory[9]
7 Hit Memory[0] Memory[4] Memory[7] Memory[9]
Mapeamento Associativo por 2 Conjuntos
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 32
Taxa Hit = 5/10 = 50%
Endereço do Bloco Bloco da Cache
0 (0 modulo 2) = 0
5 (5 modulo 2) = 1
4 (4 modulo 2) = 0
9 (9 modulo 2) = 1
7 (7 modulo 2) = 1
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Conj 0 Conj 0 Conj 1 Conj 1
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[0] Memory[4] Memory[5]
9 Miss Memory[0] Memory[4] Memory[5] Memory[9]
7 Miss Memory[0] Memory[4] Memory[7] Memory[9]
4 Hit Memory[0] Memory[4] Memory[7] Memory[9]
0 Hit Memory[0] Memory[4] Memory[7] Memory[9]
9 Hit Memory[0] Memory[4] Memory[7] Memory[9]
0 Hit Memory[0] Memory[4] Memory[7] Memory[9]
7 Hit Memory[0] Memory[4] Memory[7] Memory[9]
Mapeamento Associativo
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 33
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Bloco 0 Bloco 1 Bloco 2 Bloco 3
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[0] Memory[5] Memory[4]
9 Miss Memory[0] Memory[5] Memory[4] Memory[9]
7 Miss Memory[7] Memory[5] Memory[4] Memory[9]
4 Hit Memory[7] Memory[5] Memory[4] Memory[9]
0 Miss Memory[7] Memory[0] Memory[4] Memory[9]
9 Hit Memory[7] Memory[0] Memory[4] Memory[9]
0 Hit Memory[7] Memory[0] Memory[4] Memory[9]
7 Hit Memory[7] Memory[0] Memory[4] Memory[9]
Mapeamento Associativo
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 34
Taxa Hit = 5/10 = 40%
Endereço do bloco de
memória acessado
Hit ou 
Miss
Conteúdo dos blocos de cache após referência
Bloco 0 Bloco 1 Bloco 2 Bloco 3
0 Miss Memory[0]
5 Miss Memory[0] Memory[5]
4 Miss Memory[0] Memory[5] Memory[4]
9 Miss Memory[0] Memory[5] Memory[4] Memory[9]
7 Miss Memory[7] Memory[5] Memory[4] Memory[9]
4 Hit Memory[7] Memory[5] Memory[4] Memory[9]
0 Miss Memory[7] Memory[0] Memory[4] Memory[9]
9 Hit Memory[7] Memory[0] Memory[4] Memory[9]
0 Hit Memory[7] Memory[0] Memory[4] Memory[9]
7 Hit Memory[7] Memory[0] Memory[4] Memory[9]
Memória Cache vs. MP
 A memória cache é muito menor que a MP. 
 Não podemos guardar todos o conteúdo da MP na cache.
 Em outras palavras, só podemos armazenar um subconjunto dos blocos da 
MP. 
 Por isso, algumas questões fundamentais: 
 Quais blocos manter na cache? 
 Como determinar se um dado está em cache de forma eficiente?
 O que fazer quando um dado em cache é alterado? 
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 35
Problema da substituição dos dados
Cache cheia, novo bloco pode ser trazido para a cache, um dos blocos 
existes precisa ser substituído.
Mapeamento direto: existe apenas uma linha possível para qualquer 
bloco em particular e nenhuma escolha é possível.
Mapeamento associativos e associativa em conjunto: necessário 
algoritmo de substituição.
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 36
Problema da substituição dos dados
Algoritmos de Substituição
Algoritmo em hardware: alta velocidade de substituição. Algoritmos 
mais comuns:
 LRU (Least Recently Used);
 FIFO (First-In-First-Out);
 LFU (Least Frequently Used);
 Escolher uma linha aleatória dentre as linhas candidatas.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 37
Memória Cache vs. MP
 A memória cache é muito menor que a MP. 
 Não podemos guardar todos o conteúdo da MP na cache.
 Em outras palavras, só podemos armazenar um subconjunto dos blocos da 
MP. 
 Por isso, algumas questões fundamentais: 
 Quais blocos manter na cache? 
 Como determinar se um dado está em cache de forma eficiente?
 O que fazer quando um dado em cache é alterado? 
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 38
Problema da escrita dos dados
22/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 39
Antes da execução da instrução:
X = Y + Z
Problema da escrita dos dados
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 40
Depois da execução da instrução:
X = Y + Z
Problema da escrita dos dados
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 41
Problema da escrita dos dados
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 42
O bloco 4 (o valor de X) precisa ser atualizado na memória.
 Quando?
 Depende da política de escrita
Políticas de Escrita
Write-throug:
Todas as operações de escrita são realizadas na MP e na cache;
Módulo processador-cache monitora o tráfego para a MP para manter a 
consistência dentro de sua própria cache;
Desvantagem pois gera tráfego de memória considerável.
Write-back:
 Minimiza escritas na memória;
 Atualizações são feitas apenas na cache;
 Utiliza um bit de modificação ou uso associado à linha é marcado;
 Um bloco é substituído na MP se o bit de modificação estiver marcado;
 Partes da MP podem ficar inválidas devidos aos acessos pelos módulos de 
E/S que devem ser permitidos pela cache.
 Exige circuitos complexos e gera um gargalo em potencial.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 43
Cache nos processadores atuais
AMD
O AMD Athlon II X4 630 tem 2 MB de memória cache L2.
O AMD Phenom II X4 965 tem 6 MB de memória cache L3;
O AMD AMD Ryzen 7 1700X tem 16 MB de memória cache L3
INTEL
Todos usam memória cache L3;
Core I3 -> 3 ou 4MB.
Core I5 -> 6MB;
Core I7 -> 8MB;
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 44
Cache nos processadores atuais
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 45
Cache nos processadoresatuais
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 46
Exercício de Fixação
1. O que é a memória cache? Quais são seu objetivo e a ideia básica de seu 
funcionamento?
2. Qual é a influência da função de mapeamento no projeto da cache? 
Explique cada uma das técnicas de mapeamento que podem ser utilizadas, 
apresentando as vantagens e desvantagens, se existente.
3. Explique quais são os motivos que podem diminui a Taxa de acertos (hits) 
na operação de leitura da memória cache?
4. Quais as vantagens de se empregar uma cache da arquitetura de Harvard 
ou uma cache unificada?
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 47
Exercício de Fixação
5. Considerando as mesmas configurações da memória principal e da 
memória cache apresentado na aula. Inverta a sequência propostas e 
encontre as novas taxas de HIT aplicando os mapeamento direto, 
associativo por conjunto e associativo.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 48
Atividade complementar para a 
próxima aula
1. Solicitação de uma pesquisa que compare as configurações de três 
computadores considerando o custo/benefício das memórias caches.
2. Aplique e obtenhas as taxa de acerto do exemplo do exercício de 
número 5, aplicando os três diferentes algoritmos de substituição, LRU, 
FIFO e LFU.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 49
Referências
Bibliografia Básica
David A Patterson & John L. Hennessy. A Interface Hardware/Software. 
Campus, 4ª Edição, 2013.
 William Stallings. “Organização e Arquitetura de Computadores”, 5ª 
Edição, Pearson Prentice Hall, 2002.
Bibliografia Complementar
Xavier, M. A. S. Rodrigues, J. C., Júnior O. A. L. Simuladores de Memória 
Cache, um Estudo Comparativo Direcionado ao Ensino. Workshop sobre 
Educação em Arquitetura de Computadores WEAC. 2011.
23/05/2018 AULA: MEMÓRIA CACHE - CARLOS MÁGNO 50