Optimización de bucle - Loop optimization
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 en la mejora del rendimiento de la 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 gasta en bucles; como tal, se han desarrollado muchas técnicas de optimización de compiladores para hacerlas más rápidas.
Representación de computación y transformaciones
Dado que las instrucciones dentro de los bucles se pueden ejecutar repetidamente, con frecuencia no es posible establecer un límite en el número de ejecuciones de instrucciones que se verán afectadas por una optimización de 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 está optimizando y la optimización o las optimizaciones que se están realizando.
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 ) al código fuente o representación intermedia , con cada transformación con una prueba asociada de legalidad. 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 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, resultarían en un rendimiento reducido.
Las transformaciones de bucle común incluyen:
- Fisión o distribución: la fisión de bucle intenta dividir un bucle en varios bucles sobre el mismo rango de índice, pero cada bucle nuevo 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 iterarían la misma cantidad de veces (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 de 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 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 que se ejecuta el bucle. Hacerlo duplica la verificación de condición (aumentando el tamaño del código) pero es más eficiente porque los saltos generalmente causan un bloqueo de la tubería . Además, si se conoce la condición inicial 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 de bucle : esto puede mejorar enormemente la eficiencia al mover un cálculo desde el interior 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 las 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 moverse fuera del ciclo.
- 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. Se puede hacer 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 el que se asignan los valores a la variable de índice. Esto puede ayudar a eliminar dependencias y, por lo tanto, habilitar otras optimizaciones. Algunas arquitecturas utilizan construcciones de bucle a nivel de ensamblaje que cuentan en una sola dirección (por ejemplo, decremento-salto-si-no-cero [DJNZ]).
- Programación : esto 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 para 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 que se repiten en diferentes partes del rango de í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 dimensionados para caber en la 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, con el fin de 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 el flujo de instrucciones. Desenrollar completamente un ciclo elimina toda la sobrecarga (excepto la obtención 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 compilación Just-in-time ). También se debe tener cuidado para asegurar que el recálculo múltiple de variables indexadas no sea una sobrecarga mayor que avanzar punteros dentro del ciclo original.
- Unswitching : 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 de bandas: introducida para los procesadores vectoriales , la sección de bucle es una técnica de transformación de bucle para habilitar las codificaciones de bucles SIMD (instrucción única, datos múltiples) y mejorar el rendimiento de la memoria. Esto implica que cada operación vectorial se realice para un tamaño menor o igual que la longitud máxima del vector en una máquina vectorial determinada.
El marco de transformación unimodular
El enfoque de transformación unimodular utiliza una única matriz unimodular para describir el resultado combinado de una secuencia de muchas de las transformaciones anteriores. Es fundamental para este enfoque 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 n -dimensional, con los puntos que se ejecutan 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 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 .
Una transformación unimodular es legal si conserva 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 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 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 instrucción dentro de un bucle externo ' para i: = 0 an' y un bucle interno ' para 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 conserva la secuencia temporal de todas las dependencias . Estimar los beneficios de una transformación, o encontrar la mejor transformación para un código dado en una computadora determinada, sigue siendo objeto de investigación en curso en el momento de escribir este artículo (2010).