Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Organização e Arquitetura de Computadores (Unidade 05: Hierarquia de Memória)

Prof. Dr. Eng. Rafael Luiz Cancian - Organização e Arquitetura de Computadores (Unidade 05: Hierarquia de Memória) - Universidade Federal de Santa Catarina
by

Rafael Luiz Cancian

on 13 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Organização e Arquitetura de Computadores (Unidade 05: Hierarquia de Memória)

Universidade Federal de Santa Catarina
Organização e Arquitetura de Computadores
Professor Dr. Eng. Rafael Luiz Cancian
4. Hierarquia de Memória
4.1 - Introdução
4.2 - Memórias Cache
4.5 - Casos Reais
email, msn: cancian@lisha.ufsc.br
web: www.inf.ufsc.br/~cancian
2012.2
v0.20
Introdução
Todo programador deseja que o computador tenha uma quatidade praticamente ilimitada de memória muito rápida. Entretanto, na prática, esses desejos não podem ser atendidos simultaneamente por uma única memória.
4.4 - Memória Virtual
4.3 - Medindo e melhorando o
desempenho de memórias cache

Conforme um princípio de projeto, quanto
menor, mais rápido
.

Portanto, memórias grandes são lentas, e memórias rápidas são pequenas.
Embora uma única memória muito grande e muito rápida não exista, uma ilusão de uma memória desse tipo pode ser criada com
hierarquia de memória
.
Em verdade, na prática, uma memória muito grande e de acesso rápido não costuma nem ser necessária. Veja a analogia da biblioteca.
Uma biblioteca é como uma memória de quantidade quase ilimitada.
Mas quando você vai na biblioteca, quer acessar rapidamente todos os livros da biblioteca?
Se você for um humano normal, não!
Você deve querer acessar um assunto específico que precisa naquele momento. Então deve ir até
uma prateleira, pegar alguns livros que talvez sejam úteis e levá-los até a mesa onde você ficará sentado.
Depois que os poucos livros de interesse estão na mesa, você pode acessá-los bem rapidamente, sem ter que voltar às prateleiras da biblioteca.
O mesmo princípio vale para os programas. Um programa não acessa todo o seu código ou todos seus dados com probabilidade igual.
Ou seria impossível fazer acessos rápidos para a maioria da memória e ainda ter memórias grandes nos computadores.
O
princípio de localidade
estabelece que os softwares acessam uma parte relativamente pequena do seu
espaço de endereçamento
num instante qualquer.
A
localidade temporal
diz que se um item é referenciado, ele tende a ser referenciado novamente dentro de um curto intervalo de tempo.
A
localidade espacial
diz que se um item é referenciado, itens cujos endereços sejam próximos dele tendem a ser logo referenciados.
A
localidade temporal
em relação às
instruções
é aumentada com a existência de laços e sub-rotinas. Em relação aos
dados
, é aumentada pelo uso repetido das mesmas variáveis, como índices em laços.
A
localidade espacial
em relação às
instruções
é aumentada com a execução sequencial (e diminuída com desvios). Em relação aos
dados
, é aumentada com o uso de vetores, por exemplo.
Tiramos proveito do
princípio de localidade
implementando a memória de um computador como uma
hierarquia de memória
, com
vários níveis de memória
, cada um deles com tamanhos e velocidades diferentes.
CPU
Nível 1 Memória
Nível 2 Memória
...
Nível n Memória
Velocidade de acesso
Capacidade de armazenamento
Existem três principais tecnologias para a construção da hierarquia de memória:
SRAM (Static RAM)
, construída a partir de
flip-flops
. É a tecnologia mais rápida, mas também é mais cara e a que possui a menor
densidade
.
DRAM (Dynamic RAM)
, construída a partir de
capacitores
. É mais barata que a anterior e possui maior densidade de

dados, porém é mais lenta.
Disco magnético
, construido a partir de elementos magnéticos e mecânicos. Possui a maior densidade de dados e é a mais barata de todas, porém também é a mais lenta.
Essas características das diferentes tecnologias, faz com que cada uma seja usada em diferentes níveis da hierarquia de memória.
Nos níveis mais próximos do processador usa-se SRAM, nos níveis intermediários usa-se DRAM e nos níveis mais distantes usam-se discos magnéticos.
Em outras palavras: quanto mais próximo do processador, mais rápida e menor é a memória e quanto mais distante do processador, mais lenta e de maior capacidade é a memória.
Qualquer que seja a quantidade de níveis, as informações são sempre copiadas entre dois níveis adjacentes por vez. A unidade mínima de informação que pode ser transferida entre dois níveis é chamada
bloco
.
Se a informação solicitada pelo processador estiver presente no
nível superior
da hierarquia de dois níveis, ocorre um
acerto
, senão, temos uma
falta
.
Quando ocorre uma
falta
, o
nível mais baixo
é acessado para que seja possível recuperar o bloco com a informação, que é
copiado
para o
nível superior
.
A
taxa de acertos
é usada como
medida de desempenho
da hierarquia de memória. O
tempo de acerto
é gasto cada vez que ocorre um
acerto
, e corresponde principalmente ao acesso ao nível superior. A
penalidade por falta
é o tempo necessário para substituir um dos blocos do nível superior pelo bloco contendo a informação, copiado do nível inferior.
Perceba que a hierarquia de memória só faz sentido se o
tempo de acerto
for bem menor que a
penalidade por falta
e se a
taxa de acertos
for bem maior que a
taxa de faltas
.
As diferentes tecnologias garantem a primeira condição e os princípios de localidade espacial e temporal garantem a segunda.
O uso de sistemas hierárquicos significa que os programadores precisam entender seu funcionamento, de modo a colaborar na obtenção de um bom desempenho.
Na Prática
Observe os dois segmentos de código que zeram uma matriz:
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
M[i][j] = 0;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
M[j][i] = 0;
Varre a matriz pelas colunas e depois pelas linhas
Varre a matriz pelas linhas e depois pelas colunas
E faz qualquer
diferença ??
Sim, e muito.
Uma das duas versões apresenta bom desempenho na hierarquia de memória, enquanto a outra versão apresenta desempenho ruim.
Qual versão é boa e qual é ruim depende da linguagem de programação...
... e de como ela organiza matrizes na memória.
Exercícios
Num sistema hierárquico de dois níveis, o
tempo de acesso ao nível superior é de 1 ns
, enquanto a
penalidade por falta é 50ns
. Assumindo que a
taxa de acerto seja de 75%
, qual é o
tempo médio de acesso
à memória?
Ainda em relação ao exercício anterior, qual deveria ser a taxa de acerto para que o
tempo médio de acesso
à memória seja 2ns?
Memórias Cache
Cache
foi o nome escolhido para designar o
nível de memória situado entre o processador e a memória principal
, na primeira máquia comercial que implemetou esse nível extra de memória, e esse nome é usado ainda hoje.
Atualmente
existem vários níveis de memória (cache) entre o processador e a memória principal
, que são designados por seu índice; nível (level) 1:
L1
, nível 2:
L2
; nível 3:
L3
.
De maneira geral, também, a
cache L1
tem sido implementada dentro do mesmo chip do processador.
Existem
três tipos diferentes de cache
e, a exemplo do que ocorre com outros níveis de memória, cada tipo de cache é mais adequado a um determinado nível hierárquico. Contudo, todas as caches são
memórias associativas
.
As memórias associativas não são apenas arrays de dados indexados por um endereço. Nelas, o dado de determinado endereço pode estar presente ou não; Portanto, elas possuem uma estrutura mais complexa, em que os endereços e outras informações de controle também são armazenados.
Qualquer cache deve permitir sabermos se determinado byte ou palavra requisitado pelo processador está ou não na cahe e, se estiver, em qual bloco ele está.
Para resolvermos o primeiro problema, a cache precisa conter um conjunto de
rótulos
(
tags
) que contêm
informações sobre o endereço de memória a que determinado bloco da cache se refere
, e um conjunto de
bits de validade
, informando se determinado
bloco contém informação válida ou não
.
A resolução do segundo problema (localização do dado na cache) leva aos três tipos de memória cache, que variam conforme a flexibilidade no qual um dado pode ser colocado num bloco da cache.
As memórias cache podem ser:
Mapeadas diretamente
: Cada palavra
deve ser armazenada num bloco específico da cache
, que depende do seu endereço na memória principal.

É mais simples e barata, mas menos flexível e, portanto, com maior taxa de faltas.
Associativa por Conjunto
: Cada palavra
deve ser armazenada num dos blocos da cache que pertence a um conjunto específico
, que depende do seu endereço na memória principal.

É mais complexa e cara que a anterior, mas mais flexível e, portanto, com menos taxa de faltas.
Totalmente Associativas
: Cada palavra
pode ser armazenada em qualquer bloco da cache
(a quantidade de conjuntos é igual à quantidade de blocos).

É a mais complexa, cara e flexível e, portanto, com a menor taxa de faltas de todas.
Uma memória cache de mesma capacidade pode ser organizada de diferentes formas (mapeada diretamente, associativa n-conjuntos ou totalmente associativa), da seguinte maneira:
Quanto maior a associatividade de uma cache, mais flexível e a alocação de um bloco na cache e, portanto, menor a probabilidade de
falta
.
As
faltas
ocorridas num nível de memória podem ser classificadas em três categorias:
faltas compulsórias
,
faltas devidas à capacidade
e
faltas por conflitos
.
Como um
bloco
solicitado que ocasionou uma
falta
é copiado da memória principal para a cache, então, se esse bloco for solicitado novamente, ocorrerá um
acerto
.

Portanto,
toda cache tira proveito da localidade temporal.
Entretanto, se o tamanho do bloco for de apenas uma palavra, então, palavras de endereços próximos não são copiadas automaticamente. Portanto,
caches de uma palavra por bloco não tiram proveito da localidade espacial
.
Para que uma cache tire proveito da
localidade espacial
, a cache precisa ter
mais de uma palavra por bloco
, provindas de endereços consecutivos na memória.
No caso de uma
falta na cache
, seu tratamento é realizado pela
unidade de controle
do processador em conjunto com um cpntrolador separado. Deve-se
parar toda a operação do processador
, congelando o conteúdo dos registradores enquanto se espera pela informação.
As
escritas na memória
, quando há memórias cache, também merecem um pouco de atenção.
Na execução de uma instrução de
store
, o dado pode ser escrito somente na cache de dados, sem atualizar a memória, num esquema conhecido como
write-back
. Isso é rápido, mas faz com que a memória principal e a cache sejam
inconsistentes
.
No mecanismo
write-back
, os blocos da cahce possuem um bit
dirty
, que informa se o bloco foi alterado ou não.
Quando o bloco for substituído
, se ele tiver sido alterado, então
ele é primeiro copiado na memória
(nível inferior).
Uma alternativa ao
write-back
é o
write-throught
, no qual cada escrita na cache é sempre seguindo de uma escrita na memória (nível inferior). Isso evita inconsistências, mas é mais lento.
Outra alternativa é o
write-buffer
, no qual um buffer guarda o dado até ele ser escrito na memória. Após escrever o dado na cache e no buffer, o processador pode continuar a executar instruções
enquanto
o dado é escrito na memória.
Note que não faz sentido falar em "falta de escrita" na cache, já que, se o dado a ser escrito não está na cache, basta colocá-lo no bloco adequado, sem haver necessidade de acessar o nível inferior.
Quando mais de um processador pode acessar informações da mesma memória principal (caso dos
multiprocessadores
e
multicores
), então as memória cache de cada processador podem ficar inconsistente entre si.
Nessas arquiteturas, a cache é mais complexa, devendo ser uma memória
cache ativa
que implemente um
protocolo de coerência de caches
.
Por fim, o
Sistema Operacional
deve estar ciente das memória cache, e precisa de
instruções de máquina específicas
para
invalidar um bloco
ou toda a cache, o que é necessário sempre que há a
troca de contexto
de
threads
de
processos
diferentes.
Melhora do Desempenho com Memória Cache
Suponha um
processador RISC de 2,5GHz
com pipeline que (teoricamente) executa
uma instrução por ciclo de clock (CPI=1)
. Ele possui apenas uma memória principal com
barramento de 32 bits e frequência de 666MHz
, sem memória cache. Suponha ainda que
instruções de acesso à memória são 50% das instruções executadas
pelo processador.
Nesse contexto, qual é o CPI efetivo do processador?
Suponha agora que seja
incluído um nível hierárquico intermediário de memória
, operando com f
requência de 1,25GHz
e que, por sua organização interna, fornece
taxa de acerto de 95%
. Nesse contexto, qual é o CPI efetivo do processador?
Por fim, suponha que seja incluído um nível intermediário ainda mais próximo do processador (
L1)
e que, portanto,
trabalha na mesma frequência do processador
. Mesmo sendo menor, por ter uma organização mais flexível (totalmente associativo), esse nível
apresenta taxa de acerto de 97,5%
.
Nesse contexto, qual é o CPI efetivo do processador?
Portanto, a inclusão de um nível heirártquico de memória baixou o CPI de 2,5 para 1,55 e um segundo nível o baixou novamente para 1,01375, o que significa um aumento de desempenho de de 2,5154 vezes. Assim, ao invés da execução das instruções ficar 150% mais lenta apenas com memória RAM, ela ficou apenas 1,375% mais lenta quando foram adicionados dois níveis de cache.
Memória Virtual
Assim como ocorre nos níveis superiores da hierarquia de memória, a memória principal pode agir como "cache" para memória secundária.
Afinal, a quantidade de endereços de memória necessários por todos os programas que estão
executando concorrentemente
num processador pode exceder em muito a quantidade de
memória física
.
Num computador de 32 bits, apenas 4 executando de forma concorrente podem exigir até 16GB de memória principal.
Para permitir que diversos programas compartilhem a memória, é necessário implementar um mecanismo que garanta que cada programa terá acesso apenas a regiões de memória atribuídas a ele.
Embora já saibamos que apenas uma pequena fração dessa memória estará sendo efetivamente usada em qualquer instante considerado.
Mas não sabemos quais programas estarão executando, e nem em quais regiões de memória serão carregados.
Portanto, cada programa é
compilado
em seu próprio
espaço de endereçamento
, acessível somente a esse programa.
Assim, programas podem endereçar muito mais memória do que a quantidade realmente existente num computador. Dizemos que os programas operam usando
endereços virtuais
de uma
memória virtual
, que precisam ser
traduzidos
para
endereços físicos
por uma combinação de hardware e software.
O mecanismo de
memória virtual
mais simples é a
paginação
. Na paginação, o bloco é chamado
página
; Assim,
a memória é dividida em páginas de tamanho fixo
. Se a página que contém o endereço referenciado não estiver na memória física, ocorre uma
falta de página
e a memória secundária (nível inferior) precisa ser acessada e o conteúdo do bloco (página) copiado de lá.
A
penalidade por falta
na memória virtual é muito alta, e consome vários milhões de pulsos de clock. Portanto, o projeto do sistem de memória deve minimizar a
taxa de faltas de páginas
.
As principais decisões de projeto incluem:
As páginas devem ser grandes o suficiente para amortizar o alto tempo de acesso (~64KB)
A alocação de páginas na memória deve ser muito flexível, e usa-se a organização totalmente associativa.
Faltas de página são tratadas pelo software (SO), com o uso de algoritmos mais eficientes.
Write-throught reduz muito o desempenho; portanto, usa-se sempre a técnica write-back (copy-back).
Sempre que ocorre uma
falta de página
, o processador gera uma
exceção
e o
fluxo de execução
é desviado para a
rotina do sistema operacional
que trata a falta de página.
<=
Essa rotina é responsável por
localizar a página faltante no disco, copiá-la para uma página da memória física e atualizar a tabela de páginas
.
Se todas as páginas físicas estiverem ocupadas, ela é responsável também por escolher uma
página para ser substituída
(possivelmente gravá-la em disco) e que será sobrescrita com a página faltante.
Os principais
algoritmos de substituição de página
, e que tiram proveito da localidade temporal, são
LRU (Least recently Used)
e
LFU (Least Frequently Used)
.
Há um problema em consultar a
tabela de páginas
para fazer a
tradução
de cada
endereço virtual
em
endereço físico
: como essa tabela é grande, ela
reside em memória
. Portanto, para descobrir qual endereço da memória acessar, é necessário acessar a memória,
diminuindo o desempenho
.
Como é muitíssimo comum referenciar seguidamente muitos endereços da mesma página (
localidade temporal
), a tradução seria acelerada com uma
"cache" de tradução
, que informasse a
página física
das
páginas virtuais
recém acessadas.
Chamamos
TLB (Translation Lookaside Buffer)
a "cache" que
guarda os resultados da tradução de endereço
. A cada nova referência à memória, procuramos na TLB pelo número da página virtual da referência. Se houver um
acerto na TLB
, o número da
página física
correspondente é pego da TLB para formar o
endereço físico
; se houver uma
falta na TLB
, precisamos acessar a
tabela de páginas
na memória principal.
Uma vantagem da memória virtual é a
proteção
do espaço de endereçamento de cada processo, incluindo o sistema operacional. Uma vez que
cada processo tem sua própria tabela de páginas
, e páginas virtuais de processos dintintos não são mapeadas na mesma página física, torna-se impossível um processo acessar uma região de memória alocada a outro processo.
Para permitir que o sistema operacional implemente a proteção à memória, o hardware deve ser capaz de fornecer pelo menos as funções:
Suportar no mínimo dois modos de processamento, como
modo usuário
e
modo kernel
, em que
instruções privilegiadas
podem ser executadas.
Disponibilizar instruções de escrita na tabela de páginas e na TLB, que devem ser
instruções privilegiadas
.
Implementar
chamadas de sistema
e mecanismos pelo qual o processador possa alternar automaticamente entre
modo usuário
e
modo kernel.
Revisão
Exercícios
Full transcript