En informática , la fisión de bucle (o distribución de bucle ) es una optimización del compilador en la que un bucle se divide en múltiples bucles sobre el mismo rango de índice y cada uno de ellos toma solo una parte del cuerpo del bucle original. [1] [2] El objetivo es dividir un cuerpo de bucle grande en otros más pequeños para lograr una mejor utilización de la localidad de referencia . Esta optimización es más eficiente en procesadores de múltiples núcleos que pueden dividir una tarea en múltiples tareas para cada procesador .
Por el contrario, la fusión de bucles (o bloqueo de bucles ) es una optimización del compilador y una transformación de bucles que reemplaza varios bucles por uno solo. [3] [2] La fusión de bucle no siempre mejora la velocidad de ejecución. En algunas arquitecturas , dos bucles pueden funcionar mejor que un bucle porque, por ejemplo, hay una mayor localidad de datos dentro de cada bucle. Uno de los principales beneficios de la fusión de bucles es que permite evitar las asignaciones temporales, lo que puede generar enormes ganancias de rendimiento en lenguajes de computación numérica como Julia.al realizar operaciones de elemento en matrices (sin embargo, la fusión de bucles de Julia no es técnicamente una optimización del compilador, sino una garantía sintáctica del lenguaje). [4]
Otros beneficios de la fusión de bucles son que evita la sobrecarga de las estructuras de control de bucles, y también que permite que el cuerpo del bucle sea paralelizado por el procesador [5] aprovechando el paralelismo a nivel de instrucción . Esto es posible cuando no hay dependencias de datos entre los cuerpos de los dos bucles (Esto está en marcado contraste con el otro beneficio principal de la fusión de bucle descrito anteriormente, que sólo en sí presenta cuando no son dependencias de datos que requieren una asignación intermedia para almacenar el resultados). Si la fusión de bucles puede eliminar las asignaciones redundantes, los aumentos de rendimiento pueden ser importantes. [4] De lo contrario, existe una compensación más compleja entre la localidad de datos, el paralelismo a nivel de instrucción y la sobrecarga del bucle (ramificación, incremento, etc.) que puede hacer que la fusión del bucle, la fisión del bucle o ninguna de las dos sean la optimización preferible.
Fisión
Ejemplo en C
int i , a [ 100 ], b [ 100 ]; para ( i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; b [ i ] = 2 ; }
es equivalente a:
int i , a [ 100 ], b [ 100 ]; para ( i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; } para ( i = 0 ; i < 100 ; i ++ ) { b [ i ] = 2 ; }
Fusión
Ejemplo en C ++ y MATLAB
Considere el siguiente código MATLAB:
x = 0 : 999 ; % Crea una matriz de números del 0 al 999 (el rango es inclusivo) y = sin ( x ) + 4 ; % Toma el seno de x (elemento-sabio) y suma 4 a cada elemento
Puede lograr la misma sintaxis en C ++ utilizando la sobrecarga de funciones y operadores:
#include #include #include #include class Array { tamaño_t longitud ; std :: unique_ptr < float [] > datos ; // Constructor interno que produce una matriz no inicializada Array ( size_t n ) : length ( n ), data ( new float [ n ]) { } public : // Método de fábrica para producir una matriz sobre un rango de números enteros (el // límite superior es exclusivo, a diferencia de los rangos de MATLAB). Rango de matriz estática ( tamaño_t inicio , tamaño_t final ) { aserción ( final > inicio ); size_t longitud = final - inicio ; Array a ( longitud ); for ( size_t i = 0 ; i < length ; ++ i ) { a [ i ] = start + i ; } return a ; } // Operaciones básicas de matriz size_t size () const { longitud de retorno ; } float & operator [] ( size_t i ) { devolver datos [ i ]; } const float & operator [] ( size_t i ) const { devolver datos [ i ]; } // Declare un operador de suma sobrecargado como una función amiga gratuita (esta // sintaxis define operator + como una función gratuita que es amiga de esta // clase, a pesar de que aparece como una declaración de función miembro). amigo operador de matriz + ( const matriz & a , float b ) { matriz c ( a . tamaño ()); para ( tamaño_t i = 0 ; i < a . tamaño (); ++ i ) { c [ i ] = a [ i ] + b ; } return c ; } // De manera similar, podemos definir una sobrecarga para la función sin (). En la práctica, // sería difícil de manejar definir todas las posibles operaciones matemáticas sobrecargadas como // amigos dentro de la clase de esta manera, pero esto es solo un ejemplo. friend Array sin ( const Array & a ) { Array b ( a . size ()); para ( tamaño_t i = 0 ; i < a . tamaño (); ++ i ) { b [ i ] = estándar :: sin ( a [ i ]); } return b ; } };int main ( int argc , char * argv []) { // Aquí, realizamos el mismo cálculo que en el ejemplo de MATLAB auto x = Array :: Range ( 0 , 1000 ); auto y = sin ( x ) + 4 ; // Imprime el resultado, solo para asegurarte de que el optimizador no elimina // todo (si es lo suficientemente inteligente para hacerlo). std :: cout << "El resultado es:" << std :: endl ; para ( size_t i = 0 ; i < y . tamaño (); ++ i ) { std :: cout << y [ i ] << std :: endl ; } return 0 ; }
Sin embargo, el ejemplo anterior asigna innecesariamente una matriz temporal para el resultado de sin(x)
. Una implementación más eficiente asignaría una única matriz y
y calcularía y
en un solo bucle. Para optimizar esto, un compilador de C ++ necesitaría:
- Inline las llamadas a funciones
sin
yoperator+
. - Fusiona los bucles en un solo bucle.
- Elimine las tiendas no utilizadas en las matrices temporales (puede usar un registro o una variable de pila en su lugar).
- Elimina la asignación no utilizada y gratis.
Todos estos pasos son posibles individualmente. Incluso el paso cuatro es posible a pesar del hecho de que las funciones como malloc
y free
tienen efectos secundarios globales, ya que algunos compiladores codifican símbolos como malloc
y free
para que puedan eliminar las asignaciones no utilizadas del código. [6] Sin embargo, a partir de clang 12.0.0 y gcc 11.1, esta fusión de bucle y eliminación de asignación redundante no ocurre, incluso en el nivel de optimización más alto. [7] [8]
Algunos lenguajes dirigidos específicamente a la computación numérica, como Julia, pueden tener el concepto de fusión de bucle integrado en un nivel alto, donde el compilador notará operaciones adyacentes de elementos y las fusionará en un solo bucle. [9] Actualmente, para lograr la misma sintaxis en lenguajes de propósito general como C ++, las funciones sin
y operator+
deben asignar matrices de manera pesimista para almacenar sus resultados, ya que no saben desde qué contexto serán llamadas. Este problema se puede evitar en C ++ usando una sintaxis diferente que no dependa del compilador para eliminar asignaciones temporales innecesarias (por ejemplo, usando funciones an y sobrecargas para operaciones in situ, como operator+=
o std::transform
).
Ver también
- Plantillas de expresión
- Transformación de bucle
- Computación nuclear
Referencias
- ^ YN Srikant; Priti Shankar (3 de octubre de 2018). El manual de diseño del compilador: optimizaciones y generación de código de máquina, segunda edición . Prensa CRC. ISBN 978-1-4200-4383-9.
- ^ a b Kennedy, Ken y Allen, Randy. (2001). Optimización de compiladores para arquitecturas modernas: un enfoque basado en la dependencia . Morgan Kaufmann. ISBN 1-55860-286-0.
- ^ 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.
fusión de bucle.
- ^ a b Johnson, Steven G. (21 de enero de 2017). "Más puntos: fusión de bucle sintáctico en Julia" . Julia . Consultado el 25 de junio de 2021 .
- ^ "Loop Fusion" . Intel . Consultado el 25 de junio de 2021 .
- ^ Godbolt, Matt. "Explorador del compilador - C ++ (x86-64 clang 12.0.0)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ^ Godbolt, Matt. "Explorador del compilador - C ++ (x86-64 clang 12.0.0)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ^ Godbolt, Matt. "Explorador del compilador: C ++ (x86-64 gcc 11.1)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ^ "Funciones · El lenguaje de Julia" . docs.julialang.org . Consultado el 25 de junio de 2021 .
- Fisión de bucle