Arquitetura de Computadores 3

•
UFMT

Wanderson Timoteo
26/11/2020
Prévia do material em texto
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Memória Cache
Prof. Dr. Mauŕıcio Fernando Lima Pereira
Instituto de Computação - UFMT
4 de julho de 2018
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Conteúdo
1 Visão geral do sistema de memória do computador
2 Prinćıpios da memória cache
3 Elementos de projeto da memória cache
Conteúdo extráıdo de
Caṕıtulo 4 do livro do Stallings
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Memória de computador é composta por uma vasta gama de:
tipos
tecnologias
organização
desempenho
custo
Hierarquia de memória
Internas (Processador)
Externas (Dispositivos de E/S)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Localização
CPU (registradores, memória de microprograma)
Interna (cache, RAM)
Externa (discos, fitas)
Capacidade
Internamente relacionado ao tamanho de palavra da máquina(8, 16, 32 bits)
A unidade de organização natural
Em geral o tamanho em bits de um inteiro e da instrução
Variações na arquiteturas: x86 tem instruções de tamanhos diferentes
Externamente ao número de Bytes ou palavras
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Unidades endereçáveis
Menor local que pode ser endereçado exclusivamente.
Por Byte
Por Palavra
Endereço com A bits permite endereçar 2A unidades
Unidade de transferência
Interna:
Normalmente controlada pela largura do barramento.
Externa:
Normalmente um bloco que é muito maior que uma palavra.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Métodos de acesso
Sequencial:
Começa no ińıcio e lê em ordem.
Tempo de acesso depende da localização dos dados e local anterior.
Por exemplo, fita.
Direto:
Blocos individuais possuem endereço exclusivo.
Acesso saltando para vizinhança com busca sequencial para localização final
Tempo de acesso depende da localização e local anterior.
Por exemplo, disco.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Métodos de acesso
Aleatório:
Endereços individuais identificam localizações com exatidão.
Tempo de acesso é independente da localização ou acesso anterior.
P.e., RAM.
Associativo:
Dados são localizados por uma comparação com conteúdo de uma parte do
armazenamento
Analisa-se alguns bits do endereço
Tempo de acesso é independente do local ou acesso anterior.
P.e., cache.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Para o usuário, tão importante quanto a capacidade é o desempenho
Como avaliar este desempenho?
Três parâmetros de desempenho
Tempo de acesso (latência):
Memória de acesso aleatório: Tempo entre apresentar o endereço e obter os dados
válidos
Memória de acesso não aleatório: Tempo gasto para posicionar mecanismo de leitura
Tempo de ciclo de memória
Tempo de ciclo = tempo de acesso + recuperação.
Recuperação: Tempo que pode ser exigido para a memória se ”recuperar”antes do
próximo acesso.
Eliminação de transientes nas linhas de sinais ou restauração caso os dados sejam
lidos de forma destrutiva
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Três parâmetros de desempenho:
Taxa de transferência
Taxa em que os dados podem ser movidos
Memória de acesso aleatório
Taxa de transferencia =
1
Tempo de ciclo
Memória de acesso não aleatório
Tn = TA +
n
R
Tn → Tempo médio pra ler ou escrever n bits
TA → Tempo de acesso médio
n → Número de bits
R → Taxa de transferência em bits por segundo (bps)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Caracteŕısticas dos sistemas de memória
Tipo f́ısico
Semicondutor: RAM, cache, registradores.
Magnético: Disco e fita.
Óptico: CD e DVD
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória
Restrições de memória de um computador estão relacionadas a três questões:
Quanto? Capacidade.
Que velocidade?
Quanto mais rápido a CPU for atendida melhor.
Menor tempo de acesso
A que custo?
Boa relação de custo
Diversas tecnologias para implementar sistemas de memória
Tempo de acesso mais rápido e maior custo por bit
Maior capacidade, menor custo por bit
Maior capacidade, tempo de acesso mais lento
Solução é a hierarquia de memória
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória
Enquanto se desce na hierarquia
1 Diminuição do custo por bit
2 Aumento da capacidade
3 Aumento do tempo de acesso
4 Frequência de acesso à memória do
computador
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória - Estudo de caso
Suponha um computador com 2 ńıveis de memória
Nivel 1 - capacidade 1.000 palavras e tempo de acesso 0,01µs
Ńıvel 2 - capacidade 100.000 palavras e tempo de acesso 0,1µs
Se informação em ńıvel 1: processador acesso diretamente
Se informação no ńıvel 2: processador traz para ńıvel 1 e depois acesso
Ignoramos o tempo de trazer do ńıvel 2 para o 1
P1 e P2: % de acertos no ńıvel
Tempo(Médio) = P1 ∗ 0, 01µs + P2 ∗ (0, 1 + 0, 01)µs
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória - Estudo de caso
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória
O uso de dois ńıveis de memória funciona bem se as condições forem satisfeitas
1 Diminuição do custo por bit
2 Aumento da capacidade
3 Aumento do tempo de acesso
4 Frequência de acesso à memória do computador
Para o item 1 a 3 tem-se que diferentes tecnologias podem ser aplicadas na
construção de memórias
Mas o que garante que o item 4 será atendido?
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Hierarquia de memória
Prinćıpio da localidade
Durante execução de um programa instruções e dados tendem a se agrupar
Por exemplo: loops iterativos, funções (instruções)
Localidade espacial
Localizações de memória com endereços numericamente similares a uma localização
de memória recentemente acessada provavelmente serão acessadas no futuro
próximo.
Caches exploram essa caracteŕıstica dos programas trazendo mais dados dos que os
requisitados, na esperança de antecipar futuras utilizações
Localidade temporal
Localizações de memória recentemente acessadas são acessadas novamente
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Hierarquia de memória
Prinćıpio da localidade- Exemplo
1 i n t A [ 2 0 0 ] ;
i n t B [ 2 0 0 ] ;
3 i n t C [ 2 0 0 ] ;
i n t i , j , k , d ;
5 . . .
f o r ( i = 0 ; i < 2 0 0 ; i ++)
7 A [ i ]= B [ i ]+C [ i ] ;
. . .
9 d = k ;
Listing 1: Código exemplo em C
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória - Prinćıpio da localidade
No estudo de caso anterior
Ńıvel 2 - Todo o programa e todos os dados
Ńıvel 1 - Os conjuntos de dados e programas atuais
Eventualmente ocorre uma troca de conjuntos, com trechos saindo do ńıvel 1 para o
ńıvel 2 para dar espaço para um novo trecho
Processadores com centenas de registradores para aumentar a localidade dos
dados e ganhar velocidade
Por outro lado, memória é o principal local de armazenamento do computador
Cache com uma porção menor e mais rápida
Inviśıvel para CPU (programador)
Dispositivo para organizar a movimentação de dados entre memória e registradores
(melhorar desempenho)
Conjunto de dispositivos de memória volátil
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Introdução
Hierarquia de memória - Prinćıpio da localidade
Memórias não voláteis - tecnologias ópticas e magnéticas
Técnicas de cache por software para maximizar o uso destes dispositivos
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Exerćıcio de Fixação 1
Hierarquia de memória
1 Em um computador com 2 ńıveis de memória, um ńıvel possui uma taxa média de
acerto de 60%, o tempo de acesso é de 9 ns para dados que se encontram nesse
ńıvel, e de 60 ns no outro ńıvel. Determine o tempo de acesso médio desse ńıvel.
2 Um sistema de memória com dois ńıveis tem um tempo médio de acesso de 15 ns.
O ńıvel mais alto do sistema de memória tem uma taxa de acertos de 85% e um
tempo de acesso de 8 ns. Qual é o tempo de acesso do ńıvel mais baixo?
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Cache é uma pequena quantidade de memória rápida
Fica entre a memória principal normal e a CPU
Pode estar localizada no chip da CPU
Visa obter velocidade
Cópia parcial do que está presente na memória principal
Solicitações da CPU a memória, busca da solicitação na cache
Caso esteja presente a palavra solicitada, cache atende CPU
Caso contrário, cache traz um bloco de palavras é lido para a cache e depois
entregue a CPU
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Cópia do bloco traz além da palavra de interesse, palavras adjacentes (explorar
localidade)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Exemplo atual
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Exemplo atual
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Função de mapeamento
Memória principal
Dec End Dado
0 00000000 F3
1 00000001 A1
2 00000010 12
3 00000011 00
. . . . . . . . .
Cache
Tag Dados
0
1
2
3
4
...
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Memória principal tem 2n palavras (bytes) endereçáveis, com cada palavra tendo
um endereço distinto de n bits
Memória principal está dividida em M blocos de K palavras (M = 2
n
K )
Cache está dividida em C linhas que contém o bloco de K palavras, bits de
controle e tags
M >> C
Como existem mais blocos do que linhas, não é posśıvel colocar todos os M blocos
na cache.
Assim a tag identifica a que bloco da memória principal pertence o dado que está
em um determinada linha
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Observações
Na linha de cache existe espaço para tag e bits de controle
A largura da linha sem tag e bits de controle é do tamanho do bloco de memória
A qualquer momento um subconjunto de blocos da memória pode estar nas linhas
da cache
Tag ajuda a identificar de qual bloco da memória vieram os dados que estão na linha.
Tag em geral é parte do endereço
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
1 CPU requisita conteúdo do local de memória.
2 Verifica se os dados estão em cache.
3 Se estiverem, apanha da cache (rápido).
4 Se não, lê bloco solicitado da memória principal para a cache.
5 Depois, entrega da cache à CPU.
6 Cache inclui tags para identificar qual bloco da memória principal está em cada
slot da cache.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Prinćıpios da memória cache
Existe menos linhas de cache do que bloco de memória principal
Necessidade de estabelecer um algoritmo para mapear blocos da memória
principal para a cache
Criar mecanismos para se saber em que linha da cache está um determinado bloco
da memória principal
A escolha da função de mapeamento determinada o desempenho e como a cache
está organizada.
Existem 3 técnicas:
Direta
Associativa
Associativa em conjunto
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Função de mapeamento - Mapeamento direto
A técnica mais simples de mapeamento
Cada bloco da memória principal há apenas uma linha de cache posśıvel
O mapeamento direto expresso como
Linha de cache = Bloco de memória mod Nro. de linhas da cache
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Memória
principal
Dec End Dado
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Cache
Tag Dados
0
1
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Função de mapeamento - Mapeamento direto
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Função de mapeamento - Mapeamento direto
O efeito deste mapeamento é que os blocos da memória principal são alocados
nas linhas da cache da seguinte forma:
Linha de cache Blocos de memória principal mapeados
0 0, m, 2m, . . . , 2s -m
1 1, m+1, 2m+1,. . . , 2s -m+1
...
...
m-1 m-11, 2m-1,3m-1,. . . , 2s -1
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto damemória cache
Mapeamento direto - Exemplo
Considere uma máquina com uma memória principal endereçavel por byte com 1024
bytes (210) e um tamanho de bloco de 4 bytes. Suponha que uma cache mapeada
diretamente, consistindo em 16 linhas com 4 bytes cada (64 bytes - 24 linhas), seja
usada nessa máquina.
Bloco da memória Endereços Linha na cache
Bloco 0 0, 1, 2, 3 Linha 0
Bloco 1 4, 5, 6, 7 Linha 1
Bloco 2 8, 9, 10, 11 Linha 2
Bloco 3 12, 13, 14, 15 Linha 3
Bloco 4 16, 17, 18, 19 Linha 4
. . . . . . . . .
Bloco 15 60, 61, 62, 63 Linha 15
Bloco 16 64, 65, 66, 67 Linha 0
Bloco 17 68, 69, 70, 71 Linha 1
... Linha ...
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto
A função de mapeamento pode ser implementada por meio do endereço da
memória principal
Para fins de mapeamento e acesso a cache cada endereço de memória pode ser
visto como 3 partes
1 Tag (s-r)
2 Linha (r)
3 Byte ou Palavra (w bits menos significativos)
Informações para mapeamento
Tamanho de endereço = (s+w) bits
Número de unidades endereçáveis = 2(s+w) palavras ou bytes
Tamanho do bloco = Tamanho da linha = 2w palavras ou bytes
Número de blocos na memória principal = 2
(s+w)
2w = 2
s
Número de linhas na cache = 2r linhas
Tamanho da cache = 2r+w bytes ou palavras
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Exemplo simples
Memória com 1 KB e endereçada por byte (210 bytes ou end.)
Cache com 64 Bytes de memória (26) bytes
Em cada bloco da memória e linha de cache se tem 4 bytes
Informações para mapeamento
Tamanho de endereço = (10) bits (s+w)
Número de unidades endereçáveis = 210 bytes
Tamanho do bloco e da linha = 4 ou 22 bytes (w = 2)
Número de blocos na memória principal = 28 blocos (s = 8)
Número de linhas na cache = 24 linhas (r=4)
Tag precisa 4 bits (s-r)
0000 0000 00
TAG LINHA PALAVRA
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Memória principal
Dec End Dado
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Cache
Tag Dados
0
1
2
3
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Simulador de Cache
ParaCache Simulator
http://www.ntu.edu.sg/home/smitha/ParaCache/Paracache/start.html
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Exerćıcio de Fixação 2
A partir das configurações abaixo determine a quantidade de bits reservada para
tag(s-r), linha(r) e palavra(w)
Cache de 64 KBytes
Memória principal de 16 MBytes com cada byte endereçável diretamente por
endereço
Bloco de 4 bytes (Memória principal ↔ cache)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Exerćıcio de Fixação 3
A partir das configurações abaixo determine a quantidade de bits reservada para
tag(s-r), linha(r) e palavra(w) e mapeie os endereços
Memória com 1 KB e endereçada por byte (210 bytes ou end.)
Cache com 64 Bytes de memória (26) bytes
Em cada bloco da memória e linha de cache se tem 4 bytes
Mapear o endereço 95 (0001011111)
Mapear o endereço 335 (0101001111)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Exerćıcio de Fixação 4
Memória com 256 MB e endereçada por byte
Cache com 8 MB
Em cada bloco da memória e linha de cache se tem 64 bytes
Mapear o endereço 6984
Mapear o endereço 3492
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Exerćıcio de Fixação 5
Um sistema de computador possui um mapa de memória de 4 Gbytes, usando
endereçamento a byte e uma memória cache com organização de mapeamento direto.
A cache tem capacidade de armazenar até 1.024 palavras de 32 bits provenientes do
mapa de memória. Assuma que a cache sempre é escrita de forma atômica com quatro
bytes vindos de um endereço de memória alinhado em uma fronteira de palavra de 32
bits, e que ela usa 1 bit de validade por linha de cache. Neste caso, as dimensões do
rótulo (tag) da cache, do ı́ndice da cache e o tamanho da cache são, respectivamente:
a) 12 bits, 18 bits e 54.272 bits.
b) 14 bits, 18 bits e 56.320 bits.
c) 20 bits, 10 bits e 54.272 bits.
d) 20 bits, 12 bits e 54.272 bits.
e) 22 bits, 10 bits e 56.320 bits.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto
Como descobrir se a linha de cache está presente
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto
Cache de 64 KBytes
Memória principal de 16 MBytes com cada byte endereçável diretamente por
endereço de 224 (224 = 16 M)
Bloco de 4 bytes (Memória principal ↔ cache)
Memória principal consiste de 4M blocos de 4 bytes.
Cache consiste de 16K linhas
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento direto - Vantagens e desvantagens
Simples e pouco dispendiosa para se implementar
Porém implica que existe um local de cache fixo para cada bloco
Se o programa referenciar frequentemente dois blocos diferentes que estejam
mapeados para a mesma linha, os blocos serão repetidamente trocados.
Exemplo Matriz de 64KB × 64KB com acesso por elementos na linha
Uso de cache v́ıtima entre a cache mapeada diretamente e memória
Menor penalidade de falha.
Lembra-se do que foi descartado. Já buscado.
Usa novamente com pouca penalidade.
Totalmente associativa.
4 a 16 linhas de cache.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento associativo - Caracteŕısticas
Compensa a desvantagem do mapeamento direto, permitindo que cada bloco da
memória principal seja carregado em qualquer linha da cache
Endereço de memória é dividido em 2 partes
1 Tag (s)
2 Palavra (w)
Controle dos blocos carregados na cache se dá pela Tag, a qual identifica que
bloco da memória principal ele corresponde.
Para determinar se um bloco está na cache, compara-se simultaneamente as tags
de cada linha
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento associativo - Exemplo simples
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Memória principal
Dec End Dado
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Cache
Tag Dados
0
1
2
3
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento associativo - Exemplo simples
Memória com 1 KB e endereçada por byte (210 bytes ou end.)
Cache com 64 Bytes de memória (26) bytes
Em cada bloco da memória e linhade cache se tem 4 bytes
Informações para mapeamento
Tamanho de endereço = (10) bits (s+w)
Número de unidades endereçáveis = 210 bytes
Tamanho do bloco e da linha = 4 ou 22 bytes (w = 2)
Número de blocos na memória principal = 28 blocos (s = 8)
Tag tem 8 bits
00000000 00
TAG PALAVRA
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento associativo
Como descobrir se a linha de cache está presente ?
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento associativo - Exemplo
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo - Exerćıcio de Fixação 6
Memória com 1GB e endereçada por byte
Cache com 4 MB
Em cada bloco da memória e linha de cache se tem 128 bytes
Determine a quantidade de bits para palavra e tag
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo - Vantagens e desvantagens
Flexibilidade sobre qual bloco substituir
Algoritmos de substituição
Pesquisa da tag na cache é dispendiosa.
Complexidade do circuito necessário para comparar tags
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Meio termo entre o mapeamento direto e o associativo, onde se reforça os pontos
fortes e se minimiza as desvantagens de cada técnica
Divide-se a cache em conjuntos que correspondem a uma série de k linhas (k-way)
Determinado bloco da memória principal é mapeado a qualquer linha em
determinado conjunto da cache.
Por exemplo: Bloco B pode estar em qualquer linha do conjunto i.
Outro exemplo: 2 linhas por conjunto:
Mapeamento associativo com 2 linhas.
Determinado bloco pode estar em uma de 2 linhas em apenas um conjunto.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Lógica de controle de cache interpreta um endereço da memória como três
campos
Tag (s-d bits) ,Set (d bits) e Palavra (w bits)
Utiliza-se d bits para se representar os 2d conjuntos existentes na cache
Utiliza-se w bits para se determinar em qual dos 2w bytes ou palavras em cada linha
Tal como nos outros mapeamentos os bits da Tag servem para determinar se houve
um cache hit ou cache miss
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto - Exemplo simples
Memória com 1 KB e endereçada por byte (210 bytes ou end.)
Cache com 64 Bytes de memória (26) bytes
Em cada bloco da memória e linha de cache se tem 4 bytes
Cada conjunto tem 2 linhas
Informações para mapeamento
Tamanho de endereço = (10) bits (s+w)
Número de unidades endereçáveis = 210 bytes
Tamanho do bloco e da linha = 4 ou 22 bytes (w = 2)
Número de blocos na memória principal = 28 blocos (s = 8)
Número de linhas na cache = 24 linhas (r=4)
Número de linhas no conjunto = 2
Total de conjuntos → d = Nro. de linhas/linhas no cjto. = 23 conjuntos
Tag precisa 5 bits (s-d)
00000 000 00
TAG CONJUNTO PALAVRA
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Mapeamento Associativo em Conjunto (Set Associtative)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Desempenho de cache pelo pelo tamanho do conjunto (Set-Associative)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Diferenças de desempenho
Significativo até pelo menos 64 KB para 2 linhas.
Diferença entre 2 e 4 linhas em 4 KB muito menor que 4 KB para 8 KB.
Complexidade da cache aumenta com a associatividade.
Não justificado contra aumento da cache para 8kB ou 16kB.
Acima de 32 KB não gera melhoria. (resultados de simulação)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Algoritmos de substituição
Quando a cache fica ”cheia”, uma das linhas deve ser substitúıda quando um
novo bloco de informação for trazida da memória
Mapeamento direto não oferece diversas possibilidades, visto que apenas uma
posição é posśıvel
Porém para o mapeamento associativo e conjunto associativo é necessário
estabelecer politicas de substituição
Estas politicas devem estar implementadas em hardware
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Algoritmos de substituição
1 LRU (Last Recently Used):
Substitui aquele bloco no conjunto que permaneceu na cache por mais tempo sem
qualquer referência a ele.
Mais popular.
Associativo 2-way : bit USE (1 utilizado recentemente e 0 caso contrário)
Associativo completo: Lista separada de ı́ndices para todas as linhas na cache.
Linhas recentemente acessadas ficam na frente da lista.
2 FIFO (First-In, First-out)
Substitui o bloco no conjunto que esteve na cache por mais tempo
Buffer circular
3 LFU (Least Frequently Used)
Substitua o bloco no conjunto que teve menos referências.
Contador para cada linha
4 Aleatória: Estudo mostram que é apenas ligeiramente inferior aos algoritmos
baseado no uso
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Exerćıcio de Fixação 7
Neste exerćıcio considere uma memória de 64 KB e uma cache de capacidade de 64 bytes que utiliza associativo
em conjunto de 2 linhas e que tem em cada linha 8 bytes. Considere que o bit LRU quando 1 mostra o mais
recentemente utilizado. Determine se ocorreria um cache miss ou um cache hit para uma requisição de leitura
dos endereços abaixo. Caso ocorra um cache hit, qual seria o dado obtido. Caso ocorra um cache miss, qual
seria a linha substitúıda?
266(100001010) e 45 (101101)
Bytes da linha
Conjunto Bit LRU TAG 0 1 2 3 4 5 6 7
0 0 13 0 1 2 3 4 5 6 7
1 3 0 1 2 3 4 5 6 7
1 1 3 0 1 2 3 4 5 6 7
0 8 0 1 2 3 4 5 6 7
2 0 9 0 1 2 3 4 5 6 7
1 12 0 1 2 3 4 5 6 7
3 0 34 0 1 2 3 4 5 6 7
1 12 0 1 2 3 4 5 6 7
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Simulador de Cache
ParaCache Simulator
http://www.ntu.edu.sg/home/smitha/ParaCache/Paracache/start.html
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cachePoĺıtica de escrita
Não deve sobrescrever bloco de cache a menos que a memória principal esteja
atualizada.
Múltiplas CPUs podem ter caches individuais.
E/S pode endereçar memória principal diretamente.
1. Poĺıtica Write-through
Técnica mais simples
Todas as operações de escrita são feitas na cache e na memória principal
Garante que em todos os ńıveis a informações esteja consistente
Qualquer outro processador-cache pode manter seus dados consistentes monitorando
a memória principal
Desvantagem: tráfego de memória considerável que pode tornar-se um gargalo do
sistema
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Poĺıtica de escrita
2. Write-back
Minimiza escritas na memória principal, com atualizações apenas na memória cache
Quando ocorre uma escrita, ativa-se um bit de modificação associado a linha
Quando o bloco é substitúıdo, ele é escrito de volta na memória principal se o bit de
modificação estiver ativo
Desvantagem: Partes da memória ficam inválidas e isto bloqueia o acesso de outros
dispositivos de entrada e sáıda. A cache irá liberar o acesso aos dispositivos de E/S
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Poĺıtica de escrita - Tratamento de problemas em múltiplos processadores com cache
1 Observação de barramento com write-through
cada controlador monitora as linhas de barramento para detectar operações de escrita
escrita de outros mestres invalidam cópia local
2 Transparência de hardware
Hardware extra que garante que as atualizações de uma cache na memória principal
são refletidas nas demais caches
3 Memória não cacheavel
Uma parte da memória principal compartilhada mantida fora das linhas de cache
Acessos aos endereços compartilhados sempre ocasional cache miss
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Tamanho da linha
Recupere não apenas a palavra desejada, mas também uma série de palavras
adjacentes.
Tamanho de bloco aumentado aumentará razão de acerto a prinćıpio.
O prinćıpio da localidade.
Razão de acerto diminuirá à medida que o bloco se tornar ainda maior.
Probabilidade de uso de informações recém buscadas torna-se menor que
probabilidade de reutilizar informações substitúıdas
Blocos maiores:
Reduzem número de blocos que cabem na cache.
Dados sobrescritos pouco depois de serem buscados.
Nenhum valor ideal definitivo foi descoberto.
8 a 64 bytes parece ser razoável (Em HPC o tamanho fica entre 64 a 128)
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Número de memórias caches
Alta densidade lógica permite caches no chip.
Mais rápido que acesso ao barramento.
Libera barramento para outras transferências.
Comum usar cache dentro e fora do chip.
L1 no chip, L2 fora do chip na RAM estática.
Acesso L2 muito mais rápido que DRAM ou ROM.
L2 normalmente usa caminho de dados separado.
L2 pode agora estar no chip.
Resultando em cache L3.
Acesso ao barramento agora no chip.
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Elementos de projeto da memória cache
Caches unificadas versus separadas
Uma cache para dados e instruções ou duas, uma para dados e uma para
instruções (Harvard)
Vantagens da cache unificada:
Maior taxa de acerto.
Equilibra carga entre buscas de instrução e dados.
Apenas uma cache para projetar e implementar.
Vantagens da cache separada:
Elimina disputa pela cache entre a unidade de busca/decodificação de instrução e a
unidade de execução.
Importante no pipeline de instruções (disputa entre unidade de busca e unidade de
execução)
Maior tendência de utilização nas CPU recentes
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Cache no Pentium 4
Caracteŕısticas dos sistemas de memória
Visão geral do sistema de memória do computador Prinćıpios da memória cache Elementos de projeto da memória cache
Exerćıcios
No caṕıtulo 4 do livro do Stallings
Perguntas de revisão (Todas)
Problemas 4.5;4.6;4.8;4.10;4.11;4.12;
	Visão geral do sistema de memória do computador
	Princípios da memória cache
	Elementos de projeto da memória cache