पॉलीटॉप मॉडल

For physical models of polyhedra, see Polyhedron model.

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

सरल उदाहरण

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

<वाक्यविन्यास प्रकाश लैंग = सी> कॉन्स्टेंट इंट एन = 100; इंट आई, जे, ए [एन] [एन];

के लिए (i = 1; i <n; i++) {

 के लिए (जे = 1; जे <(आई + 2) && जे <एन; जे ++) {
   ए [आई] [जे] = ए [आई - 1] [जे] + ए [आई] [जे - 1];
 }

} </वाक्यविन्यास हाइलाइट>

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

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

<वाक्यविन्यास प्रकाश लैंग = सी> ए [आई - जे] [जे] = ए [आई - जे - 1] [जे] + ए [आई - जे] [जे - 1]; </वाक्यविन्यास हाइलाइट>

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

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

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

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

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

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