लूप नेस्ट अनुकूलन

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

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

अवलोकन

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

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

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 के लिए C³/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 बार लोड और $2*N^{3}/kb$ के मान को संग्रहीत किया जाएगा, जिसके आधार पर मेमोरी स्थानान्तरण के लिए B को अभी भी n/ib बार स्थानांतरित किया गया है, जहाँ पर $N^{3}/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. 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.

बाहरी संबंध

• Streams benchmark results, showing the overall balance between floating point operations and memory operations for many different computers
• "CHiLL: Composable High-Level Loop Transformation Framework"