Introduccion

En el laboratorio de Arquitectura de computadores de 4º de Ing. de Telecomunicaciones, en el año 2002 hubo una practica que mostraba el impacto de la cache de primer nivel en el rendimiento de los programas.

El algoritmo escogido fue casi un clasico: la multiplicacion de matrices mediante la definicion matematica clásica (complejidad O(n^3) ):

a_ij = SUM_k (b_ik * c_kj)

El entorno de pruebas

Para evitar posibles interferencias de otros procesos, se usaron las siguientes lineas:

   /* maxima prioridad. esto ajusta la cola */
   sSchedOpt.sched_priority  =  sched_get_priority_max(SCHED_FIFO);
   /* podemos usar nice o setpriority. ajusta la prioridad dentro de la cola */
   if ( (sched_setscheduler (0, SCHED_FIFO, &sSchedOpt)) == -1)

Con estas lineas, que deben ejecutarse como root, cambiamos la politica de planificacion para que sea FIFO (el proceso no abandona la CPU hasta que no termina).

El hardware usado fue un P133. Los resultados que arroja calibrator son:

Cache L1: 8 + 8 Kb Entradas TLB: 64 (datos) + 64 (código)

CPU Loop + L1 access: 30.66 ns = 4 cy (delay 2319.34 ns = 300 cy)

Caches

  Level 1   size   linesize	miss-latency	    replace-time
   1	      8      32	     172.70 ns = 23 cy    145.38 ns = 19 cy       

TLB

     Level   #entries   pagesize   miss-latency
     1	  32	  8      379.94ns = 51 cy

El codigo

Este es el fragmento relevante del codigo de pruebas:

   #define MAXCOLS 128

   for (iCnt=2;iCnt<MAXCOLS;iCnt++) {
      memset (&sTimeInit,0, sizeof(struct timeval));
      memset (&sTimeEnd, 0, sizeof(struct timeval));
      /* genero los coeficientes de la matriz */
      for (iCntMatrixGeneration=0; 
       iCntMatrixGeneration<iCnt*iCnt;
       iCntMatrixGeneration++) {
       
      pCoef1[iCntMatrixGeneration]=rand();
      pCoef2[iCntMatrixGeneration]=rand();	
      }

      gettimeofday(&sTimeInit, &sZone);
      Mult_Matrix(pCoef1, pCoef2, pMatrixResult, iCnt, iCnt);
      gettimeofday(&sTimeEnd, &sZone);

      iSec  = sTimeEnd.tv_sec  - sTimeInit.tv_sec;
      iUsec = sTimeEnd.tv_usec - sTimeInit.tv_usec;
      fTime = (double)iSec + (double)iUsec/1e6;

      fprintf(Results, "%d\t%g\n", iCnt, fTime);
   }

Resultados

Veamos primero la grafica donde comparamos el rendimiento del algoritmo con la cache activada y desactivada.

:CacheComparativa:

Aquí podemos ver como la version en la que hemos desactivado la cache es sensiblemente mas lenta. Realmente es tal la diferencia que hace pensar que la version con cache tiene un rendimiento casi lineal. La diferencia al final de la curva, para un tamaño de la matriz de 128x128 es de mas de 10 veces.

Veamos un zoom de la curva en la que se usa la cache:

:CacheOnZoom:

Se pueden observar unos picos realmente curiosos. Si nos fijamos en el tamaño de la matriz en ese instante obtenemos estos datos (de forma aproximada): 54x54, 64x64, 73x73, 79x79, ...

Si hacemos una tabla con los tamaños de una matriz y el numero de paginas que ocupan (suponiendo paginas tipicas de i386, 4KB y que las matrices son de tipo int):

• 32x32 01
• 46x46 02
• 55x55 03
• 64x64 04
• 71x71 05
• 78x78 06
• 84x84 07
• 90x90 08
• 96x96 09
• 101x101 10
• 106x106 11
• 110x110 12
• 115x115 13
• 119x119 14
• 124x124 15
• 128x128 16

Podemos ver, que el pico se produce justamente cuando el tamaño de la matriz hace que tengamos que usar una nueva página. ¿En que influye esto? Cuando se accede a una pagina por primera vez, hay que realizar una serie de conversiones mediante busquedas en las tablas de paginas para ver que marco se corresponde con que pagina. Esa resolucion, queda guardada para posteriores uso en los TLB de la CPU y asi no tener que gastar tiempo en realizar la busqueda. Esos picos que se aprecian, son provocados por el hecho de no tener en el TLB la transformacion cacheada.

Modulo de activacion y desactivacion de la cache.

Esta es una variación sobre los módulos que nos proporcionó el profesor de la asignatura, Sebastián Sánchez. Los comentarios de lo mismos son mios y el código es de Jorge (que pasaba por aquí y está arreglando varios desaguisados).

Si tienes interés en los módulos originales consulta el histórico del wiki. Básicamente lo que ha hecho Jorge es reescribir el código en C con asm inline, de forma que la compilación es más sencilla (los modulos precisan de algunos trucos normalmente escondidos en macros C, pero que en el original en puro ensamblador hay que hacer a mano) y fundir los dos módulos en uno sólo, que deshabilita la cache cuando se carga y la habilita cuando se descarga,

cache_l1.c

 #include <linux/module.h>

 MODULE_AUTHOR("Sin dueño, salvo que Chan diga lo contrario");
 MODULE_DESCRIPTION("Deshabilita la Cache L1 al cargarse y la habilita al descargarse");
 MODULE_LICENSE("GPL");

 int init_module(void)
 {
       __asm__ __volatile__ (
               /* Importante: no interrumpible */
                "cli\n"
               /* invalida la cache con write-back. vuelca a memoria
                 los cambios antes */
                "wbinvd\n"
               /* invalida la cache sin write-back */
                "invd\n"
               /* CR0 contiene flags de control del sistema que controlan
                  el modo de funcionamiento y del estado del procesador */
                "movl %cr0, %eax\n"
               /* bit 30 -> Enable/disable cache :-)
                  bit 29 -> Not Write Trough */
                "orl $0x60000000, %eax\n"
               /* actualizo al CR0 */
                "movl %eax, %cr0\n"
                "sti\n"
       );

       return 0;
 }

 void cleanup_module(void)
 {
       /* y justo a la inversa... */
       __asm__ __volatile__ (
             "cli\n"
             "wbinvd\n"
             "invd\n"
             "movl %cr0, %eax\n"
             "andl $0x9fffffff, %eax\n"
             "movl %cr0, %eax\n"
             "sti\n"
       );
  }

Para compilarlo:

  $ gcc -O2 -DMODULE -D__KERNEL__ -c cache_l1.c 

Y una advertencia... Un K6 apenas lo notará pero un moderno Pentium (a partir de un PII) o Athlon caerá en picado a los infiernos en cuando se cargue el módulo. Si lo cargáis en medio de una sesión en las X de, pongamos por caso, KDE, es posible que perdáis la interactividad totalmente (por lo lentísimo que ira todo) y los nervios.

Aqui podeis ver lo que pasa si a un PII266 se le quita la cache y ejecutamos el programita de marras.

:PIISinCache:

Sorprendentemente, es mucho mas lento que el Pentium 133 Mhz

La explicacion de eso: por lo visto el micro ejecuta instrucciones con una velocidad superior a la velocidad con que llegan las intrucciones desde la memoria hacia el micro.

Raúl Ocaña