Intercambio de bucle

En la teoría de compiladores , 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 realiza para garantizar que se acceda a los elementos de una matriz multidimensional en el orden en que están presentes en la memoria, lo que mejora la localidad de referencia .

Por ejemplo, en el fragmento de código:

para j de 0 a 20 para i de 0 a 10 a[i,j] = i + j

El intercambio de bucle daría como resultado:

para i de 0 a 10 para j de 0 a 20 a[i,j] = i + j

En ocasiones, dicha transformación puede crear oportunidades para una mayor optimización, como la vectorización automática de las asignaciones de matrices.

El objetivo principal del intercambio de bucles es aprovechar la memoria caché de la CPU al acceder a los elementos de una matriz. Cuando un procesador accede a un elemento de una matriz por primera vez, recuperará un bloque completo de datos de la memoria a la memoria 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 obtendrá directamente de la memoria caché (lo que es más rápido que obtenerlo de la memoria principal lenta). Los errores de caché ocurren si los elementos de la matriz a los que se accede de forma contigua dentro del bucle provienen de un bloque de caché diferente, y el intercambio de bucles puede ayudar a evitarlo. La eficacia 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 principal . Por otro lado, los programas FORTRAN almacenan juntos los elementos de la matriz de la misma columna (a[1,1], a[2,1], a[3,1]), utilizando el orden de columna principal . Por lo tanto, el orden de dos variables de iteración en el primer ejemplo es adecuado para un programa C, mientras que el segundo ejemplo es mejor para FORTRAN. ^[1] Los compiladores optimizadores pueden detectar el orden incorrecto por parte de los programadores e intercambiar el orden para lograr un mejor rendimiento de la caché.

El intercambio de bucles puede provocar un peor rendimiento porque el rendimiento de la memoria caché es solo una parte de la historia. Tomemos el siguiente ejemplo:

 hacer i = 1 , 10000 hacer j = 1 , 1000 a [ i ] = a [ i ] + b [ j , i ] * c [ i ] fin hacer fin hacer               

El intercambio de bucles en este ejemplo puede mejorar el rendimiento de la memoria 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 un almacenamiento adicional (para a(i)) durante cada iteración. Como resultado, el rendimiento general puede degradarse después del intercambio de bucles.

No siempre es seguro intercambiar las variables de iteración debido a las dependencias entre las instrucciones en cuanto al orden en el que deben ejecutarse. Para determinar si un compilador puede intercambiar bucles de forma segura, se requiere un análisis de dependencia .

• División de bucle
• Inclinación de bucle
• Fisión y fusión de bucles
• Desenrollado de bucle

• Kennedy, Ken ; Allen, Randy (2002). Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (edición digital de 2011 de la 1.ª ed.). Academic Press / Morgan Kaufmann Publishers / Elsevier . ISBN 978-1-55860-286-1. Número de serie LCCN  2001092381.