En informática y particularmente en el diseño de compiladores , la optimización de nidos de bucles (LNO) es una técnica de optimización que aplica un conjunto de transformaciones de bucles con el fin de optimizar la localidad o paralelizar u otra reducción de la sobrecarga de los nidos de bucles. ( Los bucles anidados ocurren cuando un bucle está dentro de otro bucle). Un uso clásico es reducir la latencia de acceso a la memoria o el ancho de banda de la caché necesario debido a la reutilización de la caché para algunos algoritmos de álgebra lineal comunes .
La técnica utilizada para producir esta optimización se llama loop tiling , [1] también conocida como loop blocking [2] o strip mine and interchange .
El mosaico de bucles divide el espacio de iteración de un bucle en fragmentos o bloques más pequeños, para ayudar a garantizar que los datos utilizados en un bucle permanezcan en la memoria caché hasta que se reutilicen. La partición del espacio de iteración del bucle conduce a la partición de una matriz grande en bloques más pequeños, ajustando así los elementos de la matriz a los que se accede al tamaño de la caché, mejorando la reutilización de la caché y eliminando los requisitos de tamaño de la caché.
Un bucle ordinario
para ( i = 0 ; i < N ; ++ i ) { ... } se puede bloquear con un bloque de tamaño B reemplazándolo con
para ( j = 0 ; j < N ; j += B ) { para ( i = j ; i < min ( N , j + B ); ++ i ) { .... } } donde min()es una función que devuelve el mínimo de sus argumentos.
El siguiente es un ejemplo de multiplicación de vectores matriciales. Hay tres matrices, cada una con 100 elementos. El código no divide las matrices en tamaños más pequeños.
int i , j , a [ 100 ] [ 100 ], b [ 100 ], c [ 100 ]; entero norte = 100 ; para ( yo = 0 ; yo < norte ; yo ++ ) { c [ yo ] = 0 ; para ( j = 0 ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ][ j ] * b [ j ]; } } Después de aplicar el mosaico de bucles utilizando bloques de 2 * 2, el código se ve así:
int i , j , x , y , a [ 100 ] [ 100 ], b [ 100 ], c [ 100 ]; entero norte = 100 ; para ( yo = 0 ; yo < norte ; yo += 2 ) { c [ yo ] = 0 ; c [ yo + 1 ] = 0 ; para ( j = 0 ; j < n ; j += 2 ) { para ( x = i ; x < min ( i + 2 , n ); x ++ ) { para ( y = j ; y < min ( j + 2 , norte ); y ++ ) { c [ x ] = c [ x ] + a [ x ][ y ] * b [ y ]; } } } } El espacio de iteración del bucle original es n por n . El fragmento de matriz al que se accede a[i, j] también es n por n . Cuando n es demasiado grande y el tamaño de caché de la máquina es demasiado pequeño, los elementos de la matriz a los que se accede en una iteración de bucle (por ejemplo, i = 1, j = 1 to n) pueden cruzar líneas de caché, provocando errores de caché.
No siempre es fácil decidir qué valor de tamaño de mosaico es óptimo para un bucle porque exige una estimación precisa de las regiones de matriz a las que se accede en el bucle y el tamaño de caché de la máquina de destino. El orden de los nidos de bucles ( intercambio de bucles ) también juega un papel importante para lograr un mejor rendimiento de la caché. El bloqueo explícito requiere elegir un tamaño de mosaico en función de estos factores. Por el contrario, los algoritmos ajenos al caché están diseñados para hacer un uso eficiente del caché sin un bloqueo explícito.
Muchas operaciones matemáticas importantes en computadoras terminan dedicando gran parte de su tiempo a la multiplicación de matrices . La operación es:
donde A, B y C son matrices N×N. Los subíndices de la siguiente descripción tienen el formato C[row][column].
El bucle básico es:
int yo , j , k ; para ( i = 0 ; i < N ; ++ i ) { para ( j = 0 ; j < N ; ++ j ) { C [ i ] [ j ] = 0 ; para ( k = 0 ; k < N ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } } Hay tres problemas a resolver:
El bucle original calcula el resultado de una entrada en la matriz de resultados a la vez. Al calcular un pequeño bloque de entradas simultáneamente, el siguiente bucle reutiliza cada valor cargado dos veces, de modo que el bucle interno tiene cuatro cargas y cuatro sumas múltiples, resolviendo así el problema n.º 2. Al transportar cuatro acumuladores simultáneamente, este código puede mantener ocupado un único sumador de coma flotante con una latencia de 4 casi todo el tiempo (problema n.º 1). Sin embargo, el código no aborda el tercer problema. (Tampoco aborda el trabajo de limpieza necesario cuando N es impar. Estos detalles quedarán fuera de la siguiente discusión).
para ( i = 0 ; i < N ; i += 2 ) { para ( j = 0 ; j < N ; j += 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; para ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } En este código se bloquearon las iteraciones iy jpor un factor de dos y los bucles internos de dos iteraciones resultantes se desenrollaron por completo.
Este código se ejecutaría de manera bastante aceptable en un Cray Y-MP (construido a principios de la década de 1980), que puede soportar 0,8 adiciones multiplicadas por operación de memoria a la memoria principal. Una máquina como un Pentium 4 de 2,8 GHz, construido en 2003, tiene un ancho de banda de memoria ligeramente menor y un punto flotante mucho mejor, de modo que puede soportar 16,5 adiciones múltiples por operación de memoria. Como resultado, el código anterior se ejecutará más lento en el Pentium 4 de 2,8 GHz que en el Y-MP de 166 MHz.
Una máquina con una latencia de adición de punto flotante más larga o con múltiples sumadores requeriría más acumuladores para ejecutarse en paralelo. Es fácil cambiar el bucle anterior para calcular un bloque de 3x3 en lugar de un bloque de 2x2, pero el código resultante no siempre es más rápido. El bucle requiere registros para contener tanto los acumuladores como los valores A y B cargados y reutilizados. Un bloque de 2x2 requiere 7 registros. Un bloque de 3x3 requiere 13, lo que no funcionará en una máquina con solo 8 registros de punto flotante en ISA . Si la CPU no tiene suficientes registros, el compilador programará cargas y almacenes adicionales para distribuir los registros en las ranuras de la pila, lo que hará que el bucle se ejecute más lento que un bucle bloqueado más pequeño.
La multiplicación de matrices es como muchos otros códigos en el sentido de que puede estar limitada por el ancho de banda de la memoria y que más registros pueden ayudar al compilador y al programador a reducir la necesidad de ancho de banda de la memoria. Esta presión de registro es la razón por la que los proveedores de CPU RISC , que pretendían construir máquinas más paralelas que las CPU de propósito general x86 y 68000 , adoptaron archivos de registro de punto flotante de 32 entradas .
El código anterior no utiliza muy bien el caché. Durante el cálculo de los resultados de una franja horizontal de C, se carga una franja horizontal de A y se carga toda la matriz B. Para todo el cálculo, C se almacena una vez (eso es bueno), A se carga en el caché una vez (asumiendo que una franja de A cabe en el caché con una franja de B), pero B se carga N/ib veces, donde ib es el tamaño de la tira en la matriz C, para un total de N 3 /ib cargas de palabras dobles desde la memoria principal. En el código anterior, ib es 2.
El siguiente paso para reducir el tráfico de memoria es hacer que ib sea lo más grande posible. Debe ser mayor que el número de "saldo" informado por las transmisiones. En el caso de un sistema Pentium 4 de 2,8 GHz en particular utilizado para este ejemplo, el número de saldo es 16,5. El segundo ejemplo de código anterior no se puede ampliar directamente, ya que requeriría muchos más registros de acumulador. En cambio, el bucle está bloqueado sobre i. (Técnicamente, esta es en realidad la segunda vez que se bloquea i, ya que la primera vez fue el factor 2).
para ( ii = 0 ; ii < N ; ii += ib ) { para ( j = 0 ; j < N ; j += 2 ) { para ( i = ii ; i < ii + ib ; i += 2 ) { cuenta00 = cuenta01 = cuenta10 = cuenta11 = 0 ; para ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } } Con este código, ib se puede configurar en cualquier parámetro deseado y el número de cargas de la matriz B se reducirá en ese factor. Esta libertad tiene un coste: N×ib porciones de la matriz A se mantienen en la memoria caché. Mientras eso encaje, este código no estará limitado por el sistema de memoria.
Entonces, ¿qué tamaño de matriz se ajusta? El sistema de ejemplo, un Pentium 4 de 2,8 GHz, tiene una caché de datos primaria de 16 KB. Con ib=20, el segmento de la matriz A en este código será mayor que el caché principal cuando N > 100. Para problemas mayores que eso, se necesita otro truco.
Ese truco consiste en reducir el tamaño de la franja de la matriz B bloqueando el bucle k para que la franja tenga un tamaño ib × kb. Bloquear el bucle k significa que la matriz C se cargará y almacenará N/kb veces, para un total de transferencias de memoria. B todavía se transfiere N/ib veces, para transferencias. Con tal que
El sistema de memoria de la máquina se mantendrá al día con la unidad de punto flotante y el código se ejecutará al máximo rendimiento. El caché de 16 KB del Pentium 4 no es lo suficientemente grande: si en su lugar se eligiera ib=24 y kb=64, se usarían 12 KB del caché, evitando llenarlo por completo, lo cual es deseable, por lo que los arreglos C y B deben tener algo de espacio para fluir. Estos números se encuentran dentro del 20% de la velocidad máxima de punto flotante del procesador.
Aquí está el código con el bucle kbloqueado.
para ( ii = 0 ; ii < N ; ii += ib ) { para ( kk = 0 ; kk < N ; kk += kb ) { para ( j = 0 ; j < N ; j += 2 ) { para ( yo = ii ; yo < ii + ib ; yo += 2 ) { si ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; else { acc00 = C [ i + 0 ][ j + 0 ]; acc01 = C [ i + 0 ][ j + 1 ]; acc10 = C [ i + 1 ][ j + 0 ]; acc11 = C [ i + 1 ][ j + 1 ]; } para ( k = kk ; k < kk + kb ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ] [ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } } } Los ejemplos de código anteriores no muestran los detalles de cómo tratar con valores de N que no son múltiplos de los factores de bloqueo. Los compiladores que optimizan el nido de bucles emiten código para limpiar los bordes del cálculo. Por ejemplo, la mayoría de los compiladores LNO probablemente dividirían la iteración kk == 0 del resto de las kkiteraciones, para eliminar la declaración if del ibucle. Este es uno de los valores de dicho compilador: si bien es sencillo codificar los casos simples de esta optimización, mantener todos los detalles correctos a medida que el código se replica y transforma es un proceso propenso a errores.
El bucle anterior solo alcanzará el 80 % de los fracasos máximos en el sistema de ejemplo cuando se bloquee para el tamaño de caché L1 de 16 KB. Funcionará peor en sistemas con sistemas de memoria aún más desequilibrados. Afortunadamente, el Pentium 4 tiene caché de nivel 2 de alto ancho de banda de 256 KB (o más, según el modelo), así como caché de nivel 1. Hay una opción:
En lugar de ajustarse específicamente a un tamaño de caché en particular, como en el primer ejemplo, un algoritmo ajeno al caché está diseñado para aprovechar cualquier caché disponible, sin importar su tamaño. Esto aprovecha automáticamente dos o más niveles de jerarquía de memoria, si están disponibles. Se conocen algoritmos ajenos al caché para la multiplicación de matrices .
embaldosado.