Memorias Entrelazadas y Cache: Principios y Optimización del Rendimiento

Memorias Entrelazadas

(2.4) Memorias Entrelazadas:

Idea: Dividir la memoria en módulos independientes para tener acceso simultáneo a varias palabras en diferentes módulos (entrelazamiento).
Condición de Eficiencia: Las referencias a memoria se distribuyen equitativamente entre módulos, siendo clave dicha distribución.
Situación Ideal: El ancho de banda de acceso a memoria se multiplica por el número de módulos.
Especificaciones:
- Memoria Total = N = 2ⁿ palabras.
- Número de Módulos = M = 2^m.

Existen dos esquemas de entrelazamiento, y con cualquiera de ellos se pueden obtener M palabras en paralelo por cada acceso a memoria. Existe conflicto de memoria cuando varias direcciones requieren a la vez un acceso al mismo módulo, reduciendo la velocidad de acceso. Los conflictos de memoria son mayores en orden superior debido a la secuencialidad de los programas. En sistemas multiprocesador, a veces es mejor el entrelazamiento superior cuando las tareas son disjuntas o interaccionan poco entre sí (lo cual no es siempre cierto). Se suele usar el entrelazamiento de orden inferior.

Esquemas de Entrelazamiento

1) Entrelazamiento de Orden Superior (Consecutivo)

Dirección física: n bits.
Al i-ésimo módulo le corresponden las direcciones consecutivas i · 2^{n – m} hasta (i+1) · 2^{n – m} – 1.
Los m bits más significativos identifican el módulo y el resto un desplazamiento dentro del módulo.
Ventajas: Expandibilidad y fiabilidad (un fallo se restringe a un área localizada del espacio de direcciones).

2) Entrelazamiento de Orden Inferior (Cíclico)

En el i-ésimo módulo se almacenarán las direcciones de la forma K · M + i con k = 0, 1, …, 2^{n – m} – 1 (espaciamiento M entre ellas).
Los m bits menos significativos de la dirección física seleccionan el módulo y el resto la posición dentro del módulo.

2a) Con Latches en la Salida

En cada acceso son leídas M palabras consecutivas: K · M + i con i = 0, 1, …, M – 1.
Se almacenan en latches y son transferidas en serie por un MUX.
Las palabras son leídas en el siguiente ciclo, lo que implica mecanismos de anticipación.
En el mejor caso, el tiempo de acceso se reduce a M.
Es ideal para accesos a memoria secuenciales.
Baja su eficiencia en programas no secuenciales (saltos). Para solucionarlo, se pueden diseñar sistemas con latches a la entrada.

2b) Con Latches a la Entrada

Cada módulo puede usar una dirección relativa particular.
Necesita un controlador de memoria para procesar las peticiones una a una secuencialmente.
Si una petición encuentra el latch ocupado por otra previa, es retardada.

Memoria Cache

(T.3) Memoria Cache:

Objetivo: Lograr una memoria rápida e ilimitada.
Principio de Localidad: Los programas acceden a una parte relativamente pequeña de su espacio de direcciones en cualquier instante de tiempo.

Principio de Localidad

a) Localidad Temporal: Si un elemento es referenciado, volverá a ser referenciado pronto (ej. bucles).
b) Localidad Espacial: Si un elemento es referenciado, los elementos cuyas direcciones estén próximas tenderán a ser referenciados pronto.

Aprovechando el principio de localidad, se implementa la memoria de un computador como una jerarquía de memoria, presentando al usuario tanta memoria disponible como sea posible en la tecnología más barata, mientras se proporciona el acceso a la velocidad ofrecida por la memoria más rápida. En nuestra jerarquía de memoria, el nivel más alto para nosotros será la memoria cache, dejando los registros de lado aparte. Un nivel más cercano al procesador es un subconjunto de cualquier nivel más apartado, y todos los datos están almacenados en el nivel más bajo, ubicándose la información en cada nivel de acuerdo a su probabilidad de uso.

Introducción a las Caches

(3.1) Introducción a las Caches:

El término fue introducido por Conti, Gibson y Pitkowsky (1968).
El primer computador comercial con cache fue el IBM 360/85 (1968).
La cache es una memoria pequeña y rápida que se sitúa entre el procesador y la memoria principal.
Almacena la información actualmente en uso de la memoria principal.
La gestión de la cache es similar a la gestión de memoria virtual.
El principio de localidad justifica el éxito de la cache.
Bloque (Línea Cache): Unidad mínima de transferencia de información entre un nivel superior y otro inferior.
Acierto (Hit): La información requerida aparece en el nivel superior.
Fallo (Miss): La información no se encuentra en el nivel superior y es necesario acceder al inferior.
Tasa de Aciertos (Hit Rate): Fracción de accesos a memoria encontrados en el nivel superior.
Tasa de Fallos (Miss Rate): Fracción de accesos a memoria no encontrados en el nivel superior (1 – Tasa de Aciertos).
Penalización de Fallo (Miss Penalty): Tiempo necesario para sustituir un bloque del nivel superior por el del nivel inferior, más tiempo para entregar este bloque al procesador. Se divide en:
- a) Tiempo de Acceso: Tiempo para acceder a la primera palabra de un bloque en un fallo.
- b) Tiempo de Transferencia: Tiempo adicional para transferir las restantes palabras del bloque.
Tiempo de Acierto (Hit Time).

Operación de un Sistema Cache

(3.2) Operación de un Sistema Cache:

Al bloque de una cache se le llama línea.

Estructura de una Cache

Directorio: Contiene información sobre las líneas de la zona de almacenamiento.
Zonas de Almacenamiento: Contiene copia de algunas líneas de la memoria principal.

El directorio contiene un conjunto de etiquetas para identificar si una palabra de la cache se corresponde con la palabra buscada. Además, necesitamos alguna forma de reconocer si un bloque de cache no tiene información válida (bit de validez: a 0 indica información no válida).

Ubicación de Líneas (Organización Cache)

Existen 3 categorías de organización cache (n líneas):

1) Correspondencia Directa (Direct Mapped)

Cada línea tiene un único lugar donde puede aparecer en la cache.
Campos de la dirección: Etiqueta, Línea de la cache (log₂n – tamaño índice), Palabra dentro de la línea, Byte de palabra.
1 vía, n conjuntos.

2) Totalmente Asociativa (Fully Associative)

Cada línea puede estar en cualquier parte de la cache.
Campos de la dirección: Etiqueta, Palabra dentro de la línea, Byte de palabra.
n vías, 1 conjunto.

3) Asociativa por Conjuntos de m Vías (Set Associative)

A cada línea le corresponde un conjunto de m líneas de la cache.
Número de conjuntos = n/m = c.
Campos de la dirección: Etiqueta, Índice del conjunto (log₂c), Palabra dentro de la línea, Byte de palabra.

Búsqueda de Líneas

Índice: Selecciona un conjunto de la cache.
Etiqueta: Se compara simultáneamente con todas las etiquetas del conjunto seleccionado.
El bit de validez nos indica si la entrada contiene una dirección válida.
Aumentar la asociatividad incrementa el tamaño de la etiqueta.

Reemplazo de Líneas

Tenemos que establecer un criterio para reemplazar líneas en un fallo de cache.

En correspondencia directa: Una única posibilidad.
En asociativa por conjuntos o totalmente asociativa: Hay que escoger una línea entre las de un conjunto o entre todas las de la cache, respectivamente.

Principales Estrategias de Reemplazo

Aleatoria: Se hace una elección aleatoria (fácil de implementar).
Menos Recientemente Usado (LRU – Least Recently Used): El bloque sustituido es el que hace más tiempo que no es usado.

Operación de Escritura

Existen 2 opciones básicas para escribir en cache:

1) Escritura Directa (Write-Through)

La información se escribe en la cache y en la memoria de nivel inferior simultáneamente.
Ventajas: Fácil de implementar (puede requerir detención de la UCP en la escritura, mitigado con un buffer de escritura), fallos de lectura menos costosos y la memoria del nivel inferior está siempre actualizada.

2) Postescritura (Write-Back)

Solo se escribe en la cache y, cuando se reemplaza la línea, se escribe en memoria.
Ventajas: Escritura a la velocidad de la cache, múltiples escrituras en una línea implican una sola escritura de la línea completa en la memoria, menor ancho de banda de memoria y se puede hacer uso efectivo del ancho de banda del nivel más bajo.

Bit de Modificación (Dirty Bit): Bit de estado que se usa en postescritura para indicar si una línea se ha modificado o no. Reduce la frecuencia de escritura ante reemplazos de línea, ya que si la línea no se ha modificado, no hace falta escribirla en memoria.

Opciones en un Fallo de Escritura (Write Miss)

Ubicar en Escritura (Write Allocate) o Búsqueda en Escritura: La línea se carga en la cache y siguen las acciones de acierto de escritura (típico en postescritura). Se busca que las escrituras subsiguientes en la línea no provoquen fallos.
No Ubicar en Escritura (No Write Allocate) o Evitar Escritura: La línea se modifica directamente en el nivel inferior y no se carga en la cache (típico en escritura directa). Las escrituras subsiguientes en la línea provocarán escrituras a memoria.

Rendimiento de la Cache

(3.3) Rendimiento de la Cache:

Tiempo Medio de Acceso a Memoria = Tiempo_Acierto + (Tasa_Fallos x Penalización_Fallo)
Tiempo_CPU = (Ciclos_{Ejecución CPU} + Ciclos_{Detención Memoria}) x Tiempo_{Ciclo Reloj}

Para simplificar, asumiremos que todas las detenciones son debidas a la cache e incluiremos los ciclos de reloj de los aciertos como ciclos de reloj de ejecución CPU:

Ciclos_{Detención Memoria} = [(Lecturas/Programa) x Tasa_{Fallos Lectura} x Penalización_{Fallos Lectura}] + [(Escrituras/Programa) x Tasa_{Fallos Escritura} x Penalización_{Fallos Escritura}]

Combinando las lecturas y escrituras, simplificamos:

Ciclos_{Detención Memoria} = (Accesos Memoria/Programa) x Tasa_Fallos x Penalización_Fallos

Factorizando el recuento de instrucciones (IC):

Tiempo_CPU = IC x [CPI_Ejecución + (Accesos Memoria/Instrucción) x Tasa_Fallos x Penalización_Fallos] x Tiempo_{Ciclo Reloj}

Si consideramos la tasa de fallos como fallos por instrucción:

Tiempo_CPU = IC x [CPI_Ejecución + (Fallos/Instrucción) x Penalización_Fallos] x Tiempo_{Ciclo Reloj}

El comportamiento de la cache tiene gran influencia en el rendimiento. En una CPU con CPI bajo y un reloj rápido, tiene un doble impacto:

A menor CPI, el impacto relativo de los ciclos de detención es más pronunciado.
Para idénticas jerarquías de memoria de dos computadores, la CPU con mayor frecuencia de reloj usa mayor número de ciclos en un fallo.

En las ecuaciones anteriores, hemos supuesto que el tiempo de acierto no es un factor determinante en el rendimiento. En las técnicas de mejora del rendimiento de cache, nos fijaremos como objetivo razonable minimizar el Tiempo Medio de Acceso a Memoria; sin embargo, debemos tener en cuenta que el objetivo final es reducir el Tiempo_CPU.

Fuentes de Fallos de Cache

(3.4) Fuentes de Fallos:

Forzosos (Compulsory Misses): El primer acceso a una línea no está en la cache (llamados también ‘fallos de arranque en frío’ o ‘fallos de primera referencia’).
De Capacidad (Capacity Misses): La cache no tiene capacidad suficiente para contener todas las líneas necesarias durante la ejecución de un programa.
De Conflicto (Conflict Misses): Ocurren en organizaciones asociativa por conjuntos o de correspondencia directa, cuando una línea es descartada y posteriormente recuperada, si a un conjunto le corresponden demasiadas líneas (llamados también ‘fallos de colisión’).

Características del modelo de clasificación de fallos:

Da una visión del comportamiento medio.
No explica fallos individuales.
No tiene en cuenta la política de reemplazo.

Muchas técnicas de reducción de la tasa de fallos pueden incrementar el Tiempo_Acierto o la Penalización_Fallo.

Caches de Datos e Instrucciones

(3.5) Caches de Datos e Instrucciones:

Las caches unificadas o mixtas que contienen instrucciones y datos pueden ser un cuello de botella. La CPU sabe si está emitiendo la dirección de una instrucción o dato, pudiendo separar puertos.

Ventajas de Caches Separadas (Split Cache)

Casi dobla el ancho de banda entre la CPU y la jerarquía de memoria.
Optimización por separado de cada cache.
Elimina fallos de conflicto entre instrucciones y datos.

Inconvenientes de Caches Separadas

Espacios fijos para instrucciones y datos, lo que puede llevar a una peor Tasa_Aciertos si la carga de trabajo es desequilibrada.
Inconsistencia: Si instrucciones y datos están en la misma línea, o si las instrucciones son modificables (código automodificable, poco común hoy en día).

Reducción de la Tasa de Fallos

(3.6) Reducción de la Tasa_Fallos:

Incrementar el Tamaño de la Línea

Reduce los fallos forzosos.
Puede incrementar los fallos de conflicto y de capacidad.
Incrementa la Penalización_Fallo.
La selección del tamaño de línea depende de la latencia y del ancho de banda del nivel inferior de la jerarquía de memoria.

Incrementar la Asociatividad

Reduce los fallos de conflicto.
En la práctica, una cache asociativa por conjuntos de 8 vías es tan efectiva como una totalmente asociativa.
Una cache de correspondencia directa tiene aproximadamente la misma Tasa_Fallos que una cache asociativa por conjuntos de 2 vías de la mitad de tamaño.
Puede aumentar el Tiempo_Acierto (incrementa el Tiempo_{Ciclo Reloj}).

Caches Víctimas (Victim Caches)

Cache pequeña totalmente asociativa.
Guarda las líneas eliminadas de la cache principal en un fallo.
Si la línea requerida se encuentra en ella, es intercambiada con una línea de la cache principal.
Especialmente útiles para caches de datos pequeñas de correspondencia directa.

Caches Pseudo-Asociativas (Pseudo-Associative Caches)

En un fallo, antes de ir al nivel inferior de la jerarquía de memoria, se chequea otra línea de la memoria (‘pseudo-conjunto’).
Existen dos posibles Tiempos_Acierto.
Hay que colocar correctamente las líneas para no degradar el rendimiento.
Puede complicar el diseño de CPU segmentadas.

Prebúsquedas de Instrucciones y Datos (Prefetching)

El objetivo es solapar la ejecución con la prebúsqueda.
El rendimiento puede reducirse si interfiere en la demanda de los fallos.
Puede realizarse de 2 formas:
1. Hardware: Directamente en la cache o en un buffer externo.
2. Controlada por el Compilador: El dato prebuscado se puede grabar en un registro o en la cache.

Optimización en Tiempo de Compilación

Mediante la reordenación del código o la reubicación de los datos, se puede reducir la Tasa_Fallos.
Algunos ejemplos de técnicas son la fusión de arrays, intercambio de lazos (loops), blocking o la fusión de lazos.

Reducción de la Penalización de Fallo

(3.7) Reducción de la Penalización_Fallo:

Dar Prioridad a los Fallos de Lectura sobre las Escrituras

En una cache de escritura directa (write-through): Añadimos un buffer de escritura del tamaño adecuado, con el inconveniente de que puede tener el valor actualizado de una posición necesaria en un fallo de lectura, con lo que o esperamos a que se vacíe el buffer o comprobamos el contenido del buffer.
En una cache de postescritura (write-back): Añadimos un buffer para almacenar el bloque modificado, deteniéndose la CPU si se presenta un nuevo fallo hasta que se vacíe el buffer.

Ubicar Subbloques (en caches de correspondencia directa)

Los subbloques tienen bit de validez.
Reduce la Penalización_Fallo.
Reduce el tamaño de la etiqueta.
Ayuda en los aciertos de escritura escribiendo siempre la palabra.