modelo de politopo
El modelo poliédrico (también llamado método de 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 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 celosía dentro de objetos matemáticos llamados poliedros , realiza transformaciones afines o transformaciones no afines más generales, como mosaicoen los politopos, y luego convierte los politopos transformados en nidos de bucle equivalentes, pero optimizados (según el objetivo de optimización objetivo), a través del escaneo de poliedros.
El problema esencial con este código es que cada iteración del ciclo 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 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 anteriores en:
En este caso, ninguna iteración del ciclo interno depende de los resultados de la iteración anterior; todo el bucle interno se puede ejecutar en paralelo. (Sin embargo, cada iteración del bucle externo depende de las iteraciones anteriores).
El siguiente código C implementa una forma de difuminado de distribución de errores similar al difuminado 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 valor 255. Durante el cálculo, el error de interpolación de cada píxel se recopila al agregarlo nuevamente a la srcmatriz. (Observe que srcy dstson de lectura y escritura durante el cálculo; srcno son de solo lectura y dstno son 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 del 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, antes de la desviación del bucle . El punto rojo corresponde a src[1][0]; el punto rosa corresponde a src[2][2].