Download 1. Introducci´on. 2. Mejora de la penalizaci´on por fallo. 3. Mejora de

T EMA 11: M EJORA DE LAS PRESTACIONES DE LAS CACHE .
1. Introducción.
2. Mejora de la penalización por fallo.
3. Mejora de la tasa de fallos.
4. Mejora de la tasa de fallos y penalización por fallo mediante
paralelismo.
5. Mejora del tiempo en caso de acierto.
Bibliografı́a:
J.L. Hennessy & D. A. Patterson. Computer Architecture: A Quantitative Approach 2a y 3a ed., Morgan Kauffman Publishers, 1996 y 2002.
Departamento de Informática de Sistemas y Computadores (DISCA)
Facultad de Informática de Valencia
11-1
1 INTRODUCCIÓN
1. Introducción
Tiempo de acceso medio a memoria:
Tacceso = T A + T F × P F
¿Mejorar las prestaciones de las cache?
Para mejorar las prestaciones de las cache hay que actuar sobre cada uno de los
términos:
Reducir el tiempo en caso de acierto (T A).
Reducir la tasa de fallos (T F ).
Reducir la penalización por fallo (P F ).
11-2
2 MEJORA DE LA PENALIZACIÓN POR FALLO
2. Mejora de la penalización por fallo
Caches multinivel
Nuevo nivel de cache (L2) ubicado entre la memoria cache y la memoria
principal:
• La cache L1 es lo suficientemente pequeña como para ser tan rápida
como el procesador.
• La cache L2 es lo suficientemente grande como para capturar muchos
de los accesos a memoria principal.
¿Cómo cambia la ecuación del tiempo de acceso?
Tacceso = T AL1 + T FL1 × P FL1
Y la penalización en caso de fallo de cache L1 es:
P FL1 = T AL2 + T FL2 × P FL2
Sustituyendo:
Tacceso = T AL1 + T FL1 × (T AL2 + T FL2 × P FL2 )
En un sistema de memoria con varios niveles de cache distinguimos dos tipos
de tasas de fallos:
• Tasa de fallos local=
Num. de fallos de la cache
Num. total accesos cache
◦ Para la cache L1 es T FL1
◦ Para la cache L2 es T FL2
• Tasa de fallos global=
Num. de fallos de la cache
Num. total accesos
◦ Para la cache L1 es T FL1
Fallos L2
Fallos L1
◦ Para la cache L2 es Total
= Total
· Fallos L2 =
accesos
accesos Fallos L1
Fallos L2
= T FL1 × T FL2
Accesos L2
→ Fracción de accesos que llegan a la memoria
Fallos L1
AccesosL1
11-3
·
2 MEJORA DE LA PENALIZACIÓN POR FALLO
Caches multinivel (cont.)
Efecto sobre la tasa de fallos:
Algunos aspectos de diseño:
• La velocidad de la cache L1 afecta al ciclo de reloj del procesador
◦ Cache L1 pequeña y con correspondencia directa.
• Velocidad de la cache L2 afecta la penalizaci ón por fallo de L1
¿Reducir P FL1 = T AL2 + T FL2 × P FL2 ? → Reducir T FL2
◦ Cache L2 mucho mayor que L1 y con correspondencia asociativa.
Inclusión/exclusión multinivel
• Inclusión multinivel
◦ Los datos que están en la cache L1 están siempre en la cache L2.
◦ Interesante para garantizar coherencia. Sólo es necesario comprobar el nivel superior (L2).
◦ Deben emplearse tamaños de bloque iguales en la caches L1 y L2
o en caso de reemplazamiento en L2 hay que invalidar todos los
bloques de L1 que componen el bloque de L2, aumentando T F L1 .
• Exclusión multinivel (AMD Athlon)
◦ Los datos contenidos en L1 nunca están en la cache L2
◦ Un fallo en L1 intercambia bloques entre las cache L1 y L2
◦ Evita desperdiciar espacio en la cache L2.
◦ Es interesante cuando el tamaño de la cache L2 es solo ligeramente
superior al de la cache L1
11-4
2 MEJORA DE LA PENALIZACIÓN POR FALLO
“Critical word first y “Early restart”
El procesador sólo necesita una palabra del bloque que ha provocado el fallo.
Idea: no esperar a tener el bloque totalmente cargado para entregar la palabra solicitada al procesador.
Critical word first
• Accede primero en memoria a la palabra solicitada por el procesador.
• Trae el resto del bloque mientras el procesador continua con la ejecución.
Early restart:
• Acceder a las palabras del bloque normalmente.
• En cuanto se lee la palabra solicitada por el procesador se le entrega y
éste continua con la ejecución.
Con estas técnicas, se obtienen ventajas cuando:
Se emplean tamaños de bloque grandes.
Cuanto menor sea la probabilidad de acceder a otra palabra del bloque antes
de que se haya cargado totalmente.
11-5
2 MEJORA DE LA PENALIZACIÓN POR FALLO
Buffers de escritura
Problema de las escrituras:
• Write-through: y No-write allocate
Las escrituras se hace directamente sobre la memoria principal.
El procesador se detiene hasta que la escritura se ha hecho.
• Write-back:
Cuando se reemplaza un bloque ”sucio”, hay que escribirlo en memoria
principal.
El procesador se detiene hasta que la escritura se ha hecho.
Idea: buffer de escritura.
• el procesador escribe sobre el buffer en vez de sobre la memoria y
• continua la ejecución en paralelo con la escritura en memoria.
Problema: dependencias de datos con la memoria.
1 sd r3,a(r10)
2 ld r1,b(r11)
3 ld r2,a(r10)
; Escritura con fallo y write-through en Mem[a+r10]
; Lectura con fallo de Mem[a+r10]
→ Si la escritura del r3 (instr 1) no se ha realizado cuando se lee el r2 (instr
3), el valor cargado es incorrecto
Solución:
• Esperar a que el buffer de escritura se vacı́e antes de leer el dato.
• Comprobar si la dirección referenciada está en el buffer de escritura, y,
sino está dejar que la lectura continúe.
11-6
2 MEJORA DE LA PENALIZACIÓN POR FALLO
Buffer de escrituras combinadas
Escribir un bloque completo en memoria es más efectivo que una palabra.
Idea: Se intenta completar todo un bloque antes de escribir en la memoria.
Caches vı́ctima
Idea: guardar lo que se desecha por si acaso se necesita nuevamente → cache vı́ctima.
Cache vı́ctima: pequeña cache totalmente asociativa que alberga los bloques desechados por reemplazamientos.
En caso de fallo de cache, se comprueba si está alojado en la cache vı́ctima.
En caso afirmativo, se intercambia el bloque entre la cache y la cache vı́ctima.
Es una técnica efectiva con tan sólo unos pocos bloques en la cache vı́ctima (8
entradas en el Athlon) .
11-7
3 REDUCIR LA TASA DE FALLOS.
3. Reducir la tasa de fallos.
Clasificación de los fallos de bloque:
Primera vez (compulsory). Los originados la primera vez que se accede a un
bloque.
→ Suelen representar un bajo porcentaje del total de fallos.
Capacidad. Si la cache no puede alojar todos los bloques necesarios durante
la ejecución de un programa, se producirán fallos de capacidad: hay bloques
que se descartan y que después deben volver a cargarse.
→ Una cache muy grande los reduce a cero.
Conflicto. Si la correspondencia es directa o asociativa por conjuntos, aparecen fallos por conflicto: hay bloques que se descartan y luego tienen que cargarse nuevamente si se ubican en el mismo lugar de la cache.
→ Una cache totalmente asociativa los reduce a cero, pero necesita mucho
hardware y puede reducir la frecuencia de reloj.
La técnicas para reducir la tasa de fallos pretenden reducir cada uno de ellos.
11-8
3 REDUCIR LA TASA DE FALLOS.
Aumentar el tamaño de bloque
Reduce los fallos de primera vez (↓ T F ). Mejora la localidad espacial.
Reduce el número de bloques para un misma capacidad de la cache.
• Puede empeorar los fallos por conflicto (↑ T F ).
• Puede empeorar los fallos por capacidad (↑ T F ).
Aumenta la penalización en caso de fallo (↑ P F ), ya que hay que traer más
información de la memoria.
P F depende de la latencia L y ancho de banda B de la memoria: P F =
L + B1 n, siendo n el tamaño de bloque.
Recordando la ecuación del tiempo de acceso Tacc = T A + T F × P F :
• Si la memoria tiene alta latencia y alto ancho de banda:
Interesa tamaño de bloque grande, ya que reduce T F con poco aumento
de P F .
• Si la memoria tiene baja latencia y bajo ancho de banda:
Interesa tamaño de bloque pequeño. Traerse un bloque más grande reduce T F pero aumenta notablemente P F .
11-9
3 REDUCIR LA TASA DE FALLOS.
Aumentar el tamaño de la cache
Reduce los fallos por capacidad (↓ T F ).
Aumenta el coste.
Aumenta el tiempo en caso de acierto (↑ T A).
Mayor asociatividad
Reduce los fallos por conflicto (↓ T F ).
Requiere más comparadores → puede aumentar el tiempo en caso de acierto
(↑ T A)
Reglas empı́ricas:
Una correspondencia asociativa de 8 vı́as es casi tan buena como totalmente
asociativa.
Una cache con correspondencia directa de tama ño N tiene la misma tasa de
fallos que una asociativa de dos vı́as de tamaño N2 .
11-10
3 REDUCIR LA TASA DE FALLOS.
Predicción de vı́a y cache pseudo-asociativas
Objetivo: reducir los fallos por conflicto sin aumentar el tiempo en caso de
acierto.
Idea: predicción de vı́a (Alpha 21264):
• La cache es asociativa.
• La cache incluye un predictor de qué bloque del conjunto se referenciará la próxima vez que se acceda a la cache.
• Se accede al bloque predicho, y si la predicci ón es correcta, se devuelve.
En otro caso, se compara con el resto de etiquetas.
• Hay dos tiempos en caso de acierto:
◦ Si la predicción es correcta: sólo se compara con la etiqueta de este
bloque → tiempo en caso de acierto bajo
◦ En caso de fallo en la predicción, se compara con el resto de bloques
del conjunto → tiempo en caso de acierto más elevado.
El predictor acierta en el 85 % de los casos.
Cache pseudoasociativa.
• Un bloque puede estar ubicado en dos sitios en la cache:
◦ El obtenido aplicando una correspondencia directa.
◦ El obtenido aplicando otra función sencilla (por ejemplo, invertir el
bit de mayor peso del ı́ndice) → pseudo-conjunto.
• Hay dos tiempo en caso de acierto:
◦ Si el bloque se encuentra en el primer lugar: tiempo en caso de
acierto similar al de una correspondencia directa.
◦ Si el bloque se encuentra en el pseudo-conjunto: tiempo en caso de
acierto mayor.
Aumenta la penalización por fallo (P F ↑) en caso de que el bloque no esté ni
en la primera ni en la segunda ubicación. Se gasta tiempo en comprobar la
segunda ubicación antes de ir a la memoria principal.
11-11
3 REDUCIR LA TASA DE FALLOS.
Optimizaciones del compilador
El compilador genera un código optimizado que reduce la tasa de fallos.
Reducción de la tasa de fallos de instrucciones:
• Obtención de estadı́sticas sobre conflictos entre grupos de instrucciones.
• Reordenación de grupos de instrucciones para reducir los fallos de conflicto.
Reducción de los fallos de datos
Ejemplo: operaciones con vectores. Reorganizar el c ódigo para operar sobre
todos los datos de un bloque antes de pasar al siguiente.
• Mejorar la localidad espacial. Intercambio de bucles
Simplemente cambiando el anidamiento de los bucles podemos conseguir operar con los datos en el orden en que están almacenados:
Ejemplo, vector x almacenado por filas:
/* antes */
for (j=0; j<100; j=j+1)
for (i=0; i<5000; i=i+1)
x[i][j] = 2* x[i][j]
/* despues */
for (i=0; i<5000; i=i+1)
for (j=0; j<100; j=j+1)
x[i][j] = 2* x[i][j]
→ salta 100 palabras en cada acceso → accede secuencialmente los datos.
• Mejorar la localidad temporal: blocking
Si los vectores se acceden tanto por filas como por columnas, es mejor
operar sobre submatrices o bloques, tratando de maximizar los accesos
a los datos cargados en la cache antes de reemplazarlos.
Ejemplo: multiplicación de matrices
/* despues */
/* antes */
for (jj=0; jj<N; jj=jj+B)
for (i=0; i<N; i=i+1)
for (kk=0; kk<N; kk=kk+B)
for (j=0; j<N; j=j+1)
for (i=0; i<N; i=i+1)
{ r=0;
for (j=jj; j< min(jj+B,N); j=j+1)
for (k=0; k<N; k=k+1)
{ r=0;
r = r+y[i][k]*z[k][j]
for (k=kk; k<min(kk+B,N); k=k+1)
x[i][j] =r;
r = r+y[i][k]*z[k][j]
};
x[i][j] =x[i][j]+r;
};
11-12
4 REDUCIENDO PF/TF MEDIANTE PARALELISMO
4. Reduciendo la penalización por fallo/tasa de fallos
mediante paralelismo
→ técnicas que solapan la ejecución de instrucciones en el procesador con el acceso
a la memoria.
Cache no bloqueante
La cache continua aceptando peticiones de acceso mientras se está sirviendo
un fallo de cache.
Posibilidades:
• “acierto ante fallo”: la cache suministra o acepta nuevas peticiones, siempre éstas sean aciertos.
• “fallo ante fallo”/“acierto ante múltiples fallos”: se pueden servir múltiples fallos simultáneamente.
11-13
4 REDUCIENDO PF/TF MEDIANTE PARALELISMO
Pre-búsqueda hardware de instrucciones y datos
Idea: buscar la información antes de que sea solicitada por el procesador.
La información pre-búscada se almacena en un buffer externo, que se accede
más rápido que la memoria principal.
Pre-búsqueda de instrucciones.
• El procesador trae dos bloques ante un fallo: el bloque solicitado, que se
ubica en la cache y el consecutivo, que se ubica en el buffer de instrucciones.
• Cuando se produce un fallo de cache, se lee el bloque del buffer de
instrucciones, si está disponible y se lanza la siguiente pre-búsqueda.
• Evaluación de la propuesta. Cache de 4KB con bloques de 16 bytes:
1 único buffer evita un 15 %–25 % de los fallos
4 buffers evitan un 50 % de los fallos
16 buffers evitan un 72 % de los fallos
Pre-búsqueda de datos.
• Similar a la de instrucciones.
• El bloque pre-buscado puede ser el consecutivo o estimado de alguna
manera (por ejemplo, tomando en cuenta la diferencia entre la última
dirección y la previa, UltraSPARC III).
Los accesos a memoria principal por pre-búsqueda pueden interferir con los
fallos de cache → puede aumentar la penalizaci ón por fallo de estos últimos.
11-14
4 REDUCIENDO PF/TF MEDIANTE PARALELISMO
Pre-búsqueda controlada por el compilador
El compilador inserta instrucciones de “pre-búsqueda” para solicitar los datos
antes de que se necesiten.
La pre-búsqueda debe ser invisible al programa:
• no debe cambiar el contenido de los registros ni de la memoria
• no debe generar fallos de página de memoria virtual ni excepciones por
violación de protección.
→ nonbinding fetch
Especialmente útil en bucles. Ejemplo:
/* original */
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];
/* con pre-búsqueda */
for (j=0; j<100; j=j+1) {
prefetch(b[j+7][0])
prefetch(a[0][j+7])
a[0][j] = b[j][0]*
b[j+1][0];};
for (i=1; i<3; i=i+1)
for (j=0; j<100; j=j+1) {
prefetch(a[i][j+7])
a[i][j] = b[j][0]*
b[j+1][0];};
Hay cierta sobrecarga: la inserción de instrucciones de pre-búsqueda aumenta
el número de instrucciones ejecutadas por el programa.
→ hay que concentrarse en los accesos que serán fallos de bloque con una
probabilidad alta.
11-15
5 REDUCIENDO EL TIEMPO EN CASO DE ACIERTO.
5. Reduciendo el tiempo en caso de acierto.
Reducir el tiempo en caso de acierto es muy importante: afecta al periodo de reloj
del procesador (la T de la ecuación del tiempo de ejecución).
Caches pequeñas y sencillas
Un gran % del tiempo de acceso a la cache se invierte en comparar el campo
de etiqueta de la dirección con las etiquetas almacenadas en la cache.
Modo de reducir este tiempo:
• Cache pequeña: “el hardware pequeño es más rápido” y cabe en el mismo chip que el procesador.
• Cache sencilla: correspondencia directa → puede solaparse la lectura
del dato con la comprobación de la etiqueta.
Tendencia:
• Caches L1: pequeñas y sencillas.
• Cache L2: más grandes, manteniendo las etiquetas en el mismo chip que
el procesador y los datos en otro chip.
11-16
5 REDUCIENDO EL TIEMPO EN CASO DE ACIERTO.
Evitar la traducción de memoria virtual durante el acceso a la
cache
Otra componente del tiempo en caso de acierto es el invertido en traducir la dirección virtual emitida por el procesador en una direcci ón fı́sica de memoria.
Idea. Utilizar direcciones virtuales en la cache. Caches virtuales vs. caches
fı́sicas
Problemas:
• Protección. Es parte del proceso de traducción dirección virtual → fı́sica.
Hay que copiar información de la TLB a la cache.
• Procesos. Cada vez que se cambia de contexto, una misma direcci ón
virtual apunta a una dirección fı́sica distinta. Hay que vaciar la cache
con cada cambio de contexto o bien añadir identificadores de proceso
(PID) a las etiquetas de la cache.
• Sinónimos o alias. Una misma dirección fı́sica puede referenciarse mediante dos o más direcciones virtuales. Hay varias copias del mismo
dato, que deben mantenerse idénticas.
Nueva idea. La dirección dentro de la página (page offset) es la misma, tanto
en la dirección virtual como en la fı́sica.
Virtually indexed physically tagged caches (Alpha 21264).
• Utiliza parte de la dirección dentro de la página para seleccionar el conjunto (campo de “Índice”).
• La lectura de la cache se realiza en paralelo con la traducci ón.
• Limitación: el tamaño de una cache con correspondencia directa o del
número de conjuntos de una cache con correspondencia asociativa no
puede exceder el tamaño de página de memoria virtual.
11-17
5 REDUCIENDO EL TIEMPO EN CASO DE ACIERTO.
Virtually indexed physically tagged caches (cont.)
11-18
5 REDUCIENDO EL TIEMPO EN CASO DE ACIERTO.
Segmentación de la cache
Segmenta el hardware de acceso a la cache de instrucciones.
Un acceso a la cache requiere varios ciclos de reloj (por ejemplo, 4 ciclos en
el Pentium 4).
Pero pueden haber varios accesos en curso.
Tiene implicaciones en la segmentación del procesador: más ciclos de parada
en los saltos y en las operaciones de carga.
Realmente, esta técnica aumenta el ancho de banda de la cache de instrucciones
más que reducir su latencia.
11-19