Pr‡cticas 6» y 7»: Memoria CachŽ: Prestaciones.

El objetivo de estas dos sesiones de pr‡cticas ser‡ profundizar en el estudio de las memorias cachŽ mediante la experimentaci—n de su funcionamiento para un conjunto de programas sencillos. Esta experimentaci—n se realizar‡ desde dos puntos de vista, observando la influencia de los distintos par‡metros de dise–o y comprobando la influencia de peque–os cambios en los programas.

Para ello utilizaremos el simulador SISMEC98, el cual recibe un fichero de trazas de acceso a memoria y calcula el efecto de los mismos en la cachŽ, segœn ciertos par‡metros programados. Para generar las trazas utilizaremos un programa en C sobre el cual haremos peque–os cambios.

Apartado 3.1

En este apartado, el algoritmo que vamos a utilizar acceder‡ a memoria del siguiente modo:

for ( i = 0; i < 10; i++ )

   for ( j = 0; j < 10; j++ )

         {

              r1[i][j] = r1[i][j] + a[i][j] + b[i][j]

         }

for ( i = 0; i < 10; i++ )

   for ( j = 0; j < 10; j++ )

         {

              r2[i][j] = r2[i][j] + a[i][j] - b[i][j]

         }

Al ejecutar el programa con este algoritmo obtenemos el fichero de trazas prueba1.prg. Lo ejecutaremos en el simulador con un tama–o de cachŽ de 512 bytes y un tama–o de bloque de 16 bytes. Segœn los distintos tipos de correspondencia en memoria cachŽ y segœn los distintos tipos de funciones de reemplazo, he obtenido las siguientes tasas de aciertos y fallos de cachŽ:

Las distintas funciones de reemplazo ser‡n la aleatoria y la LRU (Least Recently Used, es decir, el menos recientemente usado). Esta tendr‡ utilidad cuando nos referimos a funciones de correspondencia asociativa, bien sea completamente o por conjuntos. Esto es debido a que en el mapeado directo cada bloque tiene asignado una l’nea de cachŽ, y de este modo no tenemos que elegir entre varias l’neas disponibles. As’, la funci—n aleatoria no corresponder‡ a ningœn algoritmo, es decir, se realizar‡ aleatoriamente, y el algoritmo LRU reemplazar‡ la l’nea que lleva mas tiempo sin utilizarse. A causa de esto, los resultados obtenidos con la funci—n aleatoria ser‡n variables, pero con la funci—n LRU ser‡n fijos.

En general, con este algoritmo, se produce una alta tasa de fallos de cachŽ ya que se accede dos veces a cada dato, pero como este acceso se produce en dos bucles diferentes, la distancia temporal es muy grande, con lo cual se reemplaza el bloque cargado en cachŽ antes de volver a ser referenciado.

De este modo, usando la correspondencia directa, tendremos que se producen tres fallos y un acierto, pues se repite dos veces seguidas el acceso al mismo dato y por tanto al mismo bloque. Esta secuencia se repetir‡ constantemente, pues a continuaci—n ya se habr‡ sobrescrito la l’nea cuando volvamos a acceder a otro dato correspondiente al bloque de esta l’nea.

Por su parte, obtenemos una tasa menor de fallos con una correspondencia totalmente asociativa. Esto se produce a causa de que no sobrescribimos el valor de cada l’nea de cachŽ en cada acceso, sino que vamos llenando la cachŽ progresivamente. As’, siempre tendremos la cachŽ llena, con lo cual hay un mayor nœmero de posibilidades de que el dato referenciado se encuentre ya en cachŽ. Variar‡n las tasas segœn la funci—n de reemplazo cuando tenemos la cachŽ llena, ya que si es aleatoria eliminar‡ una l’nea aleatoriamente, y si es LRU eliminar‡ la menos recientemente utilizada. En este caso es mejor usar la LRU a causa de que los accesos a memoria se realizan de modo que accede a tres bloques en fallo pero despuŽs referencia a trece datos de estos bloques. Si no fuera as’ y hubiera posibilidad de acceder a datos de un mismo bloque con mucha distancia temporal seria mejor usar otra funci—n de reemplazo, como la aleatoria.

Si se trata de asociativa por conjuntos de 2 v’as, tendremos 16 conjuntos de cachŽ, cada uno con 2 v’as asignadas. De este modo obtendremos la misma tasa de fallos con un reemplazo LRU que con mapeado directo, ya que en cada conjunto reemplazar‡ siempre la l’nea menos utilizada, y siempre se reemplazar‡ antes de volver a ser referenciada. Si el reemplazo es aleatorio, podemos mantener una l’nea en cachŽ durante los suficientes accesos para conseguir que vuelva a ser referenciada, por lo tanto es posible que obtengamos mayor tasa de aciertos en este caso. Los aciertos que se producen son a causa de que se repite el acceso a un mismo dato dos veces consecutivas, cada tres accesos.

Por œltimo, si se trata de asociativa por conjuntos de 4 v’as, tendremos 8 conjuntos de cachŽ, correspondiŽndole a cada uno 4 l’neas. En este caso ocurre que se producen tres fallos y trece aciertos a causa de que se referencia al mismo dato dos veces y luego se hace referencia al mismo bloque tres veces m‡s, en total cuatro, una que ser‡ en fallo y tres m‡s en acierto, pues podemos mantener los tres bloques cargados en memoria cachŽ a la vez hasta que vuelven a ser referenciados.  En este caso obtenemos la misma tasa que con una correspondencia totalmente asociativa. Obtenemos un mayor nœmero de fallos con la funci—n aleatoria que con la LRU a causa de que la aleatoria sobrescribe alguna l’nea de las que vamos a volver a referenciar en los pr—ximos accesos.

Apartado 3.2

En este apartado cambiaremos el algoritmo anterior por el siguiente, lo cual ayudar‡ a mejorar el tiempo de ejecuci—n:

 

 

 

 

 

for ( i = 0; i < 10; i++ )

   for ( j = 0; j < 10; j++ )

         {

              r1[i][j] = r1[i][j] + a[i][j] + b[i][j]

              r2[i][j] = r2[i][j] + a[i][j] - b[i][j]

         }

Al ejecutar el programa con este algoritmo obtenemos el fichero de trazas prueba2.prg. Lo ejecutaremos en el simulador con un tama–o de cachŽ de 512 bytes y un tama–o de bloque de 16 bytes, los mismos que en el apartado anterior. En este apartado solo utilizarŽ los tipos de correspondencia asociativa por conjuntos de 2 v’as y de 4 v’as. As’, he obtenido las siguientes tasas de aciertos y fallos de cachŽ:

En este caso, la traza generada accede al mismo dato cada 4 accesos, por lo que es mayor la probabilidad de que este bloque estŽ en memoria cachŽ y por lo tanto de que aumente la tasa de aciertos.

En cuanto a la funci—n de correspondencia asociativa por conjuntos de 2 v’as, tenemos 16 conjuntos, con 2 l’neas de cachŽ para cada uno. En este caso ocurre que se sobrescribe la l’nea de cachŽ cargada en un conjunto cada 2 accesos, por lo tanto se sobrescribe la l’nea antes de volver a ser referenciada. A causa de esto la tasa de fallos es todav’a elevada, mayor con un reemplazo LRU, pero no con un aleatorio, ya que en este caso no siempre se sobrescribe la l’nea que vamos a volver a  referenciar.

Ya es m‡s —ptima la funci—n de correspondencia asociativa por conjuntos de 4 v’as, pues en este caso podemos mantener 4 l’neas de un mismo conjunto y volver a referenciar cada una despuŽs de 4 accesos. Resulta —ptimo con una funci—n de reemplazo LRU, pero no aleatoria, ya que esta puede sobrescribir alguna l’nea que vamos a utilizar en los pr—ximos 4 accesos.

En estos casos observamos que en determinados momentos es mejor utilizar una funci—n de reemplazo LRU y en otros una aleatoria. Depende de si tenemos mucho espacio o poco, es decir, si tenemos espacio para mantener varios bloques a la vez ser‡ mejor un reemplazo LRU ya que los mantendr‡ al m‡ximo; por el contrario, si tenemos poco espacio el LRU siempre reemplazar‡ al que vamos a volver a referenciar pronto, y con el aleatorio es posible que no sea as’.

Apartado 3.3

En este apartado cambiaremos el algoritmo anterior por el siguiente, lo cual recorrer‡ la matriz por columnas en vez de por filas:

for ( j = 0; j < 10; j++ )

   for ( i = 0; i < 10; i++ )

         {

              r1[i][j] = r1[i][j] + a[i][j] + b[i][j]

              r2[i][j] = r2[i][j] + a[i][j] - b[i][j]

         }

Al ejecutar el programa con este algoritmo obtenemos el fichero de trazas prueba2.prg. Lo ejecutaremos en el simulador con un tama–o de cachŽ de 512 bytes y un tama–o de bloque de 16 bytes, los mismos que en los apartados anteriores. En este apartado utilizarŽ el tipo de correspondencia asociativa por conjuntos de 2 v’as. As’, he obtenido las siguientes tasas de aciertos y fallos de cachŽ:

En este caso la traza obtenida accede con mayor distancia temporal a los mismos bloques, a causa de que accedemos por columnas y no por filas a la matriz, y las direcciones de memoria est‡n dispuestas por filas.

De este modo, la tasa de fallos en la funci—n de correspondencia por conjuntos de 2 v’as es la misma que en el apartado anterior, es decir, como cada conjunto tiene 2 l’neas asociadas, solo podemos almacenar dos bloques correspondientes a una misma l’nea a la vez. Y en este caso accedemos repetidamente a direcciones de memoria que tienen la misma l’nea asociada, repitiendo bloque cada 4 accesos, no los suficientes para no tener que cargar cada uno de nuevo. Los aciertos que se producen son a causa del acceso al mismo dato cada tres accesos. Obtendremos mayor nœmero de aciertos en la funci—n aleatoria que en la LRU por lo dicho anteriormente, dependiendo si tenemos mucho espacio a la vez o poco.

Apartado 4

Este apartado consistir‡ en introducir un peque–o c—digo que medir‡ el tiempo de ejecuci—n de los algoritmos de los apartados 3.2 y 3.3. El c—digo que introducirŽ ser‡ el siguiente:

#include <sys/times.h>

clock_t t_inicial, t_final;

t_inicial = times( NULL );

/* c—digo a temporizar */

t_final = times( NULL );

prinf( "%d\n", t_final - t_inicial );

El tiempo medido ser‡ el nœmero de tics de reloj, lo cual corresponde aproximadamente a un valor de centŽsimas de segundo. As’, despuŽs de la ejecuci—n de los algoritmos con el c—digo anterior, y variando el nœmero de filas y de columnas de la matriz, he obtenido los resultados siguientes:

El gr‡fico asociado a estos datos ser‡ el siguiente:

En este apartado podemos comprobar que el acceso a memoria en la matriz se realiza por filas, pues el tiempo de ejecuci—n del programa del apartado 3.2 es menor que el del apartado 3.3, accediŽndose a los datos de la matriz, en el 3.2 por filas y en el 3.3 por columnas.

TambiŽn comprobamos que el aumento del tiempo de ejecuci—n cuando aumentamos las filas y las columnas de la matriz responde a una progresi—n geomŽtrica, ya que aunque cada vez a–adimos 500 filas y 500 columnas m‡s, y lo vayamos doblando, no estamos doblando la cantidad de elementos de la matriz, sino que lo estamos aumentando exponencialmente. A esto se debe el aumento geomŽtrico del tiempo de ejecuci—n.

De esto podemos concluir que el tiempo de ejecuci—n de un programa depende del tiempo de acceso a los datos que utilizamos en Žl. As’, comprobamos que el tiempo ser‡ menor dependiendo del nœmero de accesos a memoria cachŽ y a memoria principal que realicemos, y esto depender‡ de la ubicaci—n de estos y del orden en el cual accedemos a cada uno.