En informática , la fisión de bucles (o distribución de bucles ) es una optimización del compilador en la que un bucle se divide en múltiples bucles sobre el mismo rango de índices, cada uno de los cuales 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 interferencia de bucles ) es una optimización del compilador y una transformación de bucles que reemplaza múltiples bucles por uno solo. [3] [2] La fusión de bucles no siempre mejora la velocidad de ejecución. En algunas arquitecturas , dos bucles pueden funcionar mejor que uno 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 asignaciones temporales, lo que puede generar enormes ganancias de rendimiento en lenguajes de computación numérica como Julia cuando se realizan operaciones elemento por 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 bucles descrito anteriormente, que solo se presenta cuando hay dependencias de datos que requieren una asignación intermedia para almacenar los resultados). Si la fusión de bucles puede eliminar las asignaciones redundantes, los aumentos de rendimiento pueden ser grandes. [4] De lo contrario, existe un equilibrio más complejo entre la localidad de los datos, el paralelismo a nivel de instrucción y la sobrecarga del bucle (ramificación, incremento, etc.) que puede hacer que la fusión de bucles, la fisión de bucles o ninguna de ellas, sea la optimización preferible.
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 ; } 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 por elemento) y suma 4 a cada elemento La misma sintaxis se puede lograr en C++ mediante el uso de sobrecarga de funciones y operadores:
#include <cmath> #include <cassert> #include <memoria> #include <iostream> clase Array { size_t length ; std :: unique_ptr < float [] > data ; // Constructor interno que produce un array no inicializado Array ( size_t n ) : length ( n ), data ( new float [ n ]) { } público : // Método de fábrica para producir un array sobre un rango entero (el límite superior es exclusivo, a diferencia de los rangos de MATLAB). static Array Range ( size_t start , size_t end ) { assert ( end > start ); size_t length = end - start ; Array a ( length ); for ( size_t i = 0 ; i < length ; ++ i ) { a [ i ] = start + i ; } return a ; } // Operaciones básicas con arrays size_t size () const { return length ; } float & operator []( size_t i ) { return data [ i ]; } const float & operator []( size_t i ) const { devolver datos [ i ]; } // Declara un operador de suma sobrecargado como una función amiga libre (esta sintaxis define al operador + como una función libre que es amiga de esta clase, a pesar de que aparece como una declaración de función miembro). friend Array operator + ( const Array & a , float b ) { Array c ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ 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 complicado 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 ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } devolver 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 ; // Imprimimos el resultado, solo para asegurarnos de que el optimizador no elimine // todo (si es lo suficientemente inteligente para hacerlo). std :: cout << "El resultado es: " << std :: endl ; for ( size_t i = 0 ; i < y . size (); ++ 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 para y, y realizaría el cálculo yen un único bucle. Para optimizar esto, un compilador de C++ tendría que:
siny operator+.Todos estos pasos son posibles de forma individual. Incluso el paso cuatro es posible a pesar de que funciones como mallocy freetienen efectos secundarios globales, ya que algunos compiladores codifican símbolos como mallocy freepara poder eliminar asignaciones no utilizadas del código. [6] Sin embargo, a partir de clang 12.0.0 y gcc 11.1, esta fusión de bucles y eliminación de asignaciones redundantes no se produce, ni siquiera en el nivel de optimización más alto. [7] [8]
Algunos lenguajes específicamente orientados a la computación numérica, como Julia, pueden tener el concepto de fusión de bucles integrado en un alto nivel, donde el compilador notará las operaciones de elementos adyacentes y las fusionará en un solo bucle. [9] Actualmente, para lograr la misma sintaxis en lenguajes de propósito general como C++, las funciones siny operator+deben asignar de manera pesimista matrices para almacenar sus resultados, ya que no saben desde qué contexto serán llamadas. Este problema se puede evitar en C++ utilizando una sintaxis diferente que no dependa del compilador para eliminar asignaciones temporales innecesarias (por ejemplo, utilizando funciones y sobrecargas para operaciones en el lugar, como operator+=o std::transform).
fusión de bucles.