La división de bucles es una técnica de optimización del compilador . Intenta simplificar un bucle o eliminar dependencias dividiéndolo en múltiples bucles que tienen los mismos cuerpos pero que iteran sobre diferentes porciones contiguas del rango de índice.
Peeling de bucle
El pelado de bucle es un caso especial de división de bucle que divide las primeras (o últimas) iteraciones problemáticas del bucle y las realiza fuera del cuerpo del bucle.
Supongamos que un bucle se escribió así:
int p = 10 ; para ( int i = 0 ; i < 10 ; ++ i ) { y [ i ] = x [ i ] + x [ p ]; p = yo ; }
Tenga en cuenta que p = 10
sólo para la primera iteración, y para el resto de iteraciones, p = i - 1
. Un compilador puede aprovechar esto desenrollando (o "pelando") la primera iteración del ciclo.
Después de pelar la primera iteración, el código se vería así:
y [ 0 ] = x [ 0 ] + x [ 10 ]; para ( int i = 1 ; i < 10 ; ++ i ) { y [ i ] = x [ i ] + x [ i -1 ]; }
Esta forma equivalente elimina la necesidad de la variable p
dentro del cuerpo del bucle.
El pelado de bucles se introdujo en gcc en la versión 3.4. Se agregó una división de bucle más generalizada en GCC 7. [1]
Breve historia del término
Aparentemente, el término fue utilizado por primera vez por Cannings, Thompson y Skolnick [2] en su artículo de 1976 sobre modelos computacionales para la herencia (humana). Allí, el término se usó para denotar un método para colapsar información fenotípica en los padres. A partir de ahí, el término se utilizó nuevamente en sus artículos, incluido su artículo fundamental sobre funciones de probabilidad en genealogías complejas. [3]
En tecnología de compiladores, el término apareció por primera vez a finales de la década de 1980 en artículos sobre VLIW y compilación superescalar, incluidos [4] y. [5]
Referencias
- ^ https://gcc.gnu.org/gcc-7/changes.html
- ^ Cannings, C .; Thompson, EA; Skolnick, HH (1976). "La derivación recursiva de probabilidades en genealogías complejas". Avances en probabilidad aplicada . 8 (4): 622–625. doi : 10.2307 / 1425918 .
- ^ Cannings, C .; Thompson, EA; Skolnick, HH (1978). "Funciones de probabilidad en genealogías complejas". Avances en probabilidad aplicada . 10 (1): 26–61. doi : 10.2307 / 1426718 .
- ^ Callahan, D .; Kennedy, Ken (1988). "Compilación de programas para multiprocesadores de memoria distribuida". El diario de la supercomputación . 2 (2): 151-169. doi : 10.1007 / BF00128175 .
- ^ Mahlke, SA; Lin, DC; Chen, WY; Hank, RE; Bringman, RA (1992). Compatibilidad eficaz con el compilador para la ejecución predicada mediante el hiperbloque . 25º Simposio Internacional Anual de Microarquitectura. págs. 45–54.
Otras lecturas
- Kennedy, Ken ; Allen, Randy (2002). "Capítulo 5.7. División de conjuntos de índices - Capítulo 5.7.2. Pelado de bucle". Optimización de compiladores para arquitecturas modernas: un enfoque basado en la dependencia (impresión digital de 2011 de la 1ª ed.). Prensa académica / Morgan Kaufmann Publishers / Elsevier . págs. 211 –212. ISBN 978-1-55860-286-1. LCCN 2001092381 . ISBN 1-55860-286-0 .