पॉलीटॉप मॉडल

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

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

सरल उदाहरण

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

<वाक्यविन्यास प्रकाश लैंग = सी> कॉन्स्टेंट इंट एन = 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 फ्रेमवर्क।

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