En la teoría del compilador , el intercambio de bucles es el proceso de intercambiar el orden de dos variables de iteración utilizadas por un bucle anidado . La variable utilizada en el bucle interno cambia al bucle externo y viceversa. A menudo se hace para asegurar que se acceda a los elementos de una matriz multidimensional en el orden en que están presentes en la memoria, mejorando la localidad de referencia .
Por ejemplo, en el fragmento de código:
para yo de 0 a 10 para j de 0 a 20 a [i, j] = i + j
el intercambio de bucle daría como resultado:
para j de 0 a 20 para yo de 0 a 10 a [i, j] = i + j
En ocasiones, tal transformación puede crear oportunidades para optimizar aún más, como la vectorización automática de las asignaciones de la matriz.
La utilidad del intercambio de bucles
El propósito principal del intercambio de bucles es aprovechar la memoria caché de la CPU al acceder a los elementos de la matriz. Cuando un procesador accede a un elemento de la matriz por primera vez, recuperará un bloque completo de datos de la memoria a la caché. Es probable que ese bloque tenga muchos más elementos consecutivos después del primero, por lo que en el siguiente acceso al elemento de la matriz, se traerá directamente desde la caché (que es más rápido que obtenerlo de la memoria principal lenta). Las pérdidas de caché ocurren si los elementos de la matriz a los que se accede contigua dentro del bucle provienen de un bloque de caché diferente, y el intercambio de bucles puede ayudar a prevenir esto. La efectividad del intercambio de bucles depende y debe considerarse a la luz del modelo de caché utilizado por el hardware subyacente y el modelo de matriz utilizado por el compilador.
En el lenguaje de programación C , los elementos de la matriz en la misma fila se almacenan consecutivamente en la memoria (a [1,1], a [1,2], a [1,3]) - en orden de fila mayor . Por otro lado, los programas FORTRAN almacenan elementos de matriz de la misma columna juntos (a [1,1], a [2,1], a [3,1]), utilizando column-major . Por lo tanto, el orden de dos variables de iteración en el primer ejemplo es adecuado para un programa en C, mientras que el segundo ejemplo es mejor para FORTRAN. [1] La optimización de los compiladores puede detectar el orden incorrecto por parte de los programadores e intercambiar el orden para lograr un mejor rendimiento de la caché.
Consideración
Como cualquier optimización del compilador , el intercambio de bucles puede conducir a un peor rendimiento porque el rendimiento de la caché es solo una parte de la historia. Tome el siguiente ejemplo:
do i = 1 , 10000 do j = 1 , 1000 a [ i ] = a [ i ] + b [ j , i ] * c [ i ] end do end do
El intercambio de bucles en este ejemplo puede mejorar el rendimiento de la caché al acceder a b (j, i), pero arruinará la reutilización de a (i) y c (i) en el bucle interno, ya que introduce dos cargas adicionales (para a ( i) y para c (i)) y una tienda adicional (para a (i)) durante cada iteración. Como resultado, el rendimiento general puede degradarse después del intercambio de bucles.
Seguridad
No siempre es seguro intercambiar las variables de iteración debido a las dependencias entre declaraciones para el orden en que deben ejecutarse. Para determinar si un compilador puede intercambiar bucles de forma segura, se requiere un análisis de dependencia .
Ver también
Referencias
- ^ "Intercambio de bucle" (PDF) . Guía de programación paralela para sistemas HP-UX . HP. Agosto de 2003.
Otras lecturas
- Kennedy, Ken ; Allen, Randy (2002). 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 . ISBN 978-1-55860-286-1. LCCN 2001092381 . ISBN 1-55860-286-0 .