पॉलीटॉप मॉडल

For physical models of polyhedra, see बहुफलकीय प्रारूप.

बहुफलकीय प्रारूप (जिसे पॉलीटॉप विधि भी कहा जाता है) प्रोग्राम के लिए एक गणितीय ढांचा है जो बड़ी संख्या में संचालन करता है - स्पष्ट रूप से गणना करने के लिए बहुत बड़े सघन प्रतिनिधित्व की आवश्यकता होती है।

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

सरल उदाहरण

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

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

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

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

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

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

आंतरिक पाश का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। जे -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,\,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 फ्रेमवर्क।

श्रेणी:संकलक अनुकूलन श्रेणी:सूडोकोड के उदाहरण वाले लेख श्रेणी:उदाहरण सी कोड वाले लेख