1. No category

Capitulo 5: Memoria
Fundamentos de Arquitecturas de Computadores
Arquitecturas de Memoria
© 1999 M. Murdocca and V. Heuring
5-2
Contenido
5.1 Jerarquías
5.2 RAM. Memorias de Acceso Aleatorio
5.3 Organización en Circuito Integrado
5.4 Módulos comerciales
5.5 ROM. Memorias sólo-lectura
5.6 Memorias Cache
5.7 Memoria Virtual
5.8 Tópicos avanzados
5.9 Caso de estudio: Intel Pentium Memory System
1999 M. Murdocca and V. Heuring
5-3
Jerarquía
Rápida y cara
Registros
Incremento
en rendimiento
y en costo
Cache
Memoria principal
Memoria secundaria (disco)
Almacenamiento masivo (cinta)
Lenta y barata
1999 M. Murdocca and V. Heuring
5-4
Comportamiento de una celda RAM de 1 bit
Read
D Q
CLK
Select
Data
In/Out
© 1999 M. Murdocca and V. Heuring
5-5
Señales de conexión en RAM
WR
A0-Am-1
Memory
Chip
CS
© 1999 M. Murdocca and V. Heuring
D0-Dw-1
D3 D1
D2 D0
5-6
Memoria de 4 palabras
WR
4 bits x palabra
2-to-4
decoder
00
A0
A1
01
10
11
WR
Word 0
CS
WR
Word 1
CS
WR
Word 2
CS
Chip Select
(CS)
WR
CS
Word 3
Q3 Q1
Q2 Q0
© 1999 M. Murdocca and V. Heuring
5-7
Representación simplificada de 4x4 RAM
D3 D2 D1 D0
WR
A0
4×4 RAM
CS
A1
Q3 Q2 Q1 Q0
© 1999 M. Murdocca and V. Heuring
5-8
Organización de una RAM 64x1 en 2 dimensiones
Read
D Q
A0
A1
A2
Row
Decoder
Read/Write
Row
Control
CLK
Select
Data Column
In/Out Select
Celda 1-Bit
A3
A4
A5
Column Decoder (MUX/DEMUX)
Data
© 1999 M. Murdocca and V. Heuring
Two bits wide:
One bit for data and
one bit for select.
5-9
Organización de 4x8 RAM
D7 D6 D5 D4
D3 D2 D1 D0
4×4 RAM
4×4 RAM
Q7 Q6 Q5 Q4
Q3 Q2 Q1 Q0
CS
WR
A0
A1
© 1999 M. Murdocca and V. Heuring
5-10
Organización de 8x4 RAM
D3 D2 D1 D0
WR
A0
A1
4×4 RAM
CS
1-to-2
decoder
A2
0
1
CS
4×4 RAM
CS
© 1999 M. Murdocca and V. Heuring
Q3 Q2 Q1 Q0
5-11
Módulo SLIM (Single-In-Line Memory)
TI Databook
PIN NOMENCLATURE
© 1999 M. Murdocca and V. Heuring
A0-A9
CAS
Address Inputs
Column-Address Strobe
DQ1-DQ8
NC
Data In/Data Out
No Connection
RAS
Vcc
Vss
W
Row-Address Strobe
5-V Supply
Ground
Write Enable
Vcc
CAS
1
2
DQ1
A0
A1
DQ2
A2
3
4
5
6
7
A3
8
Vss
9
DQ3 10
A4
A5
DQ4
11
12
13
A6
A7
14
15
DQ5
A8
A9
16
17
18
NC
DQ6
W
19
20
21
Vss 22
DQ7 23
NC
DQ8
NC
24
25
26
RAS
NC
NC
Vcc
27
28
29
30
5-12
Como funciona una ROM ?
2-to-4
decoder
00
A0
A1
Posicion
01
10
11
almacenada
00
01
10
11
Enable
Q3
© 1999 M. Murdocca and V. Heuring
Palabra
Q2
Q1
Q0
0101
1011
1110
0000
5-13
ALU como Lookup Table (LUT)
Operando
A
Operando
B
Función
© 1999 M. Murdocca and V. Heuring
A0
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
A16
A17
Q0
Q1
Q2
Q3
Q4
Q5
Q6
Q7
A17 A16 Función
Salida
0
0
1
1
0
1
0
1
Suma
Resta
Multiplic
División
5-14
Que es una memoria cache?
CPU
400 MHz
Main
Memory
10 MHz
Bus 66 MHz
Sin cache
CPU
400 MHz
Cache
Main
Memory
10 MHz
Bus 66 MHz
Con cache
- Principio de LOCALIDAD: Una posición de memoria puede ser usada
de nuevo (localidad temporal); una posición vecina de la posición de
memoria referenciada puede ser usada inmediatamente después
(localidad espacial).
© 1999 M. Murdocca and V. Heuring
5-15
Esquema de cache con organización asociativa
Valid Dirty Tag
27
Slot 0
Block 0
Slot 1
Block 1
Slot 2
.
.
.
.
.
.
Block 128
Slot 214–1
Block 129
Cache
.
.
.
Block 227–1
Main Memory
© 1999 M. Murdocca and V. Heuring
32 words
per block
5-16
Ejemplo de Memoria Asociativa
- Un acceso a la posición (A035F014)16 es mapeado a la cache como
una palabra en memoria de 2e32. La memoria es dividida en 2e27
bloques de 2e5 (32 palabras x bloque). La cache contiene 2e14
segmentos.
Tag
Word
27 bits
5 bits
- Si la palabra direccionada está en la cache, se encontrará (14)16
la palabra de un segmento (tag) (501AF80)16. Este TAG, está formado
por los 27 bits más significativos de la dirección. Si la palabra no está en
cache, entonces el bloque corresponde a un campo del tag (501AF80)16
es "leído" de memoria dentro del segmento correspondiente en la cache,
la referencia a memoria es entonces leída de la cache.
Tag
Word
101000000011010111110000000 10100
© 1999 M. Murdocca and V. Heuring
5-17
Políticas de Reemplazo
- Cuando no hay segmentos disponibles en donde colocar un bloque es
necesario implantar un método. Este método gobierna como el
segmento es liberado para albergar el bloque nuevo.
- Los mecanismos de reemplazo son usados para esquemas asociativos
de memoria y para memoria virtual. Estos son los siguientes:
- Último recientemente empleado. "Least recently used" (LRU)
- Primero que entra/primero que sale. "First-in/first-out" (FIFO)
- El menos frecuente empleado. "Least frequently used" (LFU)
- Aleatorio. "Random"
- Óptimo. (Usado por análisis en tiempo siguiendo una estrategia para
una secuencia particular de referencias a memoria).
© 1999 M. Murdocca and V. Heuring
5-18
Esquema de Cache de Mapeo Directo
Valid Dirty Tag
13
Slot 0
Block 0
Slot 1
Block 1
Slot 2
.
.
.
.
.
.
Block 214
Slot 214–1
Cache Memory
Block 214+1
.
.
.
Block 227
Main Memory
© 1999 M. Murdocca and V. Heuring
32 words
per block
5-19
Ejemplo de mapeo directo
- Para una cache de mapeo directo, cada bloque de memoria puede ser
mapeado a un único segmento, donde cada segmento puede contener
más de 1 bloque. Considerando (A035F014)16, es mapeado a la cache
como una palabra de 2e32. La memoria es dividida en 2e27 bloques de
2e5 (32 words x bloque) y la cache contiene 2e14 segmentos.
Tag
Slot
Word
13 bits
14 bits
5 bits
- Si la referencia a memoria está en la cache, se encontrará en (14)16
del segmento (2F80)16 el cual tendrá un TAG de (1406)16
Tag
Slot
Word
1010000000110 10111110000000 10100
© 1999 M. Murdocca and V. Heuring
5-20
Cache tipo Asociativa por conjuntos
Valid Dirty Tag
14
Slot 0
Block 0
Slot 1
Block 1
Slot 2
.
.
.
.
.
.
Block 213
Slot 214–1
Block 213+1
Cache
.
.
.
Set 0
Set 1
Set 213–1
Block 227–1
Main Memory
© 1999 M. Murdocca and V. Heuring
32 words
per block
5-21
Ejemplo Asociativo por Conjuntos
• Considere un acceso a la posición con localidad (A035F014)16 es
mapeada a la cache como una palabra de 22. La memoria se divide
en 227 bloques de 25 = 32 palabras por bloque, donde hay 2 bloques
conjunto, la cache consiste de 214 segmentos:
Tag
Set
Word
14 bits
13 bits
5 bits
• Los 14 bits de la izquierda forman el campo tag, seguidos de 13 bits para
el campo del conjunto, seguido de 5 bits para el campo de la palabra:
Tag
Set
Word
10100000001101 0111110000000 10100
© 1999 M. Murdocca and V. Heuring
5-22
Escritura/lectura en Cache
Cache
Write
Cache
Read
Dato en
cache ?
Perfecto !
a CPU.
© 1999 M. Murdocca and V. Heuring
Dato no
está en
cache
Load Through:
Envío de la palabra
a la vez que que
a la cache
-oEscribe en cache
entonces envía a CPU
Dato en
cache ?
Write Through:
Escribe datos en ambos
cache y memoria
principal,
-oWrite Back: Escribe
datos a cache solamente.
Espero a la memoria princ.
hasta que la cache se haya
reemplazado (Flushed))
Dato no
está en
cache
Write Allocate: Trae
la línea a cache y
reemplaza
-oWrite No-Allocate
Actualiza unicamente
memoria principal
5-23
Hit Ratios yTiempo Efectivo de Acceso
- Hit ratio y tiempo efectivo de acceso para cache de un nivel y multinivel:
© 1999 M. Murdocca and V. Heuring
5-24
Ejemplo de Cache de Mapeo Directo
- Calcular: hit ratio y
tiempo de acceso efectivo
de un programa ejectuado
de las posiciones de
memoria 48 a 95, y
hacer un bucle 10 veces
desde la 15 a la 31.
Slot 0
Block 0
0 - 15
Slot 1
Block 1
16 - 31
Slot 2
Block 2
32 - 47
Slot 3
Block 3
48 - 63
Block 4
64 - 79
Block 5
80 - 95
- La cache de mapeo
directo es de 16 palabras
Cache
x 4 segmentos, un hit time
de 80 ns, y un miss (pérdida)
de 2500 ns. Se emplea load-through
como política de reemplazo.
La cache está inicialmente vacía.
© 1999 M. Murdocca and V. Heuring
.
.
.
Main Memory
5-25
Tabla de Eventos para un Programa
Evento Posición
1 miss
15 hits
1 miss
15 hits
1 miss
15 hits
1 miss
1 miss
15 hits
9 hits
144 hits
48
49-63
64
65-79
80
81-95
15
16
17-31
15
16-31
Total hits = 213
© 1999 M. Murdocca and V. Heuring
Tiempo
2500ns
80ns×15=1200ns
2500ns
80ns×15=1200ns
2500ns
80ns×15=1200ns
2500ns
2500ns
80ns×15=1200ns
80ns×9=720ns
80ns×144=12,240ns
Total misses = 5
Comentario
Memory block 3 to cache slot 3
Memory block 4 to cache slot 0
Memory block 5 to cache slot 1
Memory block 0 to cache slot 0
Memory block 1 to cache slot 1
Last nine iterations of loop
Last nine iterations of loop
5-26
Calculo del Hit Ratio and Tiempo efectivo
de acceso para un Programa ejemplo
© 1999 M. Murdocca and V. Heuring
5-27
Algoritmo Neat Little LRU
Cache slot
• Se muestra una secuencia para el algoritmo Neat Little LRU y una cache
con 4 segmentos. Los bloques de memoria principal se accedene
en la secuencia: 0, 2, 3, 1, 5, 4.
Cache slot
0 1 2 3
0 0 0 0 0
1 0 0 0 0
2 0 0 0 0
0 1 2 3
0 0 1 1 1
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
3 0 0 0 0
Initial
0
1
2
3
0
0
0
1
1
1
1
0
1
1
2
0
0
0
1
0, 2, 3
© 1999 M. Murdocca and V. Heuring
3
0
0
0
0
0
1
2
3
0
0
1
1
1
0
0 0
1 0
2 1
1
1
0
1
2
0
1
0
1
0, 2, 3, 1
3
0
1
0
0
3
1
0
1
3 0 0 0 0
Block accesses: 0
1
0
0
0
0
2
0
0
0
0 1 2 3
0 0 1 1 1
1 0 0 1 1
2 0 0 0 0
3 0 0 1 0
0, 2, 3, 1, 5
0, 2
0
1
2
3
0
0
0
1
0
1
1
0
1
0
2
0
0
0
0
3
1
1
1
0
0, 2, 3, 1, 5, 4
5-28
Overlays
• Partición de un grafo para un programa principal y 3 subrutinas:
Compiled program Physical Memory
A
Main
Main Routine
Partition #0
Subroutine A
Smaller
than
program
C
B
Partition #1
Subroutine B
Partition graph
Subroutine C
© 1999 M. Murdocca and V. Heuring
5-29
Memoria Virtual
• La memoria virtual es almacenada en una imagen del disco duro.
La memoria mantiene un pequeño número de páginas virtuales en
bloque físicos de memoria.
• Mapeo de memoria virtual en memoria física:
Virtual
addresses Virtual memory
0 - 1023
Page 0
1024 - 2047
Page 1
2048 - 3071
Page 2
Page frame 0
3072 - 4095
Page 3
Page frame 1 1024 - 2047
4096 - 5119
Page 4
Page frame 2 2048 - 3071
5120 - 6143
Page 5
Page frame 3 3072 - 4095
6144 - 7167
Page 6
7168 - 8191
Page 7
Principles of Computer Architecture by M. Murdocca and V. Heuring
Physical
Physical memory addresses
0 - 1023
© 1999 M. Murdocca and V. Heuring
5-30
Tabla de Paginación
• La paginación mapea una tabla entre la memoria virtual y
la memoria física.
Present bit
Page frame
Page #
Disk address
Bit de presencia:
0: La página no está en
la memoria física.
1: La página está en
la memoria.
0 1 01001011100 00
1 0 11101110010 xx
2 1 10110010111 01
3 0 00001001111 xx
4 1 01011100101 11
5 0 10100111001 xx
6 0 00110101100 xx
7 1 01010001011 10
© 1999 M. Murdocca and V. Heuring
5-31
Usando una Tabla de Páginación
• Una dirección virtual se convierte en una dirección física de memoria:
Page
Offset
100 1101000101
0
1
2
3
4
1
0
1
0
1
01001011100
11101110010
10110010111
00001001111
01011100101
5 0 10100111001
6 0 00110101100
7 1 01010001011
Page table
© 1999 M. Murdocca and V. Heuring
Virtual address
00
xx
01
xx
11
xx
xx
10
11 1101000101
Physical address
5-32
Paginación
(continuación)
0
1
2
3
4
5
• La tabla cambia 6
cuando se ejecuta 7
0 01001011100 xx
1 11101110010 00
0 10110010111 xx
0 00001001111 xx After
fault on
0 01011100101 xx page #1
0 10100111001 xx
0 00110101100 xx
0 01010001011 xx
0
1
2
3
0 01001011100 xx
1 11101110010 00
1 10110010111 01
5
6
7
0 00001001111 xx After
fault on
0 01011100101 xx page #2
0 10100111001 xx
0 00110101100 xx
0 01010001011 xx
0
1
2
3
4
0
0
1
1
1
4
un programa.
• Inicialmente está
la tabla vacía. En
el proceso de configuración, 4 pags.
están en memoria
física.
© 1999 M. Murdocca and V. Heuring
0
1
0 01001011100 xx
1 11101110010 00
2
3
1 10110010111 01
1 00001001111 10 After
fault on
0 01011100101 xx page #3
0 10100111001 xx
4
5
6
7
0 00110101100 xx
0 01010001011 xx
5
6
7
01001011100
11101110010
10110010111
00001001111
01011100101
1 10100111001
0 00110101100
0 01010001011
xx
xx
01
10
Final
11
00
xx
xx
5-33
Segmentación
• Un segmento de memoria permite a dos usuarios compartir la misma
palabra de memoria en el código, con diferente espacio de datos:
Segment #0
Execute only
Used
Segment #1
Read/write by
user #0
Used
Segment #2
Read/write by
user #1
Used
Free
Free
Unused
© 1999 M. Murdocca and V. Heuring
Address space for
code segment of
word processor
Data space
for user #0
Data space
for user #1
5-34
Fragmentación
• (a) Free area
of memory
after initialization; (b)
after fragmentation;
(c) after coalescing.
1999 M. Murdocca and V. Heuring
Operating
System
Operating
System
Program A
Program A
Free Area
Free Area
Program B
Program B
Free Area
Free Area
Program C
Program C
Free Area
Free Area
Free Area
Dead Zone
Dead Zone
Dead Zone
I/O Space
I/O Space
I/O Space
(a)
(b)
(c)
Operating
System
Free Area
5-35
Translation Lookaside Buffer (TLB)
- Ejemplo de TLB con 8 entradas para un sistema de 32 paginas
virtuales y 16 paginas físicas.
Valid
Virtual page
number
Physical
page number
1
01001
1100
1
0
0
10111
---------
1001
-------
1
0
1
01110
----00110
0000
---0111
0
-----
----
© 1999 M. Murdocca and V. Heuring
5-36
Decodificador 3-Variables
- Cuidado !! el tamaño
no es expandible debido
a las cargas "fan-in" x linea.
El aumento de una línea
duplica el tamaño del
decodificador.
a0
a1
d0
d1
d2
a2
d3
d4
d5
d6
d7
© 1999 M. Murdocca and V. Heuring
5-37
Decodificiador - 3 Variables
- Un árbol de decodificación es necesario para gobernar grandes bloques.
Se ajusta el "fan-out", de acuerdo a la profundidad de niveles.
Fan-out
buffers
a0
d0
a0
d0
d1
a1
d2
d3
a2
(a)
© 1999 M. Murdocca and V. Heuring
d1
a1
d2
d3
a2
d4
d4
d5
d5
d6
d6
d7
d7
(b)
5-38
Arbol de decodificación. Un único nivel a la vez
- Arbol de decoficación para una RAM de 16 palabras:
1011
0___
1___
Level 0
00__
01__
10__
11__
Level 1
000_
001_
010_
011_
100_
101_
110_
111_
Level 2
Level 3
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
© 1999 M. Murdocca and V. Heuring
5-39
Content Addressable Memory (CAM)
- Relación entre RAM y CAM
Address
Value
Field1
Field2
Field3
0000A000
0000A004
0000A008
0000A00C
0000A010
0000A014
0000A018
0000A01C
0F0F0000
186734F1
0F000000
FE681022
3152467C
C3450917
00392B11
10034561
000
011
149
091
000
749
000
575
A
0
7
4
E
C
0
1
9E
F0
01
00
FE
6E
50
84
32 bits
32 bits
12 bits
4 bits
8 bits
Random access memory
© 1999 M. Murdocca and V. Heuring
Content addressable memory
5-40
Arquitectura CAM
Central
Control
Comparand
© 1999 M. Murdocca and V. Heuring
Cell 0
T0
Cell 1
T1
Cell 2
T2
Cell 4095
T4095
Data Gathering Device
Mask
Information and Commands
• Source: (Foster,
C. C., Content
Addressable
Parallel Processors, Van
Nostrand
Reinhold Company, 1976.)
5-41
Arboles de direccionamiento para CAM
Data: four bits
per channel
Control: one bit
per channel
4
4
4
4
4
4
© 1999 M. Murdocca and V. Heuring
4
4
4
4
4
4
4
4
4
4
4
5-42
Memoria RAM doble Lectura
D0 – D7
Data In
20
A Address
A0 – A19
220 Word ×
8 bits
8
Port A
A RAM
WR
CS
20
A Address
Data In
A0 – A19
220 Word ×
8 bits
20
20
B Address
B RAM
WR
CS
B0 – B19
WR
CS
© 1999 M. Murdocca and V. Heuring
8
Port B
5-43
Intel Pentium Memory System
Pentium Processor Chip
CPU
256
Level 1
Instruction
Cache
8 KB TLB
Level 1
Data Cache
8 KB
TLB
© 1999 M. Murdocca and V. Heuring
n
Level 2
Cache
Up to
512KB
Main Memory
Up to 8GB
n