IAC-INF1029-Vol13-Memória Cache

Prévia do material em texto

1
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Introdução à Arquitetura de 
Computadores
Anderson Oliveira da Silva
Ph. D. Ciências em Informática
Engenheiro de Computação
anderson@inf.puc-rio.br
Departamento de Informática
PUC-Rio
2
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Parte IV –
Sistema de Computação
Memória Cache
– Visão Geral do Sistema de Memória
» Localização, Capacidade, Unidade de Transferência, Método de Acesso, 
Desempenho, Tipo Físico, Características Físicas e Organização
– Princípios da Memória Cache
» Relação entre cache L1, L2 e L3
– Elementos de Projeto da Cache
» Endereços da Cache
» Política de Escrita
» Função de Mapeamento
» Número de Caches
» Algoritmo de Substituição
• LRU, FIFO, LFU e Aleatória
3
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de 
Computação
4
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Visão geral do sistema de memória
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
Extremamente rápidas
Extremamente lentas
Usa um marcador entre 
blocos de dados
Usa uma coordenada para 
localizar blocos de dados
Usa um endereço exclusivo 
para acessar uma palavra
Usa uma chave para 
selecionar uma palavra
- Memória aleatória: tempo total entre o endereçamento e 
disponibilidade do dado. - Memória não aleatória: tempo 
para posicionar o mecanismo de leitura-escrita.
- Memória aleatória: tempo de acesso mais qualquer outro 
tempo necessário para um segundo acesso (referente ao 
barramento do sistema e não ao processador).
- Memória aleatória: 1 / tempo de ciclo. - Memória não 
aleatória: tempo médio + (n bits / taxa de transf. n bits)
5
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Restrições de projeto com relação a memória
– Podem ser resumidas por três questões:
» Quantidade? 
» Velocidade? 
» Custo?
– A questão da quantidade é, de certa forma, livre.
– Para conseguir maior desempenho, a memória deve ser capaz 
de acompanhar a velocidade do processador.
– O custo da memória deve ser razoável em relação a outros 
componentes.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
6
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Dilema do projeto com relação a memória
– Diversas tecnologias são usadas para implementar sistemas de 
memória e, por meio desse espectro de tecnologias, existem as 
seguintes relações:
» Tempo de acesso mais rápido, maior custo por bit.
» Maior capacidade, menor custo por bit.
» Maior capacidade, tempo de acesso mais lento.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
7
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Hierarquia de memória
– Para sair desse dilema, é preciso não contar com um único 
componente ou tecnologia de memória, mas empregar uma 
hierarquia de memória. 
– Conforme se desce na hierarquia, ocorre 
o seguinte:
» Diminuição do custo por bit.
» Aumento da capacidade.
» Aumento do tempo de acesso.
» Diminuição da frequência de 
acesso à memória pelo 
processador.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
8
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Princípios da memória cache
– A memória cache é desenvolvida para combinar o tempo de 
acesso de memórias de alto custo e alta velocidade com as 
memórias de menor velocidade, maior tamanho e mais baixo 
custo.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
9
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Princípios da memória cache
– Normalmente, usa-se múltiplos níveis de cache 
para melhorar o desempenho:
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
10
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Princípios da memória cache
– Estrutura de cache/memória principal:
» A cache é formada por linhas compostas por dois
campos: 
• (i) a tag da linha; e 
• (ii) um bloco de palavras de tamanho K da 
memória principal.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
11
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Princípios da memória cache
– Operação de leitura 
da cache:
» RA – Read Address
12
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Princípios da memória cache
– Organização típica de memória cache:
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
13
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Elementos de projeto da cache
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
14
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Endereços da cache
– Uma cache lógica, também conhecida como cache virtual, 
armazena dados usando endereços virtuais. 
– Uma cache física armazena dados usando endereços físicos 
da memória principal.
– Uma vantagem da cache lógica é que a velocidade de acesso a 
ela é maior do que para uma cache física, pois a cache pode 
responder antes que a MMU realize uma tradução de endereço. 
– A desvantagem é que a maioria dos sistemas de memória 
virtual fornece, a cada aplicação, o mesmo espaço de 
endereços de memória virtual.
15
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Endereços da cache
– Cache lógica:
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
16
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Endereços da cache
– Cache física:
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
17
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Tamanho da memória cache
– Quanto maior a cache, maior o número de portas envolvidos no 
endereçamento da cache.
– O resultado é que caches grandes tendem a ser ligeiramente 
mais lentas que as pequenas – mesmo quando construídas 
com a mesma tecnologia de circuito integrado e colocadas no 
mesmo lugar no chip e na placa de circuito.
– A área disponível do chip e da placa limita o tamanho da cache.
– Como o desempenho da cache é muito sensível à natureza da 
carga de trabalho, é impossível chegar a um único tamanho 
ideal de cache.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
18
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Função de mapeamento
– É necessário haver um algoritmo para mapear os blocos da 
memória principal às linhas de cache. 
– É preciso haver um meio para determinar qual bloco da 
memória principal atualmente ocupa uma linha da cache. 
– Três técnicas podem ser utilizadas:
» direta, 
» associativa e 
» associativa por conjunto.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
19
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Função de mapeamento
– Mapeamento direto é a técnicaque mapeia cada bloco da 
memória principal a apenas uma linha de cache possível.
Problema:
Os blocos Bm a B2m-1
serão mapeados nas 
respectivas posições 
dos blocos B0 a Bm-1.
Logo, se ocorrerem 
acessos repetitivos 
aos blocos B0 e Bm, 
ocorrerão sucessivas 
falhas de cache e, 
como consequência, 
sucessivas 
substituições entre os 
blocos B0 e Bm.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
20
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Função de mapeamento
– O mapeamento associativo compensa a desvantagem do 
mapeamento direto, permitindo que cada bloco da memória 
principal seja carregado em qualquer linha da cache:
Problema:
Para determinar se o 
bloco está na cache, a 
lógica de controle da 
cache precisa 
comparar 
simultaneamente o 
tag de cada linha.
Esse requisito 
aumenta a 
complexidade do 
circuito necessário 
para examinar as tags
de todas as linhas da 
cache em paralelo. 
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
21
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Função de mapeamento
– O mapeamento associativo por conjunto é um meio-termo 
que realça os pontos fortes das técnicas direta e associativa, 
enquanto reduz suas desvantagens. 
• Conhecido como 
mapeamento 
associativo em 
conjunto com 
k-linhas.
Vantagem:
Com o mapeamento 
associativo em 
conjunto com k linhas 
(k-way) a tag em um 
endereço de memória 
é muito menor e só é 
comparada com a k 
tags dentro de um 
único conjunto.
Ocorre acesso direto 
ao conjunto, seguido 
de uma busca 
associativa apenas 
em k linhas.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
22
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Algoritmos de substituição
– Uma vez que a cache esteja cheia, e um novo bloco seja 
trazido para a cache, um dos blocos existentes precisa ser 
substituído.
– O mais eficaz é o usado menos recentemente (LRU – Least
Recently Used).
– Implementado com um bit de referência em cada linha no qual uma linha da cache com 
bit de referência zerado é selecionada.
– Outra possibilidade é o algoritmo primeiro a entrar, primeiro a 
sair (FIFO – First-In First-Out).
– Implementado com uma fila circular no qual a linha da cache que está na cabeça da fila 
é selecionada.
– Outra possibilidade de algoritmo, ainda, é o usado menos 
frequentemente (LFU – Least Frequently Used).
– Implementado com um contador de referências no qual a linha da cache com o 
menor contador é selecionada.
23
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Política de escrita
– Quando um bloco que está residente na cache estiver para ser 
substituído, existem dois casos a serem considerados.
– Se o bloco antigo na cache não tiver sido alterado, ele pode ser 
substituído por novo bloco sem primeiro atualizar o bloco antigo.
– Se pelo menos uma operação de escrita tiver sido realizada em 
uma palavra nessa linha da cache, então a memória principal 
precisa ser atualizada escrevendo a linha de cache no bloco de 
memória antes de trazer o novo bloco.
– Diversas políticas de escrita são possíveis, com escolhas 
econômicas e de desempenho.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
24
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Política de escrita
– A técnica mais simples é denominada write through. 
– Usando esta técnica, todas as operações de escrita são feitas 
na memória principal e também na cache, garantindo que a 
memória principal sempre seja válida.
– Numa técnica alternativa, conhecida como write back, as 
atualizações são feitas apenas na cache.
– Em uma organização de barramento em que mais de um 
dispositivo (em geral, um processador) tem uma cache e a 
memória principal é compartilhada, um novo problema é 
introduzido.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
25
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Política de escrita
– Se os dados em uma cache forem alterados, isso invalida não 
apenas a palavra correspondente na memória principal, mas 
também essa mesma palavra em outras caches (se qualquer 
outra cache tiver essa mesma palavra). 
– Mesmo que uma política write through seja usada, as outras 
caches podem conter dados inválidos. 
– Um sistema que impede esse problema mantém coerência de 
cache.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
26
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Política de escrita
– Algumas das técnicas possíveis para a coerência de cache são:
– Observação (snooping) do barramento com write through:
cada controlador de cache monitora as linhas de endereço para 
detectar as operações de escrita para a memória por outros 
mestres de barramento.
– Transparência do hardware: um hardware adicional é usado 
para garantir que todas as atualizações na memória principal 
por meio da cache sejam refletidas em todas as caches.
– Memória não cacheável: somente uma parte da memória 
principal é compartilhada por mais de um processador, e esta é 
designada como não cacheável. Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
27
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Tamanho da linha
– À medida que o tamanho do bloco aumenta, a razão de 
acerto a princípio aumentará por causa do princípio da 
localidade, que diz que os dados nas vizinhanças de uma 
palavra referenciada provavelmente serão referenciados no 
futuro próximo.
– À medida que o tamanho do bloco aumenta, dados mais úteis 
são trazidos para a cache.
– Contudo, a razão de acerto começará a diminuir enquanto o 
bloco se torna ainda maior e a probabilidade de uso da 
informação recém-trazida se torna menor que a probabilidade 
de reutilizar as informações que foram substituídas.
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
28
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Número de caches (Caches multinível)
– À medida que a densidade lógica aumenta, torna-se possível 
ter uma cache no mesmo chip que o processador: a cache no 
chip.
– A cache no chip reduz a atividade do barramento externo do 
processador e, portanto, agiliza o tempo de execução e 
aumenta o desempenho geral do sistema.
– A organização mais simples desse tipo é conhecida como uma 
cache de dois níveis, com a cache interna designada como 
nível 1 (L1) e a cache externa designada como nível 2 (L2).
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
29
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Número de caches (Caches multinível)
– Razão de acerto total (L1 e L2) para L1 de 8 kB e 16 kB:
Fonte: Arquitetura e Organização de Computadores, 
Willian Stallings, 10a edição - Editora Pearson - 2018 
30
Prof. Anderson Oliveira da Silva - anderson@inf.puc-rio.br
Sistema de Computação –
Memória Cache
Número de caches (Caches unificadas vs separadas)
– Mais recentemente, tornou-se comum dividir a cache em duas: 
uma dedicada a instruções e uma dedicada a dados.
– Essas duas caches existem no mesmo nível, normalmente 
como duas caches L1. 
– Quando o processador tenta buscar uma instruçãoda memória 
principal, ele primeiro consulta a cache L1 de instrução.
– Quando o processador tenta buscar dados da memória 
principal, ele primeiro consulta a cache L1 de dados.