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.
Paso
Acceso A
Caché A
Acceso B
Desplazamiento B
Caché B
Nivel
Tamaño
Latencia
Registros
sin tamaño
~1 ns
Caché L1
32 KB
~4 ns
Caché L2
512 KB
~10 ns
Caché L3
16 MB
~40 ns
RAM
GB
~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
Recorrido
Tiempo
Los dos programas hacen las mismas 100.000.000 de
asignaciones y ninguno usa hilos. ¿De dónde sale la diferencia?
El cuello de botella no fue el número
de núcleos: los 120 segundos de diferencia salieron con un solo hilo en las dos
corridas. Un programa rinde según cómo toque la caché, no solo según cuántos hilos
lance, y el orden de los índices se revisa antes de repartir el ciclo.
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?