Optimización de bucles

Aumentar la velocidad de ejecución y reducir los costos asociados con los bucles

En la teoría de compiladores , la optimización de bucles es el proceso de aumentar la velocidad de ejecución y reducir los costos asociados con los bucles . Desempeña un papel importante en la mejora del rendimiento de la memoria caché y en el uso 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 muchas técnicas de optimización de compiladores para hacerlos más rápidos.

Representación de cálculos y transformaciones

Dado que las instrucciones dentro de los bucles se pueden ejecutar repetidamente, con frecuencia no es posible establecer un límite para la cantidad de ejecuciones de instrucciones que se verán afectadas por una optimización de bucle. Esto presenta desafíos a la hora de razonar sobre la exactitud y los beneficios de una optimización de bucle, específicamente las representaciones del cálculo que se está optimizando y la(s) optimización(es) que se está(n) realizando. ^[1]

Optimización mediante una secuencia de transformaciones de bucle

La optimización de bucles puede verse como la aplicación de una secuencia de transformaciones de bucles 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 , y cada transformación tiene una prueba asociada de legalidad. Una transformación (o secuencia de transformaciones) generalmente debe preservar la secuencia temporal de todas las dependencias si se pretende preservar el resultado del programa (es decir, ser una transformación legal). Evaluar el beneficio de una transformación o secuencia de transformaciones puede ser bastante difícil dentro de 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í mismas, darían como resultado un rendimiento reducido.

Las transformaciones de bucle más 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 bucle nuevo ocupa solo una parte del cuerpo del bucle original. Esto puede mejorar la localidad de referencia , tanto de los datos a los que se accede en el bucle como del código en el cuerpo del bucle.
• Fusión o combinación: combina los cuerpos de dos bucles adyacentes que se iterarían la misma cantidad de veces (ya sea que se conozca o no ese número en el momento de la compilación), 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 se indexan en una matriz, dicha transformación puede mejorar la localidad de referencia, según el diseño de la matriz.
• Inversión : esta técnica convierte un bucle while estándar en un bucle do/while (también conocido como repeat/until  ) envuelto en una condición if , lo que reduce la cantidad de saltos en dos para los casos en los que se ejecuta el bucle. Al hacerlo, se duplica la verificación de la condición (lo que aumenta el tamaño del código), pero es más eficiente porque los saltos generalmente causan un bloqueo de 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 protección if inicial.
• Movimiento de código invariante respecto de los bucles : esto puede mejorar enormemente la eficiencia al mover un cálculo desde el interior del bucle hacia el exterior, calculando un valor solo una vez antes de que comience el bucle, si la cantidad resultante del cálculo será la misma para cada iteración del bucle (es decir, una cantidad invariante respecto de los bucles). Esto es particularmente importante con expresiones de cálculo de direcciones generadas por bucles sobre matrices. Para una implementación correcta, esta técnica debe usarse con inversión, porque no todo el código es seguro para moverlo fuera del bucle.
• Paralelización : este es un caso especial de paralelización automática que se centra en los bucles y los reestructura 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 ).
• Reversión: una optimización sutil que invierte el orden en el que se asignan los valores a la variable de índice. Esto puede ayudar a eliminar dependencias y, por lo tanto, permitir otras optimizaciones. Algunas arquitecturas utilizan construcciones de bucle a nivel de ensamblaje que cuentan en una sola dirección solamente (por ejemplo, decrement-jump-if-not-zero [DJNZ] ^[3] ).
• Programación : 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 iteraciones anteriores y reorganiza sus accesos a la matriz de modo que las únicas dependencias sean entre iteraciones del bucle externo.
• Canalización de software : un tipo de ejecución fuera de orden de iteraciones de bucle para ocultar las latencias de las unidades de función del procesador.
• División o pelado: este método intenta simplificar un bucle o eliminar dependencias al dividirlo en varios bucles que tienen los mismos cuerpos pero que iteran sobre diferentes partes del rango de índices. Un caso especial es el pelado de bucles , que puede simplificar un bucle con una primera iteración problemática al realizar esa iteración por separado antes de ingresar al bucle.
• Mosaico o bloqueo: reorganiza un bucle para iterar sobre bloques de datos dimensionados para caber en la memoria caché.
• Vectorización : intenta ejecutar tantas iteraciones de bucle como sea posible al mismo tiempo en un sistema SIMD .
• Desenrollado : duplica el cuerpo del bucle varias veces para disminuir la cantidad de veces que se prueba la condición del bucle y la cantidad de saltos, lo que puede degradar el rendimiento al afectar la secuencia de instrucciones. Desenrollar por completo un bucle elimina toda la sobrecarga (excepto las múltiples recuperaciones de instrucciones y el aumento del tiempo de carga del programa), pero requiere que se conozca la cantidad de iteraciones en el momento de la compilación (excepto en el caso de la compilación Just-in-time ). También se debe tener cuidado para garantizar que el recálculo múltiple de las variables indexadas no sea una sobrecarga mayor que el avance de los punteros dentro del bucle original.
• Anular conmutación : mueve un condicional desde el interior de un bucle al exterior del mismo duplicando el cuerpo del bucle y colocando una versión del mismo dentro de cada una de las cláusulas if y else del condicional.
• Seccionamiento o minería de datos en franjas: introducido para los procesadores vectoriales , el seccionamiento de bucles es una técnica de transformación de bucles que permite codificaciones 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 para un tamaño menor o igual a la longitud máxima del vector en una máquina vectorial determinada. ^{[4] [5]}

El marco de transformación unimodular

El enfoque de transformación unimodular ^[6] utiliza una única matriz unimodular para describir el resultado combinado de una secuencia de muchas de las transformaciones anteriores. Un aspecto central de este enfoque es la visión del conjunto de todas las ejecuciones de una sentencia dentro de n bucles como un conjunto de puntos enteros en un espacio n -dimensional, donde los puntos se ejecutan en orden lexicográfico . Por ejemplo, las ejecuciones de una sentencia anidada dentro de un bucle externo con índice i y un bucle interno con índice j se pueden asociar con los pares de números enteros ⁠ ⁠ ${\displaystyle (i,j)}$ . La aplicación de una transformación unimodular corresponde a la multiplicación de los puntos dentro de este espacio por la matriz. Por ejemplo, el intercambio de dos bucles corresponde a la matriz . ${\displaystyle {\begin{bmatrix}0&1\\1&0\end{bmatrix}}}$

Una transformación unimodular es legal si preserva la secuencia temporal de todas las dependencias ; medir el impacto en el rendimiento de una transformación unimodular es más difícil. Los bucles anidados de forma imperfecta y algunas transformaciones (como el teselado) no encajan fácilmente en este marco.

El marco poliédrico o basado en restricciones

El modelo poliédrico ^[7] maneja una clase más amplia de programas y transformaciones que el marco unimodular. El conjunto de ejecuciones de un conjunto de declaraciones dentro de un conjunto de bucles posiblemente anidados de manera imperfecta se considera como la unión de un conjunto de politopos que representan las ejecuciones de las declaraciones. Se aplican transformaciones afines a estos politopos, lo que produce una descripción de un nuevo orden de ejecución. Los límites de los politopos, las dependencias de datos y las transformaciones a menudo se describen utilizando sistemas de restricciones, y este enfoque a menudo se conoce como un enfoque basado en restricciones para la optimización de bucles. Por ejemplo, una sola declaración dentro de un bucle externo ' for i := 0 to n ' y un bucle interno ' for j := 0 to i+2 ' se ejecuta una vez para cada par (i, j) de modo que 0 <= i <= n y 0 <= j <= i+2 .

Una vez más, una transformación es legal si preserva la secuencia temporal de todas las dependencias . La estimación de los beneficios de una transformación, o la búsqueda de la mejor transformación para un código determinado en una computadora determinada, sigue siendo objeto de investigación en curso al momento de escribir este artículo (2010).

Véase también

• Optimización de anidación de bucles
• Modelo de politopo
• Paralelismo escalable
• Localidad escalable

Referencias

1. En el libro Reasoning About Program Transformations , Jean-Francois Collard analiza en profundidad la cuestión general de representar ejecuciones de programas en lugar del texto del programa en el contexto de la optimización estática.
2. David F. Bacon, Susan L. Graham y Oliver J. Sharp. Compiler transforms for high-performance computing. Informe n.º UCB/CSD 93/781, Computer Science Division-EECS, University of California, Berkeley, Berkeley, California 94720, noviembre de 1993 (disponible en CiteSeer [1]). Presenta análisis de compiladores, como el análisis de dependencia de datos y el análisis interprocedimental, así como una lista muy completa de transformaciones de bucles.
3. "Conjunto de instrucciones 8051". www.win.tue.nl . Consultado el 9 de diciembre de 2019 .
4. "Zona para desarrolladores de Intel".
5. "7.6.3.1 Minería a cielo abierto (Sun Studio 12: Guía de programación Fortran)".
6. Steven S. Muchnick, Diseño e implementación de compiladores avanzados, 1997 Morgan Kaufmann. La sección 20.4.2 analiza la optimización de bucles.
7. R. Allen y K. Kennedy. Optimización de compiladores para arquitecturas modernas. Morgan Kaufmann, 2002.