UNIVERSIDAD NACIONAL
MAYOR DE SAN MARCOS
Decana de America
FACULTAD DE INGENIERÍA DE
SISTEMAS E INFORMATICA
SISTEMAS DIGITALES
Mg. JUAN CARLOS GONZALES SUAREZ
2013-I
Principios Generales de las
Memorias
• Localidad
– Temporal: Datos recientes => Memorias Ràpidas
– Espacial : Datos recientes => Memorias mas cercanas
• Definiciones
– Bloque
– Block address
– Acierto (Hit)
– Tiempo de Acierto (Hit time)
– Razon de No acierto (Miss rate)
• Localidad + HW pequeño-mas rápido = Jerarquía de Memoria
– Niveles: < tamaño, > rapidez, > costo/byte que nivel bajo
– Inclusive: Datos se ubican en nivel alto como en bajo
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Tecnología de Memoria
Memoria Tiempo de acceso (ns) $ per GB
SRAM 0.2–2 $400–$1,000
DRAM 20–40 $20–$40
Magnetic disk 2,000,000–10,000,000 $0.08–$0.1
CPU
Processor
Level 1
Incremento
de tiempo
Niveles en la
de acceso
Jerarquía de Level 2 Data are transferred
desde cpu
Memoria
Level n
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Jerarquia de
Memoria Referencias
CPU 1 cycle
~1-5 cycles
L1 cache
L2 cache ~5-20 cycles
Main memory ~40-80 cycles
Clave de Estrategia de performance:
Desplazar datos e instrucciones lo mas cerca posible
del uP.
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Memoria Cache
• Son de tamaño pequeño,
• Basadas en Fast SRAM,
• Buffer entre CPU y Memoria principal (Niveles)
• Utilizan los principios de Localidad
• Son administradas por controladores
• Basadas en accesos por bloques
CPU chip
register file
L1
ALU
cache
cache bus system bus memory bus
I/O main
L2 cache bus interface
bridge memory
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Colocando una Cache L1
entre CPU and Memoria principal
Registros de CPU
Unidad de Transferencia Palabra de 4-bytes
entre registros de
CPU y cache is
Bloque de 4-bytes.
line 0 Cache L1 para
Unidad de line 1 dos bloques de 4-palabras.
Transferencia
entre Cache y RAM
es Bloque de 4
palabras block 10 abcd
(16 bytes).
...
block 21 pqrs RAM tiene
muchos bloques de 4 palabras .
...
block 30 wxyz
... Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Organiz. General una memoria Cache
1 valid bit t tag bits B = 2b bytes
Cache es un arreglo por linea por linea por boque de cache
de conjuntos(Conj.).
Cada conjunto tiene valid tag 0 1 ••• B–1
E lineas
una o mas lineas. Conj. 0: •••
por Conj.
valid tag 0 1 ••• B–1
Cada linea contine
un bloque de datos.
valid tag 0 1 ••• B–1
Conj. 1: •••
S = 2s Conj. valid tag 0 1 ••• B–1
•••
valid tag 0 1 ••• B–1
Conj. S-1: •••
valid tag 0 1 ••• B–1
Tamaño Cache : C = B x E x S bytes de dato Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Direccionando Cache
Address A:
t bits s bits b bits
m-1 0
v tag 0 1 • • • B–1
Conj. 0: •••
v tag 0 1 • • • B–1 <tag> <set index> <block offset>
v tag 0 1 • • • B–1
Conj. 1: •••
v tag 0 1 • • • B–1
••• El dato está en la
v tag 0 1 • • • B–1 cache
Conj. S-1: ••• si el tag de una línea
v tag 0 1 • • • B–1 válida en ese conjunto
coincide con el tag de
la dirección solicitada
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Cache de Mapeo Directo
• Clase más simple de Cache
• Una línea por cada conjunto.
Conj. 0: valid tag cache block E=1 lines per set
Conj. 1: valid tag cache block
•••
Conj. S-1: valid tag cache block
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Accesando una Cache de Mapeo Directo
• Selección del Conjunto
– Usa el Indice de Conjunto(set index) para la
ubicaciòn.
Conj. 0: valid tag cache block
Conj. seleccionado
Conj. 1: valid tag cache block
•••
Conj. S-1: valid tag cache block
t bits s bits b bits
00 001
m-1 0
tag set index block offset
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Accesando una Cache de Mapeo Directo
• Encontrada la línea (set index) con igual tag
se extrae el dato en base al desplazamiento (offset)
(1) =?
0 1 2 3 4 5 6 7
Conj. Selecc. (i): 1 0110 w0 w1 w2 w3
(2) = ? (3)
If (1) y (2),
Then
t bits s bits b bits cache hit, y extraigo datos
0110 i 100 desde “ block offset “
m-1 Else,
tag set index block offset 0 ir a buscar en
memoria principal.
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Cache de Mapeo Directo
3
5
4
5
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Cache de Mapeo Directo
Linea de cache
data tag
2k lines
memoria p p-k-m
Hit?
p-k-m k m
CPU
tag cache address
Dirección de Memory
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Cache de Mapeo Directo
Mem. Caché [Link] Linea Dirección
0 0 7
0 0 0 1
2
8
16
15
23
1 0 0 . .
2 0 0 Tag.0 . .
1021 8168
1022 8176
1023 8184
0 8192
1 8200
1021 0
1 0 2 8208
1022 0 0 Tag.1 .
.
.
.
1023 1 1
0 0 1021
1022
16360
16368
1023 16376
0 16384
1 16392
2 16400
VD Tag Datos (n bytes=01 pagina) Tag.2 .
.
.
.
1021 24552
1022 24560
1023 24568
Dirección: 16360 Operación: Read
003FE8h => 00000000001 1111111101 000
V D Tag Line Index Offset 0
1
4294959104
4294959112
4294959120
1 0 1 1021 0 Tag.2047
2
1021 4294967272
Dirección: 16383 Operación: Write 1022
1023
4294967280
4294967288
003FFFh => 00000000001 1111111111 111
Dirección: 24572 Operación: Read
V D Tag Line Index Offset 005FFCh => 00000000010 1111111111 100
1 1 1 1023 7 Guarda Pag.1023,Tag1 y obtiene la nueva
Dirección: 16382 Operación: Read V D Tag Line Index Offset
003FFEh => 00000000001 1111111111 110 1 0 2 1023 4
V D Tag Line Index Offset Sistemas Digitales
1 1 1 1023 6 Mg. Juan Carlos Gonzales Suárez
¿Porqué usar
los bits del medio High-Order Middle-Order
como índices? Bit Indexing Bit Indexing
0000 0000
4-line Cache 0001 0001
0010 0010
00
0011 0011
01
0100 0100
10
0101 0101
11
0110 0110
• Indexando por Bit de Mayor peso 0111 0111
– Lineas adyacentes se podrìan 1000 1000
mapear a la misma entrada de 1001 1001
cache
– Uso pobre de localidad espacial 1010 1010
1011 1011
• Indexando por bits de Orden medio 1100 1100
– Lineas consecutivas de la memoria 1101 1101
se mapean en diferente lugar en la
1110 1110
cache
– Puede mantenerse cierta regiòn en 1111 1111
un mismo tiempo Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Cache de Mapeo Asociativo
• Mas de una lìnea por conjunto
valid tag cache block
Conj. 0: E=2 lines per set
valid tag cache block
valid tag cache block
Conj. 1:
valid tag cache block
•••
valid tag cache block
Conj. S-1:
valid tag cache block
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Dieccionando en
Cache de Mapeo Asociativo
• Selección identica al mapeo direto
valid tag cache block
Conj. 0:
valid tag cache block
Conj. Selecc. valid tag cache block
Conj. 1:
valid tag cache block
•••
valid tag cache block
Conj. S-1: valid tag cache block
t bits s bits b bits
00 001
m-1 0
tag set index block offset
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Dieccionando en
Cache de Mapeo Asociativo
• Encontrada la línea (set index) con igual tag
se extrae el dato en base al desplazamiento (offset)
=1? (1) Valid bit.
0 1 2 3 4 5 6 7
1 1001
selected set (i):
1 0110 w0 w1 w2 w3
(3)
If (1) y (2),
=?
Then
(2) cache hit, y extraigo
t bits s bits b bits datos (block offset )
0110 i 100 Else,
m-1
tag set index block offset 0 ir a memoria principal.
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Mapeo de Cache Asociativo
3
1
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Mapeo de Cache Asociativo
Mem. Caché [Link] Linea Dirección
0 0 7
1 8 15
0 16 23
2
1 . .
2 Tag.0 . .
1021 8168
1022 8176
1023 8184
0 8192
1 8200
1021 2 8208
1022 Tag.1 .
.
.
.
1023 1021 16360
1022 16368
1023 16376
0 16384
1 16392
2 16400
Tag.2 .
.
.
.
VD Tag Datos(n bytes=01 pagina) 1021
1022
24552
24560
1023 24568
Dirección: 16360 Operación: Read
003FE8h => 000000000011111111101 000
V D Tag Offset 0
1
4294959104
4294959112
4294959120
1 0 2045 0 Tag.2047
2
1021 4294967272
Dirección: 16383 Operación: Write 1022
1023
4294967280
4294967288
003FFFh => 000000000011111111111 111
V D Tag Offset Dirección: 16377 Operación: Read
1 1 2045 7 003FF9h => 000000000011111111111 001
Dirección: 16382 Operación: Read V D Tag Offset
003FFEh => 000000000011111111111 110 1 0 2047 1
V D Tag Offset Sistemas Digitales
1 1 2045 6 Mg. Juan Carlos Gonzales Suárez
Example: 2-way Set Associative
Cache
tag index offset address
Valid Cache Tag Cache Data Cache Data Cache Tag Valid
Block 0 Block 0
: : : : : :
= mux =
Cache
Block
Hit
Mapeo de Cache Asociativa por conjuntos
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Algoritmos de Reemplazo
• Algoritmo implementado en Hardware (veloz)
• First in first out (FIFO)
• Least frequently used (LFU)
• Least Recently used (LRU)
• Random
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Write Strategies
• On a Hit
Write Through. Escribe en cache y memoria.
Write Back. Escribe cuando se reemplaza
página de cache.
• On a miss:
Write Allocate. Asigna linea para escritura.
Write NoAllocate. No asigna linea para escritura
• Some processors “buffer” writes.
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Metricas de Performance de Cache
• Miss Rate
– Tipico:
• 3-10% for L1
• Puede ser pequeño (e.g., < 1%) for L2, depende del
tamaño, etc.
• Hit Time
– Tipico:
• 1 ciclo de clock for L1
• 3-8 ciclo clock for L2
• Miss Penalty
– Tiempo adicional por no acierto(miss)
• Tipico 25-100 ciclos para memoria principal
• Average Access Time = Hit Time + Miss Rate * Miss Penalty
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Ejemplo: Memoria Cache Alpha 21264
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Intel Caches
• 80386 – no on chip cache
• 80486 – 8k using 16 byte lines and four way set associative
organization
• Pentium (all versions) – two on chip L1 caches
– Data & instructions
• Pentium 3 – L3 cache added off chip
• Pentium 4
– L1 caches
• 8k bytes
• 64 byte lines
• four way set associative
– L2 cache
• Feeding both L1 caches
• 256k
• 128 byte lines
• 8 way set associative
– L3 cache on chip
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Diagrama de Bloques del Pentium 4
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
PowerPC Cache Organization (Apple-
IBM-Motorola)
• 601 – single 32kb 8 way set associative
• 603 – 16kb (2 x 8kb) two way set associative
• 604 – 32kb
• 620 – 64kb
• G3 & G4
– 64kb L1 cache
• 8 way set associative
– 256k, 512k or 1M L2 cache
• two way set associative
• G5
– 32kB instruction cache
Sistemas Digitales
– 64kB data cache Mg. Juan Carlos Gonzales Suárez
Diagramas de Bloques del
PowerPC G5
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Multi-core Architecture
AMD ARCHITECTURE
L1
L2
L3
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Particionamiento Adaptativo de Cache en
modo Compartido/Privado
Cache Architecture Framework
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
Gracias
Juan Carlos Gonzales Suarez
juancgonzaless@[Link]
Example
• 32-word memory Index Valid Tag Data
• 8-word cache 000
001
• (The addresses below 010
011
are word addresses.) 100
101
110
111
Address Binary Cache block Hit or miss
22 10110 110
26 11010 010
22 10110 110
26 11010 010
16 10000 000
3 00011 011
16 10000 000
18 10010 010
Sistemas Digitales
Mg. Juan Carlos Gonzales Suárez
