Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
William Stallings
Arquitetura e Organização de Computadores
Capítulo 05
Organização Hierárquica de Memória
2
Características do Sistema de Memória
Localização (CPU, Interna, externa)
Capacidade (Tamanho da palavra, número de palavras)
Unidade de Transferência (palavra, bloco)
Método de Acesso (seqüêncial, direto, aleatório, associativo)
Desempenho (tempo de acesso, tempo de ciclo, taxa de transferência)
Tipo Físico (semicondutor, superfície magnética)
Características Fisicas (volátil, não volátil , apagável ou não)
Organização
3
Localização
CPU
Interna
Externa
4
Capacidade
Tamanho da palavra
A unidade natural da organização..
Quantidade de Palavras
ou Bytes
5
Unidade de Transferência
Interna
Usualmente governada pela largura do barramento de dados.
Externa
Usualmente um bloco que é muito maior que uma palavra.
Unidade Endereçável
Menor localização que pode ser unicamente endereçada.
Internamente o endereçamento é feito por palavras.
Em unidades de discos, blocos denominados clusters.
6
Métodos de Acesso (1)
Sequencial
O acesso deve ser feito em uma sequencia linear específica.
O tempo de acesso depende da localização dos dados e da localização anterior.
ex. unidade de fita (tape).
Direto
Blocos individuais tem endereços únicos.
O acesso é feito por um salto de aproximação seguido por acesso sequencial.
O tempo de acesso depende da localização e da localização anterior.
ex. discos
7
Métodos de Acesso (2)
Aleatório (Random)
Endereços individuais identificam localizações de maneira exata.
O tempo de acesso é independente da localização ou do acesso anterior.
ex. RAM
Associativa
Dados são localizados através de uma comparação com o conteúdo de uma porção do armazenador.
O tempo de acesso é independente da localização ou do acesso anterior.
ex. cache
8
Hierarquia de Memória
Registradores
na CPU
Interna ou Memória principal
Pode incluir um ou mais níveis de cache
“RAM”
Memória Externa
Armazenador secundário (backing store)
9
Parâmetros de Desempenho
Tempo de acesso
Tempo decorrido entre a apresentação do
endereço e a obtenção do dado válido.
Tempo do Ciclo de Memória.
Tempo requerido pela memória para
recuperação, antes do próximo acesso.
Tempo de ciclo é
✓ tempo de acesso + recuperação.
Taxa de Transferência
Taxa em que os dados podem ser movidos.
10
Tipos Físicos
Semicondutor
RAM
Magnético
Disk & Tape, flash memory
Ótico
CD & DVD
Outros
Magneto-optical
Bubble
Hologram
11
Características Físicas
Declínio (Decay)
Volatilidade (Volatility)
Apagável (Erasable)
Consumo de Energia
12
Objetivos de projeto de um sistema de memória
Prover capacidade de armazenagem
com nível desempenho aceitável
a um custo razoável
13
Quatro maneiras para alcançar o objetivo
Usar uma estrutura hierárquica de módulos de
armazenagem.
Desenvolver métodos de alocação de espaço
automático para uso eficiente da memória.
Através de técnicas de memória virtual, liberar o
usuário das tarefas de gerenciamento de memória.
Projetar a memória e sua estrutura de interconexão
relacionada de maneira que o processador possa
operar a uma taxa máxima ou próxima.
14
Lista Hierárquica
Registers
L1 Cache
L2 Cache
Main memory
Disk cache
Disk
Optical
Tape
15
Exemplo:
Sistema de memória em
dois níveis
Tempo de acesso do nível
um é de 1us
Tempo de acesso do nível
dois é de 10us
Tempo médio de acesso =
H(1) + (1-H)(10) us
H --> taxa de acerto
(hit ratio)
16
Organização hierárquica: Cache & RAM
Pequena quantidade de memória rápida.
Localizado entre a memória principal e a CPU.
Pode estar localizado internamente ao chip da CPU ou em um módulo externo.
17
Estrutura RAM/Cache
Cache ==> C blocos
Bloco ==> K palavras
RAM ==> 2n palavras
M = 2n/ K
C << M
18
Operação do Cache - Revisão
CPU faz referência ao conteúdo (dados) de uma determinada posição de memória.
Primeiro, efetua consulta ao cache.
Se presente, obtém do cache (rápido).
Se não presente, transfere o bloco requerido da memória principal para o cache.
Finalmente, transfere do cache para a CPU.
O cache inclui etiquetas para identificar qual bloco de memória principal está em cada seção do cache.
19
Operação de leitura do cache
20
Organização Típica do Cache
21
Endereçamento dos caches
Memória Virtual
Facilidade que permite aos programas endereçar memória de um ponto de vista lógico, sem considerar a quantidade de memória física disponível.
Quando usada, os campos de endereços de uma instrução de máquina (assembly) conterá endereços virtuais.
Nas operações de leitura e escrita da memória, um mecanismo de hardware (memorymanagement unit - MMU) traduz cada endereço virtual para um endereço físico da memória principal.
22
Logical
and
Physical
Caches
23
24
Elementos de Projeto da Cache
Tamanho da cache
Função de Mapeamento
Direto
Associativo
Associativo por Conjuntos
Algoritmo de Substituição
LRU, FIFO, LFU, Random
Política de Escrita
Write through
Write back
Write once
Tamanho do Bloco
Número de Caches
Single- or two-level
Unified or split
❑ Cache Size
❑ Mapping Function
❑ Replacement Algorithm
❑ Write Policy
❑ Block Size
❑ Number of Caches
25
O tamanho importa
Custo
Mais cache, maior é o custo.
Velocidade
Quanto maior for o cache, maior é a velocidade obtida (até certo ponto).
Efetuar consultas de dados no cacheconsome tempo.
Nota: Gostaríamos que o tamanho da cache fosse suficientemente pequeno, tal que, o custo médio global por bit fosse próximo do custo da memória principal e com capacidade grande o suficiente, de forma que o tempo de acesso médio global fosse próximo ao tempo do cache.
26
Função de Mapeamento
Como há um número menor de linhas cache em relação ao número de blocos da memória principal, um algorítmo faz-se necessário para mapear blocos de memória para linhas cache. Além de uma maneira para descobrir qual bloco da memória principal, em determinado momento, ocupa uma linha cache.
A escolha da função de mapeamento determina como o cache está organizado.
Três técnicas podem ser utilizadas:
direto, associativo e associativo por conjuntos
Configuração para análise: Cache de 64 KByte
Bloco Cache de 4 bytes
✓ isto é, o cache tem 16k (214) linhas de 4 bytes
Memória principal de 16MBytes
Endereços de 24 bits
✓ (224=16M)
27
28
Mapeamento Direto - Direct Mapping
Cada bloco da memória principal mapeia sempre
em uma única linha cache.
isto é, se um bloco está no cache, ele deve estar em um
local específico.
O endereço é dividido em duas partes
Os w bits menos significativos identificam uma
única palavra.
Os s bits mais significativos especificam um bloco
de memória.
Os MSBs são divididos em um campo r na linha de
cache e uma etiqueta (tag) com os s-r bits (mais
significativos)
29
Mapeamento Direto - Estrutura de Endereço
Endereço de 24 bits
Identificador de palavra → 2 bits (4 bytes por bloco)
Identificador de bloco → 22 bits
8 bit tag (= 22-14)
14 bits slot ou linha
Dois blocos na mesma linha não tem a mesma etiqueta (tag)
A consulta à conteúdo da cache é feita em dois passos: primeiro,
identifica a linha cache e, segundo, testa a etiqueta (tag)
Tag s-r Line or Slot r Word w
8 14 2
30
Mapeamento Direto - Cache Line Table
O mapeamento é expresso como:
i = j modulo m
onde i = número da linha cache
j = número do bloco da memória principal
m = número de linhas do cache
Cache line Main Memory blocks held
0 0, m, 2m, 3m…2s-m
1 1,m+1, 2m+1…2s-m+1
...
m-1 m-1, 2m-1,3m-1…2s-1
31
Organização do Cache com Mapeamento Direto
32
Exemplo de Mapeamento Direto
33
Mapeamento Direto pros & cons
Simples
Baixo custo (Inexpensive)
Localização fixa para um dado bloco
Se um programa acessa dois blocos que
mapeiam para a mesma linha cache
repetidamente, é grande o número de faltas de
cache.
34
Mapeamento Associativo - Associative Mapping
Um bloco da memória principal pode ser carregado
em qualquer linha cache.
Endereços de memória são interpretados como
uma etiqueta (tag) e palavra.
A etiqueta unicamente identifica um bloco de
memória.
Toda etiqueta (tag) da linha cache é examinada
por comparação (match)
Pesquisar o cache é uma operação de alto custo.
35
Organização do cache totalmente Associativo
36
Exemplo de Mapeamento Associativo
37
Tag 22 bitsWord
2 bits
Mapeamento Associativo - Estrutura de Endereço
Etiqueta (tag) de 22 bits armazenada em cada bloco de dados
de 32 bits.
Compara o campo Tag com cada entrada no cache para
verificar se há um acerto (hit).
Os dois bits menos significativos do endereço identificam qual
palavra de 16 bits é requerida do bloco de dados de 32 bits.
exemplo:
Address Tag Data Cache line
FFFFFC FFFFFC 24682468 3FFF
38
Mapeamento Associativo por Conjuntos
O cache é dividido em conjuntos;
Cada conjunto contém um certo número de linhas;
Um determinado bloco mapeia para qualquer linha
de um conjunto.
ex. o bloco Bj pode estar em qualquer linha do conjunto i
ex.: 2 linhas por conjunto
✓2 way associative mapping
✓Um dado bloco pode estar em uma linha de duas
possíveis de um determinado conjunto.
39
Two Way Set Associative Cache Organization
40
Set Associative Mapping - Address Structure
Utiliza o set field para determinar o conjunto
cache alvo da busca.
Compara o campo tag para verificar a presença.
exemplo:
Address Tag Data Set number
1FF7FFC 1FF 12345678 1FFF
0017FFC 001 11223344 1FFF
Tag 9 bit Set 13 bitWord
2 bit
41
Two Way Set Associative Mapping Example
42
Algoritmo de Substituição (1) Mapeamento Direto
Nenhuma escolha.
Cada bloco tem mapeamento em uma única
linha cache.
Substitua esta linha.
43
Algoritmo de Substituição (2)Associativo & Associativo por Conjuntos
Algoritmo implementado em hardware (speed)
Least Recently Used (LRU)
ex.: in 2 way set associative
qual dos dois blocos é o menos recentemente usado (lru)?
First-in, first-out (FIFO)
substitua o bloco que está no cache a mais tempo.
Least frequently used
substitua o bloco que teve poucas referências no último intervalo de
tempo.
Random
44
Política de Escrita - Write Policy
Não deve sobrescrever o bloco cache a não ser que
a memória principal esteja atualizada.
Múltiplas CPUs devem ter módulos caches próprios.
Controladoras de I/O podem endereçar memória
principal diretamente.
45
Write through
Todas as escritas são efetuadas simultaneamente
na cache e memória principal.
Múltiplas CPUs podem monitorar o tráfego da
memória principal para manter a cache local (a
CPU) atualizada.
Gera muito tráfego.
Atrasa as escritas.
46
Write back
Inicialmente, as atualizações são realizadas
somente na cache.
Cada slot cache possui um update bit que são
configurados quando uma atualização ocorre.
Caso o bloco venha ser substituido, uma escrita na
memória principal é feita se o update bit sinalizar.
Outros caches estarão fora de sincronismo.
E/S deverá acessar memória principal através da
cache.
Nota: 15% das referências a memória são escritas.
Line Size
When a block of data is retrieved and placed in the cache not only the desired word but
also some number of adjacent words
are retrieved
As the block size increases the hit ratio will at first
increase because of the principle of
locality
As the block size increases more useful data are
brought into the cache
The hit ratio will begin to decrease
as the block becomes bigger
and the probability of using the newly
fetched information
becomes less than the probability of
reusing the information that
has to be replaced
Two specific effects come into play:
• Larger blocks reduce the number of blocks that fit into a cache
• As a block becomes larger each additional word is farther from the requested word
+Multilevel Caches
◼ As logic density has increased it has become possible to have a cache on the same chip as the processor
◼ The on-chip cache reduces the processor’s external bus activity and speeds up execution time and increases overall system performance
◼ When the requested instruction or data is found in the on-chip cache, the bus access is eliminated
◼ On-chip cache accesses will complete appreciably faster than would even zero-wait state bus cycles
◼ During this period the bus is free to support other transfers
◼ Two-level cache:
◼ Internal cache designated as level 1 (L1)
◼ External cache designated as level 2 (L2)
◼ Potential savings due to the use of an L2 cache depends on the hit rates in both the L1 and L2 caches
◼ The use of multilevel caches complicates all of the design issues related to caches, including size, replacement algorithm, and write policy
Hit Ratio (L1 & L2)
For 8 Kbyte and 16 Kbyte L1
+Unified Versus Split Caches
◼ Has become common to split cache:
◼ One dedicated to instructions
◼ One dedicated to data
◼ Both exist at the same level, typically as two L1 caches
◼ Advantages of unified cache:
◼ Higher hit rate
◼ Balances load of instruction and data fetches automatically
◼ Only one cache needs to be designed and implemented
◼ Trend is toward split caches at the L1 and unified caches for higher levels
◼ Advantages of split cache:
◼ Eliminates cache contention between instruction fetch/decode unit and execution unit
◼ Important in pipelining
Pentium
4
Cache
Table 4.4 Intel Cache Evolution
Pentium 4 Block Diagram
Pentium 4 Cache Operating Modes
Note: CD = 0; NW = 1 is an invalid combination.
Table 4.5 Pentium 4 Cache Operating Modes
ARM Cache Features
Table 4.6 ARM Cache Features
ARM Cache and Write Buffer Organization