Tema 3.b: ¿Cómo afectan las decisiones de organización de la memoria caché a su rendimiento?

Ya en otro artículo hicimos referencia muy por encima a la jerarquía de memoria. En este vamos a intentar explicar con un poco más de detalle el concepto que hay detrás. Este tema resulta engañosamente sencillo y se complica muy rápidamente en cuanto profundizamos un poco, así que como estos artículos son más bien de tipo divulgativo intentaré no perderme en tecnicismos y tecnología o conceptos puramente electrónicos.

Para que un procesador pueda hacer un trabajo debe realizar infinidad de operaciones sobre una serie de operandos, la memoria de todo el sistema existe principalmente para proveer al procesador de operandos y almacenar los resultados de las operaciones que efectúa sobre ellos. La situación ideal es que el procesador pueda leer esos datos de forma instantánea pero los límites de la tecnología imponen una velocidad máxima o un tiempo de acceso mínimo que no es posible mejorar sin cambiar la tecnología.

En vista de eso la primera solución que se nos ocurre es usar siempre el tipo de memoria más rápido para construir nuestro sistema. Esto se choca de frente con un problema: el coste. Aparte de otras consideraciones técnicas, el principal problema es que cuanto más rápida es una memoria, más cara resulta y menos densidad de información tiene. El siguiente gráfico extraído de Wikipedia lo expresa muy claramente:

De los apuntes de la asignatura podemos extraer una transparencia que pone de relieve los saltos en velocidades que hay de un escalón de memoria al siguiente:

Como ya habíamos comentado antes, el orden de la memoria desde dentro del procesador hacia fuera es (con una aproximación de los saltos):

Registros -> Velocidad x (1/4), Tamaño x 8 -> Caché -> Vx(1/100) , Tx500 -> Principal -> Vx(1/1000) , Tx300 -> Virtual

La idea básica detrás de la jerarquía de memoria es muy simple y a la vez muy ambiciosa: organizar la memoria de forma que tengamos un sistema que funcione casi a la velocidad de la más rápida de ellas pero con prácticamente el coste de la más barata.

¿Cómo hacemos esto? Eso es lo que veremos ahora con diversas técnicas pero la idea más extendida es usar los periodos de menor actividad para traer los datos de las memorias más lentas hacia las más rápidas con antelación a que el procesador las necesite, de esta forma el procesador sólo tiene que esperar a que los datos le lleguen de los registros en vez de tener que parar la ejecución mientras espera que se extraigan datos de la memoria virtual.

Hoy en día la memoria principal es tan barata y se instalan módulos tan grandes (no es raro ver configuraciones de 4GB x 2 módulos x 3 canales = 24 GB) que a simple vista uno podría creer que se podrían cargar todos los datos necesarios para correr un programa en la memoria principal, sin tener que hacer un solo acceso a disco duro durante su ejecución.

Cuando el procesador necesita un dato primero lo busca en la memoria más cercana, si lo encuentra se produce un acierto y el tiempo empleado es el tiempo necesario para leer de ese tipo de memoria (latencia), que es siempre menor que el correspondiente de escritura. Si no se encuentra se produce un fallo y entonces se traerá del siguiente nivel de memoria un bloque de datos entre los cuales deberá estar el solicitado. El tiempo empleado en esta operación es bastante superior al del caso de acertar, como puede deducirse de las figuras que ya hemos visto. A este tiempo empleado le llamamos penalización por fallo.

El tiempo medio de acceso se puede calcular entonces de acuerdo a la siguiente fórmula (de los apuntes de AGM):

En base a la forma de operar de los procesadores y programas actuales, se pueden postular dos principios que después servirán para diseñar optimizaciones a la jerarquía: el principio de localidad temporal que nos dice que habitualmente los datos usados volverán a usarse en un corto espacio de tiempo, y el de localidad espacial que nos dice que normalmente usaremos datos adyacentes a uno que ya hayamos extraído.

Conviene antes mencionar que en toda jerarquía se deben respetar las propiedades de inclusión (que se consigue replicando todos los datos de la memoria más pequeña en el resto de memorias de la jerarquía) y coherencia (que todas las copias de la misma información sean iguales). 

Vamos a plantar las optimizaciones dividiendo los enfoques en:

-        Política de emplazamiento:

·        Directa

·        Asociativa

·        Por conjuntos

 

-        Política de reemplazamiento

·        Aleatoria

·        LRU (Least Recently Used)

·        FIFO (First In First Out)

-        Política de escritura

·        Escritura directa

·        Post-escritura

·        Con asignación en escritura

·        Sin asignación en escritura

Política de emplazamiento: la memoria caché se divide en marcos que pueden alojar bloques de información que provengan de la memoria principal. En la memoria directa le corresponde un único marco donde puede alojarse, en la asociativa puede alojarse en cualquier marco y en la de por conjuntos los marcos se asocian por conjuntos de manera que cada bloque de datos puede alojarse en cualquiera de los marcos que hay en el conjunto que le corresponde.

Política de reemplazamiento: gestiona las actuaciones en caso de fallo; debemos introducir nuevos datos en la memoria pero ¿qué datos eliminamos para hacer sitio? Podemos hacerlo aleatoriamente, eliminando los datos que más tiempo llevan sin usarse o eliminando los que más tiempo llevan en memoria. Vuelvan a leer esa última frase; parece lo mismo pero no lo es.

Política de escritura: las lecturas de memoria son más frecuentes que las escrituras, pero estas últimas son más lentas con lo que conviene gestionarlas adecuadamente. En el modo de escritura directa cada vez que se modifica un bloque se escribe en la memoria caché y en la principal, en el modo post-escritura sólo se modifica en la caché  y se espera a que el bloque sea reemplazado para modificar la memoria principal, además se tiene un bit que indica si se ha modificado ese dato o no en la caché de manera que se actualice en memoria principal sólo cuando cambie.

Para evitar penalizaciones por fallos en la escritura estos pueden ignorarse o no dependiendo del criterio: en el modo con asignación de escritura se tratan igual que los fallos de lectura (es decir; se resuelven) y en el modo “sin” el bloque se modifica directamente en la memoria principal y no se trae a la caché.