stringtranslate.com

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 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:

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 ⁠ ⁠ . 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 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

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.