El modelo poliédrico (también llamado método politopo ) es un marco matemático para programas que realizan un gran número de operaciones, demasiado grandes para ser enumeradas explícitamente, por lo que requieren una representación compacta . Los programas de bucles anidados son el ejemplo típico, pero no el único, y el uso más común del modelo es para la optimización del nido de bucles en la optimización de programas . El método poliédrico trata cada iteración de bucle dentro de bucles anidados como puntos de celosía dentro de objetos matemáticos llamados poliedros , realiza transformaciones afines o transformaciones no afines más generales como el mosaico en los politopos, y luego convierte los politopos transformados en nidos de bucle equivalentes, pero optimizados (según el objetivo de optimización específico) a través del escaneo de poliedros.
Ejemplo simple
Considere el siguiente ejemplo escrito en C :
const int n = 100 ; int i , j , a [ n ] [ n ]; 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 ]; } }
El problema esencial con 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 o canalizar como está escrito actualmente.
Una aplicación del modelo politopo, con la transformación afín y el cambio apropiado en los límites, transformará los bucles anidados arriba 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 interior se puede ejecutar en paralelo. (Sin embargo, cada iteración del ciclo externo depende de iteraciones anteriores).
Ejemplo detallado
El siguiente código C implementa una forma de tramado de distribución de errores similar al tramado Floyd-Steinberg , pero modificado por razones pedagógicas. La matriz bidimensional src
contiene h
filas de w
píxeles, cada píxel tiene un valor de escala de grises entre 0 y 255 inclusive. Una vez finalizada la rutina, la matriz de salida dst
contendrá solo píxeles con valor 0 o valor 255. Durante el cálculo, el error de tramado de cada píxel se recopila agregándolo de nuevo a la src
matriz. (Observe que src
y dst
se leen y escriben durante el cálculo; src
no es de solo lectura y dst
no 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]
. A los efectos de la inclinación del bucle , podemos pensar en 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.
#define ERR (x, y) (dst [x] [y] - src [x] [y])vacío dither ( carácter sin firmar ** src , carácter sin firmar ** dst , int w , int h ) { int i , j ; para ( j = 0 ; j < h ; ++ j ) { para ( i = 0 ; i < w ; ++ i ) { int v = src [ i ] [ j ]; si ( i > 0 ) v - = ERR ( i - 1 , j ) / 2 ; si ( j > 0 ) { v - = ERR ( i , j - 1 ) / 4 ; si ( i < w - 1 ) v - = ERR ( i + 1 , j - 1 ) / 4 ; } dst [ i ] [ j ] = ( v < 128 ) ? 0 : 255 ; src [ i ] [ j ] = ( v < 0 ) ? 0 : ( v < 255 ) ? v : 255 ; } } } |
Realización de la transformación afín en el diagrama de dependencia original nos da un nuevo diagrama, que se muestra en la siguiente imagen. Entonces podemos reescribir el código para que se repita p
y en t
lugar de i
y j
, obteniendo la siguiente rutina "sesgada".
void dither_skewed ( carácter sin firmar ** src , carácter sin firmar ** dst , int w , int h ) { int t , p ; para ( t = 0 ; t < ( w + ( 2 * h )); ++ t ) { int pmin = max ( t % 2 , t - ( 2 * h ) + 2 ); int pmax = min ( t , w - 1 ); para ( p = pmín ; p <= pmáx ; p + = 2 ) { int i = p ; int j = ( t - p ) / 2 ; int v = src [ i ] [ j ]; si ( i > 0 ) v - = ERR ( i - 1 , j ) / 2 ; si ( j > 0 ) v - = ERR ( i , j - 1 ) / 4 ; si ( j > 0 && i < w - 1 ) v - = ERR ( i + 1 , j - 1 ) / 4 ; dst [ i ] [ j ] = ( v < 128 ) ? 0 : 255 ; src [ i ] [ j ] = ( v < 0 ) ? 0 : ( v < 255 ) ? v : 255 ; } } } |
Ver también
Enlaces externos y referencias
- "El método politopo básico" , tutorial de Martin Griebl que contiene diagramas del ejemplo de pseudocódigo anterior
- "Generación de código en el modelo Polytope" (1998). Martin Griebl, Christian Lengauer y Sabine Wetzel
- "El generador de código poliédrico CLooG"
- "CodeGen +: escaneo de poliedros Z" [ enlace muerto permanente ]
- PoCC: la colección de compiladores poliédricos
- PLUTO: un paralelizador automático y un optimizador de localidad para nidos de bucles afines
- Bondhugula, Uday; Hartono, Albert; Ramanujam, J .; Sadayappan, P. (1 de enero de 2008). Un práctico paralelizador poliédrico automático 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.
- polyhedred.info : un sitio web que recopila información sobre la compilación poliédrica
- Polly - Marco LLVM para optimizaciones de localidades de datos y bucles de alto nivel
- El marco poliédrico de tiramisú del MIT .