लूप अनरोलिंग

From Vigyanwiki

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

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

लूप अनवाइंडिंग का लक्ष्य लूप को नियंत्रित करने वाले निर्देशों को कम या समाप्त करके प्रोग्राम की गति को बढ़ाना है, जैसे पॉइंटर अंकगणित और प्रत्येक पुनरावृत्ति पर लूप परीक्षण का अंत; 

शाखा दंड कम करना; साथ ही विलंबता को छिपाना, जिसमें मेमोरी से डेटा पढ़ने में देरी भी सम्मिलित है।  इस कम्प्यूटेशनल ओवरहेड को खत्म करने के लिए, लूप्स को समान स्वतंत्र कथनों के दोहराए गए अनुक्रम के रूप में फिर से लिखा जा सकता है। लूप क्वांटाइजेशन: फाइन-ग्रेन पैरेललिज्म एक्सप्लॉइटेशन के लिए अनवाइंडिंग

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

फायदे

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

  • यदि निष्पादित निर्देशों में कमी कार्यक्रम के साइज में किसी भी वृद्धि के कारण प्रदर्शन में कमी की भरपाई करती है, तो महत्वपूर्ण लाभ प्राप्त किया जा सकता है।
  • शाखा भविष्यवक्ता (ब्रांच पेनल्टी) को न्यूनतम कर दिया गया है।[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 का कोई बाद का संदर्भ नहीं है, इसके उपयोग को एक साधारण चर द्वारा प्रतिस्थापित किया जा सकता है। हालाँकि, इस तरह के परिवर्तन का मतलब एक साधारण चर होगा जिसका मान बदल गया है, जबकि सरणी के साथ रहने पर, कंपाइलर का विश्लेषण यह नोट कर सकता है कि सरणी के मान स्थिर हैं, प्रत्येक पिछले स्थिरांक से प्राप्त होता है, और इसलिए स्थिर मानों को आगे बढ़ाता है ताकि कोड बन जाए 

 print 2, 2;
print 3, 6;
print 4, 24;
...etc.

सामान्य तौर पर, लूप की सामग्री बड़ी हो सकती है, जिसमें जटिल सरणी अनुक्रमण सम्मिलित होता है। इन मामलों को संभवतः कंपाइलरों को अनियंत्रित करने के लिए अनुकूलित करना सबसे अच्छा है। अंतरतम लूपों की नकल करने से कई संभावित अनुकूलन की अनुमति मिल सकती है, फिर भी केवल एक छोटा सा लाभ मिलता है जब तक कि 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 प्रविष्टियाँ हैं।

* The return address is in R14.
* Initialize registers R15, R0, R1, and R2 from data defined at the end of 
* the program starting with label INIT/MAXM1.
         LM    R15,R2,INIT                  Set R15 = maximum number of MVC
*                                           instructions (MAXM1 = 16), 
*                                           R0 = number of entries of array,
*                                           R1 = address of 'FROM' array, and
*                                           R2 = address of 'TO' array.
*
* The loop starts here.
LOOP     EQU   *                            Define LOOP label.
* At this point, R15 will always contain the number 16 (MAXM1).
         SR    R15,R0                       Subtract the remaining number of 
*                                           entries in the array (R0) from R15.
         BNP   ALL                          If R15 is not positive, meaning we
*                                           have more than 16 remaining entries
*                                           in the array, jump to do the entire
*                                           MVC sequence and then repeat.
*
* Calculate an offset (from start of MVC sequence) for unconditional branch to 
* the 'unwound' MVC loop below.
* If the number of remaining entries in the arrays is zero, R15 will be 16, so 
* all the MVC instructions will be bypassed.
         MH    R15,=AL2(ILEN)               Multiply R15 by the length of one
*                                           MVC instruction.
         B     ALL(R15)                     Jump to ALL+R15, the address of the
*                                           calculated specific MVC instruction 
*                                           with drop through to the rest of them.
*
* MVC instruction 'table'. 
* First entry has maximum allowable offset with single register = hexadecimal F00
* (15*256) in this example.
* All 16 of the following MVC ('move character') instructions use base-plus-offset 
* addressing and each to/from offset decreases by the length of one array element
* (256). This avoids pointer arithmetic being required for each element up to a 
* maximum permissible offset within the instruction of hexadecimal FFF 
* (15*256+255). The instructions are in order of decreasing offset, so the last 
* element in the set is moved first.
ALL      MVC   15*256(100,R2),15*256(R1)    Move 100 bytes of 16th entry from 
*                                           array 1 to array 2 (with 
*                                           drop-through).
ILEN     EQU   *-ALL                        Set ILEN to the length of the previous
*                                           MVC instruction.
         MVC   14*256(100,R2),14*256(R1)    Move 100 bytes of 15th entry.
         MVC   13*256(100,R2),13*256(R1)    Move 100 bytes of 14th entry.
         MVC   12*256(100,R2),12*256(R1)    Move 100 bytes of 13th entry.
         MVC   11*256(100,R2),11*256(R1)    Move 100 bytes of 12th entry.
         MVC   10*256(100,R2),10*256(R1)    Move 100 bytes of 11th entry.
         MVC   09*256(100,R2),09*256(R1)    Move 100 bytes of 10th entry.
         MVC   08*256(100,R2),08*256(R1)    Move 100 bytes of 9th entry.
         MVC   07*256(100,R2),07*256(R1)    Move 100 bytes of 8th entry.
         MVC   06*256(100,R2),06*256(R1)    Move 100 bytes of 7th entry.
         MVC   05*256(100,R2),05*256(R1)    Move 100 bytes of 6th entry.
         MVC   04*256(100,R2),04*256(R1)    Move 100 bytes of 5th entry.
         MVC   03*256(100,R2),03*256(R1)    Move 100 bytes of 4th entry.
         MVC   02*256(100,R2),02*256(R1)    Move 100 bytes of 3rd entry.
         MVC   01*256(100,R2),01*256(R1)    Move 100 bytes of 2nd entry.
         MVC   00*256(100,R2),00*256(R1)    Move 100 bytes of 1st entry.
*
         S     R0,MAXM1                     Reduce the number of remaining entries
*                                           to process.
         BNPR  R14                          If no more entries to process, return
*                                           to address in R14.
         AH    R1,=AL2(16*256)              Increment 'FROM' array pointer beyond
*                                           first set.
         AH    R2,=AL2(16*256)              Increment 'TO' array pointer beyond
*                                           first set.
         L     R15,MAXM1                    Reload the maximum number of MVC 
*                                           instructions per batch into R15
*                                           (destroyed by the calculation in the 
*                                           first instruction of the loop).
         B     LOOP                         Execute loop again.
*
* Static constants and variables (these could be passed as parameters, except 
* MAXM1).
INIT     DS    0A                           4 addresses (pointers) to be 
*                                           pre-loaded with the 'LM' instruction
*                                           in the beginning of the program.
MAXM1    DC    A(16)                        Maximum number of MVC instructions
*                                           executed per batch.
N        DC    A(50)                        Number of actual entries in array (a 
*                                           variable, set elsewhere).
         DC    A(FROM)                      Address of start of array 1 
*                                           ("pointer").
         DC    A(TO)                        Address of start of array 2 
*                                           ("pointer").
*
* Static arrays (these could be dynamically acquired).
FROM     DS    50CL256                      Array of 50 entries of 256 bytes each.
TO       DS    50CL256                      Array of 50 entries of 256 bytes each.

इस उदाहरण में, पारंपरिक लूप (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 में कोड है:C:

double dotProduct = 0;
for (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 बाइट्स है।

    loop3:
            l.d     $f10, 0($5)       ; $f10 ← A[i]
            l.d     $f12, 0($6)       ; $f12 ← B[i]
            mul.d   $f10, $f10, $f12  ; $f10 ← A[i]*B[i]
            add.d   $f8, $f8, $f10    ; $f8 ← $f8 + A[i]*B[i]
            addi    $5, $5, 8         ; increment pointer for A[i] by the size
                                      ; of a double.
            addi    $6, $6, 8         ; increment pointer for B[i] by the size
                                      ; of a double.
            addi    $7, $7, -1        ; decrement loop count
    test:
            bgtz    $7, loop3         ; Continue if loop count > 0

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

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

    loop3:
            l.d     $f10, 0($5)         ; iteration with displacement 0
            l.d     $f12, 0($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 8($5)         ; iteration with displacement 8
            l.d     $f12, 8($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 16($5)        ; iteration with displacement 16
            l.d     $f12, 16($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 24($5)        ; iteration with displacement 24
            l.d     $f12, 24($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            addi    $5, $5, 32
            addi    $6, $6, 32
            addi    $7, $7, -4
    test:
            bgtz    $7, loop3           ; Continue loop if $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=252122’