مدل پولی‌توپ
مدل پولی‌هدرال -که به آن روش پولی‌توپ نیز گفته می‌شود- یک چهارچوب ریاضی برای اجرای تعداد بالای عملیات است. این تعداد باید به اندازه‌ای زیاد باشد که نتوان آن را صراحتاً عددگذاری کرد و در نتیجه یک نمایش فشرده لازم داشته باشد. برنامه‌های شامل حلقه‌های تو در تو تنها یکی از مثال‌های معمول این روش هستند. هم‌چنین متداول‌ترین کاربرد این مدل برای بهینه‌سازی حلقه‌های تو در تو، در برنامه‌ی بهینه‌سازی است. روش پولی‌هدرال با هر تکرار حلقه، در حلقه‌های تو در تو به عنوان نقاط مشبک داخل اشیای ریاضی به نام پولی‌هدرا، تبدیلات آفینی یا به صورت عمومی‌تر تبدیلات غیرآفینی مانند کاشی کاری را روی پولی‌هدرا اعمال می‌کند. سپس این پولی‌توپ‌های تبدیل شده را از طریق پویش پولی‌هدرا به شکل حلقه‌های تو در توی معادل، اما بهینه (وابسته به هدف بهینه‌سازی تعیین شده ) در می‌آورد.
نمونه‌ی ساده[ویرایش]
مثال زیر که با زبان 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 در تکرار قبلی حلقه وابسته است. نتیجتاً این کد به همان صورتی که هست قابل موازی‌سازی یا پایپ‌لاین شدن نیست.
یکی از کاربردهای مدل پولی‌توپ با استفاده از تبدیل آفینی و ایجاد تغییرات مناسب در مرزها این است که حلقه‌های تو در توی کد بالا را به:
a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];
تبدیل می‌کند. در این حالت، هیچ یک از تکرارهای حلقه‌ی داخلی وابسته به نتیجه‌ی تکرار قیبس نیست. در نتیجه کل حلقه‌ی داخلی می‌تواند به صورت موازی اجرا شود. (با این وجود، هر تکرار حلقه‌ی خارجی وابسته به تکرار قبلی است.)
نمونه‌ی دقیق[ویرایش]
src، پیش از انحراف حلقه. نقطه‌ی قرمز بیانگر src[1][0] و نقطه‌ی صورتی بیانگر src[2][2] است.کد 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;
}
}
}
|
src، پس از انحراف حلقه. از میان عنصرهای آرایه، به ترتیب اول طوسی، سپس قرمز، سبز، آبی، زرد و ... پردازش می‌شوند.نتیجه‌ی اجرای تبدیل آفینی بر نمودار وابستگی‌های آغازین، یک نمودار جدید است که در شکل بعدی نمایان است. با بازنویسی حلقه بر p و t به جای i و j، روتین منحرف شده زیر به دست می‌آید.
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;
}
}
}
|
منابع[ویرایش]
- متد پولی‌توپ پایه ای، مارتین گریبل
- تولید کد در مدل پولی‌توپ، مارتین گریبل، کریستین لنگیر، سبین وتزل
- مجموعه کامپایلر پولی‌هدرال
- کامپایلر پولی‌هدرال