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 interior cambia al bucle exterior y viceversa. A menudo se hace para garantizar 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 j de 0 a 20 para i de 0 a 10 a[i,j] = i + j
El intercambio de bucles 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 optimizar aún más, como la vectorización automática de las asignaciones de la matriz.
El objetivo principal del intercambio de bucles es aprovechar la memoria caché de la CPU al acceder a 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 al 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 memoria caché (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 evitar esto. 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 una 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 elementos de matriz de la misma columna (a[1,1], a[2,1], a[3,1]), usando column-major . Por 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é.
El intercambio de bucles puede provocar un peor rendimiento porque el rendimiento de la caché es sólo 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 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 almacén 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 declaraciones en cuanto al orden en que deben ejecutarse. Para determinar si un compilador puede intercambiar bucles de forma segura, se requiere un análisis de dependencia .