Optimización de bucle

Aumentar la velocidad de ejecución y reducir los gastos generales asociados con los bucles.

En la teoría del compilador , la optimización de bucles es el proceso de aumentar la velocidad de ejecución y reducir los gastos generales asociados con los bucles . Desempeña un papel importante a la hora de mejorar el rendimiento de la caché y hacer un uso eficaz de las capacidades de procesamiento paralelo . La mayor parte del tiempo de ejecución de un programa científico se dedica a bucles; como tal, se han desarrollado muchas técnicas de optimización del compilador 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 dar un límite al número de ejecuciones de instrucciones que se verán afectadas por una optimización del bucle. Esto presenta desafíos 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]

Optimización mediante una secuencia de transformaciones de bucle.

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

Las transformaciones de bucle comunes incluyen:

• Fisión o distribución: la fisión de bucle intenta dividir un bucle en múltiples bucles en el mismo rango de índice, 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 en el bucle como del código en el cuerpo del bucle.
• Fusión o combinación: esto combina los cuerpos de dos bucles adyacentes que se repetirían el mismo número de veces (ya sea que ese número se conozca o no en el momento de la compilación), siempre y cuando no hagan referencia a los datos de cada uno.
• 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, dependiendo del diseño de la matriz.
• Inversión : esta técnica cambia un bucle while estándar en un bucle do/ while (también conocido como repetir/hasta  ) envuelto en un condicional if , lo que reduce el número de saltos en dos para los casos en los que se ejecuta el bucle. Al hacerlo, se duplica la verificación de condición (aumentando el tamaño del código), pero es más eficiente porque los saltos generalmente causan una parada en la tubería . 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 el if -guard inicial .
• Movimiento de código invariante en bucle : esto puede mejorar enormemente la eficiencia al mover un cálculo desde dentro del bucle hacia fuera de él, 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 en bucle). 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 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 ).
• 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 así permitir otras optimizaciones. Ciertas arquitecturas utilizan construcciones de bucle a nivel de ensamblaje que cuentan en una sola dirección (por ejemplo, decremento-salto-si-no-cero [DJNZ] ^[3] ).
• Programación : divide un bucle en varias partes que pueden ejecutarse simultáneamente en varios procesadores.
• Sesgar : 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 desordenada de iteraciones de bucle para ocultar las latencias de las unidades de función del procesador.
• Dividir o pelar: esto intenta simplificar un bucle o eliminar dependencias dividiéndolo en múltiples bucles que tienen los mismos cuerpos pero iteran sobre diferentes partes del rango del índice. 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 de tamaño adecuado para caber en la memoria caché.
• Vectorización : intenta ejecutar tantas iteraciones de bucle como sea posible al mismo tiempo en un sistema SIMD .
• Desenrollar : duplica el cuerpo del bucle varias veces para reducir el número de veces que se prueba la condición del bucle y el número de saltos, lo que puede degradar el rendimiento al afectar el proceso de instrucción. Desenrollar completamente un bucle elimina toda la sobrecarga (excepto múltiples búsquedas de instrucciones y un mayor tiempo de carga del programa), pero requiere que se conozca el número 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 variables indexadas no represente una sobrecarga mayor que el avance de punteros dentro del bucle original.
• Desconmutación : mueve un condicional desde dentro de un bucle hacia 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 del condicional.
• Seccionamiento o minería a cielo abierto: introducido para los procesadores vectoriales , el seccionamiento de bucles es una técnica de transformación de bucles para permitir codificaciones SIMD (instrucción única, datos múltiples) de bucles y mejorar el rendimiento de la memoria. Esto implica que cada operación vectorial se realiza 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. Central para este enfoque es la visión del conjunto de todas las ejecuciones de una declaración dentro de n bucles como un conjunto de puntos enteros en un espacio de n dimensiones, con los puntos ejecutándose en orden lexicográfico . Por ejemplo, las ejecuciones de una declaración anidada dentro de un bucle externo con índice i y un bucle interno con índice j pueden asociarse con los pares de números enteros . 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 (i,j)}$ ${\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 imperfectamente y algunas transformaciones (como el mosaico) 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 imperfectamente anidados se considera la unión de un conjunto de politopos que representan las ejecuciones de las declaraciones. Se aplican transformaciones afines a estos politopos, produciendo una descripción de un nuevo orden de ejecución. Los límites de los politopos, las dependencias de los datos y las transformaciones a menudo se describen utilizando sistemas de restricciones, y este enfoque a menudo se denomina enfoque basado en restricciones para la optimización de bucles. Por ejemplo, una sola declaración dentro de un bucle externo ' for i := 0 an ' y un bucle interno ' for j := 0 to i+2 ' se ejecuta una vez para cada par (i, j) tal 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 . Estimar los beneficios de una transformación, o encontrar la mejor transformación para un código determinado en una computadora determinada, sigue siendo tema de investigación en curso al momento de escribir este artículo (2010).

Ver también

• Optimización del nido 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 de texto de programa en el contexto de la optimización estática.
2. David F. Bacon, Susan L. Graham y Oliver J. Sharp. Transformaciones del compilador para informática de alto rendimiento. Informe No. UCB/CSD 93/781, División de Ciencias de la Computación-EECS, Universidad de California, Berkeley, Berkeley, California 94720, noviembre de 1993 (disponible en CiteSeer [1]). Introduce el análisis del compilador, como el análisis de dependencia de datos y el análisis interprocedimental, así como una lista muy completa de transformaciones de bucle.
3. "Conjunto de instrucciones 8051". www.win.tue.nl.​ Consultado el 9 de diciembre de 2019 .
4. "Zona de desarrolladores Intel".
5. "7.6.3.1 Strip-Mining (Sun Studio 12: Guía de programación de 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 del bucle.
7. R. Allen y K. Kennedy. Optimización de compiladores para arquitecturas modernas. Morgan Kaufmann, 2002.