Este proyecto construye una simulación de un sistema
de memoria. Para comprender los conceptos que trataremos en este proyecto, incluimos
aquí un breve documento de conceptos teóricos. Se comienza con
una definición de un sistema de memoria, que se completará a continuación
con el análisis de por qué es necesario organizar una estructura
jerárquica de memoria.
Hay algunos tipos de memoria que no son aplicables para este proyecto, como
por ejemplo la memoria virtual, ya que aquí vamos a centrarnos en el
nivel de memoria más cercano a la CPU, es decir, la caché, cuyas
características y propiedades hablaremos más adelante. También
mencionaremos en este apartado la memoria principal, ya que ésta sí
se tiene en cuenta en nuestra aplicación. Los demás tipos de memoria
no los trataremos en este apartado de conceptos teóricos por la razón
mencionada anteriormente. Sin embargo, no podemos perder de vista que aunque
este simulador se centre en las relaciones entre la CPU, memoria caché
y memoria principal, en un sistema real habría que tener también
en cuenta la memoria virtual.
Sistema de memoria
La misión del sistema de memoria es servir como almacén para las
instrucciones y datos que constituyen los programas. Por tanto, interesa que
sea grande para poder almacenar muchos programar, muy grandes y con muchos datos.
Además, interesa que sea rápida ya que la CPU accede a memoria
al menos una vez en cada instrucción, en la fase de búsqueda del
código de instrucción. Si además el operando de la instrucción
también está en memoria, debe realizar un nuevo acceso. En los
accesos a memoria , como la CPU es más rápida que la memoria es
necesario añadir estados de espera en los cuales la CPU está parada,
como sucede para las instrucciones del tipo MOV [Ri], Rs o MOV Rd, [Ri] en la
CPU teórica.
El problema de la rapidez de la memoria se ha ido acentuando con el paso del
tiempo y el desarrollo tecnológico seguido por los distintos elementos
del computador. Así, la velocidad del a CPU ha experimentado un incremento
muy importante, duplicándose aproximadamente cada tres años. La
memoria, en cambio, ha evolucionado principalmente en densidad, es decir, en
capacidad de almacenamiento, pero en menor medida en velocidad.
Para solucionar estos problemas se decide utilizar una Jerarquía de Memoria.
Jerarquía de memoria
En la construcción del sistema de memoria de un computador se persiguen
entre otros tres objetivos: alta velocidad, alta capacidad y bajo coste.
El problema es que tal como hemos visto, estos objetivos son contradictorios.
La solución al problema reside en combinar memorias rápidas y
pequeñas con memorias lentas y grandes de tal forma que:
• Las memorias rápidas y pequeñas contengan los datos con
más probabilidad de acceso.
• Las memorias lentas y grandes contengan los datos con menos probabilidad
de acceso.
Con esto se consigue que la capacidad del sistema de memoria sea elevada, pues
contiene memorias grandes. Además, en la mayor parte de los casos el
sistema de memoria será rápido, pues en la mayor parte de los
casos accederá a las memorias rápidas.
Para poder llevar a la práctica la solución anterior es necesario
que se cumplan dos condiciones:
• Conocer a priori los datos con mayor probabilidad de acceso futuro para
así poder almacenarlos en las memorias pequeñas y rápidas.
• Que estos datos sean pocos y con una gran probabilidad de ser accedidos
en el futuro. De esta forma cabrán en las memorias pequeñas y
rápidas y además servirán la mayor parte de los accesos
futuros, obteniéndose un sistema de memoria rápido en la mayor
parte de los casos.
La combinación de las diferentes tecnologías de memoria se hace
en niveles de diferente capacidad y velocidad, formando lo que se conoce como
jerarquía de memoria.
Principio de funcionamiento
La CPU cuando desea acceder a una posición del sistema de memoria, accede
al nivel de la memoria caché. Si esta posición se encuentra dentro
de la memoria caché, la CPU accede a ella de forma muy rápida.
Esta es la situación más habitual, pues la mayor parte de los
accesos de la CPU al sistema de memoria son servidos directamente por la caché.
Si por el contrario la posición no está dentro de la memoria caché,
se produce un fallo que trae como consecuencia que un conjunto de posiciones
consecutivas que incluyen la posición deseada se transfieran desde la
memoria principal a la memoria caché. A este conjunto de posiciones de
memoria consecutivas se le denomina bloque. Una vez se ha realizado la transferencia,
la CPU accede directamente a la caché. En general, cada vez que se produce
un fallo en un nivel N del sistema de memoria, se copia del nivel N+1 al nivel
N el bloque que contiene la posición deseada y a continuación
se realiza el acceso.
Debe notarse que la unidad de transferencia de información entre dos
niveles contiguos de la jerarquía es el bloque. También debe tenerse
en cuenta la posibilidad de encadenar fallos en diferentes niveles.
Principio de localidad temporal
Si en un momento dado se accede a una posición de memoria, es probable
que poco después se acceda a esa misma dirección den memoria.
Un ejemplo de localidad temporal en el acceso a código se encuentra también
en la ejecución de bucles, la misma instrucción se accede para
ejecutarla varias veces. Un ejemplo de localidad temporal en el acceso a datos
es por ejemplo el acceso a un contador durante la ejecución de un bucle.
Principio de localidad
espacial
Este principio indica que: si en un momento dado se accede a una dirección
de memoria, es probable que poco después se acceda a una dirección
de memoria cercana. Un ejemplo de localidad espacial es el acceso al código
durante la ejecución secuencial de un programa. Otro ejemplo aparece
con las instrucciones de un bucle. Un ejemplo de localidad espacial en el acceso
a datos se tiene en el acceso a los datos de un array.
Memoria principal
La memoria principal se construye empleando memoria RAM dinámicas,
las cuales son de velocidad media y capacidad media.
La dirección emitida por la CPU se divide en dos campos: el bloque de
memoria principal y el desplazamiento dentro del bloque. El bloque de memoria
principal en el cual está incluida una dirección emitida por la
CPU se obtiene fácilmente teniendo en cuenta que los bits menos significativos
de la dirección se emplean para definir el desplazamiento del byte dentro
del bloque, y por lo tanto los demás proporcionan el número de
bloque de memoria principal.
Figura 1: Dirección emitida por la CPU
donde,
2dir =Espacio de direcciones físicas
2d = Tamaño del bloque
e = dir-d
Memoria caché
La memoria caché es la memoria más rápida del sistema de
memoria. En la actualidad se implementa con chips de memoria estática,
los cuales son relativamente caros y de baja capacidad.
La memoria caché se divide en bloques, todos ellos conteniendo el mismo
número de bytes. Cada bloque contiene un conjunto de datos ubicados en
posiciones de memoria consecutivas. Cada vez que la CPU intenta acceder a una
dirección de memoria que no está en ningún bloque de la
caché se produce un fallo de caché, y en caso contrario un acierto
de caché. La consecuencia del fallo es que se suspende momentáneamente
el acceso, se copia el bloque que contiene la dirección desde la memoria
principal a la memoria caché y a continuación se reanuda el acceso.
Desde el punto de vista de interacción con la memoria caché, la
memoria principal se puede ver como un gran almacén de bloques del mismo
tamaño que los bloques de la memoria caché.
Por ejemplo, una memoria caché de 32 bytes organizada en bloques de 4
bytes tendrá 8 bloques. Si la memoria principal es de 256 bytes, la memoria
caché percibe a la memoria principal como 64 bloques de 4 bytes cada
uno.
La dirección emitida por la CPU se divide en dos campos:
• Bloque de memoria principal
• Desplazamiento dentro del bloque
Toda memoria caché lleva asociado un controlador de memoria caché,
el cual se encarga de gestionar todas las lecturas y escrituras en la memoria
caché y decidir por ejemplo si una dirección está cacheada,
es decir, ubicada dentro de la memoria caché, o por el contrario se ha
producido un fallo de caché.
En general, el funcionamiento de cualquier memoria caché viene definido
por las siguientes características: estrategia de correspondencia, de
reemplazo y de escritura.
Organización de la memoria
caché
Niveles de caché
Inicialmente cuando se introdujeron las cachés, el sistema típico
tenía una única caché. Sin embargo recientemente lo habitual
es disponer de dos niveles de caché o incluso tres en computadores de
gama alta. Estos niveles se denominan L0,L1,etc., donde el nivel L0 es el más
cercano al procesador.
El objetivo de la caché L1 es reducir la penalización debida a
los fallos de caché del nivel L0. En teoría, cuantos más
niveles de caché haya entre el procesador y la memoria principal mejor
rendimiento proporciona el sistema de memoria pero con un coste mayor.
Figura 2: Velocidad y capacidad en la jerarquía de memoria
Caché unificada
La caché unificada sirve tanto para datos como para código. Tiene
la ventaja de que se reparte automáticamente los bloques cacheados entre
datos y código. De tal forma que si son necesarios menos bloques de datos
y más de código estos se reparten de forma eficiente y transparente.
Caché dividida
La memoria caché dividida está formada por dos cachés,
una para datos y otra para código. Podría suceder que la memoria
caché de datos tuviese bloques libres o muy poco usados, mientras que
la memoria caché de código estuviese generando fallos de caché.
Como se puede ver, en este caso el rendimiento sería menor.
Las primeras cachés que aparecieron solían ser unificadas debido
a la observación anterior. Sin embargo, las cachés L1 actuales
suelen ser divididas, debido a que las CPUs actuales tienen un elevado grado
de paralelismo. La caché dividida permite un mayor grado de paralelismo
pues una parte de la CPU puede escribir un dato en el sistema de memoria mientras
simultáneamente otra parte puede leer instrucciones del sistema de memoria.
Estrategias de correspondencia
Establece a qué bloque o bloques de memoria caché se puede llevar
cada bloque de memoria principal.
Directa
En este tipo de correspondencia cada bloque de memoria principal se asigna siempre
a un mismo bloque que caché, siguiendo esta fórmula:
Bloque de cache = (Bloque de MP) MOD (Nº Bloques cache)
La dirección emitida por la CPU se divide en bits de esta manera,
Figura 3: Dirección emitida por la CPU (caché directa)
donde:
2dir = E.D. físicas
2d = Tamaño del bloque
2dir-d = Número de bloques en E.D
2c = Número de bloques en cache
e = dir - c - d
La etiqueta es necesaria para diferenciar si un determinado bloque de memoria
principal está cacheado o no, ya que a varios bloques de memoria principal
les corresponde un mismo bloque en cache y por tanto si no fuera por los bits
de etiqueta sería imposible diferenciar qué bloque de memoria
principal se hace referencia.
Además de la etiqueta, se guarda en la caché un bit de validez
para cada bloque, que indica si los datos que hay en dicho bloque son válidos
o no. En la inicialización del computador, se marcarán todos estos
bits a falso ya que no son válidos y posteriormente cuando se vayan trayendo
datos desde memoria principal hasta la caché se marcará el bloque
correspondiente como válido.
Totalmente asociativa
La estrategia de correspondencia directa, explicada anteriormente, es muy sencilla
de implementar. Su mayor inconveniente proviene de la rigidez a la hora de asignar
bloques de memoria principal a memoria caché pues no hay ninguna libertad.
Cada bloque de memoria principal puede ir únicamente a un bloque de memoria
caché. Si resulta que la CPU accede con mucha frecuencia a dos bloques
de memoria principal asignados al mismo bloque de caché, aparecerán
con gran frecuencia fallos de caché, lo cual repercute en un bajo rendimiento.
Para paliar este problema, la estrategia de correspondencia asociativa da total
libertad. Un bloque de memoria principal puede asignarse a cualquier bloque
de memoria caché.
En este caso, la etiqueta que acompaña al bloque de caché coincide
con el número de bloque de memoria principal.
Figura 4: Dirección emitida por la CPU (caché totalmente asociativa)
donde,
2dir = Espacio de direcciones físicas
2d = Tamaño del bloque
e = dir-d
Asociativa por conjuntos
Esta estrategia tiene como principal cometido el proporcionar una mayor libertad
de elección del bloque a reemplazar respecto a la correspondencia directa,
pero sin llegar al extremo de la totalmente asociativa, ya que esta última
presenta el inconveniente del gran número de comparadores que usa, lo
cual incrementa mucho el coste.
La estrategia asociativa por conjuntos divide la memoria cache en conjuntos
que contendrán un número fijo de bloques. Al copiar a caché
un bloque de memoria prinicpal, obtendremos el número de conjunto al
que pertenece, y tendremos libertad para copiarlo en cualquiera de los bloques
de dicho conjunto.
La dirección emitida por la CPU se separa de esta forma:
Figura 5: Dirección emitida por la CPU (caché asociativa por conjuntos)
donde,
2dir = E.D. físicas
2d = Tamaño del bloque
2dir-d = Número de bloques en E.D
2n = Número de conjuntos
e = dir - c - d
Debido a la distribución lógica interna de una
caché asociativa por conjuntos podemos ver que:
• Una caché con correspondencia directa equivale con una asociativa
por conjuntos de un blque por conjunto.
• Una caché con corresondencia totalmente asociativa equivale con
una asociativa por conjuntos en la que hay un solo conjunto que almacena todos
los bloques.
Adicionalmente se debe tener en cuenta que comúnmente se usa el término
vía para referirse al número de bloques por conjunto.
Estrategias de reemplazo
LRU (Least Recently Used)
El bloque a reemplazar es el que lleva más tiempo sin haber sido accedido.
Reemplazo aleatorio
Cada vez que se produce un fallo de caché se copia un bloque de memoria
principal a un bloque de caché, reemplazando por tanto un bloque previamente
cacheado. En el caso del reemplazo aleatorio se elige de forma aleatoria entre
uno cualquiera de los bloques de caché candidatos.
Estrategias de escritura
Write-back
Con la escritura diferida, los datos inicialmente sólo se escriben en
la caché. El dato escrito aparece reflejado en la memoria principal sólo
cuando el bloque que lo contiene es reemplazado. Con la escritura diferida aparecen
problemas de coherencia.
Comparativamente, la estrategia write-back proporciona un mayor rendimiento
que la write-through, a costa de una mayor complejidad hardware para el mantenimiento
de la coherencia.
Conviene resaltar que se asocia un bit más a cada bloque de caché,
el bit dirty, el cual se pone a uno cada vez que la CPU escribe en el bloque
de caché.
Write-through
La estrategia de escritura write-through también se denomina escritura
a través. En ella, cada vez que se escriba un dato en memoria caché,
se modificará inmediatamente en memoria principal. Esto elimina problemas
de coherencia, es decir, que cuando un periférico acceda a memoria, siempre
accederá a datos actualizados, con lo cual se evita el tener que comprobar
si el dato está cacheado y si es diferente al que hay en la memoria principal.
Pero por el contrario, en esta estrategia, no se produce la ganancia de tiempo
en las escrituras, sino sólo en las lecturas, ya que cada escritura en
caché en realidad implica una escritura en memoria principal, con el
coste que ello implica.
Medidas del rendimiento en las cachés
Coste temporal de un fallo de
caché
La conexión entre la memoria caché y la memoria principal puede
esquematizar de la siguiente forma:
Figura 6: Conexión entre memoria principal y caché
Cada vez que se produce un fallo de caché se transfiere
un bloque de X bytes desde la memoria principal a la memoria caché. Por
lo tanto, la memoria caché y la principal se comunican en unidades de
bloque.
La transferencia de un bloque desde la memoria principal a la memoria caché
requiere un número de accesos de lectura a la memoria principal que depende
de dos factores:
• El tamaño de bloque (X bytes)
• El número de líneas de datos (Y bytes)
En la práctica X es un múltiplo de Y, y por lo tanto el número
de accesos necesarios es X/Y.
Cada acceso de lectura de memoria principal requiere un tiempo que mediremos
en ciclos del bus. Básicamente, un acceso de lectura se divide en las
tres operaciones siguientes, cada una con un número de ciclos de bus
asociado:
• (OP1) Envío de la dirección por parte del controlador
de caché a través de las líneas de direcciones.
• (OP2) Búsqueda del dato direccionado, de tamaño Y bytes,
dentro de la memoria principal.
• (OP3) Transmisión del dato desde la memoria principal a la memoria
caché sobre las líneas de datos.
Coste temporal de la actualización
de un bloque de memoria principal
Un bloque de memoria principal se actualiza cuando se cumple alguna de las condiciones
siguientes:
• Si la memoria sigue una estrategia de escritura a través o write-through,
se lleva a cabo el proceso de actualización cada vez que se modifica
un bloque de memoria caché.
• Si la memoria sigue una estrategia de escritura diferida o write-back,
la actualización del bloque de memoria caché se produce:
? Cuando el bloque de caché modificado es reemplazado.
? Si un bloque de memoria principal es accedido por la interfaz de un periférico
con capacidad DMA, y resulta que el bloque de caché asociado ha sido
modificado por la CPU.
La actualización de un bloque de memoria principal trae consigo la escritura
de un bloque de caché en memoria principal. Igual que sucedía
en el caso de un fallo de caché, son necesarios X/Y accesos a memoria
principal para llevar a cabo la transferencia. La diferencia es que en este
caso los accesos son de escritura en la memoria principal.
Cada acceso de escritura en memoria principal requiere un tiempo que mediremos
también en ciclos de bus y que descomponemos en las siguientes operaciones:
• (OP1) Envío de la dirección por parte del controlador
de caché a través de las líneas de direcciones.
• (OP2) Transmisión del dato, de tamaño Y bytes, sobre las
líneas de datos desde la memoria caché a la memoria principal
• (OP3) Escritura del dato dentro de la memoria principal.
Nota: X e Y son parámetros que hacen referencia a la figura anterior
Frecuencia de aciertos (%)
La frecuencia de aciertos se calcula como sigue:
f = (aciertos/accesos)*100
donde,
aciertos=aciertos de caché
accesos=accesos a una determinada caché
Frecuencia de fallos (%)
La frecuencia de fallos se calcula como sigue:
f = (fallos/accesos)*100
donde,
fallos=fallos de caché
accesos=accesos a una determinada caché