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 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 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 bucle 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 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 sean la optimización preferible.
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 sola matriz yy calcularía yen un solo bucle. Para optimizar esto, un compilador de C ++ necesitaría:
Todos estos pasos son posibles individualmente. Incluso el paso cuatro es posible a pesar del hecho de que las funciones como mallocy freetienen efectos secundarios globales, ya que algunos compiladores codifican símbolos como mallocy freepara 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 se produce, 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 bucles integrado en un nivel alto, 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 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 ++ mediante el uso de una sintaxis diferente que no dependa del compilador para eliminar asignaciones temporales innecesarias (por ejemplo, el uso de funciones y sobrecargas para operaciones en el lugar, como operator+=o std::transform).