En ciencias de la computación y particularmente en el diseño de compiladores , la optimización de nidos de bucle (LNO) es una técnica de optimización que aplica un conjunto de transformaciones de bucle con el propósito de optimización de localidad o paralelización u otra reducción de sobrecarga de bucle de los nidos de bucle. ( 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 comunes de álgebra lineal .
La técnica utilizada para producir esta optimización se llama mosaico de bucle , [1] también conocido como bloqueo de bucle [2] o mina a cielo abierto e intercambio .
Descripción general
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 de 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 en el 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.
Ejemplo: multiplicación matriz-vector
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 ]; 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 bucle con 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 ciclo original es n por n . El fragmento al que se accede de la matriz a [i, j] 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 de bucle (por ejemplo i = 1
, j = 1 to n
) pueden cruzar las líneas de la memoria caché, provocando fallas en la memoria caché.
Tamaño de mosaico
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 la 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 que ignoran la memoria caché están diseñados para hacer un uso eficiente de la memoria caché sin un bloqueo explícito.
Ejemplo: multiplicación de matrices
Muchas operaciones matemáticas grandes en computadoras terminan gastando gran parte de su tiempo en 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, están en forma C[row][column]
.
El ciclo 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 a resolver:
- Las adiciones de punto flotante requieren varios ciclos para completarse. Para mantener ocupado un sumador con latencia de ciclo múltiple, el código debe actualizar varios acumuladores en paralelo.
- Por lo general, las máquinas solo pueden realizar una operación de memoria por adición múltiple , por lo que los valores cargados deben reutilizarse al menos dos veces.
- Los sistemas de memoria de PC típicos solo pueden admitir una palabra doble de 8 bytes por cada 10-30 adiciones de multiplicación de doble precisión, por lo que los valores cargados en la memoria caché deben reutilizarse muchas veces.
El ciclo 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 ciclo siguiente reutiliza cada valor cargado dos veces, de modo que el ciclo interior tiene cuatro cargas y cuatro multiplica-suma, resolviendo así el problema # 2. Al llevar cuatro acumuladores simultáneamente, este código puede mantener ocupado un solo sumador de punto 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 se dejará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 ; } }
Este código ha tenido las iteraciones i
y j
bloqueadas por un factor de dos y los dos bucles internos de dos iteraciones resultantes se han desenrollado por completo.
Este código se ejecutaría de forma bastante aceptable en un Cray Y-MP (construido a principios de la década de 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, 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 multiplicadores 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 varios sumadores requeriría que más acumuladores se ejecutaran en paralelo. Es fácil cambiar el ciclo 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, 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 almacenes 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 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 tenían la intención de 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 usa muy bien la caché. Durante el cálculo de una franja horizontal de los resultados de C, se carga una franja horizontal de A y se carga toda la matriz B. Para el cálculo completo, C se almacena una vez (eso es bueno), A se carga en la caché una vez (asumiendo que una franja de A cabe en la 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 palabra doble 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 extender directamente, ya que eso requeriría muchos más registros acumuladores. En cambio, el bucle está bloqueado sobre i. (Técnicamente, esta es 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, ib se puede establecer en cualquier parámetro deseado, y el número de cargas de la matriz B se reducirá en ese factor. Esta libertad tiene un costo: N × ib cortes de la matriz A se mantienen en la caché. Siempre que se ajuste, 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 principal de 16 KB. Con ib = 20, la porción de la matriz A en este código será más grande que la 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 sea de tamaño ib × kb. Bloquear el bucle k significa que la matriz C se cargará y almacenará N / kb veces, para un total detransferencias de memoria. B todavía se transfiere N / ib veces, portransferencias. Siempre y cuando
- 2 * N / kb + N / ib
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. La caché de 16 KB del Pentium 4 no es lo suficientemente grande: si se eligieran ib = 24 y kb = 64 en su lugar, se usarían 12 KB de la caché, evitando llenarla por completo, lo cual es deseable, por lo que las matrices C y B deben tener algo de espacio para fluir. Estos números están dentro del 20% de la velocidad máxima de punto flotante del procesador.
Aquí está el código con el bucle k
bloqueado.
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 ) { if ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; más { 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 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 de LNO probablemente dividirían la iteración kk == 0 del resto de las kk
iteraciones, para eliminar la instrucción if del i
ciclo. 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 mientras el código se replica y transforma es un proceso propenso a errores.
El ciclo anterior solo alcanzará el 80% de los picos de flops en el sistema de ejemplo cuando se bloquee para el tamaño de caché L1 de 16 KB. Lo hará peor en sistemas con sistemas de memoria aún más desequilibrados. Afortunadamente, el Pentium 4 tiene una memoria caché de nivel 2 de alto ancho de banda de 256 KB (o más, según el modelo), así como la memoria caché de nivel 1. Hay una opción:
- Ajuste los tamaños de bloque para la caché de nivel 2. Esto enfatizará la capacidad del procesador para mantener muchas instrucciones en vuelo simultáneamente, y es muy probable que no pueda alcanzar el ancho de banda completo de la caché de nivel 2.
- Vuelva a bloquear los bucles, de nuevo para los tamaños de caché de nivel 2. Con un total de tres niveles de bloqueo (para el archivo de registro, para la caché L1 y 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 incurrirán en una sobrecarga de bucle aún mayor, lo que para algunos tamaños de problemas en algunos hardware puede llevar más tiempo que cualquier deficiencia en la capacidad del hardware para transmitir datos desde la caché L2.
En lugar de ajustar específicamente para un tamaño de caché en particular, como en el primer ejemplo, un algoritmo que ignora el 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 a la caché para la multiplicación de matrices .
Ver también
Referencias
- ^ Steven Muchnick; Muchnick y Asociados (15 de agosto de 1997). Implementación avanzada del diseño del compilador . Morgan Kaufmann. ISBN 978-1-55860-320-2.
embaldosado.
- ^ João MP Cardoso; Pedro C. Diniz (2 de abril de 2011). Técnicas de compilación para arquitecturas reconfigurables . Springer Science & Business Media. ISBN 978-0-387-09671-1.
Otras lecturas
- Wolfe, M. Más mosaico espacial de iteración . Supercomputing'89, páginas 655–664, 1989.
- Wolf, ME y Lam, M. Un algoritmo de optimización de localización de datos . PLDI '91, páginas 30–44, 1991.
- Irigoin, F. y Triolet, R. Particionamiento de supernodo . POPL '88, páginas 319–329, 1988.
- Xue, J. Loop Tiling for Parallelism . Editores académicos de Kluwer. 2000.
- MS Lam, EE Rothberg y ME Wolf. El rendimiento de la caché y las optimizaciones de los algoritmos bloqueados . En Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, páginas 63–74, abril de 1991.
enlaces externos
- Transmite resultados de referencia , que muestran el equilibrio general entre las operaciones de punto flotante y las operaciones de memoria para muchas computadoras diferentes
- "CHiLL: Marco de transformación de bucle de alto nivel componible" [ enlace muerto permanente ]