Download ©Mario Medina C. 1

Sistemas computacionales
Procesador
Sección de
Control
Memorias y Cache
Sistemas Computacionales
Mario Medina C.
mariomedina@udec.cl
Entrada
Memoria
Sección de
Datos
Salida
Š Sistema de memoria
z
z
Almacena datos e instrucciones durante ejecución
Incidencia dramática en desempeño del sistema global
œ Ejecución de código accesa memoria de instrucciones
œ Instrucciones movl, pushl, popl accesan memoria de datos
Modelo de memoria
Jerarquía de memoria
Š Modelo de memoria utilizado hasta ahora
z
z
z
Vector lineal de bytes
Almacena datos e instrucciones
Tiempo de acceso constante a cualquier posición
Š En la práctica, memoria está compuesta por
una jerarquía de dispositivos con diferentes
z
z
z
capacidades
costos
tiempos de accesos
Jerarquía de memoria
Š Requerimientos
z
z
z
Capacidad
Tiempo de acceso
Costo
Entregar gran cantidad de memoria,
permitida por tecnología más barata
Proveer alta velocidad de acceso, permitido
por tecnología más rápida
“El tiempo de acceso más rápido posible al
costo más barato posible”
Jerarquía de memoria
Š Principio de funcionamiento
z
Jerarquía de almacenamiento de creciente
tamaño y tiempo de acceso
œMientras más grandes, más lentas
z
Niveles más rápidos de la jerarquía contienen
una copia del subconjunto de datos más
utilizados de los niveles de mayor tamaño
œPrincipio de inclusión
©Mario Medina C.
1
Principio de inclusión
Nivel k:
4
9
14
3
Dispositivo más rápido, pequeño
y caro en nivel k almacena un
subconjunto de los bloques del
nivel k+1
Jerarquía de memoria
Š Registros en la CPU
Š Memoria RAM (Random-Access Memory)
z
z
Los datos se transfieren entre niveles
en bloques
z
RAM estática (Static RAM ó SRAM)
RAM dinámica (Dynamic RAM ó DRAM)
ROM (Read-Only Memory)
Š Almacenamiento secundario
0
1
2
4
5
6
7
8
9
10
11
12
13
14
15
Nivel k+1:
z
3
Dispositivo más grande, barato y
Lento del nivel k+1 está dividido en
bloques
z
z
Š Almacenamiento terciario (off-line)
z
Registros
Š Registros
z
z
z
z
z
z
z
Š Almacena un bit en una celda biestable
Internos al chip
Rápidos (a la velocidad de la CPU)
Pocos (Pentium 4 tiene 128)
Elementos individuales
Escritura sincronizada por reloj
Muy alta velocidad y baja densidad
Utilizados en banco de registros: múltiples puertas
de lectura y escritura
z
z
z
Š Almacena bit como carga en un capacitor
z
Sólo 1 transistor y 1 capacitor por bit
Capacitor necesita ser refrescado ~8ms
Sensibles a perturbaciones como luz y ruido
Š Memoria puede ser muy densa
z
Organizada como matriz de filas y columnas
Š Utilizada para memoria principal y gráfica
z
Circuito de 6 transistores por bit
Consume más energía que DRAM
Mantiene el estado del bit mientras tenga energía
Š Memoria más rápida y cara que DRAM
Š Tiempo de acceso cercano a TCPU
z
Organizada como vector
Š Utilizada en memorias cache
Memoria dinámica (DRAM)
z
Medios magnéticos y/o ópticos
Memoria estática (SRAM)
z
z
Medios magnéticos y/o ópticos
Memorias Flash
Memoria en la nube?
Tanto dentro como fuera del chip
Memorias cache
Š Memorias intermedias entre la CPU y la
memoria RAM principal
z
Almacenan bloques de las instrucciones y datos
más frecuentemente usados
Š Aprovechan el principio de localidad
z
z
Base del diseño de sistemas computacionales
Localidad temporal y espacial
Algunas utilizan códigos correctores de errores
Š Tiempo de acceso cercano a 10xTCPU
©Mario Medina C.
2
Principio de localidad
Probabilidad
de referencia
Principio de localidad
Š Localidad espacial
z
0
Espacio de direcciones
2n - 1
z
Š Localidad temporal
Ejemplo: instrucción en lazo iterativo se lee varias
veces, variables se reutilizan
Mantener los datos referenciados más
recientemente cerca del procesador
z
z
A CPU
Desde CPU
Ejemplo de localidad espacial
int sumaVector(int v[n]) {
int i, suma = 0;
for (i = 0; i < n; i++){
suma += v[i];
}
return suma;
}
Patrón de acceso secuencial
Š Localidad temporal en suma e i
z
Cada elemento de v[] es accesado sólo una vez
Š Localidad temporal y espacial en instrucciones
Š Acierto (Hit): dato presente en bloque de nivel
superior
z
Tasa de acierto (Hit rate): fracción de accesos a
memoria encontrados en nivel superior
Tiempo de acierto (Hit time): tiempo de acceso al
nivel superior
œtiempo de acceso a memoria + tiempo para la
determinación del acierto
©Mario Medina C.
Nivel k+1
de memoria
Bloque X
Bloque Y
Ejemplo de localidad espacial
Š Localidad temporal en i, j, suma
Š No hay localidad temporal en a[][]
z
Cada elemento de a[][] es accesado sólo una vez
Š Localidad espacial en a[][]
Terminología
z
Nivel k
be memoria
int sumaFilas(int a[m][n]) {
int i, j, suma = 0;
for (i = 0; i < m; i++){
for (j = 0; j < n; j++) {
suma += a[i][j];
}
}
return suma;
}
Š Localidad espacial en v[]
z
Ejemplo: Leer instrucción N, luego N+1, luego
N+2, etc., elementos de un vector
Mover bloques de datos contiguos a los niveles
superiores de la jerarquía de memoria
Terminología
Š Fallo (Miss): dato debe traerse de bloque de
nivel inferior
z
z
z
Tasa de fallas (Miss rate): 1 – (Hit rate)
Penalidad de fallo (Miss Penalty): tiempo para
reemplazar el bloque en nivel superior + tiempo para
entregar dato a CPU
Generalmente, se da que
Tiempo de acierto << penalidad de fallo
3
Memorias cache
Š Primer nivel en la jerarquía de memoria
z
z
z
Accesada en ciclo Fetch y Write Back
Típicamente en el mismo chip del procesador
Varios niveles: L1, L2, a veces L3
Principio de funcionamiento
Š Secuencia de acceso a memoria
z
z
z
Š Tiempo de acceso compatible con velocidad CPU
z
z
Pequeña y rápida
1-3 ciclos para cache L1
z
Š Objetivo
z
Procesador genera dirección efectiva del dato
Dato se busca primero en memoria cache
Si dato se encuentra en el cache (acierto), se
entrega al procesador
Si dato no se encuentra en el cache (fallo), se
busca en el siguiente nivel de la jerarquía de
memoria (ej. DRAM)
Mantener el subconjunto de datos más utilizado por el
programa dentro del cache
Principio de funcionamiento
Š Aprovechar localidad temporal
z
z
Si dato no se encuentra en el cache, traerlo al
cache desde DRAM
Porque es probable que se vuelva a direccionar
pronto
Š Aprovechar localidad espacial
z
z
En vez de traer palabra referenciada, traer un
bloque de varias palabras
Porque es probable que se direccione pronto
palabra cercana
Principio de funcionamiento
Š Memorias DRAM organizadas como matrices
de bits
z
Acceso rápido a bits consecutivos de la misma fila
Š Memorias DRAM transfieren datos en bloques
o líneas
z
z
Accesos aleatorios a memorias DRAM son lentos
Accesos a direcciones consecutivas son rápidos
Principio de funcionamiento
Alternativas de diseño
Š Memoria RAM típicamente usa bloques de 64
bytes
1. ¿Cómo se encuentra el bloque si éste está
en el cache? (identificación del bloque)
2. Al traer un nuevo bloque, ¿dónde
almacenar el bloque en el cache? (ubicación
del bloque)
3. ¿Qué bloque reemplazar en caso de un
fallo? (reemplazo del bloque)
4. ¿Qué pasa al escribir? (estrategia de
escritura)
z
z
z
Referencia a palabra en dirección 24 trae datos de
las direcciones 0-63
Referencia a palabra en dirección 96 trae datos de
las direcciones 64-127
Localidad temporal
œ Si ahora se necesita la dirección 96, pronto se la
necesitará de nuevo
z
Localidad espacial
œ Si ahora se necesita la dirección 96, pronto se necesitarán
las direcciones 97, 98, 99, etc.
©Mario Medina C.
4
Cache de traducción directa
z
z
Š Bloque se busca en la línea indicada por el
índice
Š Simple y rápida, pero tasa de fallos alta por
conflictos
Dirección de
bloque
31
8 7
Ej: 0x345000
Bit Validez
4 3
Índice
Tag
Ej: 0x1
Byte 15
Byte 31
0x345000
4
4
Índice
Despl.
Cache de 16 bloques
Líneas de 16 bytes
Direcciones de 32 bits
24 bits
Tag
0x0
1
0x003A54
0x1
1
0x003A54
16 bytes
Datos
0x3
0x4
Traza de direcciones
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
0x5
1
0x6
0x7
0x8
0x9
0xA
Tag
4
4
Índice
Despl.
Cache de traducción directa
4
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
Traza de direcciones
Acierto!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
1 bit
V
24 bits
Tag
0x0
1
0x003A54
0x1
1
0x003A54
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
1
0x000012
16 bytes
Datos
24
Tag
4
4
Índice
Despl.
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
Traza de direcciones
Acierto!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
0xE
0xF
©Mario Medina C.
1
0x003A54
1
0x000012
Datos
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xD
0xE
1 bit
V
24 bits
Tag
0x0
1
0x003A54
0x1
1
0x003A54
1
0x000012
16 bytes
Datos
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0x003A5401
0x1
16 bytes
Cache de traducción directa
0xB
0xD
0x003A54
0xF
0xF
Despl.
24 bits
Tag
1
0xC
0x003A5400
0xE
4
1 bit
V
0x0
0xB
0xD
Índice
15
0x3
0xC
24
Byte 240
0x2
0xB
Tag
1
Cache de traducción directa
Traza de direcciones
Acierto!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
0x000012
0
Byte 16
:
:
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
0x2
Byte 0
Byte 17
3
:
24
1 bit
V
Byte 1
2
Cache de traducción directa
24
Ej: 0x0
Datos
Tag
Byte 255
Tag
0
Desplazamiento
:
z
bloques de 2M bytes Æ 2(N-M) bloques (líneas)
M bits inferiores son desplazamiento en el bloque
(N-M) bits siguientes son índice en el cache
(32-N) bits superiores de dirección son el “tag”
:
z
Ej. dirección: 0x34500010
N = 8 M = 4 Tag: 24 bits Índice: 4 bits
:
Š Cache de traducción directa (direct-mapped)
Š Para cache de 2N bytes
Cache de traducción directa
0xC
0x003A5410
0xD
0xE
0xF
5
Cache de traducción directa
4
Despl.
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
1 bit
V
24 bits
Tag
0x0
1
0x003A54
0x1
1
0x003A54
16 bytes
Datos
0x3
0x4
0x5
1
4
4
Índice
Despl.
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
0x2
Traza de direcciones
Acierto!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
24
Tag
0x6
0x7
0x8
0x9
0xA
Š Bloque se busca en todas las líneas
simultáneamente
0x8
0x9
0xA
Cache completamente asociativa
4
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
1 bit
V
Traza de direcciones
0x003A5400
Acierto!
0x003A5401
0x003A5410
0x00001256
0x00001112
0x004E5135
0x003A5400
1
0x003A540
1
0x003A541
0x2
0x4
0x5
0x6
0x7
1
0x0000125
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
©Mario Medina C.
28 bits
Tag
0x1
0x3
0xE
0xF
Cache completamente asociativa
Ej. dirección: 0x34500100
N=8
M=4
Tag: 28 bits
31
4 3
Tag
1
0x0000111
0
Desplazamiento
Ej: 0x0
Ej: 0x345001
V
=
Datos
Byte 15
=
Byte 31
Byte 1
Byte 0
Byte 17
Byte 16 1
0
=
=
:
=
0x0
0xD
Tag
Menor tasa de fallos por conflictos, pero más
compleja y lenta
Despl.
0x000012
0x7
Conflicto en acceso a línea 1
M bits inferiores son desplazamiento en el bloque
(32-M) bits superiores de dirección son el “tag”
Tag
1
0x6
0xC
Š Cache completamente asociativo (fully
associative)
Š Para cache de 2N bytes, bloques de 2M bytes
Æ 2(N-M) bloques (líneas)
28
0x003A54
0x5
0x00001112
0xE
Cache completamente asociativa
z
1
0xB
0xD
0xF
z
0x1
0x4
0xC
z
0x003A54
0x3
0xB
0x00001256
24 bits
Tag
1
0x2
Traza de direcciones
Fallo!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
0x000012
16 bytes
Datos
1 bit
V
0x0
:
4
Índice
:
24
Tag
Cache de traducción directa
:
:
15
Cache completamente asociativa
28
4
Tag
Despl.
16 bytes
Datos
1 bit
V
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
Traza de direcciones
0x003A5400
Acierto!
0x003A5401
0x003A5410
0x00001256
0x00001112
0x004E5135
0x003A5401
0x0
28 bits
Tag
1
0x003A540
1
0x003A541
1
0x0000125
1
0x0000111
16 bytes
Datos
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
6
Cache completamente asociativa
28
4
Tag
Despl.
1 bit
V
0x0
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
1
28 bits
Tag
16 bytes
Datos
0x003A540
0x2
1
28
4
Tag
Despl.
0x003A541
0x3
0x003A5410
1
0x0000125
0x8
0x9
1
0x0000111
0xB
0xC
0xD
4
Despl.
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
0x7
28 bits
Tag
0xA
1
0x003A540
1
0x003A541
0x2
0xC
0xD
0xE
28
4
Tag
Despl.
0x0001112
0x6
1
0x0000125
0x8
0x9
0xA
1
0x0000111
0xB
0xC
0xD
0x3
M bits inferiores son desplazamiento en el bloque
(N-M-K) bits siguientes son índice del conjunto
(32-N+K) bits superiores de dirección son el “tag”
Š Bloque se busca en todos las líneas del conjunto
indicado por el índice
z
Baja tasa de fallos por conflicto, más sencillo que cache
asociativo
0x003A541
1
0x0000125
1
0x0000111
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
Cache asociativa por conjuntos
Ej. dirección: 0x34500100
N=8M=4
K = 1 (2-way) Tag: 25 bits
7 6
31
V
Tag
Datos
:
:
:
Tag Dir
=
4 3
Índice
Tag
Ej: 0x345000 | 0b
Sel1
Ej: 0x0
Datos
1
Mux
0
Sel0
0
Desplazamiento
Ej: 0x1
Tag
:
V
:
:
=
Tag Dir
OR
Hit
©Mario Medina C.
1
0x5
0x004E5135
0xE
Š Cache asociativo por conjuntos (set-associative)
Š Para cache de 2N bytes, bloques de 2M bytes Æ
2(N-M) bloques
Š Asociatividad 2K-way Æ conjuntos de 2K líneas,
2(N-M-K) conjuntos
z
0x003A540
0x2
Traza de direcciones
0x003A5400
0x003A5401
0x003A5410
Fallo!
0x00001256
0x00001112
0x004E5135
Cache asociativa por conjuntos
z
16 bytes
Datos
28 bits
Tag
1
0x1
0xF
z
1 bit
V
0x0
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
0x4
0x5
0x7
0x0000111
0xB
0x4
Traza de direcciones
0x003A5400
0x003A5401
0x003A5410
Acierto!
0x00001256
0x00001112
0x004E5135
1
0x9
Cache completamente asociativa
16 bytes
Datos
0x1
0x3
0x0000125
0x8
0xF
1 bit
V
0x0
1
0x6
0x0001256
0xE
Cache completamente asociativa
28
0x003A541
0x5
0xF
Tag
1
0x4
0x6
0xA
0x003A540
0x2
Traza de direcciones
0x003A5400
0x003A5401
0x003A5410
Acierto!
0x00001256
0x00001112
0x004E5135
0x5
0x7
16 bytes
Datos
28 bits
Tag
1
0x1
0x4
Traza de direcciones
Acierto!
0x003A5400
0x003A5401
0x003A5410
0x00001256
0x00001112
0x004E5135
1 bit
V
0x0
Cache de 16 bloques
líneas de 16 bytes
direcciones de 32 bits
0x1
0x3
Cache completamente asociativa
Dato
7
Cache asociativa por conjuntos
Cache asociativa por conjuntos
25
3
4
25
3
4
Tag
Ind.
Despl.
Tag
Ind.
Despl.
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
Traza de direcciones
0x003A5400
0x003A5401
1 bit
0x003A5410
V
0x0 1
0x00001256
1
0x1
0x00001112
0x2
0x002C0510
Línea 0
25 bits
Tag
16 bytes
Datos
1 bit
V
Línea 1
25 bits
Tag
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
Traza de direcciones
0x003A5400
0x003A5401
1 bit
0x003A5410
V
0x0 1
0x00001256
1
0x1
0x00001112
0x2
0x002C0510
16 bytes
Datos
0x003A54 | 0b
1
0x003A54 | 0b
0x000011 | 0b
0x3
Acierto!
1
Acierto!
0x000012 | 0b
0x5
0x6
0x7
0x7
Traza de direcciones
0x003A5400
0x003A5401
1 bit
0x003A5410
V
0x0 1
0x00001256
0x1 1
0x00001112
0x2
0x002C0510
16 bytes
Datos
0x003A54 | 0b
1
0x003A54 | 0b
1
0x000011 | 0b
0x000012 | 0b
25
3
4
25
3
4
Tag
Ind.
Despl.
Tag
Ind.
Despl.
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
Línea 0
25 bits
Tag
16 bytes
Datos
1 bit
V
Línea 1
25 bits
Tag
Traza de direcciones
0x003A5400
0x003A5401
1 bit
0x003A5410
V
0x0 1
0x00001256
0x1 1
0x00001112
0x2
0x002C0510
16 bytes
Datos
0x003A54 | 0b
1
0x003A54 | 0b
0x000011 | 0b
0x3
0x5
Línea 0
25 bits
Tag
16 bytes
Datos
1 bit
V
Línea 1
25 bits
Tag
16 bytes
Datos
0x003A54 | 0b
0x003A54 | 0b
1
0x000011 | 0b
0x3
0x4
1
Acierto!
0x000012 | 0b
0x4
0x5
0x6
0x6
0x7
0x7
0x003A5410
1
0x000012 | 0b
0x00001256
Clasificación de fallos
Cache asociativa por conjuntos
25
3
4
Tag
Ind.
Despl.
Š Obligatorios (compulsory)
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
z
Traza de direcciones
0x003A5400
0x003A5401
1 bit
0x003A5410
V
0x0 1
0x00001256
0x1 1
0x00001112
0x2
0x002C0510
z
Línea 0
25 bits
Tag
16 bytes
Datos
1 bit
V
Línea 1
25 bits
Tag
0x003A54 | 0b
0x003A54 | 0b
1
0x000011 | 0b
z
0x6
0x7
Tamaño del cache insuficiente para datos del programa
Š Conflicto (conflict)
z
Dos bloques compiten por el mismo lugar en el cache
œ Cero para cache completamente asociativo, máximo para cache directo
0x4
0x5
Fallo por primer acceso al bloque
Muy bajos en programas grandes con buena localidad
Š Capacidad (capacity)
16 bytes
Datos
0x3
©Mario Medina C.
Línea 1
25 bits
Tag
Cache asociativa por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
0x00001112
V
0x003A5401
Cache asociativa por conjuntos
Acierto!
1 bit
0x4
0x6
0x003A5400
Acierto!
16 bytes
Datos
0x3
0x4
0x5
Línea 0
25 bits
Tag
1
0x000012 | 0b
Š Coherencia (coherence)
z
z
Elemento externo modifica memoria principal
Necesario invalidar copia almacenada en el cache
8
Tasas de fallo por tipo
0.14
1-way (directo)
Tasa de fallo por tipo
0.12
0.1
Š Aumentar la asociatividad disminuye la tasa
de fallos
Conflicto
2-way
Tasas de fallo por tipo
4-way
0.08
z
8-way
0.06
Capacidad (asociativa)
Obligatorio
0.04
0.02
0
Š Aumentar el tamaño de la cache disminuye la
tasa de fallos
128
64
32
16
8
2
4
z
1
Mayores beneficios al pasar de cache directa a
asociativa de 2 conjuntos
z
Tamaño del cache (KB)
Pasado un cierto tamaño, ventajas son marginales
Fallos obligatorios son dominantes
Alternativas de diseño
1.
¿Cómo se encuentra el bloque si éste está en el
cache? (identificación del bloque)
Ubicación del bloque (I)
Š Cache de traducción directa
z
Sólo en línea identificada por índice en dirección
24
2.
Al traer un nuevo bloque, ¿dónde almacenar el bloque
en el cache? (ubicación del bloque)
Tag
4
4
Índice
Despl.
1 bit
V
24 bits
Tag
16 bytes
Datos
0x0
Dirección
0x00001256
0x1
0x2
0x3
3.
0x4
¿Qué bloque reemplazar en caso de un fallo?
(reemplazo del bloque)
0x5
0x6
0x7
0x8
0x9
4.
0xA
¿Qué pasa al escribir? (estrategia de escritura)
0xB
0xC
0xD
0xE
0xF
Ubicación del bloque (II)
Š Cache asociativo por conjuntos
Š Cache completamente asociativo
z
Ubicación del bloque (III)
En cualquier línea
z
z
28
Tag
Dirección
0x00001256
4
1 bit
V
Despl.
24 bits
Tag
16 bytes
Datos
Sólo en conjunto indicado por índice
En cualquier línea dentro del conjunto
27
Tag
3
4
Ind.
Despl.
0x0
0x1
0x2
0x3
Dirección
0x00001256
0x000012|0b56
Conjunto 0
0x4
1 bit
V
0x5
0x6
0x7
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
0x4
0xC
0x5
0xD
0x6
0xE
0x7
27 bits
Tag
16 bytes
Datos
Conjunto 1
1 bit
V
27 bits
Tag
16 bytes
Datos
0xF
©Mario Medina C.
9
Alternativas de diseño
1.
¿Cómo se encuentra el bloque si éste está en el
cache? (identificación del bloque)
2.
Al traer un nuevo bloque, ¿dónde almacenar el bloque
en el cache? (ubicación del bloque)
3.
¿Qué bloque reemplazar en caso de un fallo?
(reemplazo del bloque)
4.
¿Qué pasa al escribir? (estrategia de escritura)
Reemplazo de bloque
Š Cache de traducción directa
z
No hay elección: sólo una línea disponible
Š Cache completamente asociativo
z
Todas las líneas disponibles, elegir la mejor
Š Cache asociativo por conjuntos
z
Todas las líneas dentro del conjunto disponibles,
elegir la mejor
Elección de línea a reemplazar
Š Objetivo
z
Reemplazar línea a ser utilizada más lejos en el
futuro
Elección de línea a reemplazar
Š Ejemplo: Tasas de fallo medidas en un
benchmark
z
Š Algoritmos de reemplazo
z
z
z
Random: elegir línea al azar
FIFO: Primera en entrar, primera en salir
LRU (Least Recently Used)
œ Elegir línea menos recientemente utilizada por
última vez
Asociatividad
2.
4.
4-way
8-way
LRU
Random
LRU
Random
LRU
Random
16KB
5.2%
5.7%
4.7%
5.3%
4.4%
5.0%
64KB
1.9%
2.0%
1.5%
1.7%
1.4%
1.5%
1.15%
1.17%
1.13%
1.13%
1.12%
1.12%
256KB
Estrategias de escritura
¿Cómo se encuentra el bloque si éste está en el
cache? (identificación del bloque)
Š Escritura sincrónica (Write Through)
Al traer un nuevo bloque, ¿dónde almacenar el bloque
en el cache? (ubicación del bloque)
Š Escritura asincrónica (Write Back)
z
z
3.
2-way
Tamaño
Alternativas de diseño
1.
Para la mayoría de las aplicaciones, LRU tiene
mejor desempeño que FIFO o Random
¿Qué bloque reemplazar en caso de un fallo?
(reemplazo del bloque)
z
Escribir en el cache y en el nivel siguiente de la
jerarquía
Escribir sólo en el cache, escribir en nivel
siguiente sólo al reemplazar el bloque
Requiere un bit de estado adicional en el cache
para indicar que bloque ha sido modificado
¿Qué pasa al escribir? (estrategia de escritura)
©Mario Medina C.
10
Comparación de estrategias
Š Write-Through
z
z
Buffer de escritura para Write-Through
Š Buffer almacena escrituras pendientes
Fallo de lectura no produce escrituras
Alto costo de escritura a menos que se use un
buffer
z
z
œ Buffer siempre se usa para no esperar por DRAM
Š Write-Back
z
z
Procesador escribe datos tanto en buffer como en la
cache
Controlador de memoria de la CPU escribe
contenidos del buffer a memoria
Š Buffer de escritura es FIFO
Evita escrituras múltiples del mismo bloque a
DRAM
Más complejo, fallo de lectura puede producir
escritura
z
Número típico de entradas: 4-8
Cache
CPU
DRAM
Buffer de escritura
Política ante fallo de escritura
Buffer de escritura para Write-Through
Š Uso de buffer de escritura puede producir
conflictos
z
Š ¿Qué hacer si escritura produce un fallo?
z
Fallo de lectura por un bloque que está en en
buffer de escritura antes que éste haya sido escrito
en DRAM
œ Última versión de ese bloque está en el buffer!
œ Esperar a vaciar el buffer antes de servir el fallo de
lectura y leer bloque desde DRAM
œ Al servir fallo de lectura, verificar contenidos del buffer
antes de ir a la DRAM (búsqueda asociativa en buffer)
Desempeño de memorias cache
Š AMAT: Average Memory Access Time
Tiempo promedio de acceso a memoria
Se calcula como
AMAT = tasa de acierto*tiempo de acierto + tasa
de fallo*penalidad de fallo
z Tiempo de acierto: tiempo de transferencia entre
cache y la CPU
z Penalidad de fallo: Tiempo de transferencia de un
bloque entre DRAM y cache
z
z
©Mario Medina C.
Traer bloque al cache (Write Allocate)
œ Evita fallo posterior si se lee del mismo bloque
œ Pero si no se lee, habríamos sacado del cache un bloque
potencialmente importante
z
Sólo escribir a DRAM
œ Ahorra espacio en el cache si el bloque escrito no se
accesa de nuevo en un tiempo largo
Desempeño de memorias cache
Š Memoria cache pequeña
pero rápida
Š Tasa de acierto: 0.9
Š Tiempo de acierto: 1
Š Penalidad de fallo: 100
Š Memoria cache grande pero
lenta
Š Tasa de acierto: 0.98
Š Tiempo de acierto: 8
Penalidad de fallo: 100
Š AMAT = 0.9 * 1 +
(1 – 0.9) * 100
Š AMAT = 10.9 ciclos
Š AMAT = 0.98 * 8 +
(1 – 0.98) *
100
Š AMAT = 9.84 ciclos
11
Mejoras al desempeño
Š AMAT = tasa de acierto*tiempo de acierto
+ tasa de fallo*penalidad de fallo
Š ¿Cómo mejorar el desempeño?
z
z
z
Reducir tasa de fallos
Š Explotar localidad espacial con bloques más grandes
z
z
Pero incrementa penalidad de fallo
También incrementa fallos por conflicto (menos bloques)
25%
Reducir tasa de fallos
Reducir penalidad de fallos
Reducir tiempo de acierto
1K
20%
Tasa de
Fallos
4K
15%
16K
10%
64K
5%
256
128
64
32
256K
16
0%
Tamaño de bloque (bytes)
Reducir tasa de fallos
Š Aumentar asociatividad y/o tamaño
z
Š Cache de víctimas (Victim
Cache)
También aumenta tiempo de acierto
Tasa de fallo por tipo
0.14
0.12
z
1-way (directo)
Conflicto
2-way
0.1
4-way
0.08
Reducir tasa de fallos
z
8-way
0.06
Capacidad (asociativa)
Obligatorio
0.04
z
128
64
32
8
4
2
1
0
16
0.02
Tamaño del cache (KB)
z
Pequeño buffer asociativo
almacena bloques recientemente
eliminados del cache
Reduce fallos por conflicto en
cache directo manteniendo
acceso rápido
Jouppi[1990]: cache de víctimas
de 4 entradas elimina 20%-95%
de fallos de conflicto en cache
directo de 4KB
Utilizado en procesadores DEC
Alpha y HP
Reducir tasa de fallos
Š Búsqueda anticipada (Prefetch)
z
z
z
z
Transferir bloques de DRAM a la cache antes de
que el programa los requiera
Reduce fallos obligatorios (Compulsory misses)
Útil cuando localidad espacial es muy buena
(instrucciones), pero requiere predicción de saltos
En el caso de data prefetch, puede sacar de la
cache bloques que aún están en uso
©Mario Medina C.
Tags
Datos
Tag + comp
Línea datos
Tag + comp
Línea datos
Tag + comp
Línea datos
Tag + comp
Línea datos
Al siguiente nivel
de jerarquía
Reducir tasa de fallos
Š Cache de trazas (Trace cache)
œIntegrar prefetch y predicción: instrucciones en
cache en orden de ejecución
œUtilizado en arquitectura Netburst de Intel
(Pentium 4)
z
Acceso a datos (ayuda por software):
Instrucciones TOUCH
œSimilar a instrucción LOAD, pero indica al cache
que dato se accesará pronto
œProgramador puede indicar al compilador
patrón de uso de datos
12
Reducir tasa de fallos
Š Arquitecturas “stream”
z
z
z
z
Sub-procesador especializado lee datos en forma
adelantada y los almacena en colas de memoria
internas
“Coprocesador de transferencias”
Útil si el patrón de acceso a datos es predecible,
regular y conocido de antemano
Utilizado en procesadores digitales de señales
(DSP)
Mejoras al desempeño
Š AMAT = tasa de acierto*tiempo de acierto
+ tasa de fallo*penalidad de fallo
Š ¿Cómo mejorar el desempeño?
z
z
z
Reducir penalidad de fallos
Š Mejorar desempeño de sistema de memoria
principal (DRAM)
z
Bus de CPU-memoria más rápido, más ancho
œBuses anchos tienen problemas de skew y interferencia
(crosstalk), preferible aumentar velocidad
œPentium 4 utiliza un bus de 200MHz – 266MHz pero
transfiere datos 4 veces por ciclo para un ancho de
banda efectivo de 800MHz – 1066MHz
z
Reducir penalidad de fallos
Š En caso de fallo, traer al cache primero el dato
requerido, y el resto del bloque después
z
z
z
z
Acceso por bloques entrelazado, paginado,
sincrónico
Reducir penalidad de fallo
Š Buffer de escritura
z
z
z
z
Almacena escrituras a memoria pendientes
Controlador de memoria escribe bloques a DRAM
en forma independiente de CPU
Fallo de lectura tiene prioridad sobre buffer de
escritura para acceso a DRAM
Si fallo de lectura posterior es a bloque residente
en buffer de escritura, se debe buscar bloque en
buffer de escritura en vez de leerlo desde DRAM
©Mario Medina C.
Reducir tasa de fallos
Reducir penalidad de fallos
Reducir tiempo de acierto
Si se necesita el byte 24, traer los bytes 24-63
ahora y los bytes 0-23 después
Útil sólo en bloques grandes
Latencia es alta de todas maneras
Localidad espacial: probablemente hay que esperar
el siguiente dato de todas formas
Reducir penalidad de fallo
Š Fallos sin bloqueo
z
Permitir que procesador ejecute otras
instrucciones mientras se resuelve el fallo
œ Ejecución desordenada de instrucciones puede traer
problemas si no se maneja adecuadamente
z
z
Útil en procesadores superescalares o multihebra
Problema: puede producirse otro fallo antes de
resolver el primero
œ Pentium 4 puede manejar hasta 4 fallos simultáneos
œ Múltiples bancos de memoria mejoran desempeño
13
Reducir penalidad de fallo
Š Usar una cache de nivel 2
z
Atiende a los accesos que producen un fallo en la
cache de nivel 1
Š Tener cache de nivel 2 afecta a la penalidad de
fallo de cache de nivel 1
z
La penalidad de fallo de cache de nivel 2 será el
tiempo de acceso a DRAM y los tiempos de
reemplazo correspondientes
Š Esquema extensible a 3 o más niveles
Reducir penalidad de fallo
Š AMAT = tasa de acierto L1*tiempo de
acierto L1 + tasa de fallo L1*penalidad de
fallo L1
Š penalidad de fallo L1 = tasa de acierto
L2*tiempo de acierto L2 + tasa de fallo
L2*penalidad de fallo L2
Š Penalidad de fallo L2 = tiempo de acceso
DRAM
Desempeño de memorias cache
Š Recordar el ejemplo anterior
Š Memoria cache pequeña
pero rápida
Š Tasa de acierto: 0.9
Š Tiempo de acierto: 1
Š Penalidad de fallo: 100
Š Memoria cache grande pero
lenta
Š Tasa de acierto: 0.98
Š Tiempo de acierto: 8
Penalidad de fallo: 100
Š AMAT = 0.9 * 1 +
(1 – 0.9) * 100
Š AMAT = 10.9 ciclos
Š AMAT = 0.98 * 8 +
(1 – 0.98) *
100
Š AMAT = 9.84 ciclos
Desempeño de memorias cache
Š Usar cache pequeño pero rápida como cache
L1 y cache grande pero más lenta como cache
L2
Š AMAT L2 = 9.84
Š AMAT = 1*0.9 + 0.1*9.84
CPU
Š AMAT = 1.88 ciclos
Cache L1
Cache L2
Mejoras al desempeño
Š AMAT = tasa de acierto*tiempo de acierto
+ tasa de fallo*penalidad de fallo
Š ¿Cómo mejorar el desempeño?
z
z
z
Reducir tasa de fallos
Reducir penalidad de fallos
Reducir tiempo de acierto
©Mario Medina C.
Reducir tiempo de acierto
Š Tiempo de acierto es el parámetro crítico del
desempeño de cache L1
Š Utilizar L1 directo + cache de víctimas o L2
Š Segmentar (pipeline) acceso a L1
z
z
Etapa 1: determinar hit/miss
Etapa 2: transferir dato a CPU
14
Reducir tiempo de acierto
Cache unificado vs. Harvard
Š Cache unificado: Un cache L1 para datos e
instrucciones
z
z
CPU
Cache L1
Unificada
Mejor tasa de acierto
Puede hacer conflictos estructurales (stalls)
z
Elimina conflictos estructurales
División del cache aumenta tasa de fallos
Š CPUS comerciales utilizan arq. Harvard
z
Típicamente, cache L2 unificado
Cache
unificada
z
z
z
z
Ignorar efectos de L2, que es igual para ambas
Asumir que 1/3 de las instrucciones leen ó
escriben datos
Tiempo de acierto: 1 ciclo
Penalidad de fallo: 50 ciclos
Š AMAT = AMATinstrucción+AMATdatos*1/3
1 + 1/3
Cache unificado vs. Harvard
Š AMAT de Cache unificada
z
[(0.9801*1 + 0.0199*50) +
0.33*(1 + 0.9801*1 + 0.0199*50)]/1.33
AMAT Cache unificada = 2.223 ciclos
Š AMAT de Arquitectura Harvard
z
©Mario Medina C.
Arquitectura
Harvard
Š Ejemplo
z Cache unificada: 32KB, tasa de fallo 1.99%
z Harvard: 16KB instrucciones (fallo 0.64%)
16 KB datos (fallo 6.47%)
Cache unificado vs. Harvard
Š ¿Cuál es mejor?
D-Cache L1
Cache L2
Unificada
Cache L2
Unificada
Š Arquitectura Harvard: Dos caches L1 para
datos e instrucciones
z
CPU
I-Cache L1
[(0.9936*1 + 0.0064*50) +
0.33*(0.9353*1 + 0.0647*50)]/1.33
AMAT Harvard = 2.022 ciclos
15