एक्सटर्नल मेमोरी एल्गोरिदम

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

कंप्यूटिंग में, बाहरी मेमोरी एल्गोरिदम या आउट-ऑफ-कोर एल्गोरिदम ऐसे एल्गोरिदम हैं जो डेटा को संसाधित करने के लिए डिज़ाइन किए गए हैं जो बार में कंप्यूटर की मुख्य मेमोरी में फिट होने के लिए बहुत बड़े हैं। ऐसे एल्गोरिदम को धीमी बल्क मेमोरी (सहायक मेमोरी) जैसे हार्ड ड्राइव या टेप ड्राइव में संग्रहीत डेटा को कुशलतापूर्वक लाने और एक्सेस करने के लिए अनुकूलित किया जाना चाहिए, या जब मेमोरी कंप्यूटर नेटवर्क पर हो। [1] [2] बाह्य मेमोरी एल्गोरिदम का विश्लेषण बाह्य मेमोरी मॉडल में किया जाता है।

मॉडल

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

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

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

एल्गोरिदम

बाहरी मेमोरी मॉडल में एल्गोरिदम इस तथ्य का लाभ उठाते हैं कि बाहरी मेमोरी से ऑब्जेक्ट को पुनर्प्राप्त करने से आकार का पूरा ब्लॉक पुनर्प्राप्त हो जाता है $B$. इस संपत्ति को कभी-कभी स्थानीयता भी कहा जाता है।

बीच में तत्व की तलाश है $N$ ब्रांचिंग फैक्टर के साथ बी-वृक्ष का उपयोग करके बाहरी मेमोरी मॉडल में ऑब्जेक्ट संभव है $B$. बी-ट्री का उपयोग करके खोज, सम्मिलन और विलोपन प्राप्त किया जा सकता है $O(\log _{B}N)$ समय ( बिग ओ अंकन में)। सूचना सिद्धांत, इन परिचालनों के लिए यह न्यूनतम संभव समय है, इसलिए बी-ट्री का उपयोग करना असम्बद्ध रूप से इष्टतम है।

बाहरी सॉर्टिंग बाहरी मेमोरी सेटिंग में सॉर्टिंग है। बाहरी सॉर्टिंग वितरण सॉर्ट के माध्यम से की जा सकती है, जो क्विक सॉर्ट के समान है, या ए के माध्यम से ${\tfrac {M}{B}}$के-वे मर्ज एल्गोरिदम|-वे मर्ज सॉर्ट। दोनों वेरिएंट एसिम्प्टोटिक रूप से इष्टतम रनटाइम प्राप्त करते हैं $O({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}})$ सुलझाने के लिए N वस्तुएं। यह सीमा बाहरी मेमोरी मॉडल में फास्ट फूरियर ट्रांसफॉर्म पर भी लागू होती है।

क्रमपरिवर्तन समस्या पुनर्व्यवस्थित करना है $N$ तत्वों को विशिष्ट क्रमपरिवर्तन में। यह या तो सॉर्टिंग द्वारा किया जा सकता है, जिसके लिए उपरोक्त सॉर्टिंग रनटाइम की आवश्यकता होती है, या प्रत्येक तत्व को क्रम में सम्मिलित करके और स्थानीयता के लाभ को अनदेखा करके किया जा सकता है। इस प्रकार, क्रमपरिवर्तन किया जा सकता है $O(\min(N,{\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}))$ समय।

अनुप्रयोग

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

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

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

इतिहास

विशेषण के रूप में आउट-ऑफ-कोर शब्द का प्रारंभिक उपयोग 1962 में उन उपकरणों के संदर्भ में किया गया था जो आईबीएम 360 की चुंबकीय-कोर मेमोरी के अलावा अन्य हैं। एल्गोरिदम के संबंध में आउट-ऑफ-कोर शब्द का प्रारंभिक उपयोग 1971 में सामने आया।

यह भी देखें

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

बाहरी संबंध

• Out of Core SVD and QR
• Out of core graphics
• Scalapack design