Orden de recorrido y mosaico de bucles

Dos bucles anidados que visitan las mismas celdas de una matriz pueden diferir en un factor de siete en fallos de caché solo por cuál bucle va dentro. Esta lección compara la lectura fila a fila y columna a columna, luego corta una transposición en teselas para que un bloque se quede en la caché mientras se usa, y mide ambas en una matriz hecha con cierres de SPY.

Una matriz de n filas y n columnas se guarda en orden por filas. Un bucle que avanza a lo largo de una fila, cambiando j, lee valores contiguos. Un bucle que baja por una columna, cambiando i, salta una fila entera en cada paso. Los dos bucles siguientes visitan las mismas celdas, uno con j dentro y otro con i. Mostramos las seis primeras direcciones de una matriz de 4 por 4 de valores float64.

def row_major_trace(n):    return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n):    return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])

row: [0, 8, 16, 24, 32, 40]
col: [0, 32, 64, 96, 8, 40]

1. 1Con i dentro, la lectura siguiente está una fila entera más allá (aquí 4 valores = 32 bytes).

Fila a fila las direcciones suben 8 bytes, el paso del primer tema, y una línea sirve ocho lecturas. Columna a columna saltan 32 bytes aquí, y la longitud de una fila entera en una matriz mayor. Ahora contamos los fallos de los dos órdenes, en una caché pequeña de 4 KB, para matrices de 16 por 16 hasta 73 por 73.

for n in (16, 32, 48, 73):    print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))

16 x 16 row: 32 col: 32
32 x 32 row: 128 col: 1024
48 x 48 row: 288 col: 2304
73 x 73 row: 667 col: 4573

Una matriz de 16 por 16 son 2 KB y cabe en la caché, así que tras cargarla ambos órdenes cuestan 32 fallos, lo mismo. Desde 32 por 32 la matriz ya no cabe, y el orden por columnas falla en cada lectura: 1024 fallos contra 128, un factor de ocho, que son los ocho valores de una línea. A 73 por 73 el factor es casi siete. La forma de los bucles no cambió; cambió el tamaño de los datos.

A veces ningún orden de bucles ayuda. La transposición B[j][i] = A[i][j] lee A y escribe B, y si los bucles van por las filas de A bajan por las columnas de B. Sea cual sea el bucle interior, una de las dos matrices se recorre con un paso grande. El remedio es el mosaico de bucles: procesar la matriz en teselas cuadradas pequeñas, de modo que las pocas líneas que toca una tesela se usen muchas veces antes de ser expulsadas.

1. 1
   Elegir un tamaño de tesela tLo bastante pequeña para que una tesela de A y una de B quepan en la caché.
2. 2
   Recorrer las teselasDos bucles exteriores con paso t: ii y jj dan la esquina de una tesela.
3. 3
   Trabajar dentro de la teselaLos dos bucles interiores visitan solo las t por t celdas de esta tesela, como antes.
4. 4
   Pasar a la siguiente teselaSolo ahora el programa deja atrás las líneas de la tesela anterior.

El código siguiente solo lista el orden en que se visitan las celdas, para una matriz de 4 por 4, sin y con teselas de 2. Con teselas, el programa termina el bloque de 2 por 2 de arriba a la izquierda antes de tocar otra celda.

def visit_order(n, tile=None):    step = n if tile is None else tile    order = []    for ii in range(0, n, step):1        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    order.append((i, j))    return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])

plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]

1. 1Los dos bucles exteriores recorren las teselas; los dos interiores recorren el interior de una tesela.

Pasemos a la transposición real. Escribimos la traza de las lecturas de A y las escrituras de B, con B guardada justo después de A, y contamos los fallos para una matriz de 73 por 73 sin tesela y con teselas de 4, 8, 16 y 32.

def transpose_trace(n, tile=None):    base_b = n * n * 8    step = n if tile is None else tile    trace = []    for ii in range(0, n, step):        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    trace.append((i * n + j) * 8)                    trace.append(base_b + (j * n + i) * 8)    return tracefor tile in (None, 4, 8, 16, 32):    print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))

tile None misses: 5996
tile 4 misses: 2603
tile 8 misses: 2036
tile 16 misses: 1960
tile 32 misses: 1714

Sin teselas la transposición falla 5996 veces. Con teselas de 4 ya baja a 2603, y con teselas de 8 a 32 se queda entre 2036 y 1714, unas tres veces menos. Una tesela demasiado pequeña desperdicia los bordes de las líneas que carga, así que la ganancia crece con la tesela hasta que deja de caber.

El laboratorio sigue la lección: los dos órdenes de lectura, la traza de la transposición con una tesela opcional, el recuento de fallos por orden y por tesela, la elección de la mejor tesela y el estudio sobre la matriz de SPY.

• Función · preguntaSe apoya en
• row_major_trace(n)¿Qué direcciones toca una lectura fila a fila?Aritmética simple
• col_major_trace(n)¿Y una lectura columna a columna?Aritmética simple
• transpose_trace(n, tile=None)¿Qué direcciones toca una transposición, con teselas o sin ellas?Cuatro bucles anidados
• compare_orders(n)¿Cuánto peor es el orden por columnas?row_major_tracecol_major_trace
• misses_by_tile(n, tiles)¿Cómo cambian las teselas los fallos de la transposición?transpose_trace
• best_tile(n, tiles)¿Qué tesela es la mejor?misses_by_tile
• study(bars)¿Qué gana el mosaico en una matriz de cierres de SPY?compare_ordersbest_tile

Siguiente tema: el mosaico oculta el retraso de un fallo reutilizando líneas; la precarga lo oculta pidiendo una línea antes de que haga falta. En Precarga añade a la caché un detector de pasos y ve qué patrones de acceso puede predecir y cuáles, como un recorrido aleatorio por una tabla, no.