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