Hispanopedia WikiLa divisió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, tomando cada uno 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 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 múltiples bucles con uno solo. [ 3 ] [ 2 ] La fusión de bucles no siempre mejora la velocidad de ejecución. En algunas arquitecturas , dos bucles pueden tener un mejor rendimiento que uno solo 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 grandes ganancias de rendimiento en lenguajes de computación numérica como Julia al realizar operaciones elemento a 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 ]
Otras ventajas de la fusión de bucles son que evita la sobrecarga de las estructuras de control de bucles y que permite que el procesador paralelice el cuerpo del bucle [ 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 contrasta notablemente con la otra ventaja principal de la fusión de bucles descrita 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 logra eliminar asignaciones redundantes, los aumentos de rendimiento pueden ser considerables [ 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.), lo que puede hacer que la fusión de bucles, la fisión de bucles o ninguna de las dos sea la optimización preferible.
Fisión
Ejemplo en C
int a [ 100 ]; int b [ 100 ]; para ( int i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; b [ i ] = 2 ; }es equivalente a:
int a [ 100 ]; int b [ 100 ]; para ( int i = 0 ; i < 100 ; i ++ ) { a [ i ] = 1 ; } para ( int 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 por elemento) y suma 4 a cada elementoLa misma sintaxis se puede lograr en C++ mediante la sobrecarga de funciones y operadores:
importar <cassert> ;importar std ;usando std :: unique_ptr ;clase FloatArray { private : size_t length ; std :: unique_ptr < float [] > data ; // Constructor interno que produce un array no inicializado explicit FloatArray ( size_t n ) : length { n }, data { new float [ n ]} { } public : // 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). [[ nodiscard ]] static FloatArray range ( size_t start , size_t end ) { assert ( end > start ); size_t length = end - start ; FloatArray a ( length ); for ( size_t i = 0 ; i < length ; ++ i ) { a [ i ] = start + i ; } return a ; } // Operaciones básicas con arrays [[ nodiscard ]] size_t size () const noexcept { return length ; }float & operator []( size_t i ) noexcept { return data [ i ]; }const float & operator []( size_t i ) const noexcept { return data [ i ]; }// Declara un operador de suma sobrecargado como una función amiga libre (esta // sintaxis define operator+ 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 FloatArray operator + ( const FloatArray & a , float b ) { FloatArray 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 engorroso definir todas las posibles operaciones matemáticas sobrecargadas como // amigas dentro de la clase de esta manera, pero esto es solo un ejemplo. friend FloatArray sin ( const FloatArray & a ) { FloatArray b ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } return b ; } };int main ( int argc , char * argv []) { // Aquí realizamos el mismo cálculo que en el ejemplo de MATLAB FloatArray x = FloatArray :: range ( 0 , 1000 ); FloatArray y = sin ( x ) + 4 ; // Imprimimos el resultado, solo para asegurarnos de que el optimizador no elimine // todo (si es lo suficientemente inteligente como para hacerlo). std :: println ( "El resultado es: " ); for ( float f : y ) { std :: println ( "{}" , f ); } return 0 ; }Sin embargo, el ejemplo anterior asigna innecesariamente un array temporal para el resultado de sin(x). Una implementación más eficiente asignaría un único array para yy calcularía yen un solo bucle. Para optimizar esto, un compilador de C++ necesitaría:
- Incluya en línea las llamadas
sinaoperator+funciones. - Fusiona los bucles en un solo bucle.
- Elimine los datos no utilizados y guárdelos en arreglos temporales (también puede usar un registro o una variable de pila).
- Elimine la asignación no utilizada y libérela.
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 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 ocurre, 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 incorporado a un alto nivel, donde el compilador detectará operaciones adyacentes elemento a elemento 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 forma pesimista matrices para almacenar sus resultados, ya que no saben desde qué contexto se llamarán. 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 in situ, como operator+=o std::transform).
Véase también
Referencias
- ↑ YN Srikant; Priti Shankar (3 de octubre de 2018). The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition . CRC Press. ISBN 978-1-4200-4383-9.
- 1 2 Kennedy, Ken y Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach . Morgan Kaufmann. ISBN 1-55860-286-0.
- ↑ Steven Muchnick; Muchnick and Associates (15 de agosto de 1997). Diseño e implementación avanzados de compiladores . Morgan Kaufmann. ISBN 978-1-55860-320-2.
fusión de bucles.
- 1 2 Johnson, Steven G. (21 de enero de 2017). "Más puntos: Fusión de bucles sintácticos en Julia" . julialang.org . Recuperado el 25 de junio de 2021 .
- ↑ "Loop Fusion" . Intel . Consultado el 25 de junio de 2021 .
- ↑ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ↑ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ↑ Godbolt, Matt. "Compiler Explorer - C++ (x86-64 gcc 11.1)" . godbolt.org . Consultado el 25 de junio de 2021 .
- ↑ "Funciones · El lenguaje Julia" . docs.julialang.org . Consultado el 25 de junio de 2021 .
- fisión en bucle
- Optimizaciones del compilador
