लूप अनरोलिंग

From Vigyanwiki

लूप अनरोलिंग के बाद

लूप अनरोलिंग, जिसे लूप अनवाइंडिंग के रूप में भी जाना जाता है, एक लूप परिवर्तन तकनीक है जो किसी प्रोग्राम की बाइनरी फ़ाइल साइज की कीमत पर उसकी निष्पादन गति को अनुकूलित करने का प्रयास करती है, जिसे स्पेस-टाइम ट्रेडऑफ़ के रूप में जाना जाता है। परिवर्तन प्रोग्रामर द्वारा या एक अनुकूलन कंपाइलर द्वारा मैन्युअल रूप से किया जा सकता है। आधुनिक प्रोसेसर पर, लूप अनरोलिंग प्रायः प्रतिकूल होता है, क्योंकि बढ़े हुए कोड साइज के कारण अधिक कैश मिस हो सकता है; सीएफ. डफ का उपकरण#प्रदर्शन|डफ का उपकरण.<रेफरी नाम= lkml-0008.2/0171 >Tso, Ted (August 22, 2000). "पुन: [पैच] इनपुट ड्राइवर को हटाएं, आपसे कुछ शब्दों की आवश्यकता है". lkml.indiana.edu. Linux kernel mailing list. Retrieved August 22, 2014. जिम गेटीज़ के पास एक्स सर्वर में इस आशय की अद्भुत व्याख्या है। यह पता चला है कि पिछले दशक में शाखा भविष्यवाणियों और सीपीयू बनाम मेमोरी की सापेक्ष गति में बदलाव के साथ, लूप अनरोलिंग काफी हद तक व्यर्थ है। वास्तव में, XFree86 4.0 सर्वर से डफ के डिवाइस के सभी उदाहरणों को हटाने से, सर्वर का आकार _आधा_ _a_ _मेगाबाइट_ (!!!) कम हो गया, और बूट करने में तेज़ हो गया, क्योंकि सभी अतिरिक्त कोड को हटाने का मतलब था कि एक्स सर्वर कैश लाइनों को उतना तेज़ नहीं कर रहा था।</ref>

लूप अनवाइंडिंग का लक्ष्य लूप को नियंत्रित करने वाले निर्देशों को कम या समाप्त करके प्रोग्राम की गति को बढ़ाना है, जैसे पॉइंटर अंकगणित और प्रत्येक पुनरावृत्ति पर लूप परीक्षण का अंत; रेफरी>Ullman, Jeffrey D.; Aho, Alfred V. (1977). कंपाइलर डिज़ाइन के सिद्धांत. Reading, Mass: Addison-Wesley Pub. Co. pp. 471–2. ISBN 0-201-10073-8.</ref> शाखा दंड कम करना; साथ ही विलंबता को छिपाना, जिसमें मेमोरी से डेटा पढ़ने में देरी भी सम्मिलित है। रेफरी>Petersen, W.P., Arbenz, P. (2004). समानांतर कंप्यूटिंग का परिचय. Oxford University Press. p. 10.{{cite book}}: CS1 maint: multiple names: authors list (link)</ref> इस कम्प्यूटेशनल ओवरहेड को खत्म करने के लिए, लूप्स को समान स्वतंत्र कथनों के दोहराए गए अनुक्रम के रूप में फिर से लिखा जा सकता है। रेफरी>Nicolau, Alexandru (1985). "लूप क्वांटाइजेशन: फाइन-ग्रेन पैरेललिज्म एक्सप्लॉइटेशन के लिए अनवाइंडिंग". Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257. {{cite journal}}: Cite journal requires |journal= (help)</ref>

लूप अनरोलिंग भी कुछ औपचारिक सत्यापन तकनीकों का हिस्सा है, विशेष रूप से बाउंडेड मॉडल जाँच में। एसएमटी और सूचियों के सिद्धांत का उपयोग करके मॉडल की जांच

फायदे

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

  • यदि निष्पादित निर्देशों में कमी कार्यक्रम के साइज में किसी भी वृद्धि के कारण प्रदर्शन में कमी की भरपाई करती है, तो महत्वपूर्ण लाभ प्राप्त किया जा सकता है।
  • शाखा भविष्यवक्ता को न्यूनतम कर दिया गया है।[1]
  • यदि लूप में कथन एक-दूसरे से स्वतंत्र हैं (यानी जहां लूप में पहले आने वाले कथन उनके बाद आने वाले कथनों को प्रभावित नहीं करते हैं), तो कथनों को संभावित रूप से समानांतर कंप्यूटिंग में निष्पादित किया जा सकता है।
  • यदि संकलन समय पर सरणी तत्वों की संख्या अज्ञात है (जैसा कि डफ के उपकरण में है) तो इसे गतिशील रूप से कार्यान्वित किया जा सकता है।

ऑप्टिमाइज़िंग कंपाइलर कभी-कभी स्वचालित रूप से या अनुरोध पर अनरोलिंग का कार्य करेंगे।

नुकसान

  • इंक्रीसेड प्रोग्राम कोड साइज, जो अवांछनीय हो सकता है, विशेष रूप से एम्बेडेड अनुप्रयोगों के लिए। अनुदेश कैश चूक में भी वृद्धि हो सकती है, जो प्रदर्शन पर प्रतिकूल प्रभाव डाल सकती है।
  • जब तक ऑप्टिमाइज़िंग कंपाइलर द्वारा पारदर्शी तरीके से निष्पादित नहीं किया जाता, कोड कंप्यूटर प्रोग्रामिंग में कम पठनीयता#पठनीयता बन सकता है।
  • यदि लूप के मुख्य भाग में कोड में फ़ंक्शन कॉल सम्मिलित हैं, तो अनरोलिंग को इनलाइनिंग के साथ जोड़ना संभव नहीं हो सकता है, क्योंकि कोड साइज में वृद्धि अत्यधिक हो सकती है। इस प्रकार, दोनों अनुकूलन के बीच एक समझौता हो सकता है।
  • अस्थायी चरों को संग्रहीत करने के लिए एकल पुनरावृत्ति में संभावित बढ़े हुए रजिस्टर उपयोग, जो प्रदर्शन को कम कर सकता है, हालांकि बहुत कुछ संभावित अनुकूलन पर निर्भर करेगा।[2]
  • बहुत छोटे और सरल कोड के अलावा, अनियंत्रित लूप जिनमें शाखाएं होती हैं, रिकर्सन से भी धीमी होती हैं।[3]

स्टेटिक/मैन्युअल लूप अनरोलिंग

मैनुअल (या स्थिर) लूप अनरोलिंग में प्रोग्रामर को लूप का विश्लेषण करना और निर्देशों के अनुक्रम में पुनरावृत्तियों की व्याख्या करना सम्मिलित है जो लूप ओवरहेड को कम करेगा। यह डायनामिक अनरोलिंग के विपरीत है जिसे कंपाइलर द्वारा पूरा किया जाता है।

C में सरल मैनुअल उदाहरण

कंप्यूटर प्रोग्राम में एक प्रक्रिया एक संग्रह से 100 वस्तुओं को हटाने की है। यह सामान्यतः a के माध्यम से पूरा किया जाता है for-लूप जो फ़ंक्शन डिलीट (आइटम_नंबर) को कॉल करता है। यदि प्रोग्राम के इस भाग को अनुकूलित किया जाना है, और लूप के ओवरहेड को डिलीट (x) फ़ंक्शन की तुलना में महत्वपूर्ण संसाधनों की आवश्यकता है, तो इसे गति देने के लिए अनवाइंडिंग का उपयोग किया जा सकता है।

सामान्य लूप लूप अनरोलिंग के बाद 
 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }

 int x; 
 for (x = 0; x < 100; x += 5 )
 {
     delete(x);
     delete(x + 1);
     delete(x + 2);
     delete(x + 3);
     delete(x + 4);
 }

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

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

प्रारंभिक जटिलता

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

सामान्य लूप लूप अनरोलिंग के बाद 
for i := 1:8 do
    if i mod 2 = 0 then do_even_stuff(i) 
                   else do_odd_stuff(i);
    next i;

do_odd_stuff(1); do_even_stuff(2);
do_odd_stuff(3); do_even_stuff(4);
do_odd_stuff(5); do_even_stuff(6);
do_odd_stuff(7); do_even_stuff(8);

लेकिन निश्चित रूप से, निष्पादित कोड को किसी प्रक्रिया का आह्वान करने की आवश्यकता नहीं है, और इस अगले उदाहरण में गणना में सूचकांक चर सम्मिलित है:

सामान्य लूप लूप अनरोलिंग के बाद 
x(1) := 1;
for i := 2:9 do
    x(i) := x(i - 1) * i;
    print i, x(i);
    next i;

x(1) := 1;
x(2) := x(1) * 2; print 2, x(2);
x(3) := x(2) * 3; print 3, x(3);
x(4) := x(3) * 4; print 4, x(4);
... etc.

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

प्रिंट 2, 2;
प्रिंट 3, 6;
प्रिंट 4, 24;
...वगैरह।

सामान्य तौर पर, लूप की सामग्री बड़ी हो सकती है, जिसमें जटिल सरणी अनुक्रमण सम्मिलित होता है। इन मामलों को संभवतः कंपाइलरों को अनियंत्रित करने के लिए अनुकूलित करना सबसे अच्छा है। अंतरतम लूपों की नकल करने से कई संभावित अनुकूलन की अनुमति मिल सकती है, फिर भी केवल एक छोटा सा लाभ मिलता है जब तक कि n बड़ा न हो।

लूप्स को अनियंत्रित करना

निम्नलिखित के समान एक छद्मकोड WHILE लूप पर विचार करें:

सामान्य लूप लूप अनरोलिंग के बाद अनियंत्रित एवं "ट्वीक्ड" लूप 
WHILE (condition) DO
    action
ENDWHILE
.
.
.
.
.
.

WHILE (condition) DO
    action
    IF NOT(condition) THEN GOTO break
    action
    IF NOT(condition) THEN GOTO break
    action
ENDWHILE
LABEL break:
.

IF (condition) THEN
    REPEAT
        action
        IF NOT(condition) THEN GOTO break
        action
        IF NOT(condition) THEN GOTO break
        action
    WHILE (condition)
LABEL break:

इस मामले में, अनरोलिंग तेज़ है क्योंकि ENDWHILE (लूप की शुरुआत में एक छलांग) को 66% कम बार निष्पादित किया जाएगा।

इससे भी बेहतर, संशोधित छद्मकोड उदाहरण, जो कुछ अनुकूलन कंपाइलरों द्वारा स्वचालित रूप से निष्पादित किया जा सकता है, जिससे बिना शर्त छलांग पूरी तरह समाप्त हो जाती है।

डायनेमिक अनरोलिंग

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

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

असेंबलर उदाहरण (आईबीएम/360 या जेड/आर्किटेक्चर)

यह उदाहरण IBM/360 या Z/आर्किटेक्चर असेंबलर्स के लिए है और मानता है कि 100 बाइट्स (ऑफ़सेट शून्य पर) के फ़ील्ड को सरणी से FROM से सरणी TO में कॉपी किया जाना है - दोनों में 256 बाइट्स की तत्व लंबाई के साथ 50 प्रविष्टियाँ हैं। <सिंटैक्सहाइलाइट लैंग = टेक्स्ट लाइन = 1 हाइलाइट = 39-41,44-58 >

  • वापसी का पता R14 में है।
  • अंत में परिभाषित डेटा से रजिस्टर R15, R0, R1 और R2 को प्रारंभ करें
  • प्रोग्राम INIT/MAXM1 लेबल से प्रांरम्भ होता है।
        एलएम आर15,आर2,आईएनआईटी सेट आर15 = एमवीसी की अधिकतम संख्या
  • निर्देश (MAXM1 = 16),
  • R0 = सरणी की प्रविष्टियों की संख्या,
  • R1 = 'FROM' सरणी का पता, और
  • R2 = 'TO' सरणी का पता।
  • लूप यहीं से प्रांरम्भ होता है.

लूप इक्व * लूप लेबल को परिभाषित करें।

  • इस बिंदु पर, R15 में हमेशा संख्या 16 (MAXM1) होगी।
        SR R15,R0 की शेष संख्या घटाएँ
  • R15 से सरणी (R0) में प्रविष्टियाँ।
        BNP ALL यदि R15 सकारात्मक नहीं है, तो इसका अर्थ है हम
  • 16 से अधिक प्रविष्टियाँ शेष हैं
  • सरणी में, संपूर्ण कार्य करने के लिए कूदें
  • एमवीसी अनुक्रम और फिर दोहराएं।
  • बिना शर्त शाखा के लिए ऑफसेट (एमवीसी अनुक्रम की शुरुआत से) की गणना करें
  • नीचे 'अनवाउंड' एमवीसी लूप।
  • यदि सरणियों में शेष प्रविष्टियों की संख्या शून्य है, तो R15 16 होगी
  • सभी एमवीसी निर्देशों को दरकिनार कर दिया जाएगा।
        MH R15,=AL2(ILEN) R15 को एक की लंबाई से गुणा करें
  • एमवीसी निर्देश।
        B ALL(R15) ALL+R15 पर जाएं, का पता
  • विशिष्ट एमवीसी अनुदेश की गणना की गई
  • उनमें से बाकी लोगों तक ड्रॉप थ्रू के साथ।
  • एमवीसी निर्देश 'तालिका'।
  • पहली प्रविष्टि में एकल रजिस्टर = हेक्साडेसिमल F00 के साथ अधिकतम स्वीकार्य ऑफसेट है
  • (15*256) इस उदाहरण में।
  • निम्नलिखित सभी 16 एमवीसी ('मूव कैरेक्टर') निर्देश बेस-प्लस-ऑफ़सेट का उपयोग करते हैं
  • एड्रेसिंग और प्रत्येक से/से ऑफसेट एक सरणी तत्व की लंबाई से घटता है
  • (256). इससे प्रत्येक तत्व के लिए सूचक अंकगणित की आवश्यकता होने से बचा जा सकता है
  • हेक्साडेसिमल एफएफएफ के निर्देश के भीतर अधिकतम अनुमेय ऑफसेट
  • (15*256+255). निर्देश घटते ऑफसेट के क्रम में हैं, इसलिए अंतिम
  • सेट में तत्व को पहले स्थानांतरित किया जाता है।

सभी एमवीसी 15*256(100,आर2),15*256(आर1) 16वीं प्रविष्टि के 100 बाइट्स ले जाएँ

  • सारणी 1 से सारणी 2 तक (साथ में)।
  • ड्रॉप-थ्रू)।

ILEN EQU *-सभी ILEN को पिछली लंबाई पर सेट करें

  • एमवीसी निर्देश।
        एमवीसी 14*256(100,आर2),14*256(आर1) 15वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 13*256(100,आर2),13*256(आर1) 14वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 12*256(100,आर2),12*256(आर1) 13वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 11*256(100,आर2),11*256(आर1) 12वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 10*256(100,आर2),10*256(आर1) 11वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 09*256(100,आर2),09*256(आर1) 10वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 08*256(100,आर2),08*256(आर1) 9वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 07*256(100,आर2),07*256(आर1) 8वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 06*256(100,आर2),06*256(आर1) 7वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 05*256(100,आर2),05*256(आर1) छठी प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 04*256(100,आर2),04*256(आर1) 5वीं प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 03*256(100,आर2),03*256(आर1) चौथी प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 02*256(100,आर2),02*256(आर1) तीसरी प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 01*256(100,आर2),01*256(आर1) दूसरी प्रविष्टि के 100 बाइट्स ले जाएँ।
        एमवीसी 00*256(100,आर2),00*256(आर1) पहली प्रविष्टि के 100 बाइट्स ले जाएँ।

        S R0,MAXM1 शेष प्रविष्टियों की संख्या कम करें
  • प्रक्रिया को।
        बीएनपीआर आर14 यदि संसाधित करने के लिए कोई और प्रविष्टियाँ नहीं हैं, तो वापस लौटें
  • R14 में पता करने के लिए.
        AH R1,=AL2(16*256) सरणी सूचक से आगे 'FROM' बढ़ाएँ
  • आग का सेट।
        AH R2,=AL2(16*256) सरणी सूचक को 'TO' से आगे बढ़ाएं
  • आग का सेट।
        L R15,MAXM1 MVC की अधिकतम संख्या पुनः लोड करें
  • R15 में प्रति बैच निर्देश
  • (में गणना द्वारा नष्ट कर दिया गया
  • लूप का पहला निर्देश)।
        बी लूप फिर से लूप निष्पादित करें।
  • स्थैतिक स्थिरांक और चर (इन्हें पैरामीटर के रूप में पारित किया जा सकता है, सिवाय
  • MAXM1).

INIT DS 0A 4 पते (सूचक) होने चाहिए

  • 'एलएम' अनुदेश पहले से लोड किया हुआ
  • कार्यक्रम के आरंभ में.

MAXM1 DC A(16) MVC निर्देशों की अधिकतम संख्या

  • प्रति बैच निष्पादित।

एन डीसी ए(50) सरणी में वास्तविक प्रविष्टियों की संख्या (ए)।

  • परिवर्तनीय, अन्यत्र सेट करें)।
        DC A(FROM) सरणी 1 की शुरुआत का पता
  • ( सूचक ).
        डीसी ए(टीओ) सरणी 2 की शुरुआत का पता
  • ( सूचक ).
  • स्थैतिक सरणियाँ (इन्हें गतिशील रूप से प्राप्त किया जा सकता है)।

डीएस 50सीएल256 से प्रत्येक 256 बाइट्स की 50 प्रविष्टियों की सरणी। TO DS 50CL256 प्रत्येक 256 बाइट्स की 50 प्रविष्टियों की सारणी।

</सिंटैक्सहाइलाइट>

इस उदाहरण में, पारंपरिक लूप (50 पुनरावृत्तियों) के साथ लगभग 202 निर्देशों की आवश्यकता होगी, जबकि उपरोक्त गतिशील कोड के लिए केवल 89 निर्देशों (या लगभग 56% की बचत) की आवश्यकता होगी। यदि सरणी में केवल दो प्रविष्टियाँ सम्मिलित होतीं, तो भी यह मूल अनवाउंड लूप के समान ही समय में निष्पादित होती। बाइनरी फ़ाइल साइज में वृद्धि केवल 108 बाइट्स है – भले ही सरणी में हजारों प्रविष्टियाँ हों।

निश्चित रूप से समान तकनीकों का उपयोग किया जा सकता है जहां कई निर्देश सम्मिलित होते हैं, जब तक कि संयुक्त निर्देश की लंबाई तदनुसार समायोजित की जाती है। उदाहरण के लिए, इसी उदाहरण में, यदि 100 बाइट फ़ील्ड की प्रतिलिपि बनाने के तुरंत बाद प्रत्येक सरणी प्रविष्टि के शेष भाग को शून्य में साफ़ करना आवश्यक है, तो एक अतिरिक्त स्पष्ट निर्देश, XC xx*256+100(156,R1),xx*256+100(R2), अनुक्रम में प्रत्येक एमवीसी के तुरंत बाद जोड़ा जा सकता है (जहां xx इसके ऊपर एमवीसी में मान से मेल खाता है)।

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

C उदाहरण

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

#include <stdio.h>

/* The number of entries processed per loop iteration.                        */
/* Note that this number is a 'constant constant' reflecting the code below.  */
#define BUNCHSIZE (8)

int main(void)
{ 
  int i = 0;                                    /* counter */
  int entries = 50;                             /* total number to process    */
  int repeat;                                   /* number of while repetitions*/
  int left = 0;                                 /* remainder (process later)  */ 
 
  /* If the number of elements is not be divisible by BUNCHSIZE,              */ 
  /* get repeat times required to do most processing in the while loop        */

  repeat = (entries / BUNCHSIZE);                /* number of times to repeat */
  left   = (entries % BUNCHSIZE);                /* calculate remainder       */

  /* Unroll the loop in 'bunches' of 8                                        */ 
  while (repeat--) 
  { 
    printf("process(%d)\n", i    );
    printf("process(%d)\n", i + 1); 
    printf("process(%d)\n", i + 2); 
    printf("process(%d)\n", i + 3); 
    printf("process(%d)\n", i + 4); 
    printf("process(%d)\n", i + 5); 
    printf("process(%d)\n", i + 6); 
    printf("process(%d)\n", i + 7);

    /* update the index by amount processed in one go                         */ 
    i += BUNCHSIZE;
  }

  /* Use a switch statement to process remaining by jumping to the case label */ 
  /* at the label that will then drop through to complete the set             */ 
  switch (left) 
  {
     case 7 : printf("process(%d)\n", i + 6);   /* process and rely on drop 
                                                   through                    */
     case 6 : printf("process(%d)\n", i + 5); 
     case 5 : printf("process(%d)\n", i + 4);  
     case 4 : printf("process(%d)\n", i + 3);  
     case 3 : printf("process(%d)\n", i + 2); 
     case 2 : printf("process(%d)\n", i + 1);   /* two left                   */
     case 1 : printf("process(%d)\n", i);       /* just one left to process   */ 
     case 0 : ;                                 /* none left                  */
  } 
}

डफ के उपकरण की तरह दोनों भागों को एक साथ लिखकर कोड दोहराव से बचा जा सकता है।

C से एमआईपीएस असेंबली लैंग्वेज लूप अनरोलिंग उदाहरण[4]

निम्नलिखित उदाहरण दो 100-एंट्री वैक्टर A और B प्रकार के डॉट उत्पाद की गणना करेगा double. यहां C में कोड है:<सिंटैक्सहाइलाइट lang= c लाइन= 1 > डबल डॉटप्रोडक्ट = 0; (int i = 0; i < 100; i++) के लिए { 

 dotProduct += A[i]*B[i];

} </सिंटैक्सहाइलाइट>

एमआईपीएस असेंबली लैंग्वेज में कनवर्ट करना

निम्नलिखित एमआईपीएस असेंबली कोड है जो लूप अनरोलिंग को लागू करने से पहले दो 100-एंट्री वैक्टर, A और B के डॉट उत्पाद की गणना करेगा। नीचे दिया गया कोड लूप आरंभीकरण को छोड़ देता है:

  • प्रारंभिक लूप गिनती ($7) से 100 तक।
  • आरंभिक डॉट उत्पाद ($f10) से 0 करें।
  • आरंभ करें A[i] के आधार पते पर सूचक ($5)। A.
  • आरंभ करें B[i] के आधार पते पर सूचक ($6)। B.

ध्यान दें कि सरणियों के एक तत्व का साइज (a double) 8 बाइट्स है। <सिंटैक्सहाइलाइट लैंग = एएसएम लाइन = 1 > 

   लूप3:
           एलडी $एफ10, 0($5)); $f10 ← ए[i]
           एलडी $एफ12, 0($6)6; $f12 ← बी[i]
           mul.d $f10, $f10, $f12f; $f10 ← A[i]*B[i]
           add.d $f8, $f8, $f10$; $f8 ← $f8 + A[i]*B[i]
           अतिरिक्त $5, $5, 8$; साइज के अनुसार A[i] के लिए वृद्धि सूचक
                                     ; एक दोहरे का.
           अतिरिक्त $6, $6, 8,; साइज के अनुसार B[i] के लिए वृद्धि सूचक
                                     ; एक दोहरे का.
           अतिरिक्त $7, $7, -17; कमी लूप गिनती
   परीक्षा:
           bgtz $7, लूप3 ; यदि लूप गिनती > 0 है तो जारी रखें

</सिंटैक्सहाइलाइट>

एमआईपीएस में लूप को अनियंत्रित करना

निम्नलिखित ऊपर जैसा ही है, लेकिन लूप अनरोलिंग को 4 के कारक पर लागू किया गया है। फिर से ध्यान दें कि सरणियों के एक तत्व का साइज (ए) double) 8 बाइट्स है; इस प्रकार प्रत्येक लूप पर 0, 8, 16, 24 विस्थापन और 32 विस्थापन।<सिंटैक्सहाइलाइट lang= asm लाइन= 1 > 

   लूप3:
           एलडी $एफ10, 0($5) ; विस्थापन 0 के साथ पुनरावृत्ति
           एल.डी. $f12, 0($6)
           mul.d $f10, $f10, $f12
           add.d $f8, $f8, $f10

           एल.डी. $एफ10, 8($5) ; विस्थापन के साथ पुनरावृत्ति 8
           एल.डी. $f12, 8($6)
           mul.d $f10, $f10, $f12
           add.d $f8, $f8, $f10

           एल.डी. $एफ10, 16($5) ; विस्थापन के साथ पुनरावृत्ति 16
           एल.डी. $f12, 16($6)
           mul.d $f10, $f10, $f12
           add.d $f8, $f8, $f10

           एल.डी. $एफ10, 24($5) ; विस्थापन के साथ पुनरावृत्ति 24
           एल.डी. $f12, 24($6)
           mul.d $f10, $f10, $f12
           add.d $f8, $f8, $f10

           अतिरिक्त $5, $5, 32
           अतिरिक्त $6, $6, 32
           अतिरिक्त $7, $7, -4
   परीक्षा:
           bgtz $7, लूप3 ; यदि $7 > 0 हो तो लूप जारी रखें

</सिंटैक्सहाइलाइट>

यह भी देखें

संदर्भ

  1. ↑ Fog, Agner (2012-02-29). "असेंबली भाषा में सबरूटीन्स का अनुकूलन" (PDF). Copenhagen University College of Engineering. p. 100. Retrieved 2012-09-22. 12.11 Loop unrolling
  2. ↑ Sarkar, Vivek (2001). "नेस्टेड लूप्स का अनुकूलित अनरोलिंग". International Journal of Parallel Programming. 29 (5): 545–581. doi:10.1023/A:1012246031671. S2CID 3353104.
  3. ↑ Adam Horvath "Code unwinding - performance is far away"
  4. ↑ "लूप का खुलना". University of Minnesota.


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लूप_अनरोलिंग&oldid=247123’