El modelo poliédrico (también llamado método de politopos ) es un marco matemático para programas que realizan grandes cantidades de operaciones (demasiado grandes para enumerarlas 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 de anidación 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 red dentro de objetos matemáticos llamados poliedros , realiza transformaciones afines o transformaciones no afines más generales, como el mosaico de los politopos, y luego convierte los politopos transformados en anidaciones de bucles equivalentes, pero optimizadas (dependiendo del objetivo de optimización objetivo), a través del escaneo de poliedros.
Considere el siguiente ejemplo escrito en C :
constante 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 de este código es que cada iteración del bucle interno on 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 canalizar tal como está escrito actualmente.
Una aplicación del modelo de politopo, con la transformación afín 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 se puede ejecutar 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 . (Sin embargo, cada iteración del bucle externo depende de iteraciones anteriores).
src, antes de la distorsión del bucle . El punto rojo corresponde a src[1][0]; el punto rosa corresponde a src[2][2].El siguiente código C implementa una forma de tramado de distribución de errores similar al tramado de Floyd-Steinberg , pero modificado por razones pedagógicas. La matriz bidimensional srccontiene hfilas de wpí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 dstcontendrá solo píxeles con valor 0 o 255. Durante el cálculo, el error de tramado de cada píxel se recopila añadiéndolo de nuevo a la srcmatriz. (Observe que srcy dstse leen y escriben durante el cálculo; srcno es de solo lectura ni dstde solo escritura).
Cada iteración del bucle interno modifica los valores de src[i][j]en 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 de 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.
src, después de la distorsión del bucle. Los elementos de la matriz se procesarán en el orden gris, rojo, verde, azul, amarillo...Al realizar la transformación afín en el diagrama de dependencia original obtenemos un nuevo diagrama, que se muestra en la siguiente imagen. Luego podemos reescribir el código para que se repita en y en lugar de y , obteniendo la siguiente rutina "sesgada".ptij
