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

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

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

सिंहावलोकन

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

एक साधारण पाश

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) कैश लाइनों को पार कर सकता है, जिससे कैश मिस हो सकता है।

टाइलिंग आकार

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

उदाहरण: मैट्रिक्स गुणन

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

सी = ए×बी

जहां 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 की विलंबता के साथ लगभग हर समय व्यस्त रख सकता है (समस्या #1)। हालाँकि, कोड तीसरी समस्या का समाधान नहीं करता है। (न ही यह एन विषम होने पर आवश्यक सफाई कार्य को संबोधित करता है। इस तरह के विवरण को निम्नलिखित चर्चा से बाहर रखा जाएगा।)

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

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

उपरोक्त कोड कैश का बहुत अच्छी तरह से उपयोग नहीं करता है। सी परिणामों की क्षैतिज पट्टी की गणना के दौरान, ए की एक क्षैतिज पट्टी लोड की जाती है, और संपूर्ण मैट्रिक्स बी लोड किया जाता है। संपूर्ण गणना के लिए, 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$ मेमोरी स्थानान्तरण. बी को अभी भी एन/आईबी बार स्थानांतरित किया गया है $N^{3}/ib$ स्थानान्तरण. जब तक

2*एन/केबी + एन/आईबी < एन/बैलेंस

मशीन का मेमोरी सिस्टम फ़्लोटिंग पॉइंट यूनिट के साथ बना रहेगा और कोड अधिकतम प्रदर्शन पर चलेगा। पेंटियम 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;
            }
        }
    }
}

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

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

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