Aula 13

Prévia do material em texto

1
Organização de Computadores I
DCC006
Prof. Omar Paranaiba Vilela Neto
Aula 13 – Memória
2
• Mapeamento: o endereço é o módulo do número de blocos no cache
Cache Mapeado Diretamente
00001 00101 01001 01101 10001 10101 11001 11101
00
0
Cache
Memory
00
1
01
0
01
1
10
0
10
1
11
0
11
1
3
Decrescendo a taxa de faltas usando associação
Chaches totalmente associativas
 Blocos podem ser colocados em qualquer local da cache;
 Buscar um bloco é mais custoso (vários testes necessários).
4
Decrescendo a taxa de faltas usando associação
Chaches associativas por conjunto
 Blocos podem ser colocados em qualquer local dentro de um 
determinado conjunto;
 Combina o Mapeamento direto com associatividade.
5
Decrescendo a taxa de faltas usando associação
Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data
Eight-way set associative (fully associative)
Tag Data Tag Data Tag Data Tag Data
Four-way set associative
Set
0
1
Tag Data
One-way set associative
(direct mapped)
Block
0
7
1
2
3
4
5
6
Tag Data
Two-way set associative
Set
0
1
2
3
Tag Data
6
Uma implementação
Address
22 8
V TagIndex
0
1
2
253
254
255
Data V Tag Data V Tag Data V Tag Data
3222
4-to-1 multiplexor
Hit Data
123891011123031 0
7
Desempenho
0%
3%
6%
9%
12%
15%
Eight-wayFour-wayTwo-wayOne-way
1 KB
2 KB
4 KB
8 KB
M
is
s 
ra
te
Associativity 16 KB
32 KB
64 KB
128 KB
8
Questão para associatividades
Qual bloco substituir quando ocorrer 
falha?
 Aleatório: escolhe-se um bloco aleatório.
Fácil de implementar;
Bom resultados para caches grandes.
 LRU (Least Recently Used): retira-se o bloco usado menos 
recentemente
Fácil de implementar em caches 2-ways.
9
Decrescendo a penalidade por faltas com caches multinível
• Adicione um segundo nível de cache:
– o cache primário esta frequentemente no mesmo chip do µP 
– usar SRAMs para acrescentar outro nível cache acima da memória 
primária (DRAM)
– penalidade por faltas decresce se o dado está no 2o nível cache
• Exemplo:
– CPI de 1.0 numa máquina de 500Mhz com 5% taxa de faltas, e acesso de 
200ns DRAM
– Adicionando o 2o nível cache com tempo de acesso de 20ns e taxa de 2%
• Utilizando-se caches multinível:
– Tentar otimizar o tempo de acerto no 1o nível de cache
– Tentar otimizar a taxa de faltas no 2o nível de cache
10
Resumo de Cache
2
2
 
0
 
1
 
2 3 4
 
5
 
6 7
 
8
 
9
1 
0
1 
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1 
9
2 
1
2
3
2
4
2
5
2
6
2
7
2
8
2 
9
2
0
MemoryMemory
Block no.
 
0
 
1
 
2 3 4
 
5
 
6 7
 
0
 
1
 
2 3 4
 
5
 
6 7
0 
0
 
1
1 
2 3
2
4
 
5
3 
6 7
CacheCache
Totalmente 
associativa
Mapeamento direto
(12 % 8) = 4
Set no.
Parc. associativa
(12 % 4) = Set 0
3
0
3 
1
Block no. Block no. Block no.
11
Memória Virtual
Memória Virtual
12
Memória Virtual
• Memória Virtual é a técnica que dá ao programador 
a ilusão de poder acessar rapidamente um grande 
espaço de endereçamento
• Objetivos da técnica:
• Permitir que haja um meio seguro e eficiente de se 
compartilhar informações, armazenadas na memória, entre 
vários programas
• Minimizar os problemas causados aos programas pela 
existência de uma pequena quantidade de memória 
principal
13
Memória Virtual
• Os programas que compartilham a memória de 
determinada máquina mudam dinamicamente 
durante o processo de execução
• Cada programa deve ser compilado usando seu 
próprio espaço de endereçamento (ou seja, em uma 
região da memória acessível somente a esse 
programa)
• A técnica de memória virtual realiza a tradução do 
espaço de endereçamento de um programa para 
seus endereços reais
14
Memória Virtual
• A técnica de memória virtual permite que o tamanho de um 
único programa exceda a quantidade total de memória real 
disponível para sua execução
• A técnica de memória virtual gerencia automaticamente os 
seguintes dois níveis de hierarquia: 
• memória principal (física)
• memória secundária
• Antigamente, os programas eram divididos em pedaços 
• Os pedaços mutuamente exclusivos (overlays) eram identificados
• Carga/exclusão de overlays da memória era realizada sob 
controle do próprio programa
15
Memória Virtual
• A memória virtual faz com que a memória principal 
funcione como uma cache para memória secundária 
(discos magnéticos)
• Vantagens:
• Ilusão de ter mais memória física
• Realocação de programa 
• Proteção entre processos
• Separação entre memória lógica e memória física:
• Memória Lógica: visão de um processo
• Memória Física: visão do processador
16
Memória Virtual x Memória Cache
17
Memória Virtual x Memória Cache
ParâmetroParâmetro Cache L1Cache L1 Memória virtualMemória virtual
Tamanho do bloco Tamanho do bloco 
(página)(página) 16-128 bytes16-128 bytes 4.096-65.536 bytes4.096-65.536 bytes
Tempo de acerto (hit)Tempo de acerto (hit) 1-3 ciclos1-3 ciclos 100-200 ciclos100-200 ciclos
Penalidade de falhaPenalidade de falha 8-200 ciclos8-200 ciclos 1 – 10 M ciclos1 – 10 M ciclos
(Acesso)(Acesso) (6-160 ciclos)(6-160 ciclos) 0,8 – 8 M ciclos0,8 – 8 M ciclos
(Transferência)(Transferência) (2-40 ciclos)(2-40 ciclos) 0,2 – 2 M ciclos0,2 – 2 M ciclos
Taxa de falhaTaxa de falha 0,1-10%0,1-10% 0,00001-0,001%0,00001-0,001%
Mapeamento de Mapeamento de 
endereçosendereços
25-45 bits de endereço 25-45 bits de endereço 
físico para 14-20 bits físico para 14-20 bits 
de endereço de cachede endereço de cache
32-64 bits de 32-64 bits de 
endereços virtuais endereços virtuais 
para 25-45 bits de para 25-45 bits de 
endereços físicosendereços físicos
18
Memória Virtual
Espaço de endereços do 
processo A
Instruções Dados Pilha
Espaço de endereços do 
processo B
Espaço de endereços do 
processo C
Memória física:Memória física:
19
Memória Virtual
• A memória principal pode agir como uma 
“cache” para o armazenamento secundário 
(HD)
• Vantagens:
– ilusão de ter mais memória física
– relocação do programa
– proteção
Physical addresses
Disk addresses
Virtual addresses
Address translation
20
Páginas: blocos de memória virtual
• Faltas de Página: o dado não está na memória, recupera-lo do disco
– penalidade imensa por falta, por isso as páginas devem ser muito 
grandes (e.g., 4KB)
– é importante reduzir as faltas de página (LRU vale o preço)
– pode-se cuidar das faltas no software em vez do hardware
– usando-se write-through é muito caro, então usamos writeback
3 2 1 011 10 9 815 14 13 1231 30 29 28 27
Page offsetVirtual page number
Virtual address
3 2 1 011 10 9 815 14 13 1229 28 27
Page offsetPhysical page number
Physical address
Translation
21
Páginas: Posicionamento da Página
• A penalidade de erro para a memória virtual é muito 
alta, pois envolve o acesso a um dispositivo de 
armazenamento magnético rotativo
• Em razão disso, para reduzir a frequência de faltas 
de páginas, os sistemas operacionais utilizam o 
esquema de posicionamento totalmente associativo
22
Páginas: Identificação da Página
• A desvantagem da escolha do posicionamento 
totalmente associativo está em localizar uma 
entrada, já que ela pode estar em qualquer lugar da 
memória virtual
• Como o espaço ocupado pela memória virtual é 
maior que aquele ocupado pela memória cache, o 
tempo de busca aumenta substancialmente
• Para contornar essa desvantagem, utiliza-se uma 
tabela de páginas,uma estrutura que indexa as 
traduções de endereços virtuais para endereços 
físicos
23
Páginas: Identificação da Página
Tabela de Página
• A tabela de páginas está armazenada na memória 
principal
• É indexada com o número da página extraído do 
endereço virtual e contém o número da página física 
correspondente
• Como cada página virtual indexa uma entrada da 
tabela de páginas, nenhuma tag é necessária
24
Tabelas de páginas
Physical memory
Disk storage
Valid
1
1
1
1
0
1
1
0
1
1
0
1
Page table
Virtual page
number
Physical page or
disk address
25
Tabelas de páginas
Page offsetVirtual page number
Virtual address
Page offsetPhysical page number
Physical address
Physical page numberValid
If 0 then page is not
present in memory
Page table register
Page table
20 12
18
31 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 0
29 28 27 15 14 13 12 11 10 9 8 3 2 1 0
26
Páginas: Substituição de Página
• Bit de validade (residência) = 0 indica falta de 
página
• Nesse caso, o SO assume o controle, por meio do 
mecanismo de exceção
• O sistema operacional precisa:
• Encontrar a página faltante no nível hierárquico inferior 
(geralmente, no HD)
• Decidir em que lugar da memória principal deve ser 
colocada a página requisitada
• O endereço virtual não informa em que posição do 
HD está a página que gerou a falta de página
27
Páginas: Substituição de Página
• O SO cria espaço em disco para todas as páginas 
virtuais de um processo, quando da criação do 
processo
• Tal espaço é conhecido como área de swap
• Nesse momento, o SO também cria uma estrutura 
de dados para controlar onde cada página virtual 
está guardada no disco
• Tal estrutura pode ser:
• Parte da tabela de páginas, ou 
• Estrutura auxiliar, indexada da mesma forma que a tabela 
de páginas
28
TLB – Translation Lookaside Buffer
• Cada acesso à memória exige, na verdade, dois 
acessos à memória principal:
• Um para obter o endereço físico (consulta à tabela de 
páginas)
• Outro para buscar a informação
• Uma alternativa para melhorar o desempenho é 
lembrar das últimas conversões de endereços, 
baseando-se no princípio da localidade
• As traduções mais recentes são guardadas em uma 
memória cache especial: Translation lookaside 
buffer (TLB)
29
TLB – Translation Lookaside Buffer
Valid
1
1
1
1
0
1
1
0
1
1
0
1
Page table
Physical page
addressValid
TLB
1
1
1
1
0
1
Tag
Virtual page
number
Physical page
or disk address
Physical memory
Disk storage
• A TLB é uma memória cache, de 16 a 512 entradas, 
acessada pelo número de página virtual
30
Tratando Faltas de Página e Falhas na TLB
Endereço virtual
TLB
Buscar pela página na 
tabela de páginas
Criar entrada na TLB, colocando o 
no. da página física que está na 
tabela de páginas
Tratar também a falta de 
página (além da falta no acesso 
à TLB)
?
falhafalha
faltafalta
(bit de validade desligado)(bit de validade desligado)
acertoacerto
(bit de validade ligado)(bit de validade ligado)
31
Tratando Faltas de Página e Falhas na TLB
• Falha na TLB pode ser tratada por SW ou por HW:
• Requer uma curta seqüência de operações para copiar 
uma entrada válida da tabela de páginas da Mem. Princ. 
para a TLB
• O tratamento de faltas de página ou falhas na TLB 
requer uso do mecanismo de exceção para:
• Interromper o processo ativo
• Transferir o controle para o SO
• Retomar a execução do processo interrompido
• Falta de página geralmente é reconhecida durante o 
ciclo de clock usado para acessar a memória
• PC é salvo no registrador especial EPC, a fim de a 
execução ser retomada a partir da instrução seguinte
32
Integração da Memória Virtual, TLBs e Caches
• Dados não podem estar na memória cache a menos 
que estejam presentes na memória principal
• Quando o SO decide migrar uma página pouco 
usada para o disco, deve garantir:
• Remoção do conteúdo de qualquer página da cache
• Modificação das tabelas de páginas e da TLB de modo que 
uma tentativa de acessar dados da página antiga gere uma 
falta de página
33
Integração da Memória Virtual, TLBs e Caches
CPU gera endereços virtuais
Está na
TLB?
Escrita?
Sim
Sim
Não
Use P como índice em uma 
tabela de páginas
Não
Está na
Tab. de Pág.?
Sim Atualizar
TLBNão
Ler página do disco
Transferir P na memória
Memória
cheia?
Não
Atualizar Tab. de 
Pág.
Atualizar 
TLB
Encontrar pág. vítima e 
escrever no disco
Sim
Próximo slide
34
Integração da Memória Virtual, TLBs e Caches
Escrita?
Bit de acesso 
ligado?
Sim
Tentar ler dados 
da cache
Não
Endereço físico
Hit? Sim
Não
Enviar dados para 
CPU
Stall para 
tratar cache 
miss
SimNão
Tentar escrever 
dados na cache
Hit?
SimNão
Escrever dados na 
cache, atualizar bit 
sujo
Stall para 
tratar cache 
miss
Exceção de 
proteção a 
escrita
35
Integração da Memória Virtual, TLBs e Caches
Cache TLB Tabela depáginas
Tradução possível?
Se sim, em que circunstâncias?
falta acerto acerto Possível, apesar de a tabela de páginas nunca ser verificada no 
caso de acerto no acesso à TLB
acerto falta acerto Faltas no acesso à TLB, mas a entrada encontra-se na tabela de 
páginas; recuperadas as informações relativas ao mapeamento da 
tabela de páginas, a informação requisitada está na cache
falta falta acerto Faltas no acesso à TLB, mas a entrada encontra-se na tabela de 
páginas; recuperadas as informações relativas ao mapeamento da 
tabela de páginas, a informação requisitada não está na cache
falta falta falta Falta no acesso à TLB seguida de uma falta de página; após 
recuperar as informações de mapeamento, deve ser 
necessariamente gerada uma falta no acesso à cache
falta acerto falta Impossível: não pode haver tradução na TLB se a página não 
está presente na memória
acerto acerto falta Impossível: não pode haver tradução na TLB se a página não 
está presente na memória
acerto falta falta Impossível: não é permitido que a informação esteja na cache se 
a página não está na memória principal
36
Sistemas Modernos
• Sistemas de memória muito complicados:
Characteristic Intel Pentium Pro PowerPC 604
Virtual address 32 bits 52 bits
Physical address 32 bits 32 bits
Page size 4 KB, 4 MB 4 KB, selectable, and 256 MB
TLB organization A TLB for instructions and a TLB for data A TLB for instructions and a TLB for data
Both four-way set associative Both two-way set associative
Pseudo-LRU replacement LRU replacement
Instruction TLB: 32 entries Instruction TLB: 128 entries
Data TLB: 64 entries Data TLB: 128 entries
TLB misses handled in hardware TLB misses handled in hardware
Characteristic Intel Pentium Pro PowerPC 604
Cache organization Split instruction and data caches Split intruction and data caches
Cache size 8 KB each for instructions/data 16 KB each for instructions/data
Cache associativity Four-way set associative Four-way set associative
Replacement Approximated LRU replacement LRU replacement
Block size 32 bytes 32 bytes
Write policy Write-back Write-back or write-through
37
• As velocidades do processador continuam a cescer muito rápido
• — muito mais rápido que DRAM ou os tempos de acesso em disco
• Desafio de projeto: lidando-se com esta crescente disparidade
• Tendências:
– SRAMs síncronas (provém um rajada dos dados)
– reprojetar os chips DRAM para prover maior bandwidth ou 
processamento
– restruturar o código para aumentar a localidade
– usar pré-busca (prefetching) ⇒ faz o cache visível para a ISA
Alguns pontos importantes
	Slide 1
	Slide 2
	Slide 3Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37