Jerarquía de memoria: cache, reducción de fallos, ocultación de latencia, memoria principal

1
Introducción: Jerarquía de memoria
Rendimiento: mejoras
Reducir la tasa de fallos de la cache
Reducir la penalización de los fallos de cache
Reducir el tiempo de acceso a la cache
La memoria principal
Una visión global: Alpha 21064
Bibliografía
Capítulo 5 de [HePa07]
[JaMu98a] B. Jacob, T. N. Mudge. “Virtual Memory: Issues of Implementation”. IEEE Computer Magazine. Vol. 31 (6), Junio 1998,
Simulador X-CACHE
Contenidos

2
Introducción
Gap memoria –procesador
El problema
La demanda de anchura de banda con memoria crece.

9% por año
50% por año

3
Introducción
Un computador típico está formado por diversos niveles de memoria, organizados de forma jerárquica:
Registros de la CPU
Memoria Cache
Memoria Principal
Memoria Secundaria (discos)
Unidades de Cinta (Back-up) y CD-ROMs
El coste de todo el sistema de memoria excede al coste de la CPU
Es muy importante optimizar su uso
Niveles de la Jerarquía de memoria
(Gp:) Registros de la CPU
(Gp:) Cache
(SRAMs)
(Gp:) Memoria Principal
(DRAMs)
(Gp:) Almacenamiento en disco
(estado sólido, magnéticos)
(Gp:) Almacenamiento en cinta
(cintas, discos ópticos)
(Gp:) Tiempo de acceso
(Gp:) Coste
(Gp:) Capacidad
(Gp:) nivel 0
(Gp:) nivel 1(1.1,1.2,1.3)
(Gp:) nivel 2
(Gp:) nivel 3
(Gp:) nivel 4

4
Introducción
Tipos de Memoria

5
Introducción
Optimizar el uso de la memoria
Hacer que el usuario tenga la ilusión de que dispone de una memoria con:
Tiempo de acceso similar al del sistema más rápido
Coste por bit similar al del sistema más barato
La mayor parte de los accesos a un bloque de información, este bloque debe encontrarse en los niveles altos (bajos) de la memoria
Se refiere a la gestión dinámica, en tiempo de ejecución de la jerarquía de memoria
Esta gestión de la memoria sólo afecta a los niveles 1 (cache), 2 (mem. principal) y 3 (mem. secund.)
El nivel 0 (registros) lo asigna el compilador en tiempo de compilación
El nivel 4 (cintas y CD-ROMs) se utiliza para copias de seguridad (back-up)
Objetivo de la gestión de la jerarquía de memoria
Niveles a los que afecta la gestión de la jerarquía memoria
Controla la transferencia de información entre la memoria cache y la memoria principal
Suele llevarse a cabo mediante Hardware específico (MMU o “Management Memory Unit”)
Controla la transferencia de información entre la memoria secundaria y la memoria principal
Parte de esta gestión se realiza mediante hardware específico (MMU) y otra parte la realiza el S.O
Gestión de la memoria cache
Gestión de la memoria virtual
Memoria Cache
Memoria Principal
Memoria Secundaria
Gestión de la
memoria cache
Gestión de la
memoria virtual

6
Introducción
Inclusión
Cualquier información almacenada en el nivel de memoria Mi, debe encontrarse también en los niveles Mi+1, Mi+2, …, Mn. Es decir: M1? M2 ? … ? Mn
Coherencia
Las copias de la misma información existentes en los distintos niveles deben ser consistentes
Si un bloque de información se modifica en el nivel Mi, deben actualizarse los niveles Mi+1,.., Mn
Existen distintas estrategias de actualización
Escritura directa (write-through): Cuando una palabra se modifica en el nivel Mi, inmediatamente se actualiza en el nivel Mi+1
Post-escritura (write-back): La actualización del nivel Mi+1 se retrasa hasta que el bloque que se modificó es reemplazada o eliminada en el nivel Mi
Localidad
La propiedad de localidad dice que las referencias a memoria generadas por la CPU, para acceso a datos o a instrucciones, están concentradas o agrupadas en ciertas regiones del tiempo y del espacio
Localidad temporal
Las direcciones de memoria (instrucciones o datos) recientemente referenciadas, serán referenciadas de nuevo, muy probablemente, en un futuro próximo
Ejemplos: Bucles, subrutinas, accesos a pila, variables temporales, etc.
Localidad espacial
Tendencia a referenciar elementos de memoria (datos o instrucc.) cercanos a los últimos elementos referenciados
Ejemplos: programas secuenciales, arrays, variables locales de subrutinas, etc.
Propiedades de la jerarquía de memoria

7
Introducción
Bloque: unidad mínima de transferencia entre los dos niveles
Acierto (hit): el dato solicitado está en el nivel i
Tasa de aciertos (hit ratio): la fracción de accesos encontrados en el nivel i
Tiempo de acierto: tiempo de acceso del nivel i + tiempo detección de acierto
Fallo (miss): el dato solicitado no está en el nivel i y es necesario buscarlo en el nivel i+1
Tasa de fallos (miss ratio): 1 – (Tasa de aciertos)
Tiempo de penalización por fallo: tiempo de sustitución de un bloque del nivel i + tiempo de acceso al dato
Tiempo de acierto < < Penalización de fallo
Terminología
Memoria
nivel inferior
Memoria
nivel superior
Al procesador
Del procesador
Blk X
Blk Y

8
Introducción
Gap memoria -procesador
El problema
La demanda de anchura de banda con memoria crece.
Segmentación, ILP
Ejecución especulativa
1980 no caches “on chip”, 2007 2-3 niveles de cache “on chip”

No tienen valor en sí mismas. Solo para el reducir el gap

9% por año
50% por año

9
Introducción
El problema: Algunos datos
Tamaño de la cache
Del 50 al 75 % del área. Más del 80% de los transistores
Tiempo de servicio de un fallo de cache: evolución
21064 (200Mhz) 340ns, 340/5=68 ciclos, 68×2= 136 instrucciones
21164 (300Mhz) 266ns, 266/3.3=80, 80×4=320 instrucciones
21264 (1Ghz) 180ns, 180/1=180, 180×6=1080 instrucciones
PentiumIII
Itaniun 2
Madison
Latencia:
1ciclo ( Itanium2) a 3 ciclos Power4-5

10
Introducción
El problema
Tamaño de la cache
Del 50 al 75 % del área. Más del 80% de los transistores
Pentium 4
Montecito
1700Mtrans

11
La más simple: Emplazamiento directo
Memoria
Cache directa de 4 Bytes
Dirección
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Cache Index
0
1
2
3
La posición 0 de la cache almacenara los datos de:
Posiciones de memoria 0, 4, 8, … etc.
En general: Cualquier posición de memoria cuyos 2 LSBs de la dirección sean 0s
Dirección< 1:0> => cache index
¿Cuando se debe llevar una información a la cache?
¿ Como localizar la información en la cache ?
Repaso de conceptos básicos

12
Cache directa de 1 KB, 32Bytes por bloque
Para una cache de 2N con dirección de 32bits:
Los (32 – N) bits más significativos son el Tag
Los M bits menos significativos son el selector de bytes (Tamaño de bloque = 2M)
Cache Index
0
1
2
3
:
Cache Data
Byte 0
0
4
31
:
Cache Tag
Example: 0x50
Ex: 0x01
0x50
Valid Bit
:
31
Byte 1
Byte 31
:
Byte 32
Byte 33
Byte 63
:
Byte 992
Byte 1023
:
Cache Tag
Byte Select
Ex: 0x00
9
Repaso de conceptos básicos

13
Asociativa por conjuntos
N-way asociativa : N entradas por conjunto
N caches directas operando en paralelo (N típico 2 , 4)
Ejemplo: 2-way cache asociativa
Cache Index selecciona un conjunto de la cache
Los dos tags en el conjunto son comparados en paralelo
Se selecciona el dato en función de la comparación
Cache Data
Cache Block 0
Cache Tag
Valid
:
:
:
(Gp:) Cache Data
(Gp:) Cache Block 0
(Gp:) Cache Tag
(Gp:) Valid
(Gp:) :
(Gp:) :
(Gp:) :

Cache Index
Mux
0
1
Sel1
Sel0
Cache Block
Compare
Adr Tag
(Gp:) Compare

OR
Hit
Repaso de conceptos básicos

14
Comparación
Asociativa por conjuntos “versus” Directa
N comparadores vs. 1
Retardo extra por el MUX para los datos
El dato llega después del hit del acceso
En una directa, el bloque de cache es accesible antes del hit:
Es posible asumir un acierto y continuar. Recuperación si fallo.
(Gp:) Cache Data
(Gp:) Cache Block 0
(Gp:) Cache Tag
(Gp:) Valid
(Gp:) :
(Gp:) :
(Gp:) :
(Gp:) Cache Data
(Gp:) Cache Block 0
(Gp:) Cache Tag
(Gp:) Valid
(Gp:) :
(Gp:) :
(Gp:) :
(Gp:) Cache Index
(Gp:) Mux
(Gp:) 0
(Gp:) 1
(Gp:) Sel1
(Gp:) Sel0
(Gp:) Cache Block
(Gp:) Compare
(Gp:) Adr Tag
(Gp:) Compare
(Gp:) OR
(Gp:) Hit

Repaso de conceptos básicos

15
Política de actualización :Write-Through vs Write-Back
Write-through: Todas las escrituras actualizan la cache y la memoria
Se puede eliminar la copia de cache – Lo datos estan en la memoria
Bit de control en la cache: Solo un bit de validez
Write-back: Todas las escrituras actualizan solo la cache
No se pueden eliminar los datos de la cache – Deben ser escritos primero en la memoria
Bit de control: Bit de validez y bit de sucio
Comparación:
Write-through:
Memoria ( Y otros lectores ) siempre tienen el último valor
Control simple
Write-back:
Mucho menor AB, escrituras múltiples en bloque
Mejor tolerancia a la alta latencia de la memoria
Repaso de conceptos básicos
Política de actualización :Asignación o no en fallo de escritura

16
Rendimiento
4 aspectos fundamentales
Ubicación de un bloque(línea)
Emplazamiento directo, asociativo, asociativo por conjuntos
Acceso al bloque: uso del índice
Tag y bloque(línea)
Reemplazamiento del bloque(línea)
Aleatorio, LRU
Estrategia de escritura
Post-escritura( write back), escritura directa ( write through)

Tiempo CPU = ( Ciclos CPU + Ciclos de espera memoria)x Tc
Ciclos de espera memoria= Accesos a memoria x Tasa de fallos x Tiempo de penalización de fallo
Multiplicando y dividiendo por Nº de instr
Tiempo CPU = Nº de instr. x (CPI+accesos por inst x Tasa de fallos x penalización de fallo) x Tc

Rendimiento de la cache

17
Rendimiento: Mejora
¿ Como mejorar el rendimiento de la cache

Reducir la tasa de fallos
Reducir la penalización del fallo
Reducir el tiempo de acceso a la cache

Tipos de fallos (3 C´s)

Iniciales(Compulsory):
Fallos incluso en cache infinita
Localidad espacial

Capacidad:
Tamaño de la cache
Localidad temporal

Conflicto:
Política de emplazamiento
Tasa de fallos por tipo
(Average SPEC92)
Tamaño, asociatividad

18
Reducir la tasa de fallos
Cambiando el tamaño del bloque
Observaciones:
Valor óptimo mayor según aumenta Mc
Caches integradas tamaño y bloque fijo
Caches externas tamaño y bloque variable
(Gp:) Tamaño de bloque
(Gp:) 1 palabra
(Gp:) Mc

Bloque del sig. nivel => Tecnología y organización del siguiente nivel
Disminución de la tasa de fallos de inicio (captura mejor la localidad espacial )
Aumento de la tasa de fallos de capacidad (menor Nº Bloques => captura peor localidad temporal)
(Gp:) Tamaño de bloque
(Gp:) 1 palabra
(Gp:) Mc

Tasa de fallos
Penalización
Reduce fallos
iniciales
Aumenta fallos
De capacidad
Miss rate (%)
Tamaño cache
Tamaño bloque

19
Reducir la tasa de fallos
Cambiando la asociatividad
Regla 2:1
Cache directa= 2way de mitad de tamaño

8 way es igual a totalmente asociativa

Tiempo de acceso
(Gp:) Asociativo
(Gp:) Directo
(Gp:) Asociativo por conjuntos
(Gp:) E
(Gp:) 1
(Gp:) M

Tasa de fallos
Disminución de la tasa de fallos de conflicto (más marcos posibles)
Tiempo de acceso
Coste hardware
Número de comparadores => tecnología
(Gp:) Asociativo
(Gp:) Directo
(Gp:) Asociativo por conjuntos
(Gp:) E
(Gp:) 1
(Gp:) M

Observaciones:
1. Mejora menor según aumenta el tamaño Mc
– Aumenta el número de conjuntos
2. Mejora menor según aumenta asociatividad

20
Reducir la tasa de fallos
Algoritmo de reemplazamiento
Espacio de reemplazamiento
Directo: Trivial
Asociativo: Toda la cache
Asociativo por conjuntos: Los marcos de un conjunto
Algoritmos
Aleatorio: El bloque reemplazado se escoge aleatoriamente
LRU (Least Recented Used): Se reemplaza el bloque menos recientemente usado
– Gestión: pila

– Implementación: registros de edad, implementación de la pila y matriz de referencias
– Para un grado de mayor que 4, muy costoso en tiempo y almacenamiento (actualiz.> tcache)
LRU aproximado: Algoritmo LRU en grupos y dentro del grupo
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) 3
(Gp:) 0
(Gp:) 2
(Gp:) 1
(Gp:) 3
(Gp:) 3
(Gp:) 0
(Gp:) 2
(Gp:) 1
(Gp:) ACIERTO
(Gp:) REEMPLAZ.

21
Reducir la tasa de fallos
Algoritmo de reemplazamiento

Influencia del algoritmo de reemplazamiento
Grado 2 Grado 4 Grado 8
LRU AleatorioLRU AleatorioLRU Aleatorio
16 KB 5,18% 5,69% 4,67% 5,29% 4,39% 4,96%
64 KB 1,88% 2,01% 1,54% 1,66% 1,39% 1,53%
256 KB 1,15% 1,17% 1,13% 1,13% 1,12% 1,12%
Observaciones:
1. La diferencia disminuye al aumentar Mc
2. La diferencia aumenta con el grado de asociatividad E
Reemplazamiento
Tasa de fallos
ALEATORIO
LRU
Disminuye la tasa de fallos de capacidad (mejora la localidad temporal)
Tiempo de acceso
Coste hardware
(Gp:) Reemplazamiento
(Gp:) ALEATORIO
(Gp:) LRU

22
Reducir la tasa de fallos
Cache de víctimas
Memoria cache más pequeña totalmente asociativa asociada a la memoria cache
=> Contiene los bloques que han sido sustituidos más recientemente
=> En un fallo primero comprueba si el bloque se encuentra en la cache víctima
Baja la tasa de fallos de conflicto en caches con emplazamiento directo

– Cuanto menor es la memoria cache más efectiva es la cache víctima
– En una cache de 4KB con emplazamiento directo, una cache víctima de 4 bloques elimina del 20% al 95% de los fallos, según programa.

Ejemplo:
– HP 7200, 2 KB internos: 64 bloques de 32 bytes
ALPHA,
Power 4-5-6, AMD Quad, ( diferente uso)
(Gp:) CPU
registros

23
Reducir la tasa de fallos
Cache pseudo-asociativas
Trata de combinar las ventaja de la cache directa y la asociativa
Memoria cache de emplazamiento directo:
=> En un fallo busca el bloque en otro marco dado por la inversión del bit MS del índice de marco
Dos tiempos de acceso a cache => Gestión por parte del procesador
Más útiles en cache “off chip” (L2)
Ejemplos: R10000 L2, UltraSparc L2
Bloque: 0 (0000000)
Marcos: 0 (0000000); 2 (0000010)
(Gp:) ETIQUETA
(Gp:) PAL
(Gp:) MB

PAL
B
9
5
2
2
Hit Time
Pseudo Hit Time
Miss Penalty
Time

24
Reducir la tasa de fallos
Cache pseudo-asociativas
•Cachéde correspondencia directa con una modificación para que se comporte como asociativas.
•Se permite que un bloque de Mpse pueda ubicar en dos (pseudoasociativade 2 vías) marcos de Mc:
•el que le corresponde (por la correspondencia directa)
•el que resulta de conmutar el bit más significativo de la dirección del bloque

25
Reducir la tasa de fallos
Idea

Ocultar la latencia de un fallo de cache solapándolo con otras instrucciones independientes
ADD R5,R6,R6
…………………..
…………………..
LD R1, dir
PREBUSCAR: Caches con prebusqueda
Cache con prebúsqueda
Anticipa los fallos de Cache anticipando las búsquedas antes de que el procesador
demande el dato
Solapa acceso a los datos con instrucciones anteriores a la que usa el dato
No se relaciona con los registros. No genera riesgos
Posibilidad de búsquedas innecesarias

Dos tipos
Prebusqueda SW
Prebusqueda HW

26
Reducir la tasa de fallos
Prebusqueda SW

Instrucciones especiales de prebusqueda introducidas por el compilador

La eficiencia depende del compilador y del tipo de programa

Prebusqueda con destino cache (MIPS IV, PowerPC, SPARC v. 9), o registro ( HP-PA)
Instrucciones de prebusqueda no producen excepciones. Es una forma de especulación.

Funciona bien con bucles y pattern de acceso a array simples. Aplicaciones de cálculo

Funciona mal con aplicaciones enteras que presentan un amplio reúso de Cache

Overhead por las nuevas instrucciones. Más búsquedas. Más ocupación de memoria
Cache con prebusqueda

27
Reducir la tasa de fallos
Cache con prebúsqueda (ejemplo)
Cache 8 KB directa, bloque:16 bytes, write-back (con asignación en escritura)
Datos: a(3,100), b(101,3). Elemento arrays = 8 bytes. Cache inicialmente vacía. Ordenación en memoria: por filas
1 bloque cache = 2 palabras (elementos)

Programa (sin prebúsqueda):
for (i:=0; i< 3; i:=i+1)
for (j:=0; j< 100; j:=j+1)
a[i][j] := b[j][0] * b[j+1][0]
Fallos
Acceso a elementos de “a”: Se escriben y acceden en cache tal como están almacenados en memoria. Cada acceso a memoria proporciona dos palabras (beneficio de localidad espacial).
Fallos “a” = (3×100)/2 = 150

Acceso a elementos de “b” (si ignoramos fallos de conflicto): Un fallo por cada valor de j cuando i=0 => 101 fallos. Para los restantes valores de i, los elementos de b ya están en la cache.
Total fallos: 150+101 = 251

Prebúsqueda de instrucciones y datos
28
•La prebúsqueda de instrucciones y datos antes de ser demandados disminuye la tasa de fallos.
•Las instrucciones o datos prebuscadosson llevados directamente a la cachéo a un buffer externo
•El Alpha AXP 21064 prebuscados bloques cuando ocurre un fallo, el que contiene la palabra causante del fallo y el siguiente. El primero lo coloca en MCy el segundo en el buffer de prebúsqueda
•Experimentalmente se ha comprobado que un buffer de prebúsqueda simple elimina el 25 % de los fallos de una cachéde datos con correspondencia directa de 4 KB

29
Reducir la tasa de fallos
Cache con prebúsqueda (ejemplo)
Suposición: La penalización por fallo es de tal duración que se necesita iniciar la prebúsqueda 7 iteraciones antes.
Idea: partir bucle
/* para i=0 (prebusca a y b) */
for (j:=0; j< 100; j:=j+1) {
prefetch (b[j+7][0]); /* b[j][0] para 7 iteraciones más tarde */
prefetch (a[0][j+7]); /* a[0][j] para 7 iteraciones más tarde */
a[0][j] := b[j][0] * b[j+1][0] ; }

/* para i=1,2 (prebusca sólo a, ya que b ya está en cache) */
for (i:=1; i< 3; i:=i+1)
for (j:=0; j< 100; j:=j+1) {
prefetch (a[i][j+7]); /* a[i][j] para 7 iteraciones más tarde */
a[i][j] := b[j][0] * b[j+1][0] ; }

Total fallos 3 * ?7/2? + 7 = 19 fallos
Instrucciones extra (los prefetch): 100*2 + 200*1 = 400
Fallos evitados = 251 -19 = 232

Fallos: ?7/2?
Fallos: 7
Fallos: 2 * ?7/2? (para i=1,2)

30
Reducir la tasa de fallos
Prebusqueda HW

Prebusqueda secuencial de un bloque adicional

Tipos

Prebusqueda sobre fallo
Prebusca el bloque b+1 si el acceso b produce un fallo

Prebusqueda marcada
Se incluye un tag en cada bloque. Si un bloque marcado es buscado
o prebuscado el siguiente se prebusca. Sigue bien la localidad espacial

Prebusqueda adaptativa
El grado de prebusqueda ( numero de bloques prebuscados) se
ajusta en función del comportamiento

Prebusqueda con “stride” arbitrario
Cache con prebusqueda

31
Reducir la tasa de fallos
Comparación
HP 7200 Prebusqueda HW – HP8000 Prebusqueda SW
Rendimiento
Relativo
Cache con prebusqueda
Implementacion
Estado de los bloques prebuscados
(stream buffer)
Bloque prebuscado pasa a buffer
Al ser referenciado pasa a Cache
Alpha busca dos bloques en fallo

32
Reducir la tasa de fallos
Compilador: Optimización de código
Ejemplo: DEC Alpha 21064: Mc de 8 KB, E = 1, M = 256( numero de bloques), Bloque = 4 palabras de 64 bits (32 bytes)
– Cada 1024 palabras se repite la asignación de marcos de bloques.

1) Fusión de arrays: Mejora la localidad espacial para disminuir los fallos de conflicto
– Colocar las mismas posiciones de diferentes arrays en posiciones contiguas de memoria
A,B[0:1]
A,B[512:513]
A,B[510:511]
A,B[2:3]
A,B[4:5]
A,B[510:511]
A[0:3]
A[1020:1023]
A[1016:1019]
A[4:7]
A[8:11]
A[12:15]
B[0:3]
B[1020:1023]
B[1016:1019]
B[4:7]
B[8:11]
B[12:15]
2×1024 fallos
2×256 de inicio
1536 de conflicto
1024/2 fallos
2×256 de inicio
Ganancia: 4
double A[1024];
double B[1024];

for (i = 0; i < 1024; i = i + 1)
C = C + (A[i] + B[i]);
struct fusion{
double A;
double B;
} array[1024];

for (i = 0; i < 1024; i = i + 1
C = C + (array[i].A + array[i].B);

33
Reducir la tasa de fallos
Compilador: Optimización de código
3) Intercambio de bucles: Mejora la localidad espacial para disminuir los fallos de conflicto
– En lenguaje C las matrices se almacenan por filas, luego se debe variar en el bucle interno la columna
2) Alargamiento de arrays: Mejora la localidad espacial para disminuir los fallos de conflicto
– Impedir que en cada iteración del bucle se compita por el mismo marco de bloque
B[1020:1023]
B[1016:1019]
A[0:3]
A[1020:1023]
A[1016:1019]
A[4:7]
A[8:11]
A[12:15]
B[0:3]
B[4:7]
B[8:11]
B[12:15]
double A[1024];
double B[1024];

for (i=0; i < 1024; i=i +1)
C = C + (A[i] + B[i]);
double A[1028];
double B[1024];

for (i=0; i < 1024; i=i+1)
C = C + (A[i] + B[i]);
double A[128][128];

for (i=0; i < 128;i=i+1)
for (j=0; j < 128; j=j+1)
C = C * A[i][j];
double A[128][128];

for (j=0; j < 128; j=j+1)
for (i=0; i < 128;i=i+1)
C = C * A[i][j];
A[0][0:3]
A[7]124:127]
A[7][120:123]v
A[0][4:7]
A[0][8:11]
A[0][12:15]
A[8][0:3]
A[8][4:7]
A[8][8:11]
A[8][12:15]
A[15][120:123]
A[15][124:127]
A[120][0:3]
A[120][4:7]
A[120][8:11]
A[120][12:15]
A[127][120:123]
A[127][124:127]
A[0:3]
A[1020:1023]
A[1016:1019]
A[4:7]
A[8:11]
A[12:15]
A[1024:1027]
A[1016:1019]
B[1012:1015]
B[0:3]
B[4:7]
B[8:11]
B[1016:1019]
B[1020:1023]
2×1024 fallos
512 de inicio
1536 de conflicto
1024/2 fallos
512 de inicio
Ganancia: 4
128×128 fallos
16×256 de inicio
12288 de conflicto
128×128/4 fallos
16×256 de inicio
Ganancia: 4

34
Reducir la tasa de fallos
Compilador: Optimización de código
4) Fusión de bucles: Mejora la localidad temporal para disminuir los fallos de capacidad
– Fusionar los bucles que usen los mismos arrays para usar los datos que se encuentran en cache antes de desecharlos
double A[64][64]; double A[64][64];

for (i=0; i < 64; i=i+1) for (i=0; i < 64;i=i+1)
for (j=0; j < 64;j=j+1) for (j=0; j < 64;j=j+1)
C = C * A[i][j]; {
C = C * A[i][j];
for (i=0; i < 64;i=i+1) D = D + A[i][j];
for (j=0; j < 64;j=j+1) }
D = D + A[i][j];
A[0][0:3]
A[15]60:63]
A[15][56:59]
A[0][4:7]
A[0][8:11]
A[0][12:15]
A[16][0:3]
A[16][4:7]
A[16][8:11]
A[16][12:15]
A[31][56:59]
A[31][60:63]
A[32][0:3]
A[47]60:63]
A[47][56:59]
A[32][4:7]
A[32][8:11]
A[32][12:15]
A[48][0:3]
A[48][4:7]
A[48][8:11]
A[48][12:15]
A[63][56:59]
A[63][60:63]
(64×64/4)x2 fallos
4×256 de inicio
4×256 de capacidad
64×64/4 fallos
4×256 de inicio
Ganancia: 2

35
Reducir la tasa de fallos
Compilador: Optimización de código
5) Calculo por bloques( Blocking): Mejora la localidad temporal para disminuir los fallos de capacidad
/* Antes */
for (i=0; i < N; i=i+1)
for (j=0; j < N; j=j+1)
{r = 0;
for (k=0; k < N; k=k+1){
r = r + y[i][k]*z[k][j];};
x[i][j] = r;
};
Dos bucles internos:
Lee todos los NxN elementos de z
Lee N elementos de 1 fila y en cada iteración
Escribe N elementos de 1 fila de x
Fallos de capacidad dependen de N y Tamaño de la cache:

Idea: calcular por submatrices BxB que permita la cache
antes
Después

36
Reducir la tasa de fallos
Compilador: Optimización de código
5) Calculo por bloques( Blocking): Mejora la localidad temporal para disminuir los fallos de capacidad
/* Despues */
for (jj=0;jj < N; jj=jj+B)
for (kk=0;kk < N; kk=kk+B)
for (i=0; i < N; i=i+1)
for (j=jj;j < min(jj+B-1,N);j=j+1)
{r = 0;
for (k=kk;k < min(kk+B-1,N);k=k+1){
r = r + y[i][k]*z[k][j];};
x[i][j] = x[i][j]+r;
};
B Factor de bloque (Blocking Factor)
Mejora de rendimiento

37
Reducir la tasa de fallos
Ejemplo: Producto de matrices 6×6 (sin blocking)
X
Y
Z
i
j
?
i
j
k
k
i = 0, j = 0, k = 0..5
i = 0, j = 1..5 , k = 0..5
Al procesar la 2ª fila de Y (i=1) se necesita de nuevo 1ª col de Z: ¿Está todavía en la cache? Cache insuficiente provoca múltiples fallos sobre los mismos datos
X ij = ? Yik Zkj
k

38
Reducir la tasa de fallos
Ejemplo “blocking”: Con Blocking (B=3)
X
Y
Z
i
j
?
i
j
k
k
i = 0, j = 0, k = 0..2
i = 0, j = 1..2 , k = 0..2
Evidentemente, los elementos de X no están completamente calculados

39
Reducir la tasa de fallos
Ejemplo “blocking”: Con Blocking (B=3)
X
Y
Z
i
j
?
i
j
k
k
i = 1, j = 0, k = 0..2
i = 1, j = 1..2 , k = 0..2
Idea: Procesar el bloque 3×3 de Z antes de quitarlo de la cache

40
Reducir la tasa de fallos
Con Blocking (B=3). Algunos pasos después…

X
Y
Z
i
j
?
i
j
k
k
i = 0, j = 0, k = 3..5
i = 0, j = 1..2 , k = 3..5
Y ya empezamos a tener elementos de X completamente calculados!

41
Reducir la tasa de fallos
¿ Como mejorar el rendimiento de la cache

Reducir la tasa de fallos
Reducir la penalización del fallo
Reducir el tiempo de acceso a la cache

1) Tamaño del bloque
2) Asociatividad
3) Algoritmo de reemplazamiento
4) Cache de víctimas
5) Cache pseudo-asociativas
6) Cache con prebusqueda
7) Compilador: Optimización de código

Resumen

42
Política de actualización :Write-Through vs Write-Back
Write-through: Todas las escrituras actualizan la cache y la memoria
Se puede eliminar la copia de cache – Lo datos estan en la memoria
Bit de control en la cache: Solo un bit de validez
Write-back: Todas las escrituras actualizan solo la cache
No se pueden eliminar los datos de la cache – Deben ser escritos primero en la memoria
Bit de control: Bit de validez y bit de sucio
Comparación:
Write-through:
Memoria ( Y otros lectores ) siempre tienen el último valor
Control simple
Write-back:
Mucho menor AB, escrituras múltiples en bloque
Mejor tolerancia a la alta latencia de la memoria
Recordatorio
Política de actualización :Asignación o no en fallo de escritura

43
Reducir la penalización del fallo
Dar prioridad a la lecturas sobre las escrituras
Con escritura directa ( write through). Buffer de escrituras. Check buffer
si no hay conflicto prioridad lecturas
Con post-escritura. Buffer para bloque sucio y leer primero bloque en fallo
Reemplazamiento de subbloques
No reemplazar el bloque completo sobre un fallo
Localidad y tamaño ( Usado también para reducir almacenamiento de “tags”
Bits de validez

44
Reducir la penalización del fallo
Envío directo de la palabra solicitada al procesador
Carga anticipada ( early restart ): Cuando la palabra solicitada se carga en memoria cache se envía al procesador
Primero la palabra solicitada ( critical word first ): Primero se lleva al procesador y a memoria cache la palabra solicitada
El resto del bloque se carga en memoria cache en los siguientes ciclos
Su eficiencia depende del tamaño del bloque . Util con bloques grandes
=> para bloques pequeños la ganancia es muy pequeña
Problema: localidad espacial, después la siguiente palabra

45
Reducir la penalización del fallo
Idea

Ocultar la latencia de un fallo de cache solapandolo con otras instrucciones independientes
ADD R5,R6,R6
…………………..
…………………..
LD R1, dir
…………………..
…………………..
ADD R4,R4,R1
PREBUSCAR: Caches con prebusqueda
NO BLOQUEAR: Cache que no bloquean
Cache sin bloqueo ( non-blocking, lockup-free )

46
Reducir la penalización del fallo
Permite que la ejecución siga aunque se produzca un fallo mientras ni se necesite el dato

Un fallo sin servir. Sigue ejecutando y proporcionando datos que están en cache
HP7100, Alpha 21064

Múltiples fallos sin servir. R12000 (4) , Alpha21264 (8), HP8500 (10), PentiumIII y 4 ( 4)

Los beneficios dependen de la planificación de instrucciones

Requiere interfase de memoria más complejo ( múltiples bancos )
Memoria
CPU
CPU
Memoria
CPU
CPU
Memoria
CPU
Memoria
Memoria
Fallo La CPU para hasta tener el dato
Fallo Acierto
Fallos
La CPU para cuando necesita dato
Cache sin bloqueo ( non-blocking, lockup-free )

47
Reducir la penalización del fallo
Hay que asociar un registro a la petición cuando se inicia un load sin bloqueo
LD R1,dir

Información necesaria en el control de la función
Dirección del bloque que produce el fallo
Entrada de la Cache para el bloque
Ítem en el bloque que produce el fallo
Registro donde se almacena el dato

Implementación (MSHR Miss Status Holding Register):
Dirección
bloque
Bit
valido
Comparador
Bit
valido
Destino
Formato
Bit
valido
Destino
Formato
Bit
valido
Destino
Formato
Bit
valido
Destino
Formato
Palabra 0
Palabra 1
Palabra 2
Palabra 3
Fallo primario
Fallo secundario

Estructura del MSHR para bloque de 32 byte, palabra 8 bytes
(Solo un fallo por palabra)
Cache sin bloqueo ( non-blocking, lockup-free )

48
FC nº de fallos MF múltiples fallos y nº de búsquedas
AE actualización en escritura
Reducir la penalización del fallo
Cache sin bloqueo ( non-blocking, lockup-free )

49
Reducir la penalización del fallo
Cache multinivel ( L2,L3,…)
Más grande, más rapida ? Dos niveles de cache

L2 Tiempo de acceso medio a memoria (TAMA)
TAMA = Hit TimeL1 + Miss RateL1 x Miss PenaltyL1Miss PenaltyL1 = Hit TimeL2 + Miss RateL2 x Miss PenaltyL2
TAMA = Hit TimeL1 + Miss RateL1 x (Hit TimeL2 + Miss RateL2 +Miss PenaltyL2

Definiciones:
Tasa de fallos local— fallos en esta cache dividido por el numero total de accesos a esta cache (Miss rateL2)
Tasa de fallos global —fallos en esta cache dividido por el numero total de accesos a memoria generados por el procesador
La tasa de fallos global es lo importante
– L1: Afecta directamente al procesador=> Acceder a un dato en el ciclo del procesador
– L2: Afecta a la penalización de L1 => Reducción del tiempo medio de acceso

50
Reducir la penalización del fallo
Cache multinivel ( L2,L3,…)
Cache L1 32Kbytes, cache L2
diferentes tamaños
Tasa de fallos local no es una medida
El tiempo de acceso de L2 solo afecta
al tiempo de penalización
Tamaño de L2>>L1
Reducción de fallos en L2 igual que L1
asociatividad, tamaño de bloque,..
Costo
Local L2
global

51
Reducir la penalización del fallo
1) Dar prioridad a la lecturas sobre las escrituras
2) Reemplazamiento de subbloques
3) Envío directo de la palabra solicitada al procesador
4) Cache sin bloqueo ( non-blocking, lockup-free )
5) Cache multinivel ( L2,L3,…)
¿ Como mejorar el rendimiento de la cache

Reducir la tasa de fallos
Reducir la penalización del fallo
Reducir el tiempo de acceso a la cache

52
Reducir el tiempo de acceso
Caches simples y pequeñas
Pequeña para que: Se pueda integrar junto al procesador
evitando la penalización en tiempo del acceso al exterior
Tiempo de propagación versus tiempo de ciclo del procesador
Simple (grado de asociatividad pequeño)
=> solapamiento y tiempos de acceso menores
Identificación+Comparación+Lectura
(Gp:) ETIQUETA
(Gp:) PAL
(Gp:) MB
(Gp:) ACIERTO
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) MB
(Gp:) Datos
(Gp:) Etiqueta
(Gp:) V
(Gp:) DATO
(Gp:) MULTIPLE
(Gp:) COMPARA
(Gp:) PAL
(Gp:) B
(Gp:) 5
(Gp:) 2
(Gp:) 2
(Gp:) 9

(Gp:) ETIQUETA
(Gp:) PAL
(Gp:) NC
(Gp:) 0
(Gp:) 1
(Gp:) NC
(Gp:) Datos
(Gp:) Etiqueta
(Gp:) V
(Gp:) DATO
(Gp:) MULTIPLE
(Gp:) PAL
(Gp:) B
(Gp:) 6
(Gp:) 1
(Gp:) 2
(Gp:) 9
(Gp:) {
(Gp:) ACIERTO
(Gp:) COMPARA

Directo
Asociativo por conjuntos

53
Reducir el tiempo de acceso
Cache de direcciones virtuales ( evita espera TLB )
Acceder a la cache con la dirección virtual
Al cambio de contexto borrar la cache. Falsos aciertos
Costo = tiempo de borrado ( flush) + fallos iniciales
No borrado, problema de sinónimos Dos direcciones virtuales apuntan la misma dirección física
Solución a los sinónimos y borrado
Añadir un identificador de proceso a cada bloque de cache.
(Gp:) CPU
(Gp:) TLB
(Gp:) $
(Gp:) MEM
(Gp:) DV
(Gp:) DF
(Gp:) DF
(Gp:) Cache
Convencional

(Gp:) CPU
(Gp:) $
(Gp:) TLB
(Gp:) MEM
(Gp:) DV
(Gp:) DV
(Gp:) DF
(Gp:) Cache de
Direcciones virtuales
(Gp:) DV
Tags