कैश-विस्मृत एल्गोरिथ्म

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

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

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

इतिहास

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

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

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

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

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

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

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

*मेमोरी को ब्लॉकों में विभाजित किया गया है $B$ प्रत्येक वस्तु.

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

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

उदाहरण

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

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

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

कैश-विस्मृत एल्गोरिथ्म में इष्टतम कार्य जटिलता है $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 कैश-अनभिज्ञ एल्गोरिदम की अनुभवजन्य तुलना से पता चला कि:

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

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

यह भी देखें

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