Modelo politópico

El modelo poliédrico (también llamado método de politopos ) es un marco matemático para programas que realizan un gran número de operaciones —demasiado grandes para enumerarlas explícitamente—, lo que requiere una representación compacta . Los programas con bucles anidados son el ejemplo típico, pero no el único, y el uso más común del modelo es la optimización de bucles anidados en la optimización de programas . El método poliédrico trata cada iteración de bucle dentro de bucles anidados como puntos de una red dentro de objetos matemáticos llamados poliedros , realiza transformaciones afines o transformaciones no afines más generales, como el teselado en los politopos, y luego convierte los politopos transformados en bucles anidados equivalentes, pero optimizados (según el objetivo de optimización), mediante el escaneo de poliedros.

Consideremos el siguiente ejemplo escrito en C :

# define n 100 int i , j ; int a [ n ][ n ] = {{ 0 , 1 }};para ( i = 1 ; i < n ; i ++ ) { para ( j = 1 ; j < ( i + 2 ) && j < n ; j ++ ) { a [ i ][ j ] = a [ i - 1 ][ j ] + a [ i ][ j - 1 ]; } }for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; ++ j ) { printf ( "%4d " , a [ i ][ j ]); } puts ( "" ); }

El problema fundamental de este código es que cada iteración del bucle interno a[i][j]requiere que el resultado de la iteración anterior a[i][j - 1]ya esté disponible. Por lo tanto, este código no se puede paralelizar ni segmentar tal como está escrito actualmente.

Una aplicación del modelo de politopo, con la transformación afín.${\displaystyle (i',\,j')=(i+j,\,j)}$y el cambio apropiado en los límites transformará los bucles anidados anteriores en:

a [ i - j ][ j ] = a [ i - j - 1 ][ j ] + a [ i - j ][ j - 1 ];

En este caso, ninguna iteración del bucle interno depende de los resultados de la iteración anterior; todo el bucle interno puede ejecutarse en paralelo. De hecho, dado que a(i, j) = a[i-j][j]entonces a(i, j)solo depende de a(i - 1, x), con${\displaystyle x\in \{j-1,\,j\}}$(Sin embargo, cada iteración del bucle externo depende de las iteraciones anteriores).

El siguiente código C implementa una forma de tramado con distribución de errores similar al tramado de Floyd-Steinberg , pero modificada con fines pedagógicos. La matriz bidimensional srccontiene hfilas de wpíxeles, cada uno con un valor de escala de grises entre 0 y 255 (inclusive). Una vez finalizada la rutina, la matriz de salida dstcontendrá únicamente píxeles con valor 0 o valor 255. Durante el cálculo, el error de tramado de cada píxel se recopila sumándolo de nuevo a la srcmatriz. (Nótese que srcy dstse leen y escriben durante el cálculo; srcno es de solo lectura, y dstno es de solo escritura).

Cada iteración del bucle interno modifica los valores en src[i][j]función de los valores de src[i-1][j], src[i][j-1], y src[i+1][j-1]. (Las mismas dependencias se aplican a dst[i][j]. Para efectos de sesgo del bucle , podemos considerar src[i][j]y dst[i][j]como el mismo elemento). Podemos ilustrar las dependencias de src[i][j]gráficamente, como en el diagrama de la derecha.

Realizando la transformación afín${\displaystyle (p,\,t)=(i,\,2j+i)}$En el diagrama de dependencias original obtenemos un nuevo diagrama, que se muestra en la siguiente imagen. Luego podemos reescribir el código para iterar sobre py ten lugar de iy j, obteniendo la siguiente rutina "sesgada".

• Marcos de referencia que respaldan el modelo poliédrico
• Optimización de bucles anidados
• Optimización de bucles
• Desenrollado del bucle
• Baldosas de bucle

• "El método básico del politopo" , tutorial de Martin Griebl que contiene diagramas del ejemplo de pseudocódigo anterior.
• "Generación de código en el modelo de politopo" (1998). Martin Griebl, Christian Lengauer y Sabine Wetzel.
• "El generador de código poliédrico CLooG"
• "CodeGen+: Escaneo de poliedros Z"
• PoCC: la colección de compiladores poliédricos
• PLUTO: un paralelizador automático y optimizador de localidad para bucles afines anidados.
  • Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (1 de enero de 2008). «Un paralelizador poliédrico automático práctico y un optimizador de localidad». Actas de la 29.ª Conferencia ACM SIGPLAN sobre Diseño e Implementación de Lenguajes de Programación . PLDI '08. Nueva York, NY, EE. UU.: ACM. págs. 101–113 . doi : 10.1145/1375581.1375595 . ISBN  9781595938602. S2CID 7086982 . 
• polyhedral.info - Un sitio web que recopila información sobre la compilación de poliedros.
• Polly: marco de trabajo LLVM para optimizaciones de alto nivel de bucles y localidad de datos.
• El marco poliédrico Tiramisú del MIT.