En informática y particularmente en diseño de compiladores , la optimización de anidación de bucles (LNO) es una técnica de optimización que aplica un conjunto de transformaciones de bucles con el propósito de optimizar la localidad o paralelizar u otra reducción de la sobrecarga de los bucles anidados. (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 caché necesario debido a la reutilización de caché para algunos algoritmos de álgebra lineal comunes .
La técnica utilizada para producir esta optimización se denomina teselado de bucles , [1] también conocido como bloqueo de bucles [2] o minado a cielo abierto e intercambio .
El agrupamiento en mosaicos de bucles divide el espacio de iteración de un bucle en fragmentos o bloques más pequeños, de modo de ayudar a garantizar que los datos utilizados en un bucle permanezcan en la memoria caché hasta que se vuelvan a utilizar. La partición del espacio de iteración de un bucle conduce a la partición de una matriz grande en bloques más pequeños, lo que permite que los elementos de la matriz a los que se accede se adapten al tamaño de la memoria caché, lo que mejora la reutilización de la memoria caché y elimina los requisitos de tamaño de la memoria caché.
Un bucle ordinario
para ( i = 0 ; i < N ; ++ i ) { ... } se puede bloquear con un tamaño de bloque 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 matrices y vectores. 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 ]; int n = 100 ; para ( i = 0 ; i < n ; i ++ ) { c [ i ] = 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 2 * 2, el código se ve así:
int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; para ( i = 0 ; i < n ; i += 2 ) { c [ i ] = 0 ; c [ i + 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 , n ); 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 la matriz a la que se accede también es n por n . Cuando n es demasiado grande y el tamaño de la memoria caché de la máquina es demasiado pequeño, los elementos de la matriz a los que se accede en una iteración del bucle (por ejemplo, i = 1, j = 1 to n) pueden cruzar las líneas de la memoria caché, lo que provoca errores de caché.
No siempre es fácil decidir qué valor de tamaño de mosaico es óptimo para un bucle, ya que 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 anidamientos 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 que ignoran la caché están diseñados para hacer un uso eficiente de la caché sin bloqueo explícito.
Muchas operaciones matemáticas importantes en las computadoras terminan dedicando gran parte de su tiempo a realizar multiplicaciones de matrices . La operación es:
donde A, B y C son matrices N×N. Los subíndices, para la siguiente descripción, tienen el formato C[row][column].
El bucle básico es:
entero i , 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 por 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 bucle siguiente reutiliza cada valor cargado dos veces, de modo que el bucle interno tiene cuatro cargas y cuatro multiplicaciones-sumas, resolviendo así el problema n.° 2. Al llevar cuatro acumuladores simultáneamente, este código puede mantener ocupado casi todo el tiempo a un único sumador de punto flotante con una latencia de 4 (problema n.° 1). Sin embargo, el código no aborda el tercer problema (ni tampoco aborda el trabajo de limpieza necesario cuando N es impar. Dichos detalles se omitirán en 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 ; } } Este código tenía las iteraciones iy jbloqueadas por un factor de dos y ambos bucles internos de dos iteraciones resultantes estaban completamente desenrollados.
Este código se ejecutaría de manera bastante aceptable en un Cray Y-MP (fabricado a principios de los años 1980), que puede soportar 0,8 multiplicaciones-adiciones por operación de memoria a la memoria principal. Una máquina como un Pentium 4 de 2,8 GHz, fabricado en 2003, tiene un ancho de banda de memoria ligeramente menor y un punto flotante mucho mejor, de modo que puede soportar 16,5 multiplicaciones-adiciones 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 que más acumuladores se ejecuten 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 la ISA . Si la CPU no tiene suficientes registros, el compilador programará cargas y almacenamientos adicionales para derramar 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 memoria. Esta presión de registros es la razón por la que los proveedores de CPU RISC , que pretendían construir máquinas más paralelas que las CPU x86 y 68000 de propósito general, adoptaron archivos de registro de punto flotante de 32 entradas .
El código anterior no utiliza muy bien la memoria caché. Durante el cálculo de una franja horizontal de resultados 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 la memoria caché una vez (suponiendo que una franja de A cabe en la memoria caché con una franja de B), pero B se carga N/ib veces, donde ib es el tamaño de la franja 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 los flujos. 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 extender directamente, ya que eso requeriría muchos más registros acumuladores. En cambio, el bucle se bloquea 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 ) { 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 ; } } } Con este código, se puede configurar ib con cualquier parámetro deseado y la cantidad de cargas de la matriz B se reducirá por ese factor. Esta libertad tiene un costo: se mantienen en la memoria caché N×ib porciones de la matriz A. Mientras esto sea posible, este código no estará limitado por el sistema de memoria.
Entonces, ¿qué tamaño de matriz es el adecuado? El sistema de ejemplo, un Pentium 4 de 2,8 GHz, tiene una caché de datos primaria de 16 KB. Con ib=20, la porción de la matriz A en este código será más grande que la caché primaria cuando N > 100. Para problemas más grandes 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 de modo que la franja tenga un tamaño de 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. Siempre que
El sistema de memoria de la máquina se mantendrá al día con la unidad de coma flotante y el código se ejecutará al máximo rendimiento. La caché de 16 KB del Pentium 4 no es lo suficientemente grande: si se eligiera ib=24 y kb=64, se utilizarían 12 KB de la caché, evitando llenarla por completo, lo que es deseable para que las matrices C y B tengan algo de espacio para fluir. Estos números están dentro del 20% de la velocidad máxima de coma 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 ( i = ii ; i < ii + ib ; i += 2 ) { si ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; de lo contrario { 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 manejar valores de N que no son múltiplos de los factores de bloqueo. Los compiladores que realizan optimización de anidación de bucles emiten código para limpiar los bordes del cálculo. Por ejemplo, la mayoría de los compiladores LNO probablemente separarí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 un compilador de este tipo: si bien es sencillo codificar los casos simples de esta optimización, mantener todos los detalles correctos a medida que se replica y transforma el código es un proceso propenso a errores.
El bucle anterior solo alcanzará el 80% de los picos de flops en el sistema de ejemplo cuando se bloquea para el tamaño de caché L1 de 16 KB. Tendrá un rendimiento peor en sistemas con sistemas de memoria aún más desequilibrados. Afortunadamente, el Pentium 4 tiene una caché de nivel 2 de alto ancho de banda de 256 KB (o más, según el modelo), así como la 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 que ignora la memoria 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 que ignoran la memoria caché para la multiplicación de matrices .
mosaico.