लूप नेस्ट अनुकूलन: Difference between revisions

From Vigyanwiki
No edit summary
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में और विशेष रूप से [[ संकलक |संकलक]] डिज़ाइन में, लूप नेस्ट ऑप्टिमाइज़ेशन (एलएनओ) अनुकूलन तकनीक है जो संदर्भ अनुकूलन या समानांतरकरण या लूप नेस्ट के किसी अन्य लूप ओवरहेड कटौती के उद्देश्य के लिए लूप परिवर्तनों का सेट लागू करती है। ([[ अंतर प्रविष्ट पाश | अंतर प्रविष्ट पाश]] तब होते हैं जब लूप दूसरे लूप के अंदर होता है।) शास्त्रीय उपयोग कुछ सामान्य रैखिक बीजगणित [[कलन विधि]] के लिए कैश पुन: उपयोग के कारण मेमोरी एक्सेस विलंबता या आवश्यक कैश बैंडविड्थ को कम करना है।
[[कंप्यूटर विज्ञान]] में और विशेष रूप से [[ संकलक |कंप्यूटर]] डिज़ाइन में, '''लूप नेस्ट ऑप्टिमाइज़ेशन''' (एलएनओ) अनुकूलन की ऐसी तकनीक है जो संदर्भिक रूप से अनुकूलन या समानांतरकरण या लूप नेस्ट के किसी अन्य लूप में ओवरहेड कटौती के उद्देश्य के लिए लूप में होने वाले परिवर्तनों का सेट लागू करती है। इस प्रकार[[ अंतर प्रविष्ट पाश | नेस्टेड लूप]] तब उत्पन्न होते हैं जब एक लूप किसी दूसरे लूप के अंदर होता है। मौलिक रूप से इसका उपयोग कुछ सामान्य रैखिक बीजगणित [[कलन विधि|एल्गोरिदम]] के लिए कैश को पुन: उपयोग के कारण मेमोरी एक्सेस में विलंबता या आवश्यक कैश की बैंडविड्थ को कम करना है।


इस अनुकूलन को उत्पन्न करने के लिए उपयोग की जाने वाली तकनीक को लूप टाइलिंग कहा जाता है,<ref name="MuchnickAssociates1997">{{cite book|author1=Steven Muchnick|author2=Muchnick and Associates|title=उन्नत कंपाइलर डिज़ाइन कार्यान्वयन|url=https://archive.org/details/advancedcompiler00much|url-access=registration|quote=खपरैल लगाना।|date=15 August 1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2}}</ref> इसे लूप ब्लॉकिंग के रूप में भी जाना जाता है<ref name="CardosoDiniz2011">{{cite book|author1=João M.P. Cardoso|author2=Pedro C. Diniz|title=पुन: कॉन्फ़िगर करने योग्य आर्किटेक्चर के लिए संकलन तकनीकें|url=https://books.google.com/books?id=4xwWNCiF9CgC&q=%22loop+tiling%22|date=2 April 2011|publisher=Springer Science & Business Media|isbn=978-0-387-09671-1}}</ref> या मेरा छीन लो और अदला-बदली करो।
इस अनुकूलन को उत्पन्न करने के लिए उपयोग की जाने वाली तकनीक को '''लूप टाइलिंग''' कहा जाता है,<ref name="MuchnickAssociates1997">{{cite book|author1=Steven Muchnick|author2=Muchnick and Associates|title=उन्नत कंपाइलर डिज़ाइन कार्यान्वयन|url=https://archive.org/details/advancedcompiler00much|url-access=registration|quote=खपरैल लगाना।|date=15 August 1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2}}</ref> इसे लूप ब्लॉकिंग के रूप में भी जाना जाता है<ref name="CardosoDiniz2011">{{cite book|author1=João M.P. Cardoso|author2=Pedro C. Diniz|title=पुन: कॉन्फ़िगर करने योग्य आर्किटेक्चर के लिए संकलन तकनीकें|url=https://books.google.com/books?id=4xwWNCiF9CgC&q=%22loop+tiling%22|date=2 April 2011|publisher=Springer Science & Business Media|isbn=978-0-387-09671-1}}</ref> या परिवर्तित करना हैं।


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


एक साधारण पाश
नेस्टेड लूप का उदाहरण
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
for (i=0; i<N; ++i) {
for (i=0; i<N; ++i) {
Line 20: Line 20:
}
}
</syntaxhighlight>
</syntaxhighlight>
कहाँ <code>min()</code> फ़ंक्शन है जो अपने न्यूनतम तर्क लौटाता है।
जहाँ <code>min()</code> फ़ंक्शन है जो अपने न्यूनतम तर्क लौटाता है।


== उदाहरण: मैट्रिक्स-वेक्टर गुणन ==
== उदाहरण: आव्यूह-सदिश गुणन ==


निम्नलिखित मैट्रिक्स वेक्टर गुणन का उदाहरण है। तीन सारणियाँ हैं, प्रत्येक में 100 तत्व हैं। कोड सरणियों को छोटे आकारों में विभाजित नहीं करता है।
निम्नलिखित आव्यूह सदिश गुणन का उदाहरण है। इसकी तीन सारणियाँ हैं, जिसमें प्रत्येक सारणी में 100 तत्व हैं। इस कोड में सूची को छोटे आकारों में विभाजित नहीं करता है।


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 36: Line 36:
   }
   }
</syntaxhighlight>
</syntaxhighlight>
2 * 2 ब्लॉक का उपयोग करके लूप टाइलिंग लागू करने के बाद, कोड इस तरह दिखता है:
2 * 2 ब्लॉक का उपयोग करके लूप टाइलिंग लागू करने के पश्चात कोड इस तरह दिखता है:


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 53: Line 53:
   }
   }
</syntaxhighlight>
</syntaxhighlight>
मूल लूप पुनरावृत्ति स्थान n बटा n है। सरणी a[i, j] का एक्सेस किया गया भाग भी n बटा n है। जब n बहुत बड़ा होता है और मशीन का कैश आकार बहुत छोटा होता है, तो लूप पुनरावृत्ति में एक्सेस किए गए सरणी तत्व (उदाहरण के लिए, <code>i = 1</code>, <code>j = 1 to n</code>) कैश लाइनों को पार कर सकता है, जिससे कैश मिस हो सकता है।
मूल लूप पुनरावृत्ति स्थान n बटा n है। इस सूची a[i, j] का एक्सेस किया गया भाग भी n बटा n है। जहाँ पर n बहुत बड़ा होता है, और मशीन का कैश आकार बहुत छोटा होता है, तो लूप पुनरावृत्ति में एक्सेस किए गए सूची तत्व (उदाहरण के लिए, <code>i = 1</code>, <code>j = 1 to n</code>) कैश लाइनों को पार कर सकता है, जिससे कैश मिस हो सकता है।


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


==उदाहरण: [[मैट्रिक्स गुणन]]==
==उदाहरण: [[मैट्रिक्स गुणन|आव्यूह गुणन]]==
कंप्यूटर पर कई बड़े गणितीय ऑपरेशन मैट्रिक्स गुणन में अपना अधिकांश समय व्यतीत करते हैं। ऑपरेशन है:
कंप्यूटर पर कई बड़े गणितीय ऑपरेशन आव्यूह गुणन में अपना अधिकांश समय व्यतीत करते हैं। ऑपरेशन है:


: सी = ए×बी
: C = A×B


जहां A, B, और C N×N सरणियाँ हैं। निम्नलिखित विवरण के लिए सदस्यताएँ प्रपत्र में हैं <code>C[row][column]</code>.
जहां A, B, और C N×N सरणियाँ हैं। निम्नलिखित विवरण के लिए सदस्यताएँ प्रपत्र <code>C[row][column]</code> में हैं।


मूल पाश है:
इस प्रकार मौलिक नेस्टेड लूप इस प्रकार है:


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 81: Line 81:
}
}
</syntaxhighlight>
</syntaxhighlight>
हल करने के लिए तीन समस्याएं हैं:
इसे हल करने के लिए तीन समस्याएं इस प्रकार संदर्भित की जा सकती हैं:


* फ़्लोटिंग पॉइंट परिवर्धन को पूरा होने में कुछ चक्र लगते हैं। एकाधिक चक्र विलंबता वाले [[योजक (इलेक्ट्रॉनिक्स)]] को व्यस्त रखने के लिए, कोड को समानांतर में एकाधिक [[संचायक (कंप्यूटिंग)]] को अद्यतन करना होगा।
* फ़्लोटिंग पॉइंट परिवर्धन को पूरा होने में कुछ चक्र लगते हैं। यहाँ पर एकाधिक चक्र विलंबता वाले [[योजक (इलेक्ट्रॉनिक्स)]] को व्यस्त रखने के लिए कोड को समानांतर में एकाधिक [[संचायक (कंप्यूटिंग)]] को अद्यतन करना होगा।
* मशीनें आम तौर पर प्रति गुणा-जोड़|गुणा-जोड़ केवल मेमोरी ऑपरेशन कर सकती हैं, इसलिए लोड किए गए मानों को कम से कम दो बार पुन: उपयोग किया जाना चाहिए।
* मशीनें सामान्यतः प्रति गुणा-जोड़ या गुणा-जोड़ केवल मेमोरी ऑपरेशन कर सकती हैं, इसलिए लोड किए गए मानों को कम से कम दो बार पुन: उपयोग किया जाना चाहिए।
* विशिष्ट पीसी मेमोरी सिस्टम केवल 10-30 डबल-प्रिसिजन मल्टीपल ऐड के लिए 8-बाइट डबलवर्ड को बनाए रख सकते हैं, इसलिए कैश में लोड किए गए मानों को कई बार पुन: उपयोग किया जाना चाहिए।
* विशिष्ट पीसी मेमोरी सिस्टम केवल 10-30 डबल-प्रिसिजन मल्टीपल ऐड के लिए 8-बाइट डबलवर्ड को बनाए रख सकते हैं, इसलिए कैश में लोड किए गए मानों को कई बार पुन: उपयोग किया जाना चाहिए।


मूल लूप समय में परिणाम मैट्रिक्स में प्रविष्टि के लिए परिणाम की गणना करता है। साथ प्रविष्टियों के छोटे ब्लॉक की गणना करके, निम्नलिखित लूप प्रत्येक लोड किए गए मान का दो बार पुन: उपयोग करता है, ताकि आंतरिक लूप में चार लोड और चार गुणा-जोड़ हों, इस प्रकार समस्या #2 का समाधान हो सके। साथ चार संचायक ले जाकर, यह कोड एकल फ़्लोटिंग पॉइंट योजक को 4 की विलंबता के साथ लगभग हर समय व्यस्त रख सकता है (समस्या #1)। हालाँकि, कोड तीसरी समस्या का समाधान नहीं करता है। (न ही यह एन विषम होने पर आवश्यक सफाई कार्य को संबोधित करता है। इस तरह के विवरण को निम्नलिखित चर्चा से बाहर रखा जाएगा।)
मूल लूप समय में परिणाम आव्यूह में प्रविष्टि के लिए परिणाम की गणना करता है। इसके साथ ही निम्नवत प्रविष्टियों के छोटे ब्लॉक की गणना करके, निम्नलिखित लूप प्रत्येक लोड किए गए मान का दो बार पुन: उपयोग करता है, जिससे कि आंतरिक लूप में चार लोड और चार गुणा-जोड़ हों, इस प्रकार समस्या #2 को हल किया जा सके। इसके साथ चार संचायकों का उपयोग करके यह कोड एकल फ़्लोटिंग पॉइंट योजक को 4 की विलंबता के साथ लगभग हर समय व्यस्त रख सकता है। चूंकि, कोड तीसरी समस्या का समाधान नहीं करता है। इसके अतिरिक्त न ही यह n विषम होने पर आवश्यक सफाई कार्य को संबोधित करता है। इस प्रकार के विवरण को निम्नलिखित चर्चा से बाहर रखा जाता हैं।


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 109: Line 109:
}
}
</syntaxhighlight>
</syntaxhighlight>
इस कोड में दोनों हैं <code>i</code> और <code>j</code> पुनरावृत्तियों को दो के कारक द्वारा अवरुद्ध कर दिया गया और दोनों परिणामी दो-पुनरावृत्ति आंतरिक लूप पूरी तरह से अनियंत्रित हो गए।
इस कोड में दोनों <code>i</code> और <code>j</code> हैं, जिसकी पुनरावृत्तियों को दोनों के विभिन्न कारकों द्वारा अवरुद्ध कर दिया जाता हैं और दोनों परिणामी दो-पुनरावृत्ति आंतरिक लूप को पूर्ण रूप से अनियंत्रित किया जा सकता हैं।


यह कोड क्रे वाई-एमपी (1980 के दशक की शुरुआत में निर्मित) पर काफी स्वीकार्य रूप से चलेगा, जो मुख्य मेमोरी में प्रति मेमोरी ऑपरेशन 0.8 गुणा-जोड़ को बनाए रख सकता है। 2003 में निर्मित 2.8 गीगाहर्ट्ज़ पेंटियम 4 जैसी मशीन में थोड़ी कम मेमोरी बैंडविड्थ और काफी बेहतर फ़्लोटिंग पॉइंट होता है, जिससे यह प्रति मेमोरी ऑपरेशन 16.5 गुणा-जोड़ को बनाए रख सकता है। परिणामस्वरूप, उपरोक्त कोड 166 मेगाहर्ट्ज वाई-एमपी की तुलना में 2.8 गीगाहर्ट्ज पेंटियम 4 पर धीमी गति से चलेगा!
यह कोड क्रे वाई-एमपी को सन् 1980 के दशक के प्रारंभ में निर्मित पर अत्यधिक स्वीकार्य रूप से चलेगा, जो मुख्य मेमोरी में प्रति मेमोरी ऑपरेशन 0.8 गुणा-जोड़ को बनाए रख सकता है। इसके आधार पर 2003 में निर्मित 2.8 गीगाहर्ट्ज़ पेंटियम 4 जैसी मशीन में थोड़ी कम मेमोरी बैंडविड्थ और अत्यधिक उत्तम फ़्लोटिंग पॉइंट होता है, जिससे यह प्रति मेमोरी ऑपरेशन 16.5 गुणा-जोड़ को बनाए रख सकता है। परिणामस्वरूप, उपरोक्त कोड 166 मेगाहर्ट्ज वाई-एमपी की तुलना में 2.8 गीगाहर्ट्ज पेंटियम 4 पर धीमी गति से चलेगा।


लंबी फ़्लोटिंग-पॉइंट ऐड विलंबता वाली या एकाधिक योजक वाली मशीन को समानांतर में चलाने के लिए अधिक संचायक की आवश्यकता होगी। 2x2 ब्लॉक के बजाय 3x3 ब्लॉक की गणना करने के लिए उपरोक्त लूप को बदलना आसान है, लेकिन परिणामी कोड हमेशा तेज़ नहीं होता है। लूप को संचायक और लोड किए गए और पुन: उपयोग किए गए ए और बी मान दोनों को रखने के लिए रजिस्टरों की आवश्यकता होती है। 2x2 ब्लॉक के लिए 7 रजिस्टरों की आवश्यकता होती है। 3x3 ब्लॉक के लिए 13 की आवश्यकता होती है, जो निर्देश सेट में केवल 8 फ्लोटिंग पॉइंट रजिस्टर वाली मशीन पर काम नहीं करेगा। यदि सीपीयू के पास पर्याप्त रजिस्टर नहीं हैं, तो कंपाइलर रजिस्टरों को स्टैक स्लॉट में फैलाने के लिए अतिरिक्त लोड और स्टोर शेड्यूल करेगा, जिससे लूप छोटे अवरुद्ध लूप की तुलना में धीमा चलेगा।
इस प्रकार लंबी फ़्लोटिंग-पॉइंट ऐड विलंबता वाली या एकाधिक योजक वाली मशीन को समानांतर में चलाने के लिए अधिक संचायक की आवश्यकता होगी। इसके आधार पर 2x2 ब्लॉक के अतिरिक्त 3x3 ब्लॉक की गणना करने के लिए उपरोक्त लूप को परिवर्तित करना साधारण है, अपितु परिणामी कोड सदैव तेज़ नहीं होता है। इस प्रकार किसी लूप को संचायक और लोड किए गए और पुन: उपयोग किए गए A और B के मान को दोनों को रखने के लिए रजिस्टरों की आवश्यकता होती है। इस प्रकार 2x2 ब्लॉक के लिए 7 रजिस्टरों की आवश्यकता होती है। जिसके आधार पर 3x3 ब्लॉक के लिए 13 की आवश्यकता होती है, जो निर्देश सेट में केवल 8 फ्लोटिंग पॉइंट रजिस्टर वाली मशीन पर कार्य नहीं करता हैं। यदि सीपीयू के पास पर्याप्त रजिस्टर नहीं हैं, तो कंपाइलर रजिस्टरों को स्टैक स्लॉट में फैलाने के लिए अतिरिक्त लोड और स्टोर शेड्यूल करेगा, जिससे लूप छोटे अवरुद्ध लूप की तुलना में धीमा चलेगा।


मैट्रिक्स गुणन कई अन्य कोडों की तरह है जिसमें इसे मेमोरी बैंडविड्थ द्वारा सीमित किया जा सकता है, और अधिक रजिस्टर कंपाइलर और प्रोग्रामर को मेमोरी बैंडविड्थ की आवश्यकता को कम करने में मदद कर सकते हैं। यह रजिस्टर दबाव ही है कि [[ जोखिम |जोखिम]] सीपीयू के विक्रेताओं, जो सामान्य प्रयोजन x[[86]] और [[68000]] सीपीयू की तुलना में अधिक समानांतर मशीनें बनाने का इरादा रखते थे, ने 32-एंट्री फ़्लोटिंग-पॉइंट [[फ़ाइल पंजीकृत करें]] को अपनाया।
आव्यूह गुणन कई अन्य कोडों की तरह है जिसमें इसे मेमोरी बैंडविड्थ द्वारा सीमित किया जा सकता है, और अधिक रजिस्टर कंपाइलर और प्रोग्रामर को मेमोरी बैंडविड्थ की आवश्यकता को कम करने में सहायता कर सकते हैं। यह रजिस्टर दबाव ही है, जिससे कि उत्पन्न होने वाले [[ जोखिम |खतरों]] के लिए सीपीयू के विक्रेताओं, जो सामान्य प्रयोजन x[[86]] और [[68000]] सीपीयू की तुलना में अधिक समानांतर मशीनें बनाने का विश्वास रखते थे, इसके द्वारा 32-एंट्री फ़्लोटिंग-पॉइंट [[फ़ाइल पंजीकृत करें|फ़ाइल पंजीकृत करके]] अपनाया गया हैं।


उपरोक्त कोड कैश का बहुत अच्छी तरह से उपयोग नहीं करता है। सी परिणामों की क्षैतिज पट्टी की गणना के दौरान, ए की क्षैतिज पट्टी लोड की जाती है, और संपूर्ण मैट्रिक्स बी लोड किया जाता है। संपूर्ण गणना के लिए, C को बार संग्रहीत किया जाता है (यह अच्छा है), A को कैश में बार लोड किया जाता है (मान लिया जाता है कि A की पट्टी B की पट्टी के साथ कैश में फिट होती है), लेकिन B को N/ib बार लोड किया जाता है, जहां ib कुल N के लिए C मैट्रिक्स में पट्टी का आकार है<sup>3</sup>/ib डबलवर्ड मुख्य मेमोरी से लोड होता है। उपरोक्त कोड में, ib 2 है।
उपरोक्त कोड कैश का बहुत अच्छी तरह से उपयोग नहीं करता है। इस प्रकार C परिणामों की क्षैतिज पट्टी की गणना के समय, A की क्षैतिज पट्टी लोड की जाती है, और संपूर्ण आव्यूह B लोड किया जाता है। जिसके आधार पर संपूर्ण गणना के लिए, C को बार संग्रहीत किया जाता है, यहाँ पर A को कैश में बार लोड किया जाता है, इसके आधार पर मान लिया जाता है कि A की पट्टी B की पट्टी के साथ कैश में फिट होती है, अपितु B को N/ib बार लोड किया जाता है, जहाँ ib कुल N के लिए C<sup>3</sup>/ib आव्यूह में पट्टी का आकार है, डबलवर्ड मुख्य मेमोरी से लोड होता है। उपरोक्त कोड में ib 2 है।


मेमोरी ट्रैफिक को कम करने का अगला कदम आईबी को जितना संभव हो उतना बड़ा बनाना है। इसे स्ट्रीम द्वारा रिपोर्ट की गई शेष संख्या से बड़ा होना आवश्यक है। इस उदाहरण के लिए उपयोग किए गए विशेष 2.8 GHz पेंटियम 4 सिस्टम के मामले में, शेष संख्या 16.5 है। उपरोक्त दूसरे कोड उदाहरण को सीधे विस्तारित नहीं किया जा सकता है, क्योंकि इसके लिए कई अधिक संचायक रजिस्टरों की आवश्यकता होगी। इसके बजाय, लूप i पर अवरुद्ध है। (तकनीकी रूप से, यह वास्तव में दूसरी बार है जब i को ब्लॉक किया गया है, क्योंकि पहली बार 2 का कारक था।)
मेमोरी ट्रैफिक को कम करने का अगली स्थिति आईबी को जितना संभव हो उतना बड़ा बनाना है। इसे स्ट्रीम द्वारा रिपोर्ट की गई शेष संख्या से बड़ा होना आवश्यक है। इस उदाहरण के लिए उपयोग किए गए विशेष 2.8 GHz पेंटियम 4 सिस्टम की स्थिति में, शेष संख्या 16.5 है। उपरोक्त दूसरे कोड उदाहरण को सीधे विस्तारित नहीं किया जा सकता है, क्योंकि इसके लिए कई अधिक संचायक रजिस्टरों की आवश्यकता होगी। इसके अतिरिक्त, लूप i पर अवरुद्ध है। इस तकनीकी के आधार पर यह वास्तव में दूसरी बार है जब i को ब्लॉक किया गया है, क्योंकि पहली बार 2 का कारक था।


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 144: Line 144:
}
}
</syntaxhighlight>
</syntaxhighlight>
इस कोड के साथ, आईबी को किसी भी वांछित पैरामीटर पर सेट किया जा सकता है, और बी मैट्रिक्स के लोड की संख्या उस कारक से कम हो जाएगी। इस स्वतंत्रता की कीमत है: A मैट्रिक्स के N×ib स्लाइस को कैश में रखा जा रहा है। जब तक यह फिट बैठता है, यह कोड मेमोरी सिस्टम द्वारा सीमित नहीं होगा।
इस कोड के साथ आईबी को किसी भी वांछित पैरामीटर पर सेट किया जा सकता है, और बी आव्यूह के लोड की संख्या उस कारक से कम हो जाएगी। इस स्वतंत्रता की कीमत है: A आव्यूह के N×ib स्लाइस को कैश में रखा जा रहा है। जब तक यह फिट बैठता है, यह कोड मेमोरी सिस्टम द्वारा सीमित नहीं होगा।


तो कौन सा आकार मैट्रिक्स फिट बैठता है? उदाहरण प्रणाली, 2.8 GHz पेंटियम 4 में 16KB प्राथमिक डेटा कैश है। Ib=20 के साथ, इस कोड में A मैट्रिक्स का स्लाइस N > 100 होने पर प्राथमिक कैश से बड़ा होगा। इससे बड़ी समस्याओं के लिए, और ट्रिक की आवश्यकता है।
तो कौन सा आकार आव्यूह फिट बैठता है? इस प्रकार उदाहरण प्रणाली, 2.8 GHz पेंटियम 4 में 16KB प्राथमिक डेटा कैश है। जिसके आधार पर Ib=20 के साथ, इस कोड में A आव्यूह का स्लाइस N > 100 होने पर प्राथमिक कैश से बड़ा होगा। इससे बड़ी समस्याओं के लिए, और ट्रिक की आवश्यकता है।


वह तरकीब k लूप को अवरुद्ध करके B मैट्रिक्स की पट्टी के आकार को कम कर रही है ताकि पट्टी का आकार ib × kb हो। K लूप को ब्लॉक करने का मतलब है कि C सरणी को कुल मिलाकर N/kb बार लोड और संग्रहीत किया जाएगा {{tmath|2*N^3/kb}} मेमोरी स्थानान्तरण. बी को अभी भी एन/आईबी बार स्थानांतरित किया गया है {{tmath|N^3/ib}} स्थानान्तरण. जब तक
इस विधि में k लूप को अवरुद्ध करके B आव्यूह की पट्टी के आकार को कम कर रही है जिससे कि पट्टी का आकार ib × kb हो जाता हैं। इसके आधार पर K लूप को ब्लॉक करने का अर्थ है कि C सूची को कुल मिलाकर N/kb बार लोड और {{tmath|2*N^3/kb}} के मान को संग्रहीत किया जाएगा, जिसके आधार पर मेमोरी स्थानान्तरण के लिए B को अभी भी n/ib बार स्थानांतरित किया गया है, जहाँ पर {{tmath|N^3/ib}} के स्थानान्तरण के लिए यह मान जब तक निम्नवत नहीं हो जाता हैं-
: 2*एन/केबी + एन/आईबी < एन/बैलेंस
: 2*n/kb + n/ib < n/balance
मशीन का मेमोरी सिस्टम फ़्लोटिंग पॉइंट यूनिट के साथ बना रहेगा और कोड अधिकतम प्रदर्शन पर चलेगा। पेंटियम 4 का 16KB कैश काफी बड़ा नहीं है: यदि इसके बजाय ib=24 और kb=64 को चुना जाता, तो 12KB कैश का उपयोग किया जाता - इसे पूरी तरह से भरने से बचा जाता, जो वांछनीय है ताकि C और B सरणियों में प्रवाह के लिए कुछ जगह होनी चाहिए। ये संख्याएँ प्रोसेसर की चरम फ़्लोटिंग-पॉइंट गति के 20% के भीतर आती हैं।
मशीन का मेमोरी सिस्टम फ़्लोटिंग पॉइंट यूनिट के साथ बना रहेगा और कोड अधिकतम प्रदर्शन पर चलेगा। इस प्रकार पेंटियम 4 का 16KB कैश अत्यधिक बड़ा नहीं है: यदि इसके अतिरिक्त ib=24 और kb=64 को चुना जाता, तो 12KB कैश का उपयोग किया जाता हैं- इसे पूर्ण रूप से भरने से बचा जाता हैं, जो वांछनीय है जिससे कि C और B सरणियों में प्रवाह के लिए कुछ जगह होनी चाहिए। ये संख्याएँ प्रोसेसर की सीमा को फ़्लोटिंग-पॉइंट गति के 20% के भीतर आती हैं।


यहाँ लूप वाला कोड है <code>k</code> अवरुद्ध.
यहाँ लूप वाला कोड <code>k</code> अवरुद्ध है, जो इस प्रकार हैं-


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 188: Line 188:
}
}
</syntaxhighlight>
</syntaxhighlight>
उपरोक्त कोड उदाहरण एन के मूल्यों से निपटने का विवरण नहीं दिखाते हैं जो अवरुद्ध कारकों के गुणक नहीं हैं। कंपाइलर जो लूप नेस्ट ऑप्टिमाइज़ेशन करते हैं, गणना के किनारों को साफ करने के लिए कोड उत्सर्जित करते हैं। उदाहरण के लिए, अधिकांश एलएनओ कंपाइलर्स संभवतः केके == 0 पुनरावृत्ति को बाकी हिस्सों से अलग कर देंगे। <code>kk</code> यदि कथन को हटाने के लिए पुनरावृत्तियाँ <code>i</code> कुंडली। यह ऐसे कंपाइलर के मूल्यों में से है: जबकि इस अनुकूलन के सरल मामलों को कोड करना सीधा है, कोड को दोहराने और परिवर्तित करने के दौरान सभी विवरणों को सही रखना त्रुटि-प्रवण प्रक्रिया है।
उपरोक्त कोड उदाहरण n के मान को हल करने का विवरण नहीं दिखाते हैं, जो अवरुद्ध कारकों के गुणक नहीं हैं। इसके आधार पर कंपाइलर जो लूप नेस्ट ऑप्टिमाइज़ेशन करते हैं, जिसकी गणना के लिए इसके किनारों को साफ करने के लिए कोड उत्सर्जित करते हैं। उदाहरण के लिए अधिकांश LNO कंपाइलर्स संभवतः KK == 0 की पुनरावृत्ति के कारण इसके बचे हुए भाग से अलग कर देंगे। इसके कारण <code>kk</code> के इस कथन को हटाने के लिए <code>i</code> क्वायल की पुनरावृत्ति होती हैं। यह ऐसे कंपाइलर के मान में से है: जबकि इस अनुकूलन के सरल मामलों को कोड करना सीधा है, कोड को दोहराने और परिवर्तित करने के समय सभी विवरणों को सही रखना त्रुटि-प्रवण प्रक्रिया है।


16KB L1 कैश आकार के लिए अवरुद्ध होने पर उपरोक्त लूप उदाहरण सिस्टम पर केवल 80% पीक फ्लॉप प्राप्त करेगा। यह और भी अधिक असंतुलित मेमोरी सिस्टम वाले सिस्टम पर और भी बुरा प्रदर्शन करेगा। सौभाग्य से, पेंटियम 4 में 256KB (या मॉडल के आधार पर अधिक) हाई-बैंडविड्थ लेवल-2 कैश के साथ-साथ लेवल-1 कैश भी है। विकल्प है:
16KB L1 कैश आकार के लिए अवरुद्ध होने पर उपरोक्त लूप उदाहरण सिस्टम पर केवल 80% पीक फ्लॉप प्राप्त करेगा। यह और भी अधिक असंतुलित मेमोरी सिस्टम वाले सिस्टम पर और भी बुरा प्रदर्शन करेगा। सौभाग्य से, पेंटियम 4 में 256KB या मॉडल के आधार पर अधिक हाई-बैंडविड्थ लेवल-2 कैश के साथ-साथ लेवल-1 कैश भी है। जिसके विभिन्न विकल्प इस प्रकार है:


* लेवल-2 कैश के लिए ब्लॉक आकार समायोजित करें। इससे प्रोसेसर की उड़ान में कई निर्देशों को साथ रखने की क्षमता पर दबाव पड़ेगा, और इस बात की अच्छी संभावना है कि यह लेवल -2 कैश से पूर्ण बैंडविड्थ प्राप्त करने में असमर्थ होगा।
* लेवल-2 कैश के लिए ब्लॉक आकार समायोजित करता हैं। इससे प्रोसेसर की उड़ान में कई निर्देशों को साथ रखने की क्षमता पर दबाव पड़ेगा, और इस बात की अच्छी संभावना है कि यह लेवल -2 कैश से पूर्ण बैंडविड्थ प्राप्त करने में असमर्थ होगा।
* लेवल-2 कैश साइज़ के लिए लूप्स को फिर से ब्लॉक करें। ब्लॉकिंग के कुल तीन स्तरों (रजिस्टर फ़ाइल के लिए, एल1 कैश और एल2 कैश के लिए) के साथ, कोड मेमोरी पदानुक्रम के प्रत्येक स्तर पर आवश्यक बैंडविड्थ को कम कर देगा। दुर्भाग्य से, अवरोधन के अतिरिक्त स्तरों पर अभी भी अधिक लूप ओवरहेड लगेगा, जो कि कुछ हार्डवेयर पर कुछ समस्या आकारों के लिए L2 कैश से डेटा स्ट्रीम करने की हार्डवेयर की क्षमता में किसी भी कमी की तुलना में अधिक समय लेने वाला हो सकता है।
* लेवल-2 कैश साइज़ के लिए लूप्स को फिर से ब्लॉक करें। इस प्रकार ब्लॉकिंग के कुल तीन स्तरों के लिए रजिस्टर फ़ाइल के लिए, L1 कैश और L2 कैश के साथ, कोड मेमोरी पदानुक्रम के प्रत्येक स्तर पर आवश्यक बैंडविड्थ को कम कर देगा। दुर्भाग्य से, अवरोधन के अतिरिक्त स्तरों पर अभी भी अधिक लूप ओवरहेड लगेगा, जो कि कुछ हार्डवेयर पर कुछ समस्या आकारों के लिए L2 कैश से डेटा स्ट्रीम करने की हार्डवेयर की क्षमता में किसी भी कमी की तुलना में अधिक समय लेने वाला हो सकता है।


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


==यह भी देखें==
==यह भी देखें==
Line 220: Line 220:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 07:37, 28 September 2023

कंप्यूटर विज्ञान में और विशेष रूप से कंप्यूटर डिज़ाइन में, लूप नेस्ट ऑप्टिमाइज़ेशन (एलएनओ) अनुकूलन की ऐसी तकनीक है जो संदर्भिक रूप से अनुकूलन या समानांतरकरण या लूप नेस्ट के किसी अन्य लूप में ओवरहेड कटौती के उद्देश्य के लिए लूप में होने वाले परिवर्तनों का सेट लागू करती है। इस प्रकार नेस्टेड लूप तब उत्पन्न होते हैं जब एक लूप किसी दूसरे लूप के अंदर होता है। मौलिक रूप से इसका उपयोग कुछ सामान्य रैखिक बीजगणित एल्गोरिदम के लिए कैश को पुन: उपयोग के कारण मेमोरी एक्सेस में विलंबता या आवश्यक कैश की बैंडविड्थ को कम करना है।

इस अनुकूलन को उत्पन्न करने के लिए उपयोग की जाने वाली तकनीक को लूप टाइलिंग कहा जाता है,[1] इसे लूप ब्लॉकिंग के रूप में भी जाना जाता है[2] या परिवर्तित करना हैं।

अवलोकन

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

नेस्टेड लूप का उदाहरण 

for (i=0; i<N; ++i) {
  ...
}

इसे ब्लॉक साइज बी से बदलकर ब्लॉक किया जा सकता है 

for (j=0; j<N; j+=B) {
  for (i=j; i<min(N, j+B); ++i) {
    ....
  }
}

जहाँ min() फ़ंक्शन है जो अपने न्यूनतम तर्क लौटाता है।

उदाहरण: आव्यूह-सदिश गुणन

निम्नलिखित आव्यूह सदिश गुणन का उदाहरण है। इसकी तीन सारणियाँ हैं, जिसमें प्रत्येक सारणी में 100 तत्व हैं। इस कोड में सूची को छोटे आकारों में विभाजित नहीं करता है। 

  int i, j, a[100][100], b[100], c[100];
  int n = 100;
  for (i = 0; i < n; i++) {
    c[i] = 0;
    for (j = 0; j < n; j++) {
      c[i] = c[i] + a[i][j] * b[j];
    }
  }

2 * 2 ब्लॉक का उपयोग करके लूप टाइलिंग लागू करने के पश्चात कोड इस तरह दिखता है: 

  int i, j, x, y, a[100][100], b[100], c[100];
  int n = 100;
  for (i = 0; i < n; i += 2) {
    c[i] = 0;
    c[i + 1] = 0;
    for (j = 0; j < n; j += 2) {
      for (x = i; x < min(i + 2, n); x++) {
        for (y = j; y < min(j + 2, n); y++) {
          c[x] = c[x] + a[x][y] * b[y];
        }
      }
    }
  }

मूल लूप पुनरावृत्ति स्थान n बटा n है। इस सूची a[i, j] का एक्सेस किया गया भाग भी n बटा n है। जहाँ पर n बहुत बड़ा होता है, और मशीन का कैश आकार बहुत छोटा होता है, तो लूप पुनरावृत्ति में एक्सेस किए गए सूची तत्व (उदाहरण के लिए, i = 1, j = 1 to n) कैश लाइनों को पार कर सकता है, जिससे कैश मिस हो सकता है।

टाइलिंग आकार

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

उदाहरण: आव्यूह गुणन

कंप्यूटर पर कई बड़े गणितीय ऑपरेशन आव्यूह गुणन में अपना अधिकांश समय व्यतीत करते हैं। ऑपरेशन है:

C = A×B

जहां A, B, और C N×N सरणियाँ हैं। निम्नलिखित विवरण के लिए सदस्यताएँ प्रपत्र C[row][column] में हैं।

इस प्रकार मौलिक नेस्टेड लूप इस प्रकार है: 

int i, j, k;

for (i = 0; i < N; ++i)
{
    for (j = 0; j < N; ++j)
    {
        C[i][j] = 0;

        for (k = 0; k < N; ++k)
            C[i][j] += A[i][k] * B[k][j];
    }
}

इसे हल करने के लिए तीन समस्याएं इस प्रकार संदर्भित की जा सकती हैं:

  • फ़्लोटिंग पॉइंट परिवर्धन को पूरा होने में कुछ चक्र लगते हैं। यहाँ पर एकाधिक चक्र विलंबता वाले योजक (इलेक्ट्रॉनिक्स) को व्यस्त रखने के लिए कोड को समानांतर में एकाधिक संचायक (कंप्यूटिंग) को अद्यतन करना होगा।
  • मशीनें सामान्यतः प्रति गुणा-जोड़ या गुणा-जोड़ केवल मेमोरी ऑपरेशन कर सकती हैं, इसलिए लोड किए गए मानों को कम से कम दो बार पुन: उपयोग किया जाना चाहिए।
  • विशिष्ट पीसी मेमोरी सिस्टम केवल 10-30 डबल-प्रिसिजन मल्टीपल ऐड के लिए 8-बाइट डबलवर्ड को बनाए रख सकते हैं, इसलिए कैश में लोड किए गए मानों को कई बार पुन: उपयोग किया जाना चाहिए।

मूल लूप समय में परिणाम आव्यूह में प्रविष्टि के लिए परिणाम की गणना करता है। इसके साथ ही निम्नवत प्रविष्टियों के छोटे ब्लॉक की गणना करके, निम्नलिखित लूप प्रत्येक लोड किए गए मान का दो बार पुन: उपयोग करता है, जिससे कि आंतरिक लूप में चार लोड और चार गुणा-जोड़ हों, इस प्रकार समस्या #2 को हल किया जा सके। इसके साथ चार संचायकों का उपयोग करके यह कोड एकल फ़्लोटिंग पॉइंट योजक को 4 की विलंबता के साथ लगभग हर समय व्यस्त रख सकता है। चूंकि, कोड तीसरी समस्या का समाधान नहीं करता है। इसके अतिरिक्त न ही यह n विषम होने पर आवश्यक सफाई कार्य को संबोधित करता है। इस प्रकार के विवरण को निम्नलिखित चर्चा से बाहर रखा जाता हैं। 

for (i = 0; i < N; i += 2)
{
    for (j = 0; j < N; j += 2)
    {
        acc00 = acc01 = acc10 = acc11 = 0;
        for (k = 0; k < N; k++)
        {
            acc00 += B[k][j + 0] * A[i + 0][k];
            acc01 += B[k][j + 1] * A[i + 0][k];
            acc10 += B[k][j + 0] * A[i + 1][k];
            acc11 += B[k][j + 1] * A[i + 1][k];
        }
        C[i + 0][j + 0] = acc00;
        C[i + 0][j + 1] = acc01;
        C[i + 1][j + 0] = acc10;
        C[i + 1][j + 1] = acc11;
    }
}

इस कोड में दोनों i और j हैं, जिसकी पुनरावृत्तियों को दोनों के विभिन्न कारकों द्वारा अवरुद्ध कर दिया जाता हैं और दोनों परिणामी दो-पुनरावृत्ति आंतरिक लूप को पूर्ण रूप से अनियंत्रित किया जा सकता हैं।

यह कोड क्रे वाई-एमपी को सन् 1980 के दशक के प्रारंभ में निर्मित पर अत्यधिक स्वीकार्य रूप से चलेगा, जो मुख्य मेमोरी में प्रति मेमोरी ऑपरेशन 0.8 गुणा-जोड़ को बनाए रख सकता है। इसके आधार पर 2003 में निर्मित 2.8 गीगाहर्ट्ज़ पेंटियम 4 जैसी मशीन में थोड़ी कम मेमोरी बैंडविड्थ और अत्यधिक उत्तम फ़्लोटिंग पॉइंट होता है, जिससे यह प्रति मेमोरी ऑपरेशन 16.5 गुणा-जोड़ को बनाए रख सकता है। परिणामस्वरूप, उपरोक्त कोड 166 मेगाहर्ट्ज वाई-एमपी की तुलना में 2.8 गीगाहर्ट्ज पेंटियम 4 पर धीमी गति से चलेगा।

इस प्रकार लंबी फ़्लोटिंग-पॉइंट ऐड विलंबता वाली या एकाधिक योजक वाली मशीन को समानांतर में चलाने के लिए अधिक संचायक की आवश्यकता होगी। इसके आधार पर 2x2 ब्लॉक के अतिरिक्त 3x3 ब्लॉक की गणना करने के लिए उपरोक्त लूप को परिवर्तित करना साधारण है, अपितु परिणामी कोड सदैव तेज़ नहीं होता है। इस प्रकार किसी लूप को संचायक और लोड किए गए और पुन: उपयोग किए गए A और B के मान को दोनों को रखने के लिए रजिस्टरों की आवश्यकता होती है। इस प्रकार 2x2 ब्लॉक के लिए 7 रजिस्टरों की आवश्यकता होती है। जिसके आधार पर 3x3 ब्लॉक के लिए 13 की आवश्यकता होती है, जो निर्देश सेट में केवल 8 फ्लोटिंग पॉइंट रजिस्टर वाली मशीन पर कार्य नहीं करता हैं। यदि सीपीयू के पास पर्याप्त रजिस्टर नहीं हैं, तो कंपाइलर रजिस्टरों को स्टैक स्लॉट में फैलाने के लिए अतिरिक्त लोड और स्टोर शेड्यूल करेगा, जिससे लूप छोटे अवरुद्ध लूप की तुलना में धीमा चलेगा।

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

उपरोक्त कोड कैश का बहुत अच्छी तरह से उपयोग नहीं करता है। इस प्रकार C परिणामों की क्षैतिज पट्टी की गणना के समय, A की क्षैतिज पट्टी लोड की जाती है, और संपूर्ण आव्यूह B लोड किया जाता है। जिसके आधार पर संपूर्ण गणना के लिए, C को बार संग्रहीत किया जाता है, यहाँ पर A को कैश में बार लोड किया जाता है, इसके आधार पर मान लिया जाता है कि A की पट्टी B की पट्टी के साथ कैश में फिट होती है, अपितु B को N/ib बार लोड किया जाता है, जहाँ ib कुल N के लिए C3/ib आव्यूह में पट्टी का आकार है, डबलवर्ड मुख्य मेमोरी से लोड होता है। उपरोक्त कोड में ib 2 है।

मेमोरी ट्रैफिक को कम करने का अगली स्थिति आईबी को जितना संभव हो उतना बड़ा बनाना है। इसे स्ट्रीम द्वारा रिपोर्ट की गई शेष संख्या से बड़ा होना आवश्यक है। इस उदाहरण के लिए उपयोग किए गए विशेष 2.8 GHz पेंटियम 4 सिस्टम की स्थिति में, शेष संख्या 16.5 है। उपरोक्त दूसरे कोड उदाहरण को सीधे विस्तारित नहीं किया जा सकता है, क्योंकि इसके लिए कई अधिक संचायक रजिस्टरों की आवश्यकता होगी। इसके अतिरिक्त, लूप i पर अवरुद्ध है। इस तकनीकी के आधार पर यह वास्तव में दूसरी बार है जब i को ब्लॉक किया गया है, क्योंकि पहली बार 2 का कारक था। 

for (ii = 0; ii < N; ii += ib)
{
    for (j = 0; j < N; j += 2)
    {
        for (i = ii; i < ii + ib; i += 2)
        {
            acc00 = acc01 = acc10 = acc11 = 0;
            for (k = 0; k < N; k++)
            {
                acc00 += B[k][j + 0] * A[i + 0][k];
                acc01 += B[k][j + 1] * A[i + 0][k];
                acc10 += B[k][j + 0] * A[i + 1][k];
                acc11 += B[k][j + 1] * A[i + 1][k];
            }
            C[i + 0][j + 0] = acc00;
            C[i + 0][j + 1] = acc01;
            C[i + 1][j + 0] = acc10;
            C[i + 1][j + 1] = acc11;
        }
    }
}

इस कोड के साथ आईबी को किसी भी वांछित पैरामीटर पर सेट किया जा सकता है, और बी आव्यूह के लोड की संख्या उस कारक से कम हो जाएगी। इस स्वतंत्रता की कीमत है: A आव्यूह के N×ib स्लाइस को कैश में रखा जा रहा है। जब तक यह फिट बैठता है, यह कोड मेमोरी सिस्टम द्वारा सीमित नहीं होगा।

तो कौन सा आकार आव्यूह फिट बैठता है? इस प्रकार उदाहरण प्रणाली, 2.8 GHz पेंटियम 4 में 16KB प्राथमिक डेटा कैश है। जिसके आधार पर Ib=20 के साथ, इस कोड में A आव्यूह का स्लाइस N > 100 होने पर प्राथमिक कैश से बड़ा होगा। इससे बड़ी समस्याओं के लिए, और ट्रिक की आवश्यकता है।

इस विधि में k लूप को अवरुद्ध करके B आव्यूह की पट्टी के आकार को कम कर रही है जिससे कि पट्टी का आकार ib × kb हो जाता हैं। इसके आधार पर K लूप को ब्लॉक करने का अर्थ है कि C सूची को कुल मिलाकर N/kb बार लोड और के मान को संग्रहीत किया जाएगा, जिसके आधार पर मेमोरी स्थानान्तरण के लिए B को अभी भी n/ib बार स्थानांतरित किया गया है, जहाँ पर के स्थानान्तरण के लिए यह मान जब तक निम्नवत नहीं हो जाता हैं-

2*n/kb + n/ib < n/balance

मशीन का मेमोरी सिस्टम फ़्लोटिंग पॉइंट यूनिट के साथ बना रहेगा और कोड अधिकतम प्रदर्शन पर चलेगा। इस प्रकार पेंटियम 4 का 16KB कैश अत्यधिक बड़ा नहीं है: यदि इसके अतिरिक्त ib=24 और kb=64 को चुना जाता, तो 12KB कैश का उपयोग किया जाता हैं- इसे पूर्ण रूप से भरने से बचा जाता हैं, जो वांछनीय है जिससे कि C और B सरणियों में प्रवाह के लिए कुछ जगह होनी चाहिए। ये संख्याएँ प्रोसेसर की सीमा को फ़्लोटिंग-पॉइंट गति के 20% के भीतर आती हैं।

यहाँ लूप वाला कोड k अवरुद्ध है, जो इस प्रकार हैं- 

for (ii = 0; ii < N; ii += ib)
{
    for (kk = 0; kk < N; kk += kb)
    {
        for (j=0; j < N; j += 2)
        {
            for (i = ii; i < ii + ib; i += 2)
            {
                if (kk == 0)
                    acc00 = acc01 = acc10 = acc11 = 0;
                else
                {
                    acc00 = C[i + 0][j + 0];
                    acc01 = C[i + 0][j + 1];
                    acc10 = C[i + 1][j + 0];
                    acc11 = C[i + 1][j + 1];
                }
                for (k = kk; k < kk + kb; k++)
                {
                    acc00 += B[k][j + 0] * A[i + 0][k];
	                acc01 += B[k][j + 1] * A[i + 0][k];
	                acc10 += B[k][j + 0] * A[i + 1][k];
	                acc11 += B[k][j + 1] * A[i + 1][k];
                }
                C[i + 0][j + 0] = acc00;
                C[i + 0][j + 1] = acc01;
                C[i + 1][j + 0] = acc10;
                C[i + 1][j + 1] = acc11;
            }
        }
    }
}

उपरोक्त कोड उदाहरण n के मान को हल करने का विवरण नहीं दिखाते हैं, जो अवरुद्ध कारकों के गुणक नहीं हैं। इसके आधार पर कंपाइलर जो लूप नेस्ट ऑप्टिमाइज़ेशन करते हैं, जिसकी गणना के लिए इसके किनारों को साफ करने के लिए कोड उत्सर्जित करते हैं। उदाहरण के लिए अधिकांश LNO कंपाइलर्स संभवतः KK == 0 की पुनरावृत्ति के कारण इसके बचे हुए भाग से अलग कर देंगे। इसके कारण kk के इस कथन को हटाने के लिए i क्वायल की पुनरावृत्ति होती हैं। यह ऐसे कंपाइलर के मान में से है: जबकि इस अनुकूलन के सरल मामलों को कोड करना सीधा है, कोड को दोहराने और परिवर्तित करने के समय सभी विवरणों को सही रखना त्रुटि-प्रवण प्रक्रिया है।

16KB L1 कैश आकार के लिए अवरुद्ध होने पर उपरोक्त लूप उदाहरण सिस्टम पर केवल 80% पीक फ्लॉप प्राप्त करेगा। यह और भी अधिक असंतुलित मेमोरी सिस्टम वाले सिस्टम पर और भी बुरा प्रदर्शन करेगा। सौभाग्य से, पेंटियम 4 में 256KB या मॉडल के आधार पर अधिक हाई-बैंडविड्थ लेवल-2 कैश के साथ-साथ लेवल-1 कैश भी है। जिसके विभिन्न विकल्प इस प्रकार है:

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

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

यह भी देखें

संदर्भ

  1. ↑ Steven Muchnick; Muchnick and Associates (15 August 1997). उन्नत कंपाइलर डिज़ाइन कार्यान्वयन. Morgan Kaufmann. ISBN 978-1-55860-320-2. खपरैल लगाना।
  2. ↑ João M.P. Cardoso; Pedro C. Diniz (2 April 2011). पुन: कॉन्फ़िगर करने योग्य आर्किटेक्चर के लिए संकलन तकनीकें. Springer Science & Business Media. ISBN 978-0-387-09671-1.


अग्रिम पठन

  1. Wolfe, M. More Iteration Space Tiling. Supercomputing'89, pages 655–664, 1989.
  2. Wolf, M. E. and Lam, M. A Data Locality Optimizing Algorithm. PLDI'91, pages 30–44, 1991.
  3. Irigoin, F. and Triolet, R. Supernode Partitioning. POPL'88, pages 319–329, 1988.
  4. Xue, J. Loop Tiling for Parallelism. Kluwer Academic Publishers. 2000.
  5. M. S. Lam, E. E. Rothberg, and M. E. Wolf. The cache performance and optimizations of blocked algorithms. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 63–74, April 1991.

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लूप_नेस्ट_अनुकूलन&oldid=262133’