← Volver a los ejercicios

El orden del recorrido pesa más que el número de hilos

Dos ciclos llenan la misma matriz de 10.000 × 10.000 enteros, ninguno lanza un hilo y entre los dos hay dos minutos de diferencia. Prediga cuántos accesos aprovecha cada línea de caché, recorra la traza de los primeros accesos y termine con cuatro hilos que escriben en cuatro enteros vecinos y tardan más que uno solo.

1. El mismo trabajo, dos órdenes

A, por filas:

1for (int i = 0; i < n; i++)
2 for (int j = 0; j < n; j++)
3 arr[i][j] = i + j;

B, por columnas:

1for (int j = 0; j < n; j++)
2 for (int i = 0; i < n; i++)
3 arr[i][j] = i + j;
Las dos versiones escriben el mismo valor en las mismas 100.000.000 de posiciones y ninguna lanza un hilo. La única diferencia es cuál de los dos índices recorre el ciclo interno.

2. Antes de ver el reloj

Una línea de caché son 64 bytes y un entero 4. ¿Cuántos accesos aprovechan cada línea traída, recorriendo por filas?

3. La traza

Los primeros diecisiete accesos de cada versión, uno por paso, y lo que encuentra la caché en cada uno.

PasoAcceso ACaché AAcceso BDesplazamiento BCaché B

NivelTamañoLatencia
Registrossin tamaño~1 ns
Caché L132 KB~4 ns
Caché L2512 KB~10 ns
Caché L316 MB~40 ns
RAMGB~100 ns
Un acierto en L1 se sirve en unos 4 ns; un fallo que baja hasta la RAM, en unos 100 ns. La matriz ocupa 400 MB y la L3 tiene 16 MB, así que esos fallos se pagan contra la RAM.

4. Los dos tiempos

RecorridoTiempo

Los dos programas hacen las mismas 100.000.000 de asignaciones y ninguno usa hilos. ¿De dónde sale la diferencia?

Las dos medidas se tomaron en un AMD Ryzen 5 3600 (6 núcleos, 12 hilos de hardware).

5. Falsa compartición

Ahora sí hay hilos. Cuatro suman en paralelo y cada uno guarda su total en su propia casilla de un arreglo de cuatro enteros: nadie escribe en la casilla de otro y el resultado sale correcto, pero el programa tarda más que la versión secuencial. Los cuatro enteros ocupan 16 de los 64 bytes de una línea y caben en la misma. La caché no trabaja por variable, trabaja por línea.

suma[0]h0
suma[1]h1
suma[2]h2
suma[3]h3

La línea va y viene en cada iteración del ciclo. ¿Qué detiene el ping-pong?