Valgrind es una herramienta muy usada para comprobar los fallos de memoria en un programa, con la herramienta memcheck. Pero no se habla mucho de la herramienta que incluye para comprobar fallos de caché,
cachegrind.
El aprovechamiento de la memoría caché es muy importante, ya que su velocidad es muy superior a la de la memoria RAM. Por desgracia, esa velocidad es inversamente proporcional a su tamaño, y si un dato no se encuentra en la caché hay que traerlo de memoria principal, incurriendo en una gran penalización de tiempo. Si hay bucles de por medio, dicha penalización se multiplica.
La herramienta cachegrind permite comprobar esos fallos de caché, configurando incluso su tamaño (muy interesante para simular arquitecturas con otros tamaños de caché). Ésta es la forma de usarla:
$ valgrind --tool=cachegrind --D1=16384,2,128 --L2=65536,2,128 programa
- En primer lugar "--tool=cachegrind" indica que usaremos la herramienta de simulación de caché.
- A continuación se especifican los tamaños, asociatividad y tamaño de vía de las memorias caché (si no se especifican se usarán los de la máquina). En primer lugar está la de nivel uno, dividida en datos e instrucciones (D1 e I1, aquí no especificada), y luego la caché de nivel 2 L2 (que es única para datos e instrucciones). Para cada una de ellas se indican, en orden, tamaño en bytes (debe ser potencia de 2), asociatividad (es decir, número de operaciones de lectura/escritura simultáneas) y tamaño de la línea caché (número de bytes que pasan en cada transferencia).
- Finalmente, el programa a comprobar.
He hecho este programa simple que no es nada óptimo a la hora de acceder a memoria:
matriz.c
#define N 512
int main(int argc, char **argv){
double matriz[N][N];
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
matriz[j][i] = matriz[j][i] * 2.0;
}
El problema es que el contador
j es el que más cambia, y se usa para indicar las columnas de la matriz. En C, el compilador guarda los datos de las filas de forma contigua en memoria, y las columnas suelen estar lo suficientemente alejadas unas de otras como para que no quepan en caché varias columnas.
Con valgrind vamos a simular el efecto que esto tendría en una caché de nivel 2 de 16 Kbytes y líneas caché de 512 bytes (igual al tamaño de fila de la matriz), que sería este comando:
$ valgrind --tool=cachegrind --L2=16384,2,512 ./matrizEstos son los resultados:
=9666== Copyright (C) 2000-2005, and GNU GPL'd, by Julian Seward et al.
==9666== For more details, rerun with: -v
==9666==
--9666-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--9666-- Simulating a 16 KB I-cache with 32 B lines
==9666==
==9666== I refs: 4,346,532
==9666== I1 misses: 959
==9666== L2i misses: 172
==9666== I1 miss rate: 0.02%
==9666== L2i miss rate: 0.00%
==9666==
==9666== D refs: 2,171,229 (1,887,833 rd + 283,396 wr)
==9666== D1 misses: 263,896 ( 263,701 rd + 195 wr)
==9666== L2d misses: 262,953 ( 262,896 rd + 57 wr)
==9666== D1 miss rate: 12.1% ( 13.9% + 0.0% )
==9666== L2d miss rate: 12.1% ( 13.9% + 0.0% )
==9666==
==9666== L2 refs: 264,855 ( 264,660 rd + 195 wr)
==9666== L2 misses: 263,125 ( 263,068 rd + 57 wr)
==9666== L2 miss rate: 4.0% ( 4.2% + 0.0% )
La tasa de fallos en la caché de nivel 2 de datos (L2d miss rate) es del 12,1%, todas ellas en la lectura (más de 260.000 fallos de lectura con un número parecido de peticiones).
Es decir, si el bucle tiene 512*512=262144 iteraciones, estamos obteniendo al menos un fallo de caché en cada acceso a la matriz debido a que procesamos el dato de una fila y la desechamos para pasar después a la fila siguiente. Tras cierto número de filas procesadas, la caché está tan llena que sobreescribe los datos de la primera fila para introducir la nueva. En la siguiente iteración del bucle en que cambia el valor de i (proceso del segundo elemento de todas las filas), los datos se han eliminado y hay que volver a captarlos.
Si en el programa intercambiamos los contadores así:
matriz[i][j] = matriz[i][j] * 2.0;El acceso será ahora por filas, pasando a la siguiente cuando se haya procesado toda la fila actual. Es decir, primero trabajaremos con posiciones de memoria contiguas y por tanto cuando la caché se llene se librará de datos que no se volverán a necesitar. Veamos el resultado con valgrind:
==9667== Copyright (C) 2000-2005, and GNU GPL'd, by Julian Seward et al.
==9667== For more details, rerun with: -v
==9667==
--9667-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--9667-- Simulating a 16 KB I-cache with 32 B lines
==9667==
==9667== I refs: 4,346,542
==9667== I1 misses: 960
==9667== L2i misses: 171
==9667== I1 miss rate: 0.02%
==9667== L2i miss rate: 0.00%
==9667==
==9667== D refs: 2,171,230 (1,887,834 rd + 283,396 wr)
==9667== D1 misses: 34,525 ( 34,330 rd + 195 wr)
==9667== L2d misses: 4,912 ( 4,856 rd + 56 wr)
==9667== D1 miss rate: 1.5% ( 1.8% + 0.0% )
==9667== L2d miss rate: 0.2% ( 0.2% + 0.0% )
==9667==
==9667== L2 refs: 35,485 ( 35,290 rd + 195 wr)
==9667== L2 misses: 5,083 ( 5,027 rd + 56 wr)
==9667== L2 miss rate: 0.0% ( 0.0% + 0.0% )
Mucho mejor, ahora la tasa de fallos es de 0,2%. Ahora sólo hay unas 35.000 referencias a la caché de nivel 2 (ya que la caché de nivel 1 trabaja con una fila completamente captada antes de pasar a la siguiente no captada), y unos 5.000 fallos de caché de nivel 2.
Nota: el programa está compilado usando gcc con opciones de depuración y ninguna optimización..
La diferencia de 260.000 a 5.000 es muy importante si tenemos en cuenta que la caché de nivel 2 suele ser 10 veces más rápida que la memoria RAM.
Con esto espero que haya explicado bien la importancia de un correcto uso de la caché para aumentar la velocidad de proceso y cómo valgrind puede ayudar a lograrlo.
Estos conceptos los estudié en mayor profundidad en la asignatura de Ingeniería de Computadores, y me hubiese venido bien saber por entonces de la existencia de cachegrind.
LibreOffice, el fork de OpenOffice.org, ha lanzado su primera versión estable, la 3.3.
