Optimización de bucles

En la teoría de compiladores , la optimización de bucles es el proceso de aumentar la velocidad de ejecución y reducir la sobrecarga asociada a los bucles . Desempeña un papel importante en la mejora del rendimiento de la caché y en el aprovechamiento eficaz de las capacidades de procesamiento paralelo . La mayor parte del tiempo de ejecución de un programa científico se dedica a los bucles; por ello, se han desarrollado numerosas técnicas de optimización de compiladores para acelerarlos.

Dado que las instrucciones dentro de los bucles pueden ejecutarse repetidamente, con frecuencia no es posible establecer un límite al número de ejecuciones de instrucciones que se verán afectadas por una optimización de bucle. Esto plantea dificultades al razonar sobre la corrección y los beneficios de una optimización de bucle, específicamente las representaciones del cálculo que se optimiza y las optimizaciones que se realizan. ^{[ 1 ]}

La optimización de bucles puede considerarse como la aplicación de una secuencia de transformaciones de bucle específicas (enumeradas a continuación o en Transformaciones del compilador para computación de alto rendimiento ^{[ 2 ]} ) al código fuente o representación intermedia , con una prueba de validez asociada para cada transformación . Generalmente, una transformación (o secuencia de transformaciones) debe preservar la secuencia temporal de todas las dependencias para mantener el resultado del programa (es decir, debe ser una transformación válida). Evaluar el beneficio de una transformación o secuencia de transformaciones puede resultar bastante difícil con este enfoque, ya que la aplicación de una transformación beneficiosa puede requerir el uso previo de una o más transformaciones que, por sí solas, reducirían el rendimiento.

Las transformaciones de bucle comunes incluyen:

• Fisión o distribución: la fisión de bucles intenta dividir un bucle en varios bucles sobre el mismo rango de índices, pero cada nuevo bucle toma solo una parte del cuerpo del bucle original. Esto puede mejorar la localidad de referencia , tanto de los datos a los que se accede dentro del bucle como del código dentro del cuerpo del bucle.
• Fusión o combinación: esto combina los cuerpos de dos bucles adyacentes que iterarían el mismo número de veces (independientemente de si ese número se conoce en tiempo de compilación o no), siempre que no hagan referencia a los datos del otro.
• Intercambio o permutación: estas optimizaciones intercambian bucles internos con bucles externos. Cuando las variables del bucle indexan un array, dicha transformación puede mejorar la localidad de referencia, dependiendo de la estructura del array.
• Inversión : esta técnica transforma un bucle while estándar en un bucle do/while (también conocido como repeat/until ) envuelto en una condición if , reduciendo a la mitad el número de saltos en los casos en que se ejecuta el bucle. Si bien esto duplica la comprobación de la condición (aumentando el tamaño del código), resulta más eficiente, ya que los saltos suelen provocar un bloqueo en la canalización . Además, si la condición inicial se conoce en tiempo de compilación y se sabe que no tiene efectos secundarios , se puede omitir la condición if inicial .
• Movimiento de código invariante en bucle : esto puede mejorar enormemente la eficiencia al mover un cálculo del interior del bucle al exterior, calculando un valor solo una vez antes de que comience el bucle, si la cantidad resultante del cálculo será la misma en cada iteración del bucle (es decir, una cantidad invariante en bucle). Esto es particularmente importante con expresiones de cálculo de direcciones generadas por bucles sobre arreglos. Para una implementación correcta, esta técnica debe usarse con inversión, ya que no todo el código se puede mover fuera del bucle sin problemas.
• Paralelización : este es un caso especial de paralelización automática que se centra en los bucles, reestructurándolos para que se ejecuten de manera eficiente en sistemas multiprocesador. Puede realizarse automáticamente mediante compiladores ( paralelización automática ) o manualmente (insertando directivas paralelas como OpenMP ).
• Inversión : una optimización sutil que invierte el orden en que se asignan los valores a la variable de índice. Esto puede ayudar a eliminar dependencias y, por lo tanto, permitir otras optimizaciones. Ciertas arquitecturas utilizan construcciones de bucle a nivel de ensamblador que cuentan en una sola dirección (por ejemplo, decrement-jump-if-not-zero [DJNZ] ^{[ 3 ]} ).
• Planificación : este proceso divide un bucle en varias partes que pueden ejecutarse simultáneamente en varios procesadores.
• Sesgo : esta técnica se aplica a un bucle anidado que itera sobre una matriz multidimensional, donde cada iteración del bucle interno depende de las iteraciones anteriores, y reorganiza sus accesos a la matriz de manera que las únicas dependencias se den entre las iteraciones del bucle externo.
• La segmentación de software es un tipo de ejecución fuera de orden de las iteraciones de bucles para ocultar las latencias de las unidades funcionales del procesador.
• La división o fragmentación de bucles busca simplificar un bucle o eliminar dependencias dividiéndolo en múltiples bucles con el mismo cuerpo, pero que iteran sobre diferentes partes del rango de índices. Un caso especial es la fragmentación de bucles , que puede simplificar un bucle con una primera iteración problemática al realizarla por separado antes de entrar en el bucle principal.
• Bloqueo o segmentación: reorganiza un bucle para iterar sobre bloques de datos cuyo tamaño se ajusta a la caché.
• Vectorización : intenta ejecutar el mayor número posible de iteraciones del bucle simultáneamente en un sistema SIMD .
• El desenrollado duplica el cuerpo del bucle varias veces para reducir la cantidad de veces que se comprueba la condición del bucle y la cantidad de saltos, lo que puede degradar el rendimiento al afectar la segmentación de instrucciones. El desenrollado completo de un bucle elimina toda la sobrecarga (excepto la búsqueda de múltiples instrucciones y el aumento del tiempo de carga del programa), pero requiere que se conozca el número de iteraciones en tiempo de compilación (excepto en el caso de la compilación Just-in-Time ). También se debe tener cuidado para asegurar que el recálculo múltiple de variables indexadas no genere una sobrecarga mayor que el avance de punteros dentro del bucle original.
• Desactivación : mueve una condición desde dentro de un bucle a fuera de él duplicando el cuerpo del bucle y colocando una versión del mismo dentro de cada una de las cláusulas if y else de la condición.
• El seccionamiento o minería de tiras, introducido para procesadores vectoriales , es una técnica de transformación de bucles que permite la codificación SIMD (instrucción única, datos múltiples) de bucles y mejora el rendimiento de la memoria. Esto implica que cada operación vectorial se realice con un tamaño menor o igual a la longitud máxima del vector en una máquina vectorial determinada. ^{[ 4 ] [ 5 ]}

• Optimización de bucles anidados
• Modelo politópico
• Paralelismo escalable
• Localidad escalable