Práctica 3: Jerarquías de Memoria

Desarrollo de la práctica

Para esta práctica se hace imprescindible el uso del software educativo SIJEM, un simulador de jerarquías de memorias de la Universidad de La Laguna de Tenerife. Mediante el simulador podremos visualizar la actividad de la memoria virtual en el tratamiento de la traducción de direcciones lógicas a direcciones reales, estrategias de reemplazo y búsqueda; y visualizar cómo las políticas de ubicación hacen uso de los niveles de memoria, tales como la memoria secundaria, memoria principal y memoria caché y sus niveles.

En nuestra primera toma de contacto simulamos un sistema de jerarquías de memoria con un sólo nivel de caché y una organización tipo mapeado directo. Por tanto las direcciones que la CPU va solicitando se almacenan en este nivel de caché. Si la CPU solicita una dirección que no se encuentra en la caché  L1, se dice que se ha producido un fallo y dicha dirección virtual debe ser  traducida a dirección  real para que  la memoria principal  pueda acceder a la ubicación real del dato o instrucción requerido y copiarlo al nivel 1 de la caché.

Cuando se produce un fallo en la caché y la memoria principal copia la dirección a la caché puede ser que esta se encuentre llena y por tanto tendrá que aplicarse una política de sustitución para ubicar la nueva dirección suministrada por la memoria principal.

En los ejercicios posteriores se implementan los niveles 2 y 3 respectivamente de la caché. Cuando se implementa un nuevo nivel de caché, la probabilidad de acierto, es decir, de que la dirección solicitada por la CPU se encuentre en algunos de los niveles, es mayor que cuando sólo teníamos un único nivel, por tanto también reducimos el uso de la memoria principal.

El proceso es como sigue, por ejemplo, si implementamos en SIJEM una memoria caché de 3 niveles, cuando iniciamos la simulación, la CPU solicita una dirección, busca en el nivel 1, posteriormente en el nivel 2 y por último en el nivel 3. Como inicialmente los niveles se hallan vacíos, continúa hacia el siguiente paso en la jerarquía: la memoria principal.

Para ilustrar de forma cuantitativa el número de aciertos implementando distintos niveles de caché, tomamos los datos de la práctica: el tamaño de la caché L1 es 2¹⁴  byte,  el tamaño de la caché L2 es 2¹⁵  byte y el tamaño del bloque de la caché es 2¹²  byte.


El número de bloques de la caché donde se almacenarán las direcciones las obtenemos dividiendo el tamaño de la caché  entre el tamaño del bloque. Así tendremos 4 bloques en el nivel 1 y 8 bloques en el nivel 2.

Seleccionando el fichero de direcciones “crafty_d.trd”, simulamos implementando sólo el nivel 1 de caché:

Número de ciclos CPU:
Aciertos L1: 41
Aciertos memoria principal: 49

Añadimos un segundo nivel de caché

Número de ciclos CPU:
Aciertos L1: 41
Aciertos L2: 33
Aciertos memoria principal: 16

Rápidamente observamos la eficiencia al implementar un segundo nivel a la caché. Los aciertos se incrementaron casi en un 50% y el uso de la memoria principal bajó un 67%.

Sin embargo, podemos mejorar la estadística de aciertos todavía más si empleamos una buena política de organización de bloques. Hasta ahora hemos empleado organización de tipo mapeado directo en el que cada dirección de memoria se corresponde con una sola entrada de la caché. Aunque esta política es la más económica y su acceso es rápido veremos que es la que causa más desaciertos.

En la siguiente simulación usaremos organización de tipo asociativa y asociativa por conjuntos. La organización asociativa usa una política de ubicación en la que cualquier bloque de memoria puede ubicarse en cualquier bloque del caché.

Este método, aunque es el que mejor rinde, también es el más caro dado que usa un comparador por cada bloque. Encontraremos el equilibrio pues en la organización asociativa por conjuntos. Intermedio al método directo y completamente asociativo, su política dicta que cada bloque de memoria puede ser ubicado en uno de los N bloques de la caché (conjuntos de N bloques).

Esta organización en cuanto a rendimiento-coste es la mejor opción ya que al dividir la memoria caché en conjuntos fijos de bloques ahorrará en comparadores.

Llevando a la práctica nuestra breve fundamentación y con los mismos datos de antes, simulamos y comparamos con la organización de mapeado directo usada al principio.


Para la organización “completamente asociativa” se obtuvieron lo siguientes resultados
Aciertos caché L1: 47
Aciertos caché L2: 35
Aciertos caché : 82
Aciertos memoria principal: 8

Para la organización “asociativa por conjuntos de 2 vías” se obtuvieron lo siguientes resultados
Aciertos caché L1: 43
Aciertos caché L2: 37
Aciertos caché : 80
Aciertos memoria principal: 10


Cuando usabamos mapeado directo los aciertos en caché fueron 74. Con la política completamente asociativa se obtuvo un 10% más de aciertos y con la asociativa por conjuntos de 2 vías los aciertos se incrementaron un 7,5%.

Como último apartado trataremos qué bloque sustituir cuando se produce un fallo o desacierto en la memoria caché. Hasta ahora, cada vez que la memoria caché fallaba, copiabamos el bloque de memoria principal sobre cualquier bloque de la memoria caché, es decir, mediante reemplazo aleatorio, sin embargo existen otras políticas de sustitución con buena tasa de aciertos: FIFO, LRU y LFU.

Las políticas de reemplazo FIFO (First In First Out) y aleatoria contemplan buena tasa de aciertos y son económicas de implementar.
Las políticas LRU (Least Recently Used) y LFU (Least Frecuency Used) contemplan también buena tasa de aciertos aunque son complejas de implementas (mediante contadores), y puede fallar con matrices.

En la simulación usamos el fichero de ejemplo ejem5.cfg y ejem8.cfg con las siguientes especificaciones:

Fichero: Ejem5.cfg
Configuración de la memoria principal:
Tamaño: 1024 KByte
Tamaño página: 4 KByte
Tamaño acceso: 1000 Ciclos
Tipo de organización: Completamente Asociativa
Tipo de sustitucion: Azar

Y comparamos con los fichero de direcciones: crafty_a.trd, facerec_a.trd, gcc_a.trd

Archivo de traza: crafty_a.trd	Archivo de traza: facerec_a.trd	Archivo de traza: gcc_a.trd
Aciertos L1: 12 Aciertos L2: 5 Aciertos L3: 4 Aciertos Totales: 21 Aciertos memeria principal: 15 Fallos: 64	Aciertos L1: 51 Aciertos L2: 6 Aciertos L3: 4 Aciertos Totales: 61 Aciertos memeria principal: 1 Fallos: 37	Aciertos L1: 54 Aciertos L2: 5 Aciertos L3: 4 Aciertos Totales: 63 Aciertos memeria principal: 2 Fallos: 35

Fichero: Ejem8.cfg
Configuración de la memoria principal:
Tamaño: 1024 KByte
Tamaño página: 4 KByte
Tamaño acceso: 1000 Ciclos
Tipo de organización: Completamente Asociativa
Tipo de sustitucion: LFU



Comparamos con los fichero de direcciones usados antes: crafty_a.trd, facerec_a.trd, gcc_a.trd

Archivo de traza: crafty_a.trd	Archivo de traza: facerec_a.trd	Archivo de traza: gcc_a.trd
Aciertos L1: 5 Aciertos L2: 3 Aciertos L3: 1 Aciertos Totales: 9 Aciertos memeria principal: 27 Fallos: 64	Aciertos L1: 49 Aciertos L2: 3 Aciertos L3: 7 Aciertos Totales: 59 Aciertos memeria principal: 3 Fallos: 37	Aciertos L1: 53 Aciertos L2: 1 Aciertos L3: 8 Aciertos Totales: 62 Aciertos memeria principal: 3 Fallos: 35

Comparando ambas tablas nos damos cuenta de que obtienen los mismo fallos, sin embargo, el uso de la memoria principal es menor usando reemplazo aleatorio. La tasa de aciertos también es más alta con reemplazamiento aleatorio para nuestra simulación.

Valoración y autocrítica de la práctica.

Con respecto al enunciado de la práctica se pueden mejorar algunos aspectos. La práctica podría dividirse en tres fases: implementando una jerarquia de memoria, políticas de emplazamiento de bloques y políticas de sustitución de bloques.

De este modo, intercambiaría los ejercicios 4 y 5 para que primeramente en los ejercicios 2,3 y 4 se implementaran las caché desde el nivel 1 al 3. Y así, en el ejercicio 5, se pediría implementar una caché de tres niveles con múltiples organizaciones de emplazamiento.

Llegando pues al ejercicio 6, bien situado, donde para unas especificaciones se contrastan los resultados cambiando las políticas de sustitución en cada caso.

José Ezequiel Gallardo Marín