पॉलीटॉप मॉडल

पॉलीटॉप मॉडल जिसे बहुफलकीय प्रारूप भी कहा जाता है, एक गणितीय ढांचा है, जिन्हे गणना करने के लिए स्पष्ट रूप से अत्यधिक सघन प्रतिनिधित्व की आवश्यकता होती है। नेस्टेड लूप प्रोग्राम विशिष्ट प्रयोगों के लिए उपयोगी हैं, परंतु इसके लिए ये एकमात्र उदाहरण नहीं है, और इस प्रारूप का सबसे सरल उपयोग प्रोग्राम अनुकूलन में लूप नेस्ट अनुकूलन के लिए है। बहुफलकीय विधि नेस्टेड लूप के भीतर प्रत्येक लूप पुनरावृत्ति को बहुकोणीय आकृति नामक गणितीय वस्तुओं के अंदर नेस्टेड बिंदुओं के रूप में प्रदर्शित करती है, और सजातीय रूपान्तरण या अधिक सामान्य, गैर- सजातीय रूपान्तरण करती है। जैसे कि बहुतलों पर टाइलिंग, और तत्पश्चात रूपांतरित बहुतलों को समतुल्य बहुफलनों में परिवर्तित करती है, परंतु अनुकूलित, बहुफलकीय प्रारूप स्कैनिंग के माध्यम से लूप नेस्ट करता है।

सरल उदाहरण

सी प्रोग्रामिंग भाषा में लिखे गए निम्नलिखित उदाहरण पर विचार करें:

 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];
 

इस कूट के साथ आवश्यक समस्या यह है कि [i] [j] पर आंतरिक लूप के प्रत्येक पुनरावृत्ति के लिए आवश्यक है, कि पिछले पुनरावृत्ति का परिणाम, [i] [j - 1], पहले से ही उपलब्ध हो। इसलिए, इस कूट को समानांतर या पाइपलाइन नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।

सजातीय परिवर्तन के साथ बहुतलीय प्रारूप का एक अनुप्रयोग $(i',\,j')=(i+j,\,j)$ और सीमाओं में उपयुक्त परिवर्तन, ऊपर नेस्टेड लूप को रूपांतरित कर देगा-

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

इस स्थिति में, आंतरिक लूप का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक लूप को समानांतर में निष्पादित किया जा सकता है, यद्यपि बाहरी लूप का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है

विस्तृत उदाहरण

लूप तिरछा करने से पहले, एसआरसी की निर्भरता। लाल बिंदु एसआरसी[1][0]; गुलाबी बिंदु एसआरसी[2] से मेल खाता है.

निम्नलिखित सी कूट फ़्लॉइड-स्टाइनबर्ग डाइथरिंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को अनुबंधित करता है, परंतु शैक्षणिक कारणों से इन्हे संशोधित किया गया है। द्वि-आयामी सरणी एसआरसी में डब्ल्यू पिक्सेल की एच पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। रूटीन समाप्त होने के उपरांत, निर्गत त्रुटि डीएसटीमें मात्र 0 मान या 255 मान वाले पिक्सेल उपस्थित होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस एसआरसी सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के समय, एसआरसी और डीएसटीदोनों पढ़े और लिखे जाते हैं; एसआरसी मात्र पढ़ने के लिए नहीं है, और डीएसटीमात्र लिखने के लिए नहीं है।

आंतरिक लूप का प्रत्येक पुनरावृत्ति एसआरसी[i][j] के मानों के आधार पर एसआरसी [i-1] [j], एसआरसी [i] [j-1], और एसआरसी[i+1] के मानों को संशोधित करता है। [j-1]] वाली समान निर्भरताएँ डीएसटी [i] [j] पर लागू होती हैं।

लूप विषमन के प्रयोजनों के लिए, हम एसआरसी[i][j] और डीएसटी [i] [j] को एक ही तत्व के रूप में मान सकते हैं। हम उदाहरण दे सकते हैं एसआरसी[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; } } }

की निर्भरताएँ एसआरसी,लूप तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला क्रम में संसाधित किया जाएगा।

सजातीय परिवर्तन करना $(p,\,t)=(i,\,2j+i)$ मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कूट को लूप प्रारंभ करने के लिए पुनः लिख सकते हैं 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; } } }

यह भी देखें

• बहुफलकीय प्रारूप का समर्थन करने वाले ढांचे
• लूप नीड अनुकूलीकरण
• लूप अनुकूलन
• लूप अनोलिंग
• लूप टाइलिंग

बाहरी लिंक और संदर्भ

• बुनियादी बहुफलकीय विधि, मार्टिन ग्रिब्ल द्वारा ट्यूटोरियल जिसमें उपरोक्त स्यूडोकूट उदाहरण के आरेख शामिल हैं
• बहुफलकीय प्रारूप में कूट जनरेशन (1998)। मार्टिन ग्रीब्ल, क्रिश्चियन लेंगौएर और सबाइन वेटज़ेल
• सीएलओओजी बहुफलकीय कूट जेनरेटर
• CodeGen+: Z-पॉलीहेड्रा स्कैनिंग
• PoCC: बहुफलकीय संकलक संग्रह
• PLUTO - affine लूप नीड के लिए एक स्वचालित पैरेललाइज़र और स्थानीयता अनुकूलक
  • Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (2008-01-01). एक व्यावहारिक स्वचालित पॉलीहेड्रल समानांतर और स्थानीयता अनुकूलक. pp. 101–113. doi:10.1145/1375581.1375595. ISBN 9781595938602. S2CID 7086982. {{cite book}}: |journal= ignored (help)
• polyhedral.info - एक वेबसाइट जो बहुफलकीय संकलन के बारे में जानकारी एकत्र करती है
• पोली - हाई-लेवल लूप और डेटा-लोकलिटी ऑप्टिमाइजेशन के लिए एलएलवीएम फ्रेमवर्क
• एमआईटी Tiramisu Polyhedral फ्रेमवर्क।