Aula_12

Prévia do material em texto

IntroduçãoIntrodução àà
InformáticaInformática
AlexandreAlexandre MeslinMeslin
((meslinmeslin@@ncence.ufrj..ufrj.brbr))
Organização da MemóriaOrganização da Memória
zz Conceito de hierarquia de memóriaConceito de hierarquia de memória
zz MemMemóória principal e memria principal e memóórias secundrias secundááriasrias
zz Projeto lógico da memória principalProjeto lógico da memória principal
zz MemMemóóriasrias cachecache
zz MemMemóória virtualria virtual
Conceito de Hierarquia de Conceito de Hierarquia de 
MemóriaMemória
zz Memória no computadorMemória no computador
™™RegistradoresRegistradores
™™Memória principalMemória principal
™™MemóriaMemória cachecache
™™Memória ROMMemória ROM
™™Discos magnéticosDiscos magnéticos
™™Discos ópticosDiscos ópticos
™™Fitas magnéticasFitas magnéticas
Memória Memória CacheCache
zz Na aula anterior, Na aula anterior, foi vistofoi visto::
™™Memória Memória cache com cache com mapeamento diretomapeamento direto
™™Conflito Conflito de de endereços na endereços na cachecache
CacheCache com Conjunto com Conjunto 
AssociativoAssociativo
zz Semelhante ao mapeamento diretoSemelhante ao mapeamento direto
zz Bits mais baixos utilizados para selecionar linhas Bits mais baixos utilizados para selecionar linhas 
com conjuntos de 2, 4, 8com conjuntos de 2, 4, 8 ou maisou mais blocosblocos
zz Parte alta do endereço utilizada para garantir que Parte alta do endereço utilizada para garantir que 
realmente houve um acertorealmente houve um acerto
Cache com Cache com Conjunto Conjunto 
AssociativoAssociativo
zz Assumindo queAssumindo que::
™™ MemóriaMemória cache tem 2cache tem 2kk linhaslinhas
™™ BlocoBloco com 2com 2mm bytesbytes
™™ p bits dep bits de barramentobarramento de de endereçoendereço
™™ 22aa conjuntos associativosconjuntos associativos
zz Bits mais baixos utilizados para selecionar a linha daBits mais baixos utilizados para selecionar a linha da cachecache
zz Bits mais altos usados para comparar o endereço da linhaBits mais altos usados para comparar o endereço da linha
p-k+a-m mk-a
p bits
tag Endereço da
linha do cache
Endereço
do byte
CacheCache AssociativoAssociativo
zz Cache com Cache com nn conjuntos associativosconjuntos associativos
™™Cada linhaCada linha de cachede cache pode terpode ter nn blocosblocos
™™nn podepode serser pequenopequeno (2, 4, 8)(2, 4, 8)
™™Melhor desempenhoMelhor desempenho
™™Custo moderadoCusto moderado
CacheCache AssociativoAssociativo
zz ComoComo cada linha possuicada linha possui oo mesmo endereço mesmo endereço 
básicobásico ÆÆ
zz ParaPara selecionarselecionar aa linhalinha,, basta calcularbasta calcular oo seu seu 
endereendereççoo, com no, com no exemploexemplo dede mapeamento mapeamento 
diretodireto
zz DentroDentro dede uma linhauma linha,, vváários blocosrios blocos
zz ParaPara selecionarselecionar oo blocobloco,, devedeve sese eleita uma eleita uma 
polpolííticatica dede substituisubstituiçãçãoo
PolíticaPolítica dede SubstituiçãoSubstituição dede
BlocoBloco
zz FIFO (FirstFIFO (First--in, Firstin, First--out):out): primeiroprimeiro aa chegarchegar,,
primeiroprimeiro aa sairsair
™™SeSe houver blocos vazioshouver blocos vazios,, qualquerqualquer umum podepode serser
escolhidoescolhido
™™SeSe todos estiverem ocupadostodos estiverem ocupados, o, o mais antigo deve sairmais antigo deve sair
PolíticaPolítica dede SubstituiçãoSubstituição dede
BlocoBloco
zz LRU (least recently used):LRU (least recently used): menos recentemente menos recentemente 
utilizadoutilizado
™™SeSe houver blocos vazioshouver blocos vazios,, qualquerqualquer umum podepode serser
escolhidoescolhido
™™SeSe todos estiverem ocupadostodos estiverem ocupados, o, o bloco que estábloco que está aa maismais
tempotempo semsem serser utilizado será substituidoutilizado será substituido
Cache comCache com Conjunto Conjunto 
AssociativoAssociativo
dadodado tagstags dadodado tagstags
pp--kk--mm kk mm
CPUCPU
ExemploExemplo
zz Supondo memóriaSupondo memória cache com:cache com:
™™256 bytes256 bytes
™™32 bytes /32 bytes / blocobloco
™™88 linhaslinhas
™™Mapeamento diretoMapeamento direto
™™BarramentoBarramento dede endereçosendereços de 32 bitsde 32 bits
™™PalavraPalavra de dados de 32 bitsde dados de 32 bits
ExemploExemplo
zz ComportamentoComportamento de umde um programaprograma::
™™SuporSupor umum programa que inicieprograma que inicie nono endereçoendereço 00
™™Muito provavelmenteMuito provavelmente aa seqüênciaseqüência dede endereçosendereços dede
instruções seráinstruções será 0, 4, 8, 12, 16, 20, …0, 4, 8, 12, 16, 20, …
™™ InicialmenteInicialmente a cachea cache está toda vaziaestá toda vazia (bit de(bit de validade validade 
emem zero)zero)
ExemploExemplo
zz Estado inicial daEstado inicial da cache cache 
00????
00????
00????
00????
00????
00????
00????
00????
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado daEstado da cachecache depoisdepois dodo acessoacesso 0 (0 (falhafalha))
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 4 (acerto)Estado da cache depois do acesso 4 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 8 (acerto)Estado da cache depois do acesso 8 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 12 (acerto)Estado da cache depois do acesso 12 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 16 (acerto)Estado da cache depois do acesso 16 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 20 (acerto)Estado da cache depois do acesso 20 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 24 (acerto)Estado da cache depois do acesso 24 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 28 (acerto)Estado da cache depois do acesso 28 (acerto)
00????
00????
00????
00????
00????
00????
00????
1100Inst 0 Inst 0 ÆÆ 2828
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 32 (Estado da cache depois do acesso 32 (falhafalha))
00????
00????
00????
00????
00????
00????
113232Inst 32 Inst 32 ÆÆ 6060
1100Inst 0 Inst 0 ÆÆ 3232
ValidadeValidadeEndereçoEndereçoDadoDado
ExemploExemplo
zz Estado da cache depois do acesso 36 (acerto).Estado da cache depois do acesso 36 (acerto).
00????
00????
00????
00????
00????
00????
113232Inst 32 Inst 32 ÆÆ 6060
1100Inst 0 Inst 0 ÆÆ 3232
ValidadeValidadeEndereçoEndereçoDadoDado
Outro ExemploOutro Exemplo
zz Este mesmo sistema, agora somando duas Este mesmo sistema, agora somando duas 
matrizesmatrizes
zz Cada matriz ocupa 256 bytes de memóriaCada matriz ocupa 256 bytes de memória
zz Matriz 8x8 inteiros de 4 bytesMatriz 8x8 inteiros de 4 bytes
zz Observe que a distância entre as matrizes pode Observe que a distância entre as matrizes pode 
ser múltipla do tamanho do cacheser múltipla do tamanho do cache
zz Alto risco de haver conflitoAlto risco de haver conflito
Trecho do ProgramaTrecho do Programa--ExemploExemplo
Para i Para i ÅÅ 0 at0 atéé 7 fa7 faççaa
Para j Para j ÅÅ 1 at1 atéé 7 fa7 faççaa
a(i,j) a(i,j) ÅÅ b(i,j)+c(i,j)b(i,j)+c(i,j)
fim parafim para
fim parafim para
zz Este programa irá gerar (além de outros) acessos Este programa irá gerar (alémde outros) acessos 
a endereços com 256 bytes de diferença para a endereços com 256 bytes de diferença para 
acessar as matrizes b e cacessar as matrizes b e c
Estado da CacheEstado da Cache
zz No inícioNo início
00????
00????
00????
00????
00????
00????
00????
00????
ValidadeValidadeEndereçoEndereçoDadoDado
Estado da CacheEstado da Cache
zz Leitura do dado b(0, 0) (Leitura do dado b(0, 0) (falhafalha))
00????
00????
00????
00????
00????
00????
00????
11End b(0,0)End b(0,0)b(0,0)b(0,0)
ValidadeValidadeEndereçoEndereçoDadoDado
Estado da CacheEstado da Cache
zz Leitura do dado c(0, 0) (Leitura do dado c(0, 0) (falhafalha))
00????
00????
00????
00????
00????
00????
00????
11End c(0,0)End c(0,0)c(0,0)c(0,0)
ValidadeValidadeEndereçoEndereçoDadoDado
Estado da CacheEstado da Cache
zz Leitura do dado b(0, 1) (Leitura do dado b(0, 1) (falhafalha))
00????
00????
00????
00????
00????
00????
00????
11End b(0,1)End b(0,1)b(0,1)b(0,1)
ValidadeValidadeEndereçoEndereçoDadoDado
Estado da CacheEstado da Cache
zz Leitura do dado c(0, 1) (Leitura do dado c(0, 1) (falhafalha))
00????
00????
00????
00????
00????
00????
00????
11End c(0,1)End c(0,1)c(0,1)c(0,1)
ValidadeValidadeEndereçoEndereçoDadoDado
Cache com Conjunto Cache com Conjunto 
AssociativoAssociativo
zz Mesmo sistema, mesmo programa, agora com Mesmo sistema, mesmo programa, agora com 
cache com conjunto associativocache com conjunto associativo
zz Supondo memória cache com:Supondo memória cache com:
™™256 bytes256 bytes
™™32 bytes / bloco32 bytes / bloco
™™4 linhas4 linhas
™™2 ou mais conjuntos associativos2 ou mais conjuntos associativos
™™Barramento de endereços de 32 bitsBarramento de endereços de 32 bits
™™Palavra de dados de 32 bitsPalavra de dados de 32 bits
Estado da CacheEstado da Cache
zz No inícioNo início
00????00????
00????00????
00????00????
00????00????
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado b(0,0) (Leitura do dado b(0,0) (falhafalha))
00????00????
00????00????
00????00????
00????11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado c(0,0) (Leitura do dado c(0,0) (falhafalha))
00????00????
00????00????
00????00????
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado b(0,1) (acerto)Leitura do dado b(0,1) (acerto)
00????00????
00????00????
00????00????
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado c(0,1) (acerto)Leitura do dado c(0,1) (acerto)
00????00????
00????00????
00????00????
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Mais tarde…Mais tarde…
00????00????
00????00????
00????00????
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado b(1,0) (acerto)Leitura do dado b(1,0) (acerto)
00????00????
00????00????
00????00End. End. 
B(1,0)B(1,0)
b(1,0) b(1,0) 
b(1,7)b(1,7)
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Estado da CacheEstado da Cache
zz Leitura do dado c(1,0) (acerto).Leitura do dado c(1,0) (acerto).
00????00????
00????00????
00End. End. 
c(1,0)c(1,0)
c(1,0) c(1,0) 
c(1,7)c(1,7)
00End. End. 
B(1,0)B(1,0)
b(1,0) b(1,0) 
b(1,7)b(1,7)
11End. End. 
c(0,0)c(0,0)
c(0,0) c(0,0) 
c(0,7)c(0,7)
11End. End. 
b(0,0)b(0,0)
b(0,0) b(0,0) 
b(0,7)b(0,7)
Val.Val.End.End.DadoDadoVal.Val.End.End.DadoDado
Cache Totalmente AssociativoCache Totalmente Associativo
zz Pedido da CPU procurado em todo o cachePedido da CPU procurado em todo o cache
™™Se encontrar: acerto na cache (cache hit)Se encontrar: acerto na cache (cache hit)
™™Caso contrário: falha na cache (cache miss)Caso contrário: falha na cache (cache miss)
zz Todas as tags são comparadas ao mesmo tempoTodas as tags são comparadas ao mesmo tempo
zz Qualquer endereço de memória pode estar Qualquer endereço de memória pode estar 
sendo representado em qualquer linha da cachesendo representado em qualquer linha da cache
zz Evita substituição desnecessáriaEvita substituição desnecessária
Cache Totalmente AssociativoCache Totalmente Associativo
zz Política de substituiçãoPolítica de substituição
™™LRULRU
™™FIFOFIFO
zz Necessita de muitos bits adicionais de estado (na Necessita de muitos bits adicionais de estado (na 
tag)tag)
zz Custo de hardware muito altoCusto de hardware muito alto
™™Muitos comparadoresMuitos comparadores
™™Tags muito grandes (muitos bits)Tags muito grandes (muitos bits)
Cache Totalmente AssociativoCache Totalmente Associativo
Dados Tags
Política de Escrita Política de Escrita –– Write Write 
ThroughThrough
zz Write ThroughWrite Through
™™Todo acesso de escrita com acerto é feito Todo acesso de escrita com acerto é feito 
simultaneamente na cache e na memória principalsimultaneamente na cache e na memória principal
™™Se houver um acesso de escrita com falha, somente a Se houver um acesso de escrita com falha, somente a 
memória principal será modificadamemória principal será modificada
™™ Informação na memória principal está sempre Informação na memória principal está sempre 
atualizadaatualizada
™™Leitura pode ser feita em um único cicloLeitura pode ser feita em um único ciclo
™™Escrita demora o tempo de acesso à memória principalEscrita demora o tempo de acesso à memória principal
Política de Escrita Política de Escrita –– Write Write 
BackBack
zz Write BackWrite Back
™™Todo acesso de escrita com acerto é feito somente na Todo acesso de escrita com acerto é feito somente na 
cachecache
™™O que ocorre em caso de falha dependerá da política O que ocorre em caso de falha dependerá da política 
de alocação (ver mais tarde)de alocação (ver mais tarde)
™™ Informação na memória principal pode estar Informação na memória principal pode estar 
desatualizadadesatualizada
™™Leitura e escrita podem ser feitas em um único cicloLeitura e escrita podem ser feitas em um único ciclo
™™Se o Se o bloco for substituído e a sua informação estiver bloco for substituído e a sua informação estiver 
sido modificada, esta deverá ser enviada para a sido modificada, esta deverá ser enviada para a 
memória principalmemória principal
Outros Campos da TagOutros Campos da Tag
zz Bit de “dirty” (sujo)Bit de “dirty” (sujo)
zz Utilizado para controlar o estado da memória Utilizado para controlar o estado da memória 
principalprincipal
™™Coerente Coerente ÆÆ memmemóória atualizadaria atualizada
™™ Incoerente Incoerente ÆÆ memmemóória desatualizadaria desatualizada
zz Caso a memória esteja incoerente, este bit Caso a memória esteja incoerente, este bit 
indicará que o bloco na cache está sujoindicará que o bloco na cache está sujo
zz Em caso de substituição deste bloco, os dados Em caso de substituição deste bloco, os dados 
deverão ser escritos na memóriadeverão ser escritos na memória
Política de AlocaçãoPolítica de Alocação
zz O que acontece em caso de falha de escrita em O que acontece em caso de falha de escrita em 
um cache write back?um cache write back?
1.1. A informação pode ser lida da memória principal para A informação pode ser lida da memória principal para 
a cache e então modificadaa cache e então modificada
2.2. A escrita pode ser feita diretamente na memória A escrita pode ser feita diretamente na memória 
principalprincipal
Write Back x WriteThroughWrite Back x Write Through
zz Qual o melhor?Qual o melhor?
zz Write backWrite back
™™Escritas mais rápidasEscritas mais rápidas
zz Write throughWrite through
™™Bom para multiprocessamento (memória sempre Bom para multiprocessamento (memória sempre 
coerente)coerente)
™™Necessita de menos hardwareNecessita de menos hardware
Próxima AulaPróxima Aula
zz Continuação da hierarquia de memóriaContinuação da hierarquia de memória
	Introdução àInformática
	Organização da Memória
	Conceito de Hierarquia de Memória
	Memória Cache
	Cache com Conjunto Associativo
	Cache com Conjunto Associativo
	Cache Associativo
	Cache Associativo
	Política de Substituição de Bloco
	Política de Substituição de Bloco
	Cache com Conjunto Associativo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Exemplo
	Outro Exemplo
	Trecho do Programa-Exemplo
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Cache com Conjunto Associativo
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Estado da Cache
	Cache Totalmente Associativo
	Cache Totalmente Associativo
	Cache Totalmente Associativo
	Política de Escrita – Write Through
	Política de Escrita – Write Back
	Outros Campos da Tag
	Política de Alocação
	Write Back x Write Through
	Próxima Aula