कैश-ओब्लिवियस एल्गोरिदम

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

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

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

इतिहास

कैश-ओब्लिवियस एल्गोरिदम के लिए विचार (और नाम) की कल्पना चार्ल्स ई. लेइसर्सन ने 1996 के प्रारंभ में की थी और पहली बार 1999 में मैसाचुसेट्स की तकनीकी संस्था में अपने मास्टर की थीसिस में हेराल्ड प्रोकोप द्वारा प्रकाशित किया गया था। ऐसे अनेक पूर्ववर्ती थे, जो सामान्यतः विशिष्ट समस्याओं का विश्लेषण करते थे; इन पर फ्रिगो एट अल में विस्तार से चर्चा की गई है। उद्धृत प्रारंभिक उदाहरणों में पुनरावर्ती फास्ट फूरियर ट्रांसफॉर्म के लिए सिंगलटन 1969, अग्रवाल एट अल 1987 में समान विचार, आव्यूह गुणन और एलयू अपघटन के लिए फ्रिगो 1996, और ब्लिट्ज़++ लाइब्रेरी में आव्यूह एल्गोरिदम के लिए टॉड वेल्धुइज़न 1996 सम्मिलित हैं।

आदर्शीकृत कैश मॉडल

सामान्यतः, कंप्यूटर प्रोग्राम को अधिक कैश-सचेत बनाया जा सकता है:

• लौकिक स्थान, जहां एल्गोरिदम मेमोरी के एक ही टुकड़े को अनेक बार लाता है;
• स्थानिक स्थान, जहां बाद की मेमोरी पहुंच आसन्न या निकटतम मेमोरी एड्रेस हैं।

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

विशेष रूप से, कैश-ओब्लिवियस मॉडल अमूर्त मशीन है (अर्थात्, गणना का सैद्धांतिक मॉडल)। यह रैम मॉडल के समान है, जो ट्यूरिंग मशीन के अनंत टेप को अनंत ऐरे से परिवर्तित कर देता है। ऐरे के अन्दर प्रत्येक स्थान को वास्तविक कंप्यूटर पर रैंडम एक्सेस मेमोरी के समान, $O(1)$ समय में एक्सेस किया जा सकता है। रैम मशीन मॉडल के विपरीत, यह कैश भी रैम और सीपीयू के बीच भंडारण का दूसरा स्तर प्रस्तुत करता है। दोनों मॉडलों के बीच अन्य अंतर नीचे सूचीबद्ध हैं। कैश-ओब्लिवियस मॉडल में:

बायीं ओर के कैश में कुल M ऑब्जेक्ट के लिए प्रत्येक $B$ आकार के ${\tfrac {M}{B}}$ ब्लॉक होते हैं। दाहिनी ओर की बाह्य मेमोरी असीमित है।

• मेमोरी को प्रत्येक $B$ ऑब्जेक्ट के ब्लॉक में विभाजित किया गया है।
• मुख्य मेमोरी और सीपीयू रजिस्टर के बीच लोड या स्टोर को अब कैश से सर्विस किया जा सकता है।
• यदि किसी लोड या स्टोर को कैश से सर्विस नहीं किया जा सकता है, तो इसे कैश मिस कहा जाता है।
• कैश मिस होने के परिणामस्वरूप ब्लॉक मुख्य मेमोरी से कैश में लोड हो जाता है। अर्थात्, यदि सीपीयू शब्द $w$ तक पहुँचने का प्रयास करता है और $x$ वह युक्त पंक्ति है, जिसमें $w$ है, तब $x$ को कैश में लोड किया जाता है। यदि कैश पहले भरा हुआ था, तो लाइन भी हटा दी जाएगी (नीचे प्रतिस्थापन नीति देखें)।
• कैश में $M$ ऑब्जेक्ट होते हैं, जहाँ $M=\Omega (B^{2})$ है। इसे लंबी कैश धारणा के रूप में भी जाना जाता है।
• कैश पूरी तरह से सहयोगी है: प्रत्येक पंक्ति को कैश में किसी भी स्थान पर लोड किया जा सकता है।
• प्रतिस्थापन नीति इष्टतम है। दूसरे शब्दों में, यह माना जाता है कि कैश को एल्गोरिदम निष्पादन के समय मेमोरी एक्सेस का संपूर्ण अनुक्रम दिया गया है। यदि इसे $t$ समय पर लाइन को हटाने की आवश्यकता है, तो यह भविष्य के अनुरोधों के अनुक्रम को ध्यान करेगा और उस लाइन को हटा देगा जिसकी पहली पहुंच भविष्य में सबसे दूर है। व्यवहार में उसका अनुकरण कम से कम गतकाल में प्रयुक्त नीति के साथ किया जा सकता है, जिसे ऑफ़लाइन इष्टतम प्रतिस्थापन रणनीति के छोटे स्थिर कारक के अन्दर दिखाया गया है।

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

उदाहरण

पंक्ति और स्तंभ-प्रमुख क्रम का चित्रण

फ्रिगो एट अल में प्रस्तुत सबसे सरल कैश-ओब्लिवियस एल्गोरिदम है। आउट-ऑफ़-प्लेस ट्रांसपोज़ ऑपरेशन है, इन-प्लेस आव्यूह एल्गोरिदम भी ट्रांसपोज़िशन के लिए तैयार किए गए हैं, लेकिन गैर-स्क्वायर आव्यूह के लिए बहुत अधिक जटिल हैं)। m×n ऐरे A और n×m ऐरे B को देखते हुए, हम A के स्थानान्तरण को B में संग्रहीत करना चाहेंगे। सरल समाधान ऐरे को पंक्ति-प्रमुख क्रम में और दूसरे को स्तंभ-प्रमुख क्रम में पार करता है। इसका परिणाम यह होता है कि जब आव्यूह बड़े होते हैं, तो हमें कॉलम-वार ट्रैवर्सल के प्रत्येक चरण पर कैश मिस मिलता है। कैश छूटने की कुल संख्या $\Theta (mn)$ है।

विभाजन और विजय-दृष्टिकोण का उपयोग करके आव्यूह ट्रांसपोज़िशन के लिए कैश-ओब्लिवियस एल्गोरिदम का सिद्धांत। ग्राफ़िक आव्यूह को विभाजित करने और प्रत्येक भाग को व्यक्तिगत रूप से स्थानांतरित करने का पुनरावर्ती चरण (a → b) दिखाता है।

कैश-ओब्लिवियस एल्गोरिदम में इष्टतम कार्य जटिलता $O(mn)$ है और इष्टतम कैश जटिलता $O(1+mn/B)$ है। मूल विचार यह है कि दो बड़े आव्यूहों के स्थानान्तरण को कम करके छोटे (उप)आव्यूहों का स्थानान्तरण किया जाए। हम आव्यूह को उनके बड़े आयाम के साथ आधे में विभाजित करके ऐसा करते हैं, जब तक कि हमें केवल आव्यूह का स्थानांतरण नहीं करना पड़ता जो कैश में फिट होगा। क्योंकि कैश का आकार एल्गोरिदम को ज्ञात नहीं है, इस बिंदु के बाद भी आव्यूह को पुनरावर्ती रूप से विभाजित किया जाना जारी रहेगा, लेकिन ये आगे के उपखंड कैश में होंगे। एक बार जब आयाम m और n अत्यधिक छोटे हो जाते हैं तो $m\times n$ आकार का इनपुट ऐरे और $n\times m$ आकार का आउटपुट ऐरे कैश में फिट हो जाता है, रो-मेजर और कॉलम-मेजर दोनों ट्रैवर्सल के परिणामस्वरूप $O(mn)$ कार्य होता है और $O(mn/B)$ कैश छूट जाता है।

(सैद्धांतिक रूप से, कोई भी आव्यूह को तब तक विभाजित करना जारी रख सकता है जब तक कि आकार 1×1 का बेस केस नहीं पहुंच जाता है, लेकिन व्यवहार में कोई पुनरावर्ती उपरूटीन कॉल के ओवरहेड का परिशोधन विश्लेषण करने के लिए बड़े बेस केस (जैसे 16×16) का उपयोग करता है।)

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

बाहय मेमोरी मॉडल में बाहरी सॉर्टिंग की तरह, कैश-ओब्लिवियस सॉर्टिंग दो वेरिएंट में संभव है: फ़नलसॉर्ट, जो मर्ज़ सॉर्ट जैसा दिखता है, और कैश-ओब्लिवियस वितरण प्रकार, जो क्विक सॉर्ट जैसा दिखता है। अपने बाहरी मेमोरी समकक्षों की तरह, दोनों रनिंग टाइम $O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)$ प्राप्त करते हैं, जो निचली सीमा से मेल खाता है और इस प्रकार स्पर्शोन्मुख रूप से इष्टतम है।

व्यावहारिकता

प्राथमिकता पंक्तियों को प्रयुक्त करने वाले 2 रैम-आधारित, 1 कैश-अवेयर और 2 कैश-अनअवेयर एल्गोरिदम की अनुभवजन्य तुलना से पता चला कि:

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

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

यह भी देखें

• कैश-ओब्लिवियस वितरण प्रकार
• बाह्य मेमोरी एल्गोरिदम
• फ़नलसॉर्ट