Arquitectura de
Computadores II
5. Hierarquia de Memória
2004/2005
5.1. Cache
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
“O Fosso de Performance”
2
Hierarquia de Memória

Princípio da localidade espacial
“Se eu acedi a estes dados, é provável
que aceda aos dados que estão
próximos”

Princípio da localidade temporal
“Se eu acedi à pouco tempo a estes
dados, é provável que lhes vá aceder
dentro de pouco tempo”
Velocidade
Preço
Registos
~128x32bits, 0.25ns
Cache
Memória Central (RAM)
Memória de Massa (Disco)
~1MByte, 10ns
$5000/GB
~512Mbyte, 100ns
$100/GB
~200Gbyte, 5ms
$1/GB
Tamanho
3
Conceitos Básicos (Cache Directamente Mapeada)
LD
R1, 1012
Cache Directamente Mapeada
1012 MOD 8 = 4
0 1 2 3 4 5 6 7
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
Cache
...
Memória
...
Cache Hit  O bloco está na cache
Cache Miss  O bloco não está na cache
4
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Conceitos Básicos (Cache Directamente Mapeada)
LB
...
R1, 1012
Cache Line
Memória
...
5
Cache Directamente Mapeada
6
Associatividade
7
Porquê diferentes tipos de associatividade?

Directamente Mapeada



Completamente Associativa




 Rápida a aceder aos dados (só podem estar num local)
 Sempre que existe um miss, limpa a entrada correspondente
(hit rate baixo)
 Lenta a aceder aos dados (têm de se comparar todas as tags)
 Quando existe um miss, podemos escolher qual a entrada a
eliminar (hit rate elevado)
[E.g. Caches a nível do sistema operativo]
Associativa Por blocos


O melhor (e/ou pior) de ambos os mundos
[E.g. Caches no processador]
8
Uma cache associativa em blocos de 4
9
Efeito da associatividade no miss rate
15%
1 KB
12%
2 KB
9%
4 KB
6%
8 KB
16 KB
32 KB
3%
64 KB
128 KB
0
One-way
Two-way
Four-way
Eight-way
Associativity
10
Efeito do tamanho do bloco no miss rate

À medida que o tamanho do bloco aumenta...
 Localidade Espacial (reaproveitamento de dados)
 Poucos Blocos (competição pelos mesmos blocos)
 Penalidade nos misses aumenta (...o tempo de ir buscar os blocos)
11
O que acontece num cache read miss?
1.
2.
3.
Envia o endereço em falta para a memória
Ordena à memória que efectue a leitura e espera que a
mesma complete
Escreve o valor lido na cache, actualizando os dados, tag
e ligando o bit valid
No caso das caches associativas utiliza-se uma das seguintes
técnicas para seleccionar o bloco:



4.
Random
Least-Recently Used (LRU)
First-in, First-out (FIFO)
Efectivamente lê o valor, partindo da cache
12
O que acontece numa escrita?

A memória central e a cache devem de estar consistentes


Write-through: Sempre que se escreve na cache, os dados são
também enviados para a memória central





Manter ambas consistentes pode sair bastante caro...
Utilização de um write-buffer de actualização da memória central
 Simples de implementar
 Coerência de dados (importante em multi-processadores)
 Pode ser lenta, se os programas têm uma taxa de escritas superior ao
o write-buffer aguenta
Write-back: Apenas se escreve na cache; a memória central só é
actualizada quando o bloco tem de ser eliminado da cache





É necessária a presença de um dirty-bit a marcar cada entrada em cache
 Utiliza menos largura de banda com a memória (importante em multiprocessadores)
 Várias escritas num bloco apenas implicam uma escrita em memória
 Read misses podem implicar escritas em memória (e.g. se é necessário
substituir um bloco dirty)
 Escritas complicadas (e potencialmente lentas). É necessário verificar
se se trata de um hit ou miss antes de actualizar a memória; não se pode
simplesmente “escrever”. Utilização de um store-buffer.
13
Considerações sobre Memória

DRAM = Dynamic Random Access Memory



Ênfase na densidade (bits/cm^2)
Latência de acesso / Velocidade de transferência
Tem de ser refrescada periodicamente
(basta “ler” os bits de uma linha)
RAS = Row Access Strobe
CAS = Column Access Strobe
14
Evolução da tecnologia DRAM
Year
1985
1989
1992
1996
1998
2000
2002
2004
Chip Size
1 Mbit
4 Mbit
16 Mbit
64 Mbit
128 Mbit
256 Mbit
512 Mbit
1024 Mbit
$/MB
$200
$50
$15
$10
$4
$1
$0.25
$0.10
Total Access Time
(RAS + CAS)
135 ns
110 ns
90 ns
60 ns
60 ns
55 ns
50 ns
45 ns
Column Access time
for an Existing Row
(CAS)
40 ns
40 ns
30 ns
12 ns
10 ns
7 ns
5 ns
3 ns
15
Como aumentar a largura de banda com a memória?
CPU
CPU
CPU
Multiplexor
Cache
Cache
Cache
Bus
Bus
Memory
b. Wide memory organization
Memory

(a)
(b)
a. One-word-wide
memory organization
(c)
Bus
Memory
Memory
Memory
Memory
bank 0
bank 1
bank 2
bank 3
c. Interleaved memory organization
Vencer a latência de acesso é complicado; mas
é possível melhorar a largura de banda!
Abordagem assumida até agora
Bus largo, acede a todas as palavras de um
bloco simultaneamente
Interleaved memory, evita o custo da latência
de acesso (embora ainda pague o custo da
transferência dos dados)
16
Algumas técnicas para melhorar a performance
1.
Hierarquias de Caches
2.
“Requested Word First” & “Early Restart”
3.
Merge Write Buffer
4.
Victim Caches
17
Exemplos de Caches
18
Arquitectura de
Computadores II
5. Hierarquia de Memória
2004/2005
5.2. Memória Virtual
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Conceito

A memória física de um computador pode ser considerada
apenas como uma “cache” para os dados em disco

Os dados em disco correspondem à memória virtual  swap file
20
Mapeamento de endereços
Atenção: Nada obriga a que os endereços físicos tenham
o mesmo tamanho que os endereços virtuais
21
Aspecto de um sistema com memória virtual
4Gb
4Gb
Disco
5000
1000
1000
0
0
Espaço de
endereçamento
do processo A
256Mb
Espaço de
endereçamento
do processo B
Tabela(s) de
Tradução de
Endereços
0
Memória física
Nota: não existe apenas uma tabela de tradução de endereços, mas várias.
A tabela do processo corrente é carregada utilizando um registo especial
do processador
22
Considerações Importantes

O tamanho das páginas deve ser grande para amortizar o
enorme tempo de acesso ao disco


É importantíssimo baixar o miss rate


Abordagens completamente associativas
Quando existe uma page fault, a mesma é resolvida em
software e não em hardware


Hoje são tipos valores de 4KB e 16KB. Começam a surgir sistemas
de 32KB e 64KB.
O preço de resolver o problema em software é baixo comparado
com o preço de ir a disco e/ou de incorporar tal solução em
hardware. Para além disso, podem-se utilizar algoritmos mais
sofisticados em software.
Write-thought não é uma opção
23
Tabela de Páginas (1)
24
Tabela de Páginas (1)
O que é que falta neste diagrama???
25
Translation-Lookaside Buffer (TLB)
26
Exemplo de TLB+Cache (Intrinsity FastMATH)
Nota: Falta mostrar a tabela de páginas
(no caso de TLB miss)
27
Intrinsity FastMATH, c/ TLB hit
28
Vários acontecimentos possíveis
29
Alguns Exemplos de Processadores
30
AMD Athlon64 3500+ (2.2GHz)
31
Material para ler

Computer Architecture: A Quantitative Approach, 3rd Ed.





Secções 5.1, 5.2, 5.3
(Brevemente) 5.4 e 5.5
Secção 5.8 e a parte de 5.9 que diz respeito à tecnologia DRAM
Secção 5.10
Alternativamente (ou complementarmente), a matéria
encontra-se bastante bem explicada no Capítulo 7 do

Computer Organization and Design, 3rd Ed.
D. Patterson & J. Hennessy
Morgan Kaufmann, ISBN 1-55860-604-1
August 2004
32
» People who are more than casually
interested in computers should have at
least some idea of what the underlying
hardware is like. Otherwise, the
programs they write will be pretty weird «
Donald Knuth
33
Questão Interessante

Multiplicação de Matrizes, 1024x1024 INT

@XTITAN(Dual Xeon – 2 GHz)
[pmarques@ingrid ~/tmp] ./Mult 1024
Size = 1024x1024
Total time = 57 sec

@T01
(Pentium Celeron – 1 GHz)
[pmarques@t10 ~/tmp] ./Mult 1024
Size = 1024x1024
Total time = 16 sec
O que é que se passa aqui?!?!?!?!
34
Organização da Memória
[pmarques@ingrid ~/tmp] cat /proc/cpuinfo
(...)
model name
: Intel(R) XEON(TM) CPU 2.00GHz
cpu MHz
: 1993.562
cache size
: 512 KB
bogomips
: 3971.48
(...)
[pmarques@ingrid ~/tmp]
[pmarques@t01 ~/tmp] cat /proc/cpuinfo
(...)
model name
: Celeron (Coppermine)
cpu MHz
: 1002.301
cache size
: 128 KB
bogomips
: 1998.84
(...)
[pmarques@t01 ~/tmp]
35
Latência de Acesso a Memória
Celeron @ 1GHz
Xeon @ 2GHz
36
Largura de Banda de Acesso a Memória (MB/s)
Celeron @ 1GHz
Xeon @ 2GHz
37