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 varios bucles en el mismo rango de índice y cada uno 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 multinúcleo que pueden dividir una tarea en varias 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 varios 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 al realizar operaciones por elementos 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 de la lengua). [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 procesador [5] paralelice el cuerpo del bucle 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 contrasta marcadamente con el otro beneficio principal de la fusión de bucles descrito anteriormente, que sólo se presenta cuando hay dependencias de datos que requieren una asignación intermedia para almacenar los datos). resultados). Si la fusión de bucles puede eliminar asignaciones redundantes, los aumentos de rendimiento pueden ser grandes. [4] De lo contrario, existe una compensación más compleja 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 del bucle, la fisión del bucle, o ninguna de las dos, sea la optimización preferible.
int i , a [ 100 ], b [ 100 ]; para ( i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; segundo [ yo ] = 2 ; } es equivalente a:
int i , a [ 100 ], b [ 100 ]; para ( yo = 0 ; yo < 100 ; yo ++ ) { a [ yo ] = 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 inclusive) y = sin ( x ) + 4 ; % Tome el seno de x (por elementos) y agregue 4 a cada elemento Podrías lograr la misma sintaxis en C++ usando la sobrecarga de funciones y operadores:
#include <cmath> #include <cassert> #include <memoria> #include <iostream> clase Matriz { tamaño_t longitud ; std :: Unique_ptr < float [] > datos ; // Constructor interno que produce una matriz no inicializada Array ( size_t n ) : longitud ( n ), datos ( new float [ n ]) { } public : // Método de fábrica para producir una matriz sobre un rango de enteros (el // límite superior es exclusiva, a diferencia de las gamas de MATLAB). Rango de matriz estática ( tamaño_t inicio , tamaño_t final ) { afirmar ( fin > inicio ); tamaño_t longitud = fin - inicio ; Matriz a ( longitud ); for ( tamaño_t i = 0 ; i < longitud ; ++ i ) { a [ i ] = inicio + i ; } devolver un ; } // Operaciones básicas con matrices size_t size () const { return length ; } flotador y operador []( size_t i ) { devolver datos [ i ]; } const float & operador []( size_t i ) const { devolver datos [ i ]; } // Declarar un operador de suma sobrecargado como una función amiga libre (esta // sintaxis define 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). amigo Operador de matriz + ( const Array & a , float b ) { Array c ( a . size ()); para ( tamaño_t i = 0 ; i < a . tamaño (); ++ i ) { c [ i ] = a [ i ] + b ; } devolver 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 // amigas dentro de la clase de esta manera, pero esto es sólo un ejemplo. amigo 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 = pecado ( x ) + 4 ; // Imprime el resultado, solo para asegurarte de que el optimizador no elimine // todo (si es lo suficientemente inteligente como para hacerlo). std :: cout << "El resultado es: " << std :: endl ; for ( size_t i = 0 ; i < y . size (); ++ i ) { std :: cout << y [ i ] << std :: endl ; } devolver 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 yy calcularía yen un solo bucle. Para optimizar esto, un compilador de C++ necesitaría:
siny operator+.Todos estos pasos son posibles individualmente. 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 que puedan 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 ocurre, ni siquiera en el nivel de optimización más alto. [7] [8]
Algunos lenguajes específicamente dirigidos 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á 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 pesimistamente matrices 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 y sobrecargas para operaciones in situ, como operator+=o std::transform).
fusión de bucles.