Reducción del tiempo de acierto

El tiempo de acierto podemos optimizarlo (minimizarlo) actuando sobre tres factores:

Cachés pequeñas y simples

• El hardware pequeño acelera la comparación de etiquetas y por tanto el tiempo de acierto
• También hace posible su incorporación al chip de la CPU, eliminando el conexionado externo y por tanto el tiempo de acceso desde la CPU

Evitar traducción de direcciones durante la indexación de las cachés

• Utilización de direcciones virtuales en las cachés

Escrituras segmentadas para rápidos aciertos de escritura


Los aciertos de lectura son más rápidos que los de escritura, entre otros motivos porque en los primeros se puede leer el dato de Mc al tiempo que se comprueba si su etiqueta coincide con la de la dirección física. Si no coincide se ignora el dato leído. Esto no es posible en las escrituras, pero sí podemos simultanear la escritura de un dato con la comparación de la etiqueta del siguiente. Es decir, segmentar (pipe-line) la escritura sobre Mc. De esta forma se aceleran los aciertos de escritura.

Reducción de la penalización de fallos [parte 2]

Utilización de un segundo nivel de caché

Como los fallos se sirven leyendo bloques de Mp, una alternativa para disminuir la penalización por fallo consiste en disminuir el tiempo de acceso a Mp utilizando el mismo mecanismo caché, es decir, utilizando una caché intermedia o de segundo nivel (L2) entre Mc (L1)
y Mp.

Reducción de la penalización de fallos [parte 1]

Prioridad a los fallos de lectura frente a los de escritura

Como vimos con anterioridad, con una caché de escritura directa (writre throuhg) la mejora de rendimiento se consigue utilizando un buffer de escritura de tamaño apropiado. Sin embargo, esto complica los accesos a memoria debido a que el buffer en un momento determinado puede contener aún el valor actualizado (escrito) de una posición que debería estar en Mp para servir un fallo de lectura.

Utilización de sub-bloques dentro de un bloque

La utilización de bloques de gran tamaño no solo disminuyen la tasa de fallos sino que reduce el espacio de memoria caché dedicado al directorio (almacenamiento de las etiquetas de los bloques residentes en una línea). Sin embargo, bloques grandes aumentan la penalización por fallos debido al aumento de la cantidad de datos que se deben transferir en el servicio de cada fallo. Una forma de disminuir la penalización por fallos sin modificar los otros factores positivos consiste en dividir el bloque en sub-bloques y asociar un bit de validez a cada sub-bloque. De esta forma, cuando se produzca un fallo, no será necesario actualizar más que el sub-bloque que contiene la palabra referenciada. Esta alternativa hace que no sólo haya que comprobar si el bloque está en la caché comparando etiquetas, sino que habrá que asegurar que el sub-bloque que contiene la palabra referenciada es un sub-bloque válido, es decir, con datos actualizados.

También podemos ver esta alternativa de diseño como una forma de economizar información de directorio asociando una sola etiqueta a un grupo de bloques, e indicando con un bit particular asociado a cada bloque (bit de validez) su estado de actualización cuando el grupo está en Mc. En la siguiente figura se muestra un esquema de esta alternativa de diseño:

Reducción de la tasa de fallos [parte 2]

Prebúsqueda de instrucciones y datos

• La prebúsqueda de instrucciones y/o datos antes de ser demandados por la caché disminuye la tasa de fallos.
• Las instrucciones o datos prebuscados son llevados directamente a la caché o a un buffer externo que es accedido a mayor velocidad que Mp.

• El Alpha AXP 21064 pre-busca dos bloques cuando ocurre un fallo, el que contiene la palabra causante del fallo y el siguiente. El primero lo coloca en MC y 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

Prebúsqueda controlada por el compilador

• Utiliza instrucciones explícitas de prebúsqueda del tipo prefetch(dato) que el compilador utiliza para optimizar los programas después de realizar un análisis de sus sentencias.
• La prebúsqueda se realiza al tiempo que el procesador continúa la ejecución del programa, es decir, la prebúsqueda se hace en paralelo con la ejecución de las instrucciones.
• Los bucles son las construcciones más apropiadas para que el compilador genere prebúsqueda

Optimizaciones del compilador

Las optimizaciones consisten en transformaciones del código fuente del programa, realizadas en tiempo de compilación, con el objetivo de aumentar la localidad espacial y/o temporal del programa, y consiguientemente reducir la tasa de fallos.

Reducción de la tasa de fallos [parte 1]

La tasa de fallos podemos reducirla con las siguientes alternativas:

Aumento del tamaño del bloque

• Al aumentar el tamaño de bloque disminuye la tasa de fallos iniciales (forzosos)
• porque mejora la localidad espacial.
• Sin embargo con el aumento del tamaño de bloque aumenta la penalización de fallos, ya que el tiempo de lectura y transmisión serán mayores si los bloques son mayores.

Aumento de la asociatividad

• Experimentalmente se comprueba que una caché asociativa por conjuntos de 8 vías es tan eficiente (tasa de fallos) como una caché completamente asociativa.
• Una caché de correspondencia directa de tamaño N tiene aproximadamente la misma tasa de fallos que una asociativa por conjuntos de 2 vías de tamaño N/2
• Al aumentar la asociatividad se incrementa el ciclo de reloj y por tanto Tacierto

Utilización de una caché de víctimas

• Se añade una pequeña caché completamente asociativa entre Mc y su camino hacia Mp para contener sólo los bloques descartados (sustituidos) por un fallo (víctimas)
• Ante un fallo se comprueba si el bloque está en la caché de víctima antes de acudir a Mp
• Reduce los fallos de conflicto fundamentalmente en cachés pequeñas con correspondencia directa.

Cachés pseudoasociativas

Se trata de cachés de correspondencia directa que con una ligera modificación se pueden comportar como asociativas. Para ello se permite que un bloque de Mp se pueda ubicar en dos (pseudoasociativa de 2 vías) marcos de bloque de Mc, el que le corresponde (por la correspondencia directa) y el que resulta de conmutar el bit más significativo de la dirección del bloque, tal como se indica en el siguiente esquema:

Factores que determinan el rendimiento de la memoria caché

Si frente a un fallo, el bloque de Mp se lleva a Mc al tiempo que la palabra referenciada del bloque se lleva (en paralelo) a la CPU, el tiempo de acceso a memoria durante la ejecución de un programa será :

Tacceso = Na * Tc + Nf * Tp donde:

Na es el número de referencias con acierto

Nf es el número de referencias con fallo

Tc es el tiempo de acceso a una palabra de Mc

Tp es el tiempo de acceso a un bloque de Mp

El tiempo de acceso a un bloque de Mp, Tp, constituye la componente principal del tiempo total de penalización por fallo.

El tiempo de acceso medio durante la ejecución del programa valdrá:

Tacceso_medio = Tacceso/ Nr = Ta*Tc + Tf*Tp donde:

Ta = Na/Nr es la tasa de aciertos

Tf = Na/Nr es la tasa de fallos

Nr es el número total de referencias a memoria

A la primera componente se le denomina Tacierto = Ta*Tc,

En cambio, si frente a un fallo, el bloque de Mp se lleva primero a Mc y después se lee la palabra referenciada de Mc y se lleva a la CPU, el tiempo de acceso a memoria durante la ejecución de un programa será :

Tacceso = Nr * Tc + Nf * Tp y Tacceso_medio = Tacceso/ Nr = Tc + Tf*Tp En este caso Tacierto = Tc

De cualquiera de las expresiones anteriores podemos deducir que para mejorar el rendimiento de una caché, podemos actuar sobre tres términos, dando lugar a tres tipos de optimizaciones:

1. Reducción de la tasa de fallos, Tf
2. Reducción de la penalización de los fallos, Tp
3. Reducción del tiempo de acierto, Tacierto

Clasificación de los fallos caché

Los fallos de la caché se pueden clasificar en tres tipos:

• Forzosos: producidos por el primer acceso a un bloque.
• Capacidad: producidos cuando Mc no puede contener todos los bloques del programa.
• Conflicto: (en correspondencia directa o asociativa por conjuntos) producidos por la necesidad de ubicar un bloque en un conjunto lleno cuando Mc no está completa.