Localidad en caché: por qué importa el orden de lectura

Una matriz de enteros de 8 × 8 está almacenada en memoria por filas. Entre ella y el procesador hay una caché con 8 líneas de 16 bytes. Suma sus elementos por filas o por columnas y sigue las lecturas paso a paso. Cada celda indica la única línea de caché que puede usar su dirección: ámbar si hay un fallo, verde si hay un acierto y un tono claro para los elementos vecinos que se han cargado junto con el que produjo el fallo.

Ejemplo resuelto — Localidad en caché: por qué importa el orden de lectura

Lecturas en cualquiera de los órdenes	64
Bloques de 16 bytes a los que accede la matriz	16
Máximo de aciertos posible	48 de 64 (75,0 %)
Aciertos por filas	48 de 64 (75,0 %)
Aciertos por columnas	0 de 64 (0,0 %)
Líneas de caché que usa la columna 0	4 de 8

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Localidad en caché: por qué importa el orden de lectura

Una caché es una memoria pequeña y rápida que guarda copias de la memoria principal en líneas. Cada línea contiene un bloque alineado de L bytes. Si el bloque al que pertenece un dato ya está en una línea, su lectura es un acierto; en caso contrario, es un fallo y se carga el bloque completo. En una caché de correspondencia directa con S líneas, el bloque que contiene la dirección a solo puede ocupar la línea ⌊a / L⌋ mod S. Un bucle que lee direcciones contiguas una tras otra aprovecha cada bloque cargado para varias lecturas. Esta propiedad se llama localidad espacial.

Qué significa cada símbolo

L: el tamaño de cada línea en bytes: aquí, 16; en la mayoría de los procesadores de sobremesa y de servidores, 64
S: el número de líneas: aquí, 8

Supone: Se supone una caché de correspondencia directa inicialmente vacía, enteros de 4 bytes y una matriz almacenada por filas, como en C. Fortran almacena las matrices por columnas, así que allí el orden más rápido es el contrario. Solo se cuentan las lecturas de la matriz. Las cachés reales de datos de primer nivel son mayores y asociativas por conjuntos, normalmente de 8 vías: cada bloque puede ocupar cualquiera de las 8 líneas de su conjunto. Esto elimina la mayoría de los conflictos que ves aquí, pero no resuelve la falta de espacio. Tampoco se incluye la precarga por hardware, que trae la siguiente línea antes de que se solicite.

Las mismas 64 sumas dan 48 aciertos o ninguno 🖖

Pulsa 8 × 8 por filas y después 8 × 8 por columnas. En ambos casos se leen los mismos 64 enteros en las mismas 64 direcciones; solo cambia el orden. Por filas, la primera lectura de cada línea de 16 bytes falla y carga 4 enteros, de modo que los 3 siguientes ya están en la caché: 48 aciertos. Por columnas, la siguiente lectura está una fila más abajo, a 32 bytes de distancia, en otra línea. Aquí cada fila ocupa exactamente 2 líneas, por lo que la columna 0 solo usa las líneas 0, 2, 4 y 6. Al leer a[4][0], se expulsa el bloque que se había cargado al leer a[0][0]. Cuando el bucle vuelve a a[0][1], ese bloque ya no está. Fallan las 64 lecturas. Ulrich Drepper midió este efecto a mayor escala en 2007: al multiplicar matrices de 1000 × 1000 en un Intel Core 2, bastó con transponer primero la matriz que se leía por columnas para leer ambas por filas y reducir los ciclos de reloj al 23,4 % de los originales.

Si la matriz cabe en la caché, el orden da igual 🖖

Fija el tamaño en 5 y cambia de orden: obtienes 18 aciertos de 25 en ambos casos. La matriz ocupa 100 bytes y la caché tiene 128 bytes. Sus 7 bloques se asignan a 7 líneas distintas, y ningún bloque se expulsa una vez cargado. Cada uno produce un solo fallo, en su primera lectura, sea cual sea el orden. Con 6 × 6, la matriz ocupa 144 bytes y 2 de sus bloques deben compartir una línea. Los resultados ya difieren: 27 aciertos por filas y 25 por columnas. Sin relleno, el recorrido por columnas queda por detrás en todos los tamaños desde ese hasta 16 × 16.

Con 4 enteros sin usar por fila, los aciertos pasan de 0 a 48 🖖

Pulsa Filas con relleno. Lees por columnas la misma matriz de 8 × 8, pero al final de cada fila hay 4 enteros que nunca se leen. Así, cada fila ocupa 48 bytes: 3 líneas en lugar de 2. Como 3 y 8 son primos entre sí, la columna 0 usa ahora las 8 líneas. Sus 8 bloques quedan en líneas distintas y siguen allí para las lecturas de las 3 columnas siguientes: 48 aciertos de 64, tantos como por filas. El coste son 128 bytes que nunca se leen. El relleno elimina los fallos por conflicto, que aparecen cuando dos bloques se disputan una línea mientras otras quedan vacías. No puede aumentar la capacidad de la caché. El problema resuelto termina con una matriz para la que esa falta de espacio es decisiva.

Problema resuelto al detalle

¿Cuánto tráfico de memoria cuesta elegir el orden más lento? 4 pasos
Pulsa 8 × 8 por columnas y explica por qué hay 0 aciertos. Considera después una matriz de 1024 × 1024 con enteros de 4 bytes y una caché de correspondencia directa de 32 KiB con líneas de 64 bytes. ¿Cuántos bytes se transfieren desde la memoria al sumar los elementos por filas? ¿Y por columnas? ¿Ayuda añadir una línea de relleno al final de cada fila?

Abre este problema en la herramienta
1. En esta página, cada fila ocupa 8 × 4 = 32 bytes, es decir, 2 líneas. La fila i empieza en la línea 2i mod 8, y la columna 0 solo usa las líneas 0, 2, 4 y 6. a[4][0] ocupa la línea en la que estaba a[0][0]. Cuando el bucle llega a a[0][1], su bloque ya se ha expulsado: 0 aciertos de 64. Por filas hay un fallo por cada bloque de 16 bytes. Son 16 fallos y, por tanto, 48 aciertos: 1 − 4/16 = 75 %.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. La caché grande tiene 32 768 / 64 = 512 líneas. Por filas, cada línea de 64 bytes contiene 16 enteros y solo falla la primera lectura de cada una: 1 048 576 / 16 = 65 536 fallos. La tasa de aciertos es 1 − 4/64 = 93,75 %, y se transfieren 65 536 × 64 = 4 194 304 bytes: exactamente una lectura completa de la matriz.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. Por columnas, cada fila ocupa 4096 bytes, es decir, 64 líneas. La fila i empieza en la línea 64i mod 512, por lo que una columna solo usa 8 de las 512 líneas. a[8][0] expulsa el bloque de a[0][0], que desaparece mucho antes de que el bucle vuelva a a[0][1]. Fallan las 1 048 576 lecturas: se transfieren 67 108 864 bytes, 16 veces más.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Añadir 16 enteros de relleno al final de cada fila hace que ocupe 4160 bytes, es decir, 65 líneas. Como 65 y 512 son primos entre sí, cada columna usa ahora las 512 líneas. Sigue sin haber aciertos: una columna accede a 1024 bloques y la caché solo admite 512, de modo que todos se han expulsado cuando la siguiente columna los necesita.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Respuesta

4 MiB por filas, 64 MiB por columnas. El relleno distribuye los bloques de cada columna por toda la caché y aun así no se obtiene ningún acierto. Elimina los conflictos, pero los bloques de cada columna de esta matriz necesitan más espacio del que tiene la caché.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Ruta de aprendizaje

Cómo ejecuta un programa un ordenador

Referencias (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.