Optimización de bucles anidados

En informática , y en particular en el diseño de compiladores , la optimización de bucles anidados (LNO) es una técnica de optimización que aplica un conjunto de transformaciones de bucles con el fin de optimizar la localidad , paralelizar o reducir la sobrecarga de los bucles anidados. (Los bucles anidados se producen cuando un bucle está dentro de otro). 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 comunes de álgebra lineal .

La técnica utilizada para producir esta optimización se llama teselado de bucles , ^{[ 1 ]} también conocido como bloqueo de bucles ^{[ 2 ]} o mina de franjas e intercambio .

La segmentación de bucles divide el espacio de iteración de un bucle en fragmentos o bloques más pequeños, lo que ayuda a garantizar que los datos utilizados en un bucle permanezcan en la caché hasta que se reutilicen. Esta partición del espacio de iteración del bucle permite dividir un array grande en bloques más pequeños, ajustando así los elementos del array a los que se accede dentro del tamaño de la caché, lo que mejora la reutilización de la caché y elimina los requisitos de tamaño de la misma.

Un bucle ordinario

para ( i = 0 ; i < N ; ++ i ) { ... }

puede bloquearse 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.

A continuación se muestra un ejemplo de multiplicación matriz-vector. Hay tres arreglos, cada uno con 100 elementos. El código no divide los arreglos en tamaños más pequeños.

int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i ++ ) { c [ i ] = 0 ; for ( j = 0 ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ][ j ] * b [ j ]; } }

Después de aplicar el mosaico en bucle usando bloques de 2 * 2, el código se ve así:

int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i += 2 ) { c [ i ] = 0 ; c [ i + 1 ] = 0 ; for ( j = 0 ; j < n ; j += 2 ) { for ( x = i ; x < min ( i + 2 , n ); x ++ ) { for ( 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 de n por n . El fragmento de matriz al que se accede, a[i, j], también es de n por n . Cuando n es demasiado grande y el tamaño de la 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 líneas de caché, lo que provoca fallos de caché.

No siempre es fácil determinar el tamaño óptimo de la teselación para un bucle, ya que requiere una estimación precisa de las regiones de la matriz a las que se accede dentro del bucle y del tamaño de la caché de la máquina de destino. El orden de anidamiento de los bucles ( intercambio de bucles ) también influye significativamente en el rendimiento de la caché. El bloqueo explícito exige elegir el tamaño de la teselación en función de estos factores. Por el contrario, los algoritmos que no tienen en cuenta la caché están diseñados para utilizarla de forma eficiente sin bloqueo explícito.

Muchas operaciones matemáticas complejas en las computadoras terminan dedicando gran parte de su tiempo a la multiplicación de matrices . La operación es:

C = A×B

donde A, B y C son matrices N×N. Los subíndices, para la siguiente descripción, tienen la forma C[row][column].

El bucle básico es:

int 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 que resolver:

• Las sumas de punto flotante requieren cierto número de ciclos para completarse. Para mantener ocupado un sumador con una latencia de varios ciclos, el código debe actualizar varios acumuladores en paralelo.
• Normalmente, las máquinas solo pueden realizar una operación de memoria por cada multiplicación y suma , por lo que los valores cargados deben reutilizarse al menos dos veces.
• Los sistemas de memoria típicos de PC solo pueden almacenar una palabra doble de 8 bytes por cada 10 a 30 operaciones de multiplicación y suma de doble precisión, por lo que los valores cargados en la caché deben reutilizarse muchas veces.

El bucle original calcula el resultado para una entrada de 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 multiplicaciones-sumas, resolviendo así el problema n.° 2. Al manejar cuatro acumuladores simultáneamente, este código puede mantener ocupado casi todo el tiempo un único sumador de punto flotante con una latencia de 4 (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 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 ha tenido ambas iiteraciones jbloqueadas por un factor de dos y ambos bucles internos resultantes de dos iteraciones completamente desenrollados.

Este código funcionaría de forma bastante aceptable en un Cray Y-MP (fabricado a principios de la década de 1980), que puede soportar 0,8  multiplicaciones y sumas por operación de 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 una precisión de coma flotante mucho mejor, por lo que puede soportar 16,5  multiplicaciones y sumas por operación de memoria. En consecuencia, 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 suma de punto flotante mayor 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 uno de 2x2, pero el código resultante no siempre es más rápido. El bucle requiere registros para almacenar 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 el ISA . Si la CPU no tiene suficientes registros, el compilador programará cargas y almacenamientos adicionales para volcar los registros en las ranuras de la pila, lo que hará que el bucle se ejecute más lento que un bucle de bloques más pequeño.

La multiplicación de matrices, al igual que muchos otros códigos, puede verse limitada por el ancho de banda de la memoria, y un mayor número de registros puede ayudar al compilador y al programador a reducir la necesidad de dicho ancho de banda. Esta presión sobre los registros explica por qué los fabricantes de CPU RISC , que pretendían construir máquinas más paralelas que las CPU x86 y 68000 de propósito general , adoptaron registros de punto flotante de 32 entradas .

El código anterior no utiliza la caché de forma eficiente. Durante el cálculo de una franja horizontal de los resultados de C, se carga una franja horizontal de A y se carga la matriz B completa. Para todo el cálculo, C se almacena una vez (lo cual es bueno), A se carga en la caché una vez (suponiendo que una franja de A cabe en la caché junto 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 ³ /ib cargas de doble palabra desde la memoria principal. En el código anterior, ib es 2.

El siguiente paso para reducir el tráfico de memoria es aumentar al máximo el tamaño de ib. Debe ser mayor que el valor de "balance" reportado por los flujos. En el caso de un sistema  Pentium  4 de 2,8 GHz utilizado en este ejemplo, el valor de balance es 16,5. El segundo ejemplo de código anterior no se puede extender directamente, ya que requeriría muchos más registros acumuladores. En su lugar, el bucle se bloquea en i. (Técnicamente, esta es la segunda vez que se bloquea i, ya que la primera vez fue por un factor de 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 establecer ib en cualquier parámetro deseado, y la cantidad de cargas de la matriz B se reducirá en ese factor. Esta flexibilidad tiene un costo: se almacenan en caché N×ib segmentos de la matriz A. Mientras esto sea posible, este código no estará limitado por el sistema de memoria.

¿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á mayor que la caché primaria cuando N > 100. Para problemas de mayor tamaño, se necesita otro método.

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${\displaystyle 2*N^{3}/kb}$Transferencias de memoria . B todavía se transfiere N/ib veces, para${\displaystyle N^{3}/ib}$transferencias . Siempre y cuando

2*N/kb + N/ib < N/balance

El sistema de memoria de la máquina podrá seguir el ritmo de la unidad de coma flotante y el código se ejecutará con el máximo rendimiento. La caché de 16 KB del Pentium 4 no es del todo suficiente: si se eligieran ib=24 y kb=64, se usarían 12 KB de la caché, evitando así llenarla por completo, lo cual es deseable para que las matrices C y B tengan espacio para funcionar. Estos valores se sitúan 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 del manejo de valores de N que no son múltiplos de los factores de bloqueo. Los compiladores que optimizan el anidamiento de bucles generan 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 instrucción if del ibucle. Esta es una de las ventajas de este tipo de 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 las operaciones de punto flotante máximas en el sistema de ejemplo cuando se bloquea para el tamaño de caché L1 de 16 KB. Su rendimiento será aún 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), además de la caché de nivel 1. Hay una opción:

• Ajusta el tamaño de los bloques de la caché de nivel 2. Esto pondrá a prueba la capacidad del procesador para mantener muchas instrucciones en ejecución simultáneamente, y es probable que no pueda alcanzar el ancho de banda completo de la caché de nivel 2.
• Bloquea los bucles una y otra vez para los tamaños de caché de nivel 2. Con un total de tres niveles de bloqueo (para el archivo de registros, para la caché L1 y para la caché L2), el código minimizará el ancho de banda requerido en cada nivel de la jerarquía de memoria . Desafortunadamente, los niveles adicionales de bloqueo generarán aún más sobrecarga de bucle, lo que para ciertos tamaños de problemas en ciertos hardware puede consumir más tiempo que cualquier deficiencia en la capacidad del hardware para transmitir datos desde la caché L2.

En lugar de optimizarse específicamente para un tamaño de caché concreto, como en el primer ejemplo, un algoritmo que ignora la caché está diseñado para aprovechar cualquier caché disponible, independientemente de 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 caché para la multiplicación de matrices .

• El dispositivo de Duff
• Optimización de bucles

1. Wolfe, M. Más teselado del espacio de iteración . Supercomputing'89, páginas 655–664, 1989.
2. Wolf, ME y Lam, M. Un algoritmo de optimización de la localidad de datos . PLDI '91, páginas 30–44, 1991.
3. Irigoin, F. y Triolet, R. Particionamiento de supernodos . POPL '88, páginas 319–329, 1988.
4. Xue, J. Loop Tiling for Parallelism . Kluwer Academic Publishers. 2000.
5. MS Lam, EE Rothberg y ME Wolf. El rendimiento de la caché y las optimizaciones de los algoritmos bloqueados . En Actas de la 4.ª Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos, páginas 63-74, abril de 1991.

• Resultados de la prueba de rendimiento Streams , que muestran el equilibrio general entre las operaciones de punto flotante y las operaciones de memoria para muchos ordenadores diferentes.
• "CHiLL: Marco de transformación de bucles de alto nivel componible"