पॉलीटॉप मॉडल: Difference between revisions
(Created page with "{{for|physical models of polyhedra|Polyhedron model}} पॉलीहेड्रल मॉडल (जिसे पॉलीटॉप विधि भी कहा जात...") |
No edit summary |
||
Line 1: | Line 1: | ||
{{for|physical models of polyhedra| | {{for|physical models of polyhedra|बहुफलकीय प्रारूप}} | ||
बहुफलकीय प्रारूप उन प्रोग्रामों के लिए एक गणितीय ढांचा है जो बड़ी संख्या में संचालन करते हैं स्पष्ट रूप से गणना करने के लिए बहुत बड़े जिससे सुसम्बद्ध प्रतिनिधित्व की आवश्यकता होती है। नीड़ित प्रविष्ट पाश कार्यक्रमों मे विशिष्ट हैं, और प्रारूप का सबसे सरल उपयोग कार्यक्रमों के अनुकूलीकरण में पाश नीड अनुकूलीकरण के लिए है। पॉलीहेड्रल विधि नीड़ित प्रविष्ट पाश के भीतर प्रत्येक पाश पुनरावृत्ति को बहुफलकीय नामक गणितीय वस्तुओं के अंदर जाली बिंदुओं के रूप में मानती है, [[affine परिवर्तन|सजातीय परिवर्तन]] या अधिक सामान्य गैर- सजातीय रूपांतरित करती है जैसे कि बहुफलकीय पर [[लूप टाइलिंग|पाश टाइलिंग]], और फिर रूपांतरित बहुतलीय को समतुल्य में परिवर्तित करती है, लेकिन बहुफलकीय रेखाचित्रण के माध्यम से पाश नीड अनुकूलित लक्षित अनुकूलन लक्ष्य पर निर्भर करता है | |||
== सरल उदाहरण == | == सरल उदाहरण == | ||
Line 19: | Line 20: | ||
इस कोड के साथ आवश्यक समस्या यह है कि आंतरिक पाश के प्रत्येक पुनरावृत्ति पर <code>a[i][j]</code> आवश्यकता है कि पिछले पुनरावृत्ति के परिणाम, <code>a[i][j - 1]</code>, पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या [[पाइपलाइन (कंप्यूटिंग)]] नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है। | इस कोड के साथ आवश्यक समस्या यह है कि आंतरिक पाश के प्रत्येक पुनरावृत्ति पर <code>a[i][j]</code> आवश्यकता है कि पिछले पुनरावृत्ति के परिणाम, <code>a[i][j - 1]</code>, पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या [[पाइपलाइन (कंप्यूटिंग)]] नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है। | ||
एफ़िन परिवर्तन के साथ | एफ़िन परिवर्तन के साथ बहुफलकीय प्रारूप का एक अनुप्रयोग <math>(i',\, j') = (i+j,\, j)</math> और सीमाओं में उपयुक्त परिवर्तन, नेस्टेड छोरों को ऊपर में बदल देगा: | ||
<वाक्यविन्यास प्रकाश लैंग = सी> | <वाक्यविन्यास प्रकाश लैंग = सी> | ||
Line 25: | Line 26: | ||
</वाक्यविन्यास हाइलाइट> | </वाक्यविन्यास हाइलाइट> | ||
इस स्थिति में, आंतरिक | इस स्थिति में, आंतरिक पाश का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक पाश को समानांतर में निष्पादित किया जा सकता है। (हालांकि, बाहरी पाश का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है।) | ||
== विस्तृत उदाहरण == | == विस्तृत उदाहरण == | ||
[[File:Polytope model unskewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, | [[File:Polytope model unskewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, पाश अनुकूलीकरण से पहले # कॉमन पाश रूपांतरण। लाल बिंदु से मेल खाता है <code>src[1][0]</code>; गुलाबी बिंदु से मेल खाता है <code>src[2][2]</code>.]]निम्नलिखित सी (प्रोग्रामिंग भाषा) कोड फ़्लॉइड-स्टाइनबर्ग [[तड़पना]]िंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों से संशोधित किया गया है। द्वि-आयामी सरणी <code>src</code> रोकना <code>h</code> की पंक्तियों <code>w</code> पिक्सेल, प्रत्येक पिक्सेल का ग्रे[[स्केल]] मान 0 और 255 सहित के बीच होता है। दिनचर्या समाप्त होने के बाद, आउटपुट array <code>dst</code> मान 0 या मान 255 के साथ केवल पिक्सेल शामिल होंगे। गणना के दौरान, प्रत्येक पिक्सेल की डाइथरिंग त्रुटि को वापस जोड़कर एकत्र किया जाता है <code>src</code> सरणी। (नोटिस जो <code>src</code> और <code>dst</code> गणना के दौरान दोनों पढ़े और लिखे जाते हैं; <code>src</code> केवल-पढ़ने के लिए नहीं है, और <code>dst</code> केवल लिखने के लिए नहीं है।) | ||
आंतरिक पाश का प्रत्येक पुनरावृत्ति मूल्यों को संशोधित करता है <code>src[i][j]</code> के मूल्यों पर आधारित है <code>src[i-1][j]</code>, <code>src[i][j-1]</code>, और <code>src[i+1][j-1]</code>. (समान निर्भरताएं लागू होती हैं <code>dst[i][j]</code>. | आंतरिक पाश का प्रत्येक पुनरावृत्ति मूल्यों को संशोधित करता है <code>src[i][j]</code> के मूल्यों पर आधारित है <code>src[i-1][j]</code>, <code>src[i][j-1]</code>, और <code>src[i+1][j-1]</code>. (समान निर्भरताएं लागू होती हैं <code>dst[i][j]</code>. पाश अनुकूलीकरण # कॉमन पाश रूपांतरण के प्रयोजनों के लिए, हम सोच सकते हैं <code>src[i][j]</code> और <code>dst[i][j]</code> एक ही तत्व के रूप में।) हम निर्भरताओं को चित्रित कर सकते हैं <code>src[i][j]</code> ग्राफिक रूप से, जैसा कि दाईं ओर आरेख में है। | ||
<!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ --> | <!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ --> | ||
Line 60: | Line 61: | ||
|} | |} | ||
[[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, पाश तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।]]एफ़िन परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को | [[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, पाश तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।]]एफ़िन परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को पाश ऑन करने के लिए फिर से लिख सकते हैं <code>p</code> और <code>t</code> के बजाय <code>i</code> और <code>j</code>, निम्नलिखित तिरछी दिनचर्या प्राप्त करना। | ||
<!-- Please don't break this code. Test before committing! --> | <!-- Please don't break this code. Test before committing! --> | ||
Line 92: | Line 93: | ||
== यह भी देखें == | == यह भी देखें == | ||
* बहुफलकीय | * बहुफलकीय प्रारूप का समर्थन करने वाले ढांचे | ||
* | * पाश नीड अनुकूलीकरण | ||
* [[लूप अनुकूलन]] | * [[लूप अनुकूलन|पाश अनुकूलन]] | ||
* [[लूप अनोलिंग]] | * [[लूप अनोलिंग|पाश अनोलिंग]] | ||
* | * पाश टाइलिंग | ||
== बाहरी लिंक और संदर्भ == | == बाहरी लिंक और संदर्भ == | ||
*[https://www.infosun.fim.uni-passau.de/cl/loopo/doc/loopo_doc/node3.html बुनियादी | *[https://www.infosun.fim.uni-passau.de/cl/loopo/doc/loopo_doc/node3.html बुनियादी बहुफलकीय विधि], मार्टिन ग्रिब्ल द्वारा ट्यूटोरियल जिसमें उपरोक्त स्यूडोकोड उदाहरण के आरेख शामिल हैं | ||
*[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5675 | *[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5675 बहुफलकीय प्रारूप में कोड जनरेशन] (1998)। मार्टिन ग्रीब्ल, क्रिश्चियन लेंगौएर और सबाइन वेटज़ेल | ||
*[http://www.cloog.org/ सीएलओओजी पॉलीहेड्रल कोड जेनरेटर] | *[http://www.cloog.org/ सीएलओओजी पॉलीहेड्रल कोड जेनरेटर] | ||
*[http://www.chunchen.info/omega CodeGen+: Z-पॉलीहेड्रा स्कैनिंग]{{dead link|date=March 2018 |bot=InternetArchiveBot |fix-attempted=yes }} | *[http://www.chunchen.info/omega CodeGen+: Z-पॉलीहेड्रा स्कैनिंग]{{dead link|date=March 2018 |bot=InternetArchiveBot |fix-attempted=yes }} | ||
*[http://web.cs.ucla.edu/~pouchet/software/pocc/ PoCC: बहुफलकीय संकलक संग्रह] | *[http://web.cs.ucla.edu/~pouchet/software/pocc/ PoCC: बहुफलकीय संकलक संग्रह] | ||
*[http://pluto-compiler.sourceforge.net/ PLUTO - affine | *[http://pluto-compiler.sourceforge.net/ PLUTO - affine पाश नीड के लिए एक स्वचालित पैरेललाइज़र और स्थानीयता अनुकूलक] | ||
**{{Cite book|last1=Bondhugula|first1=Uday|last2=Hartono|first2=Albert|last3=Ramanujam|first3=J.|last4=Sadayappan|first4=P.|date=2008-01-01|title=एक व्यावहारिक स्वचालित पॉलीहेड्रल समानांतर और स्थानीयता अनुकूलक|journal=Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation|series=PLDI '08|location=New York, NY, USA|publisher=ACM|pages=101–113|doi=10.1145/1375581.1375595|isbn=9781595938602|s2cid=7086982}} | **{{Cite book|last1=Bondhugula|first1=Uday|last2=Hartono|first2=Albert|last3=Ramanujam|first3=J.|last4=Sadayappan|first4=P.|date=2008-01-01|title=एक व्यावहारिक स्वचालित पॉलीहेड्रल समानांतर और स्थानीयता अनुकूलक|journal=Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation|series=PLDI '08|location=New York, NY, USA|publisher=ACM|pages=101–113|doi=10.1145/1375581.1375595|isbn=9781595938602|s2cid=7086982}} | ||
*[http://polyhedral.info/ polyhedral.info] - एक वेबसाइट जो बहुफलकीय संकलन के बारे में जानकारी एकत्र करती है | *[http://polyhedral.info/ polyhedral.info] - एक वेबसाइट जो बहुफलकीय संकलन के बारे में जानकारी एकत्र करती है | ||
*[http://polly.llvm.org/ पोली - हाई-लेवल | *[http://polly.llvm.org/ पोली - हाई-लेवल पाश और डेटा-लोकलिटी ऑप्टिमाइजेशन के लिए एलएलवीएम फ्रेमवर्क] | ||
* एमआईटी [http://tiramisu-compiler.org/ Tiramisu Polyhedral] फ्रेमवर्क। | * एमआईटी [http://tiramisu-compiler.org/ Tiramisu Polyhedral] फ्रेमवर्क। | ||
Revision as of 13:43, 17 March 2023
बहुफलकीय प्रारूप उन प्रोग्रामों के लिए एक गणितीय ढांचा है जो बड़ी संख्या में संचालन करते हैं स्पष्ट रूप से गणना करने के लिए बहुत बड़े जिससे सुसम्बद्ध प्रतिनिधित्व की आवश्यकता होती है। नीड़ित प्रविष्ट पाश कार्यक्रमों मे विशिष्ट हैं, और प्रारूप का सबसे सरल उपयोग कार्यक्रमों के अनुकूलीकरण में पाश नीड अनुकूलीकरण के लिए है। पॉलीहेड्रल विधि नीड़ित प्रविष्ट पाश के भीतर प्रत्येक पाश पुनरावृत्ति को बहुफलकीय नामक गणितीय वस्तुओं के अंदर जाली बिंदुओं के रूप में मानती है, सजातीय परिवर्तन या अधिक सामान्य गैर- सजातीय रूपांतरित करती है जैसे कि बहुफलकीय पर पाश टाइलिंग, और फिर रूपांतरित बहुतलीय को समतुल्य में परिवर्तित करती है, लेकिन बहुफलकीय रेखाचित्रण के माध्यम से पाश नीड अनुकूलित लक्षित अनुकूलन लक्ष्य पर निर्भर करता है
सरल उदाहरण
सी (प्रोग्रामिंग भाषा) में लिखे गए निम्नलिखित उदाहरण पर विचार करें:
<वाक्यविन्यास प्रकाश लैंग = सी> कॉन्स्टेंट इंट एन = 100; इंट आई, जे, ए [एन] [एन];
के लिए (i = 1; i <n; i++) {
के लिए (जे = 1; जे <(आई + 2) && जे <एन; जे ++) { ए [आई] [जे] = ए [आई - 1] [जे] + ए [आई] [जे - 1]; }
} </वाक्यविन्यास हाइलाइट>
इस कोड के साथ आवश्यक समस्या यह है कि आंतरिक पाश के प्रत्येक पुनरावृत्ति पर a[i][j]
आवश्यकता है कि पिछले पुनरावृत्ति के परिणाम, a[i][j - 1]
, पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या पाइपलाइन (कंप्यूटिंग) नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।
एफ़िन परिवर्तन के साथ बहुफलकीय प्रारूप का एक अनुप्रयोग और सीमाओं में उपयुक्त परिवर्तन, नेस्टेड छोरों को ऊपर में बदल देगा:
<वाक्यविन्यास प्रकाश लैंग = सी> ए [आई - जे] [जे] = ए [आई - जे - 1] [जे] + ए [आई - जे] [जे - 1]; </वाक्यविन्यास हाइलाइट>
इस स्थिति में, आंतरिक पाश का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक पाश को समानांतर में निष्पादित किया जा सकता है। (हालांकि, बाहरी पाश का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है।)
विस्तृत उदाहरण
निम्नलिखित सी (प्रोग्रामिंग भाषा) कोड फ़्लॉइड-स्टाइनबर्ग तड़पनािंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों से संशोधित किया गया है। द्वि-आयामी सरणी 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;
}
}
}
|
एफ़िन परिवर्तन करना मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को पाश ऑन करने के लिए फिर से लिख सकते हैं 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-पॉलीहेड्रा स्कैनिंग[permanent dead link]
- 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)
- Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (2008-01-01). एक व्यावहारिक स्वचालित पॉलीहेड्रल समानांतर और स्थानीयता अनुकूलक. pp. 101–113. doi:10.1145/1375581.1375595. ISBN 9781595938602. S2CID 7086982.
- polyhedral.info - एक वेबसाइट जो बहुफलकीय संकलन के बारे में जानकारी एकत्र करती है
- पोली - हाई-लेवल पाश और डेटा-लोकलिटी ऑप्टिमाइजेशन के लिए एलएलवीएम फ्रेमवर्क
- एमआईटी Tiramisu Polyhedral फ्रेमवर्क।
श्रेणी:संकलक अनुकूलन श्रेणी:सूडोकोड के उदाहरण वाले लेख श्रेणी:उदाहरण सी कोड वाले लेख