Marcos que sustentan el modelo poliédrico

El uso del modelo poliédrico (también llamado modelo de politopo ) dentro de un compilador requiere un software para representar los objetos de este marco (conjuntos de puntos con valores enteros en regiones de varios espacios) y realizar operaciones sobre ellos (por ejemplo, probar si el conjunto está vacío).

Para obtener más detalles sobre los objetos y operaciones de este modelo, y un ejemplo que relaciona el modelo con los programas que se están compilando, consulte la página del modelo poliédrico.

Existen muchos marcos que respaldan el modelo poliédrico . Algunos de estos marcos utilizan una o más bibliotecas para realizar operaciones poliédricas. Otros, en particular Omega, combinan todo en un solo paquete. Algunas bibliotecas de uso común son la biblioteca Omega ^[1] (y una bifurcación más reciente), ^[2] piplib, ^{[3] [4]} PolyLib, ^{[5] [6]} PPL, ^[7] isl , ^[8] el generador de código poliédrico Cloog, ^{[9] [10]} y la biblioteca barvinok para contar soluciones enteras. ^[11] De estas bibliotecas, PolyLib y PPL se centran principalmente en valores racionales, mientras que las otras bibliotecas se centran en valores enteros. El marco poliédrico de gcc se llama Graphite. ^[12] Polly ^[13] proporciona optimizaciones poliédricas para LLVM , y R-Stream ^[14] ha tenido un mapeador poliédrico desde aproximadamente 2006.

Los marcos poliédricos están diseñados para respaldar las técnicas de los compiladores para el análisis y la transformación de código con bucles anidados, lo que produce resultados exactos para los bucles anidados con límites de bucle afines y subíndices ("partes de control estático" de los programas). Se pueden utilizar para representar y razonar sobre ejecuciones (iteraciones) de declaraciones, en lugar de tratar una declaración como un único objeto que representa las propiedades de todas las ejecuciones de esa declaración. Los marcos poliédricos generalmente también permiten el uso de expresiones simbólicas.

Los marcos poliédricos se pueden utilizar para el análisis de dependencias de matrices, incluido tanto el análisis de alias tradicional como técnicas más avanzadas, como el análisis del flujo de datos en matrices o la identificación de dependencias condicionales. También se pueden utilizar para representar la transformación de código y proporcionar funciones para generar el código transformado en un lenguaje de alto nivel. Los sistemas de transformación y generación suelen poder gestionar bucles anidados de forma imperfecta.

Para comparar el modelo poliédrico basado en restricciones con enfoques anteriores, como las transformaciones de bucles individuales y el enfoque unimodular , considere la pregunta de si podemos paralelizar (ejecutar simultáneamente) las iteraciones del siguiente bucle artificial pero simple:

para i := 0 a N hacer
      A(i) := (A(i) + A(Ni))/2

Los enfoques que no pueden representar términos simbólicos (como la cantidad invariante del bucle N en el límite y el subíndice del bucle) no pueden razonar sobre las dependencias en este bucle. Se negarán conservadoramente a ejecutarlo en paralelo o, en algunos casos, lo ejecutarán especulativamente completamente en paralelo, determinarán que esto no es válido y lo volverán a ejecutar secuencialmente.

Los enfoques que manejan términos simbólicos pero representan dependencias a través de vectores de dirección o vectores de distancia determinarán que el bucle i tiene una dependencia (de distancia desconocida), ya que, por ejemplo, cuando N = 10, la iteración 0 del bucle escribe un elemento de matriz (A(0)) que se leerá en la iteración 10 (como A(10-10)) y lee un elemento de matriz (A(10-0)) que luego se sobrescribirá en la iteración 10 (como A(10)). Si todo lo que sabemos es que el bucle i tiene una dependencia, una vez más no podemos ejecutarlo de manera segura en paralelo.

En realidad, solo existen dependencias desde las primeras N/2 iteraciones hasta las últimas N/2, por lo que podemos ejecutar este bucle como una secuencia de dos bucles completamente paralelos (de 0...N/2 y de N/2+1...N). La caracterización de esta dependencia, el análisis del paralelismo y la transformación del código se pueden realizar en términos de la información de cada instancia proporcionada por cualquier marco poliédrico.

El análisis y la transformación instancia por instancia permiten que el modelo poliédrico unifique transformaciones adicionales (como la división de conjuntos de índices, el pelado de bucles, el teselado, la fusión o fisión de bucles y la transformación de bucles anidados de forma imperfecta) con aquellas ya unificadas por el marco unimodular (como el intercambio de bucles, la distorsión y la inversión de bucles anidados de forma perfecta). También ha estimulado el desarrollo de nuevas transformaciones, como la segmentación del espacio de iteración de Pugh y Rosser (una versión instancia por instancia de la segmentación de programas; tenga en cuenta que el código nunca se publicó con la biblioteca Omega).

Los autores de marcos poliédricos han explorado el cálculo simple de la ecuación de calor de diferencias finitas unidimensionales expresado por el siguiente pseudocódigo :

para t := 0 a T hacer 
    para i := 1 a N-1 hacer
        new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // diferencia hacia adelante explícita con R = 0.25
    fin 
    para i := 1 a N-1 hacer
        A(i) := nuevo(i)
    
fin fin

Este código confunde a muchos de los sistemas de transformación del siglo XX, debido a la necesidad de optimizar un bucle anidado imperfecto. Los marcos poliédricos pueden analizar el flujo de información entre diferentes ejecuciones de instrucciones en el bucle anidado y transformar este código para explotar simultáneamente el paralelismo escalable y la localidad escalable .

Sería bueno hacer un resumen de los dos enfoques de este ejemplo, pero por ahora veamos los artículos individuales de Wonnacott, ^{[15] [16]} y Sadayappan et al. ^[17] así como otros que han estudiado este código usando diferentes marcos, como Song y Li. ^[18]

La comparación de trabajos realizados con diferentes marcos de trabajo se complica por diferencias técnicas (que se analizan más adelante) y diferencias en el vocabulario y la presentación. A continuación se ofrecen algunos ejemplos para facilitar la traducción:

Los marcos poliédricos respaldan el análisis de dependencias de diversas maneras, ayudando a capturar el impacto de los términos simbólicos, identificar dependencias condicionales y separar los efectos del aliasing de memoria. Los efectos del aliasing de memoria, en particular, se han descrito de dos maneras: muchos autores distinguen entre dependencias de datos "verdaderas" (que corresponden al flujo real de información) y dependencias falsas que surgen del aliasing de memoria o de la precisión limitada del análisis de dependencias.

Las publicaciones del Proyecto Omega utilizan términos específicos para identificar efectos específicos en el análisis. Mantienen la distinción tradicional entre dependencias de flujo, de salida y antidependencias, según los tipos de acceso a la matriz (de escritura a lectura, de escritura a escritura o de lectura a escritura, respectivamente). Las dependencias se pueden clasificar de forma independiente como basadas en memoria o basadas en valores: la primera corresponde al alias de memoria y la segunda no incluye las dependencias interrumpidas por escrituras intermedias. Una prueba de dependencia puede producir información exacta o aproximada, según la naturaleza del programa que se analiza y los algoritmos utilizados en la prueba. Por último, los resultados del análisis de dependencia se informarán en una abstracción de dependencia que proporciona un cierto grado de precisión.

Por ejemplo, las "relaciones de dependencia" producidas por la Prueba Omega, y los "quasts" producidos por los algoritmos de Feautrier o Maydan y Lam, contienen información precisa (aunque en formas diferentes) acerca de las iteraciones de bucle involucradas en una dependencia. Los resultados de cualquiera de las pruebas pueden convertirse a la forma más tradicional de "vector de dependencia", pero dado que esta abstracción proporciona menos precisión, se perderá gran parte de la información acerca de la dependencia. Ambas técnicas producen información exacta para programas con expresiones de control y subíndice afines, y deben aproximarse para muchos programas fuera de este dominio (es decir, en presencia de subíndices no afines como matrices de índices). El trabajo original de Feautrier se centró en describir dependencias verdaderas , a las que el Proyecto Omega se referiría como dependencias de flujo basadas en valores exactos . El Proyecto Omega también describió el uso de sus algoritmos para dependencias y antidependencias basadas en valores, aunque los quasts de Feautrier presumiblemente también podrían adaptarse fácilmente a esto.

Existen muchas maneras de producir una representación visual del proceso de transformación y disposición en mosaico de un espacio de iteración. Algunos autores representan las transformaciones cambiando la ubicación de los puntos en la página, alineando esencialmente la imagen con los ejes de coordenadas del espacio transformado; en dichos diagramas, los mosaicos aparecen como rectángulos alineados con los ejes o sólidos rectangulares que contienen iteraciones. Se pueden encontrar ejemplos de este enfoque en las publicaciones y el software de visualización de transformaciones de Michelle Mills Strout. ^[19]

Otros autores describen diferentes transformaciones como diferentes frentes de onda de ejecución que se mueven a través de los puntos del sistema de coordenadas original en diferentes ángulos. En estos diagramas, las teselas aparecen como paralelogramos/paralelepípedos. Se pueden encontrar ejemplos de este enfoque en las publicaciones de David G. Wonnacott sobre sesgo temporal . ^[20]

Algunas de las bibliotecas han experimentado un desarrollo más extenso que la biblioteca Omega a principios de la década de 2000, y en muchos lugares tienen algoritmos mucho más sofisticados. En particular, los usuarios han informado de buenos resultados con el generador de código Cloog (tanto en términos del código generado como en términos de capacidad para controlar las compensaciones al generar el código) y con los algoritmos para contar soluciones enteras ( el trabajo de Alexander Barvinok ^[21] requiere una descripción de vértice del politopo, que no está soportada en la biblioteca Omega).

Hay varios otros puntos en los que los marcos difieren, a saber:

La programación entera es NP-completa , y Maydan demostró que el problema de comprobar el aliasing de matrices en bucles anidados con límites y subíndices afines es equivalente a la programación entera; otras operaciones, como el análisis del flujo de datos de matrices, son incluso más complejas (los algoritmos de la biblioteca Omega manejan el lenguaje completo de la aritmética de Presburger, que es O(2^2^2^n)). Por lo tanto, es claramente poco realista esperar resultados rápidos y exactos para problemas arbitrarios de aliasing de matrices o flujo de datos de matrices, incluso en el dominio afín. Afortunadamente, muchos problemas caen en un subconjunto de este dominio donde los algoritmos generales pueden producir una respuesta exacta en tiempo polinomial. ^{[22] [23]}

Fuera de este dominio, la biblioteca Omega, piplib e isl enfatizan la producción de un resultado exacto (excepto en los casos de ciertos usos de símbolos de funciones no interpretadas en Omega), a pesar de la alta complejidad. En algunos casos, como la eliminación de variables ("proyección"), PolyLib y PPL utilizan principalmente algoritmos para el dominio racional y, por lo tanto, producen una aproximación del resultado para variables enteras. Puede darse el caso de que esto reduzca la experiencia común con la biblioteca Omega en la que un cambio menor en un coeficiente puede causar un cambio drástico en la respuesta de los algoritmos de la biblioteca.

Polylib tiene algunas operaciones para producir resultados exactos para Z-poliedros (puntos enteros delimitados por poliedros), pero al momento de escribir este artículo, se han informado errores significativos. ^[24] Tenga en cuenta que también existen errores en la biblioteca Omega, incluida la dependencia de tipos enteros provistos por hardware y casos de algoritmos aritméticos Presburger completos que no se implementaron en la biblioteca. Los usuarios que necesitan resultados exactos para variables enteras pueden tener que tener cuidado con cualquiera de las bibliotecas.

Las técnicas de Barvinok para contar soluciones enteras requieren una descripción de los vértices (y los rayos que los delimitan) del poliedro, pero producen una respuesta exacta de una manera que puede ser mucho más eficiente que las técnicas descritas por Pugh. El algoritmo de Barvinok siempre es polinomial en el tamaño de entrada, para una dimensión fija del politopo y un grado fijo de pesos, mientras que la "fragmentación" en el algoritmo de Pugh puede crecer con los valores de los coeficientes ^[25] (y, por lo tanto, exponencialmente en términos del tamaño de entrada, a pesar de la dimensión fija, a menos que haya algún límite en los tamaños de los coeficientes).

Las bibliotecas poliédricas como PolyLib y PPL explotan la doble descripción de los poliedros y, por lo tanto, admiten naturalmente la enumeración de vértices en politopos (no paramétricos). La biblioteca Omega realiza internamente la enumeración de vértices durante el cálculo de la envoltura convexa. PolyLib e isl proporcionan enumeración de vértices en politopos paramétricos, lo que es esencial para aplicar el algoritmo de Barvinok a los politopos paramétricos.

En algunas partes de un compilador, un resultado aproximado es aceptable en ciertos casos. Por ejemplo, cuando se utiliza el análisis de dependencia para guiar la transformación de bucles, generalmente es aceptable utilizar un superconjunto de las dependencias verdaderas; esto puede evitar una optimización, pero no permite transformaciones de código ilegales. Cuando la biblioteca Omega produce una respuesta aproximada, la respuesta se marca adecuadamente como un límite superior (por ejemplo, mediante "y DESCONOCIDO") o un límite inferior (por ejemplo, mediante "o DESCONOCIDO"). Las respuestas que no se marcan de esta manera son descripciones exactas de conjuntos de puntos con valores enteros (excepto en casos de errores en el software).

Cuando el código contiene una mezcla de términos afines y no afines, las bibliotecas poliédricas pueden, en principio, utilizarse para producir resultados aproximados, por ejemplo, simplemente omitiendo dichos términos cuando sea seguro hacerlo. Además de proporcionar una forma de marcar dichos resultados aproximados, la Biblioteca Omega permite usos restringidos de "Símbolos de Función No Interpretados" para reemplazar cualquier término no lineal, lo que proporciona un sistema que mejora ligeramente el resultado del análisis de dependencia y (probablemente de manera más significativa) proporciona un lenguaje para la comunicación sobre estos términos (para impulsar otros análisis o la comunicación con el programador). Pugh y Wonnacott analizaron un dominio ligeramente menos restringido que el permitido en la biblioteca, pero esto nunca se implementó (existe una descripción en la disertación de Wonnacott).

Algunos tipos de análisis, como el corte del espacio de iteración de Pugh y Rosser , se pueden expresar más fácilmente en términos del cierre transitivo de la información de dependencia. Tanto la Biblioteca Omega como isl proporcionan una operación de cierre transitivo que es exacta para muchos casos que surgen en programas con patrones de dependencia simples. En otros casos, la Biblioteca Omega produce un subconjunto del cierre transitivo, mientras que isl produce un superconjunto. En el caso de la Biblioteca Omega, el propio subconjunto puede ser aproximado, lo que da como resultado un límite superior (etiquetado) de un límite inferior (no etiquetado) del cierre transitivo. Nótese que el cálculo de un cierre transitivo exacto es indecidible. ^[26]

• Optimización de anidación de bucles
• El libro de Jean-Francois Collard Reasoning About Program Transformations, ^[27] cubre parte de la filosofía compartida de estos proyectos.
• La tesis de Cédric Bastoul ^[28] ofrece una introducción al modelo poliédrico.
• La entrada "Prueba Omega" en la próxima Enciclopedia de Computación Paralela de Springer ^[29] describe las aplicaciones y algoritmos de la Biblioteca Omega, indicando las principales publicaciones del Proyecto Omega donde se pueden encontrar más detalles. Se puede encontrar un borrador anterior de este contenido en formato de informe técnico como Informe Técnico de Ciencias de la Computación de Haverford College. ^[30]
• En el primer párrafo de este artículo se proporcionan enlaces a bibliotecas de código abierto relevantes.
• Reservoir Labs ^[31] ofrece "Jolylib", una implementación en Java de Polylib, etc. que "ofrece un rendimiento, una estabilidad y unas características mejorados". Jolylib está disponible para uso comercial y académico.