पॉलीटॉप मॉडल: Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
{{for|physical models of polyhedra|बहुफलकीय प्रारूप}}
बहुफलकीय प्रारूप, किसी प्रोग्राम में बड़ी संख्याओ वाली संक्रियाओ के लिए एक गणितीय ढांचा है जिन्हे स्पष्ट रूप से गणना करने के लिए बहुत बड़े सघन प्रतिनिधित्व की आवश्यकता होती है। नेस्टेड लूप प्रोग्राम विशिष्ट प्रयोगों के लिए उपयोगी हैं परंतु इसके लिए ये एकमात्र उदाहरण नहीं है और इस प्रारूप का सबसे सरल उपयोग प्रोग्राम अनुकूलन में लूप नेस्ट अनुकूलन के लिए है। बहुफलकीय विधि नेस्टेड लूप के भीतर प्रत्येक लूप पुनरावृत्ति को बहुकोणीय आकृति नामक गणितीय वस्तुओं के अंदर नेस्टेड बिंदुओं के रूप में मानती है, और सजातीय रूपान्तरण या अधिक सामान्य गैर- सजातीय रूपान्तरण करती है। जैसे कि बहुतलों पर टाइलिंग, और फिर रूपांतरित बहुतलों को समतुल्य बहुफलनों में परिवर्तित करती है, परंतु अनुकूलित, बहुफलकीय प्रारूप स्कैनिंग के माध्यम से लूप नेस्ट करता है।     
 
बहुफलकीय प्रारूप, किसी प्रोग्राम में बड़ी संख्याओ वाली संक्रियाओ के लिए  एक गणितीय ढांचा है जिन्हे  स्पष्ट रूप से गणना करने के लिए बहुत बड़े सघन प्रतिनिधित्व की आवश्यकता होती है। नेस्टेड लूप प्रोग्राम विशिष्ट प्रयोगों के लिए उपयोगी हैं परंतु इसके लिए ये एकमात्र उदाहरण नहीं है और इस  प्रारूप का सबसे सरल उपयोग प्रोग्राम अनुकूलन में लूप नेस्ट अनुकूलन के लिए है। बहुफलकीय विधि नेस्टेड लूप के भीतर प्रत्येक लूप पुनरावृत्ति को बहुकोणीय आकृति नामक गणितीय वस्तुओं के अंदर नेस्टेड बिंदुओं के रूप में मानती है, और सजातीय रूपान्तरण या अधिक सामान्य गैर- सजातीय रूपान्तरण करती है। जैसे कि बहुतलों पर टाइलिंग, और फिर रूपांतरित बहुतलों को समतुल्य बहुफलनों में परिवर्तित करती है, परंतु  अनुकूलित, बहुफलकीय प्रारूप स्कैनिंग के माध्यम से लूप नेस्ट करता है।     


== सरल उदाहरण ==
== सरल उदाहरण ==
Line 12: Line 10:
   
   
  for (i = 1; i < n; i++) {
  for (i = 1; i < n; i++) {
  for (j = 1; j < (i + 2) && j < n; j++) {
  for (j = 1; j < (i + 2) && j < n; j++) {


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


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


a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];
a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];
Line 26: Line 24:
== विस्तृत उदाहरण ==
== विस्तृत उदाहरण ==


[[File:Polytope model unskewed.svg|thumb|right|लूप तिरछा करने से पहले, src की निर्भरता। लाल बिंदु src[1][0]; गुलाबी बिंदु src[2] से मेल खाता है.]]निम्नलिखित सी कोड फ़्लॉइड-स्टाइनबर्ग डाइथरिंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को अनुबंधित  करता है, परंतु शैक्षणिक कारणों से इन्हे संशोधित किया गया है।  द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। रूटीन समाप्त होने के उपरांत, निर्गत त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल उपस्थित होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के समय,  src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र पढ़ने के लिए नहीं है, और dst मात्र लिखने के लिए नहीं है।
[[File:Polytope model unskewed.svg|thumb|right|लूप तिरछा करने से पहले, src की निर्भरता। लाल बिंदु src[1][0]; गुलाबी बिंदु src[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] के मानों को संशोधित करता है। [j-1]] वाली समान निर्भरताएँ dst[i][j] पर लागू होती हैं।
आंतरिक लूप का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। [j-1]] वाली समान निर्भरताएँ dst[i][j] पर लागू होती हैं।
Line 57: Line 55:
|}
|}


[[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>, निम्नलिखित तिरछी रूटीन प्राप्त करते है ।
[[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 89: Line 87:


== यह भी देखें ==
== यह भी देखें ==
* बहुफलकीय प्रारूप   का समर्थन करने वाले ढांचे
* बहुफलकीय प्रारूप का समर्थन करने वाले ढांचे
* लूप नीड अनुकूलीकरण
* लूप नीड अनुकूलीकरण
*  [[लूप अनुकूलन]]
*  [[लूप अनुकूलन]]
Line 97: Line 95:
== बाहरी लिंक और संदर्भ ==
== बाहरी लिंक और संदर्भ ==
*[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 बहुफलकीय प्रारूप   में कोड जनरेशन] (1998)। मार्टिन ग्रीब्ल, क्रिश्चियन लेंगौएर और सबाइन वेटज़ेल
*[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] फ्रेमवर्क।
श्रेणी:संकलक अनुकूलन
श्रेणी:सूडोकोड के उदाहरण वाले लेख
श्रेणी:उदाहरण सी कोड वाले लेख
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 18/02/2023]]
[[Category:Created On 18/02/2023]]

Revision as of 10:51, 23 March 2023

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

सरल उदाहरण

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

 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], पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या पाइपलाइन नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।

सजातीय परिवर्तन के साथ बहुतलीय प्रारूप का एक अनुप्रयोग और सीमाओं में उपयुक्त परिवर्तन, ऊपर नेस्टेड लूप को रूपांतरित कर देगा

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

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

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

लूप तिरछा करने से पहले, src की निर्भरता। लाल बिंदु src[1][0]; गुलाबी बिंदु src[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] के मानों को संशोधित करता है। [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 और 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;
         }
     }
 }


यह भी देखें

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