Hierarquia da Memória
Caches
1
Hierarquia da memória

Uma afirmação antiga, mas perfeitamente actual…
“Ideally one would desire an indefinitely large memory
capacity such that any particular word would be
immediately available.
We are forced to recognize the possibility of constructing
a hierarchy of memories, each of which has greater
capacity than the preceding but is less quickly
accessible.”
Burks, Goldstine & von Newmann (1946)
2
Hierarquia da memória
Capacidade
Chip do processador
CPU
Registos
Cache
Memória
Principal
Memória
Secundária
(RAM)
(Disco)
Rapidez de acesso
Custo
3
Memórias Cache

Introdução

A memória cache é uma memória com pouca
capacidade, mas rápida, tipicamente associada ao
processador

Esta memória guarda blocos de dados ou instruções
copiados da memória principal (RAM)

Uma vez na cache, o acesso aos valores guardados
passa a ser muito mais rápido

As caches tiram partido do carácter local das
referências
4
Memórias Cache

Carácter local das referências

Espacial


Se uma dada posição de memória foi acedida, é provável que
posições de memória que lhe são vizinhas também venham a
ser acedidas.

os dados de uma matriz

as instruções de um programa, etc
Temporal

Se uma dada posição de memória foi acedida, é provável que
no futuro próximo seja acedida mais vezes.

as instruções dentro de um ciclo do programa

uma variável utilizada muitas vezes, etc
5
Memórias Cache

Acesso à memória cache

Quando é efectuada um acesso à memória, o CPU
acede em primeiro lugar à cache

Podem ocorrer duas situações:


cache hit – os dados pretendidos encontram-se na cache

caso ideal

a taxa de hits deve ser tão alta quanto o possível
cache miss – os dados não estão na cache

nesse caso terão que ser lidos da memória principal

substitui-se um bloco na cache pelo bloco copiado da memória
principal onde estão os dados pretendidos

pode introduzir penalizações temporais adicionais
6
Memórias Cache

Exemplo:

Suponha que o acesso à RAM requer 10 ns, ao passo
que à cache requer apenas 1 ns.

A percentagem de hits na cache é 90%, mas quando
acontece um miss, o processador perde 1 ns
adicional, para além dos tempos referidos.

Qual será o tempo médio de acesso à memória?
Tacesso = 0.9  1ns + 0.1  (10ns + 1ns + 1ns)
= 0.9 + 1.2 = 2.1ns
7
Organização e tipos de cache

Tipos de caches

Cache directa (direct-mapped cache)

Cache associativa


completamente associativa (fully associative)

associativa de n-vias (n-way set-associative)
A organização interna varia consoante o tipo
8
Cache Directa

Estrutura de uma cache directa
Bit de
validade
Tag
Linhas
Bloco de dados
0
1
2
3
4
...
...
9
Cache Directa

Descrição

A cache encontra-se organizada segundo linhas

Em cada tem-se:

Bit de validade


Tag ou etiqueta


Indica se o conteúdo dessa linha é válido ou não
Identifica o bloco de memória de onde vieram os dados
Bloco

Conjunto de dados ou de instruções que foram copiados de
posições consecutivas da memória
10
Cache Directa

Estruturação de um endereço para acesso à cache
Etiqueta
Índice de linha
Índice de palavra
Indexa as palavras
dentro do bloco
0
1
2
3
4
5
...
11
Cache Directa

Determinação de hit ou miss
BUS Endereços
Linha
Tags
Tag
Dados
Tag em cache
Comparador
hit / miss
BUS Dados
12
Cache Directa

Exemplo

Quantas linhas terá uma cache directa com uma capacidade
para 1 KByte de dados organizados por blocos de 128 Bytes ?
N linhas

1 KByte
210

 7  2 3  8 linhas
128 Bytes 2
Qual a estruturação dos endereços, admitindo um espaço de
endereçamento de 64K x 1 Bytes



128 Bytes por bloco  7 bits p/ indexar os blocos
8 linhas  3 bits p/ indexar as linhas
64K  16 bits de endereçamento  etiquetas de 6 bits (16–3–7=6)
6 bits
3 bits
7 bits
Etiqueta
Linha
Palavra
13
Cache Directa

Exemplo (cont.)

Para que linha será carregado o blocos composto pelos
endereços 1024 a 1151 (0x0400 a 0x047F)?
Etiqueta
Linha
Palavra
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
...
0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1
0x0400
...
0x047F
A linha será a 0.
14
Cache Associativa

Completamente associativa

Numa cache completamente associativa, um bloco poderá
ocupar qualquer entrada na cache


Não existe o conceito de linha


Não ocupam posições “pré-determinadas” como nas caches directas
Ou então pode considerar que existe um única linha, com
capacidade para todos os blocos
Só são utilizadas as tags e o índice de palavra
Estruturação dos endereços
Etiqueta
Índ. palavra
15
Cache Associativa

Completamente associativa (cont.)

Mais complexa do que uma cache directa:

Quando há um acesso, é necessário “procurar” o bloco em
causa em todas as entradas da cache

Se o bloco não for encontrado em nenhuma das entradas,
então ocorre um miss

Essa procura é feita em paralelo para todas as entradas da
cache

mais hardware (muitos comparadores)

e apesar do paralelismo, são introduzidos atrasos
16
Cache Associativa

Associativa de n-vias

Este tipo de cache encontra-se a meio caminho entre
uma cache directa e uma cache completamente
associativa

A ideia consiste em dividir a cache segundo linhas
com lugar para n blocos

Uma vez mapeado para uma dada linha, um bloco
poderá ocupar uma das n entradas dessa linha
17
Cache Associativa

Uma cache associativa de 2 vias
Via 0
Via 1
...
...
0
1
2
3
4
...
Estruturação dos endereços
Etiqueta
Índ. linha
Índ. palavra
18
Políticas de substituição de blocos

Quando ocorre um miss e a linha correspondente está
ocupada, qual o bloco que deverá ser substituído na
cache ?

Principais estratégias:


Escolha aleatória

o bloco a substituir é escolhido de forma aleatória

muito fácil de implementar
Algoritmo LRU (Least Recently Used)



o bloco a substituir é aquele que não é acedido à mais tempo, na
esperança de já não voltar a ser necessário
obriga a utilizar um “selo temporal” associado a cada bloco em
cache
estratégia mais complexa e mais cara
19
Políticas de substituição de blocos

Alguma estatística
Dimensão da cache
Aleatório
LRU
16KB
5.69 %
5.18 %
64KB
2.01 %
1.88 %
256KB
1.17 %
1.15 %
% de cache misses durante a execução de um programa utilizando uma cache
associativa de 2 vias com blocos de 16 bytes.
Tabela retirada do livro “Computer architecture: a quantitative approach”
Observações:
O desempenho com LRU é melhor, principalmente em caches pequenas
À medida que a dimensão da cache cresce, o desempenho da escolha
aleatória tende a igualar o algoritmo LRU – preferível utilizar escolha aleatória
20
Políticas de Escrita

O que acontece numa escrita ?

Estratégias mais comuns, em caso de hit numa escrita

Write through (ou store through)


Os dados são sempre escritos tanto na cache como na memória
principal.
Write back (ou store in)



Os dados são apenas escritos na cache. Só serão copiados para a
memória depois do bloco em cache ser substituído.
Utiliza-se um bit extra – dirty bit – em cada linha da cache, que
indica se um dado bloco foi modificado desde que está em cache.
Quando um bloco é substituído, se o seu dirty bit estiver a ‘1’, então
esse bloco é copiado para a memória principal
21
Políticas de Escrita

Write back


Geralmente mais eficiente, pois causa menos acessos para
escrita na memória principal
Write through

Mais simples de implementar

Todas as escritas obrigam a aceder à memória principal


Perde-se mais tempo…
A memória principal tem sempre os dados actualizados

Vantajoso em situações de partilha de memória com outros
dispositivos (tanto periféricos como outros CPUs)
22
Políticas de Escrita

Estratégias em caso de cache miss

Write allocate (ou fetch on write)


No-write allocate (ou write around)


O bloco é carregado na cache, antes de se escreverem os dados
O bloco não é carregado em cache. Apenas se escreve na memória
principal.
Normalmente utiliza-se

write back em conjunto com write allocate

write through em conjunto no-write allocate

... embora possam ser utilizadas outras combinações
23
Redução de misses

Classificação de cache misses:

Cold-start

O primeiro acesso a um bloco que não se encontra em cache


Acontece, por exemplo, no início da execução de um programa
Colisões

Vários blocos de um programa estão à partida destinados a
utilizar a mesma linha da cache, o que pode obrigar a
substituições.

Acontecem porque:

Os programas podem usar uma quantidade de memória
superior à capacidade da cache

Os programas podem referenciar zonas de memória diferentes
que são mapeadas para a mesma linha da cache
24
Redução de misses

Para reduzir a taxa de misses, a hipótese mais
óbvia seria aumentar a capacidade da cache

Mantendo a cache com a mesma capacidade,
existem estratégias para reduzir os misses

Aumentar a dimensão do bloco

Usar um maior grau de associatividade (mais vias)

Utilização de “caches vítimas”

Optimizações do compilador (software)
25
Redução de misses

Aumento da dimensão do bloco
(mantendo a mesma capacidade da cache)


Tenta-se tirar mais partido da localização espacial das
referências
Por um lado diminuem os cold-start misses, mas...


... aumentam os misses devido a colisões ...
... e perde-se mais tempo em caso de miss


são necessários ler mais dados da memória principal devido ao
bloco ser maior
Atenção que o desempenho pode na realidade piorar
quando se aumenta a dimensão do bloco!
26
Redução de misses

Maior grau de associatividade

Aumentando a associatividade reduzem-se os misses devido a
interferências. Os restantes mantém-se.

O preço a pagar é um maior tempo de acesso à própria cache, o
que poderá ter implicações negativas

Na prática, compensa aumentar a associatividade até certo
ponto.
Dimensão da cache
2 vias
4 vias
8 vias
16 KB
5.18 %
4.67 %
4.39 %
64KB
1.88 %
1.54 %
1.39 %
256KB
1.15 %
1.13 %
1.12 %
% de cache misses durante a execução de um programa em função do grau
de associatividade de uma cache (blocos de 16 bytes).
Tabela retirada do livro “Computer architecture: a quantitative approach”
27
Redução de misses

Utilização de caches vítimas

Uma cache vítima é basicamente uma cache de dimensões muito
reduzidas (4 a 8 entradas)


A cache vítima contém blocos que foram substituídos na cache principal




Para ser muito rápida
Sempre que ocorre um miss na cache principal verifica-se se o bloco
pretendido se encontra na “vítima”
No caso de lá se encontrar, trocam-se os blocos entre as duas caches
Esta técnica reduz de forma significativa os misses devido a
interferências
Não apresenta nenhuma desvantagem de maior, excepto o aumento do
custo e um ligeiro aumento da penalidade devido a um miss completo
(miss na cache principal e na vítima)
28
Redução de misses

Técnicas de compilação

Quando os programas (linguagem de alto nível) são traduzidos
para código-máquina, o compilador poderá ter em conta a cache
do processador

Sendo assim, poderá gerar código-máquina que execute a
mesma função, mas que tira partido das características da cache

Manipular o modo de indexação das matrizes

Trocas de índices em ciclos dentro de ciclos

Fusões de ciclos

etc.
29
Níveis de Cache

Níveis de caches



Abordagem comum para redução do tempo médio de acesso à
memória
Quando ocorre um miss no 1º nível, verifica-se se o bloco
pretendido se encontra na cache de 2º nível (maior) e assim
sucessivamente
Só se acede à memória principal se não for encontrado o bloco
pretendido em nenhum dos níveis
Cache
Nível 1
Cache
Nível 2
Memória
principal
RAM
CPU
30
Exemplo – Intel Core 2 Duo E6600
Caches nível 1
Cache nível 2
31
Exemplo – AMD Quad Core Opteron
Caches nível 1
Caches nível 2
Cache nível 3
32
Hierarquia da Memória
Memória virtual
33
Memória Virtual

Espaço de endereçamento virtual

Espaço de endereçamento que engloba a memória primária
(RAM) e a secundária (disco)



O objectivo é poder carregar múltiplos programas (e dados) sem
estar limitado às dimensões físicas da memória RAM
Cada programa a ser executado pode ter partes

carregadas em RAM,

em disco, ...

... ou em ambos os lados
Transferem-se instruções e dados entre a RAM e o disco
(swapping) consoante as necessidades
34
Memória Virtual

Espaço de endereçamento virtual


As formas mais comums para implementar memória virtual são

Paginação

Segmentação

Misto (segmentação + paginação)
A dimensão do espaço virtual corresponde ao número total de
endereços que são indexáveis pelo processador

Exemplo

um processador com endereços de 32 bits consegue gera um espaço
de endereçamento virtual de 232 posições de memória

ou seja, 4 Giga posições de memória (para cada programa)
35
Memória Virtual

Endereços reais


Correspondem aos endereços físicos envolvidos no acesso à
memória ou outros dispositivos (o que temos visto até agora)
Endereços virtuais

Endereços utilizados internamente pelo processador

São convertidos em endereços reais

através de uma unidade localizada no CPU, designada MMU
(Memory Management Unit)

e recorrendo a estruturas de dados, mantidas em memória
36
Memória Virtual

MMU (Memory Management Unit)

Converte endereços virtuais em endereços reais

Assinala o CPU quando é feito um acesso a um endereço que
fisicamente não se encontra localizado na memória principal
CPU
Memória
RAM
MMU
Controlador
de
Disco
Bus de endereços (reais)
37
Paginação

Método mais comum para implementação de
memória virtual

O espaço de endereçamento virtual é divido em
blocos de dimensão fixa designados por páginas.


A dimensão de cada página é uma potência de 2
A memória principal é dividida em blocos com a
mesma dimensão de uma página – estes blocos
designam-se por molduras ou page frames
38
Paginação
Espaço
virtual
8000
RAM
4000
7000
3000
6000
2000
5000
1000
4000
0000
molduras
3000
Disco
2000
1000
0000
páginas
39
Paginação

Tabelas de páginas (page tables)
Endereço virtual
Deslocamento
Nº Página
Tabela de páginas
0
Descritor da página 0
1
Descritor da página 1
2
Descritor da página 2
3
Descritor da página 3
N-1
Descritor da página N-1
Nº Moldura
Deslocamento
Endereço real
40
Paginação

Principais campos num descritor de página

Bit de presença – Indica se a página se encontra carregada na
memória principal (RAM) ou não

Moldura – Índice de moldura (page frame) – indica qual moldura
onde se encontra a página

Protecção – Bits de protecção da página (exemplo, read-only)

Controlo – Bits auxiliares (por exemplo, para o funcionamento
dos algoritmos de substituição de páginas)
Descritor de página
Índice da moldura
Bit de presença
Bits de controlo
Bits de protecção
41
Paginação

Exemplo
0010
0110
1010
0001
0x26A1 (9889)
0110
1010
0001
0x66A1 (26273)
Tabela de páginas
0000
1
101
0001
0
xxx
0010
1
110
0011
0
xxx
0100
1
100
0101
1
111
0110
1
010
0111
0
xxx
1000
0
xxx
1001
0
xxx
1010
1
001
1011
0
xxx
1100
0
xxx
1101
0
xxx
1110
1
000
1111
1
011
110
42
Paginação

Page fault

Quando é acedida uma página que não se encontra na memória
principal, ocorre uma page fault

Quando o CPU recebe o sinal de page fault

Efectuam-se as alterações necessárias na tabela de páginas, de
modo a que esta fique consistente

Se todas as molduras já estiverem ocupadas é necessário escolher
uma página a transferir para o disco, nesse caso corre-se o
algoritmo de substituição de páginas


Normalmente a cargo do sistema operativo
Carrega-se a página em falta (do disco para a RAM)
43
Paginação

Algoritmos de substituição de páginas

LRU (least recently used)


NFU (not frequently used)


descarta a que foi acedida menos vezes
FIFO (first in, first out)


descarta a que não é acedida à mais tempo
descarta a que já se encontra em RAM à mais tempo
Como são implementados pelo Sistema Operativo,
terão mais detalhes nessa disciplina)
44
Paginação

Tabelas multi-nível

Usadas para evitar ter que manter em RAM tabelas de páginas
com grandes dimensões



Vantagem


Existe uma tabela principal (1º nível) chamada directoria,
relativamente pequena, e que é sempre mantida em RAM
A directoria indexa várias tabelas de páginas (2º nível) que podem
estar ou não na RAM, consoante a necessidade
Só são mantidas na memória principal a directoria e as tabelas de
páginas que estão a ser utilizadas
Desvantagem

Demora-se mais tempo a converter um endereço virtual em real,
pois é necessário um acesso à directoria e depois um acesso à
tabela de páginas resultante
45
Paginação
Endereço virtual
10 bits
10 bits
12 bits
TP_L1
TP_L2
Deslocamento
Tabela de 1º nível
(Directoria)
Tabelas de 2º nível
(Tabelas de páginas)
0
1
2
0
1
2
1023
1023
0
1
2
1023
Nº de moldura
0
1
2
Deslocamento
Endereço real
1023
46
Paginação

TLB (Translation Lookaside Buffer)



Ao efectuar a conversão de um endereço virtual para endereço
físico, é necessário de consultar a(s) tabela(s) envolvidas
Como consequência, são feitos acessos à memória
Para minimizar o número de acessos, existe a TLB


Uma “cache especial” para auxiliar a paginação
Tipicamente é uma cache completamente associativa, que guarda
informação sobre os descritores de página
Bit de validade
Etiquetas
(N de página)
Blocos de dados
(Descritores)
1
24
Descritor da página 24
1
56
Descritor da página 56
0
xxx
xxx
1
3
Descritor da página 3
0
xxx
xxx
0
xxx
xxx
os
47