مدل پولی‌توپ

مثال زیر که با زبان C برنامه‌نویسی شده‌است را ملاجظه کنید.

  const int n = 100;
  int i, j, a[n][n];
  for (i = 1; i < n; i++) {
    for (j = 1; j < (i + 2) && j < n; j++) {
      a[i][j] = a[i - 1][j] + a[i][j - 1];
    }
  }

مسأله‌ی اصلی این کد در این است که در هر تکرار حلقه‌ی داخلی، محاسبه‌ی [a[i][j به نتیجه‌ی [a[i][j - 1 در تکرار قبلی حلقه وابسته است. نتیجتاً این کد به همان صورتی که هست قابل موازی‌سازی یا پایپ‌لاین شدن نیست.

یکی از کاربردهای مدل پولی‌توپ با استفاده از تبدیل آفینی ${\displaystyle (i^{\prime },j^{\prime })=(i+j,j)}$

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

تبدیل می‌کند. در این حالت، هیچ یک از تکرارهای حلقه‌ی داخلی وابسته به نتیجه‌ی تکرار قیبس نیست. در نتیجه کل حلقه‌ی داخلی می‌تواند به صورت موازی اجرا شود. (با این وجود، هر تکرار حلقه‌ی خارجی وابسته به تکرار قبلی است.)

کد ‌C ذیل، نوعی از تفکیک توزیع خطا مشابه با تفکیک فلوید-اشتاینبرگ است که به دلایل آموزشی تغییر داده شده‌است. آرایه‌ی دو بعدی src شامل h ردیف است که هر یک w پیکسل دارند. هر کدام از این پیکسل‌ها شامل یک مقدار بین صفر تا ۲۵۵ در مقیاس خاکستری است. بعد از پایان روتین آرایه‌ی خروجی dst شامل پیکسل‌هایی است که یا مقدار صفر دارند و یا ۲۵۵. در حین اجرای محاسبات، تفکیک خطای هر پیکسل با دوباره اضافه شدن به آرایه‌ی src جمع‌آوری شده‌است. (به این نکته دقت کنید که در طی محاسبات، هر دو آرایه‌ی src و dst هم‌زمان نوشته و خوانده می‌شوند. src فقط قابل خواندن نیست و dst هم فقط قابل نوشتن نیست.)

در هر تکرار حلقه‌ی داخلی مقدار [src[i][j، بر اساس مقادیر [src[i-1][j و [src[i+1][j-1 و [src[i][j-1 تغییر می‌کند. (وابستگی‌های مشابه بر [dst[i][j اعمال می‌شود. می‌توان برای اهداف انحراف حلقه، به [src[i][j و [dst[i][j به چشم یک عنصر نگاه کرد. ) وابستگی‌های [src[i][j در نمودار سمت راست قابل مشاهده است.

#define ERR(x, y) (dst[x][y] - src[x][y])

void dither(unsigned char** src, unsigned char** dst, int w, int h)
{
    int i, j;
    for (j = 0; j < h; ++j) {
        for (i = 0; i < w; ++i) {
            int v = src[i][j];
            if (i > 0)
                v -= ERR(i - 1, j) / 2;
            if (j > 0) {
                v -= ERR(i, j - 1) / 4;
                if (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;
        }
    }
}

نتیجه‌ی اجرای تبدیل آفینی ${\displaystyle (p,t)=(i,2j+i)}$

 void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h)  
 {
     int t, p;
     for (t = 0; t < (w + (2 * h)); ++t) {
         int pmin = max(t % 2, t - (2 * h) + 2);
         int pmax = min(t, w - 1);
         for (p = pmin; p <= pmax; p += 2) {
             int i = p;
             int j = (t - p) / 2;
             int v = src[i][j];
             if (i > 0)
               v -= ERR(i - 1, j) / 2;
             if (j > 0)
               v -= ERR(i, j - 1) / 4;
             if (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;
         }
     }
 }

• متد پولی‌توپ پایه ای، مارتین گریبل
• تولید کد در مدل پولی‌توپ، مارتین گریبل، کریستین لنگیر، سبین وتزل
• مجموعه کامپایلر پولی‌هدرال
• کامپایلر پولی‌هدرال