एक्सटर्नल मेमोरी एल्गोरिदम
कम्प्यूटिंग में, एक्सटर्नल मेमोरी एल्गोरिदम या आउट-ऑफ-कोर एल्गोरिदम वह एल्गोरिदम हैं जो डेटा को संसाधित करने के लिए डिज़ाइन किए गए हैं जो कंप्यूटर की मुख्य मेमोरी में फिट होने के लिए बहुत बड़े हैं। ऐसे एल्गोरिदम को स्लो बुलक मेमोरी (सहायक मेमोरी) होती है जिसे हार्ड ड्राइव या टेप ड्राइव में संग्रहीत डेटा को कुशलतापूर्वक लाने और एक्सेस करने के लिए अनुकूलित किया जाना चाहिए, या जब यह मेमोरी कंप्यूटर नेटवर्क पर होती हैं। [1][2] एक्सटर्नल मेमोरी एल्गोरिदम का विश्लेषण एक्सटर्नल मेमोरी मॉडल में किया जाता है।
मॉडल
एक्सटर्नल मेमोरी एल्गोरिदम विधि का विश्लेषण गणना के आदर्श मॉडल में किया जाता है जिसे एक्सटर्नल मेमोरी मॉडल (या आई/ओ मॉडल, या डिस्क एक्सेस मॉडल) कहा जाता है। एक्सटर्नल मेमोरी मॉडल रैम मॉडल के समान अमूर्त मशीन है, किन्तु मुख्य मेमोरी के अतिरिक्त यह कैश (कंप्यूटिंग) के साथ होती हैं। मॉडल इस तथ्य को पकड़ता है कि मुख्य मेमोरी की तुलना में कैश (कंप्यूटिंग) में पढ़ने और लिखने का संचालन बहुत शीघ्र होता है, और डिस्क पढ़ने और लिखने वाला शीर्ष का उपयोग करके यादृच्छिक रूप से पढ़ने की तुलना में (कंप्यूटर) लंबे सन्निहित ब्लॉकों को पढ़ना शीघ्रता से होता है। एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम का रनिंग टाइम आवश्यक मेमोरी में पढ़ने और लिखने की संख्या से परिभाषित होता है।[3] यह मॉडल 1988 में आलोक अग्रवाल और जेफरी विटर द्वारा प्रस्तुत किया गया था।[4] एक्सटर्नल मेमोरी मॉडल कैश-ओब्लिवियस एल्गोरिथम यह आदर्शित कैश मॉडल हैं | कैश-ओब्लिवियस मॉडल से संबंधित है, किन्तु एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम ब्लॉक (डेटा संग्रहण) और कैश (कंप्यूटिंग) आकार दोनों को जान सकता है। इस कारण से, मॉडल को कभी-कभी कैश-अवेयर मॉडल के रूप में जाना जाता है।[5]
मॉडल में प्रोसेसर (कंप्यूटिंग) होता है जिसमें आंतरिक मेमोरी या आकार M, का कैश होता है, अनंत एक्सटर्नल मेमोरी से जुड़ा है। इसमें आंतरिक और एक्सटर्नल दोनों मेमोरी को आकार B के ब्लॉक (डेटा स्टोरेज) में विभाजित किया गया है | इनपुट/आउटपुट या मेमोरी ट्रांसफर ऑपरेशन में B सन्निहित अवयवों के ब्लॉक को एक्सटर्नल से आंतरिक मेमोरी में ले जाना सम्मिलित है, और एल्गोरिदम का चलने का समय संख्या से निर्धारित होता है यह इनपुट/आउटपुट ऑपरेशन होता हैं।[4]
एल्गोरिदम
एक्सटर्नल मेमोरी मॉडल में एल्गोरिदम इस तथ्य का लाभ उठाते हैं कि एक्सटर्नल मेमोरी से ऑब्जेक्ट को पुनर्प्राप्त करने से आकार का पूर्ण ब्लॉक पुनर्प्राप्त हो जाता है | इस संपत्ति को कभी-कभी स्थानीयता भी कहा जाता है।
ब्रांचिंग फैक्टर के साथ बी-ट्री का उपयोग करके एक्सटर्नल मेमोरी मॉडल में ऑब्जेक्ट के मध्य अवयव की खोज संभव होती है। बी-ट्री का उपयोग करके, खोज, इंसर्शन और डिलेशनन को समय में (बिग ओ नोटेशन में) प्राप्त किया जा सकता है। सूचना सिद्धांत रूप से, यह इन परिचालनों के लिए न्यूनतम संभव समय है, इसलिए इसमें बी-ट्री का उपयोग करना असम्बद्ध रूप से बहुततम होता है। [4]
एक्सटर्नल सॉर्टिंग एक्सटर्नल मेमोरी सेटिंग में सॉर्टिंग है। एक्सटर्नल सॉर्टिंग वितरण सॉर्ट के माध्यम से की जा सकती है, जो क्विक सॉर्ट के समान होती है, यह - के-वे मर्ज सॉर्ट एल्गोरिदम के माध्यम से की जा सकती है। दोनों वेरिएंट एन ऑब्जेक्ट्स को सॉर्ट करने के लिए के एसिम्प्टोटिक रूप से बहुततम रनटाइम को प्राप्त करते हैं। यह सीमा एक्सटर्नल मेमोरी मॉडल में फास्ट फूरियर ट्रांसफॉर्म पर भी प्रयुक्त होती है। [2]
क्रमपरिवर्तन समस्या अवयवों को विशिष्ट क्रम परिवर्तन में पुनर्व्यवस्थित करना है। या यह तब सॉर्टिंग द्वारा किया जा सकता है, जिसके लिए उपरोक्त सॉर्टिंग रनटाइम की आवश्यकता होती है, इसमें प्रत्येक अवयव को क्रम में सम्मिलित करके और स्थानीयता के लाभ को अप्रत्यक्ष करके किया जा सकता है। इस प्रकार, यह क्रमपरिवर्तन समय में किया जा सकता है।
अनुप्रयोग
एक्सटर्नल मेमोरी मॉडल मेमोरी पदानुक्रम को कैप्चर करता है, जिसे डेटा संरचनाओं का विश्लेषण करने में उपयोग किए जाने वाले अन्य सामान्य मॉडल, जैसे रैंडम-एक्सेस मशीन, में मॉडल नहीं किया जाता है, और डेटा संरचनाओं के लिए निचली सीमा प्रमाणित करने के लिए उपयोगी है। यह मॉडल उन एल्गोरिदम का विश्लेषण करने के लिए भी उपयोगी होता है जो आंतरिक मेमोरी में फिट होने के लिए बहुत बड़े डेटासेट पर कार्य करते हैं।[4]
ऐसे विशिष्ट उदाहरण भौगोलिक सूचना प्रणाली होते है, यह विशेष रूप से डिजिटल एलिवेशन मॉडल होते हैं, इसमें पूर्ण डेटा सेट सरलता से अनेक गीगाबाइट में होते हैं और यहां तक कि यह टेराबाइट्स डेटा से भी अधिक हो जाता है।
यह कार्यप्रणाली सेंट्रल प्रोसेसिंग यूनिट से आगे तक विस्तारित हुई है और इसमें ग्राफ़िक्स प्रोसेसिंग यूनिट कंप्यूटिंग के साथ-साथ मौलिक अंकीय संकेत प्रक्रिया भी सम्मिलित होती है। ग्राफिक्स प्रोसेसिंग यूनिट (जीपीजीपीयू) पर सामान्य प्रयोजन कंप्यूटिंग में, कम मेमोरी वाले शक्तिशाली ग्राफिक्स कार्ड (जीपीयू) (बहुत परिचित सिस्टम मेमोरी की तुलना में होती हैं, जिसे प्रायः रैंडम एक्सेस मेमोरी के रूप में संदर्भित किया जाता है) इसका उपयोग अपेक्षाकृत स्लो सीपीयू-टू-जीपीयू के साथ किया जाता है। जीपीयू मेमोरी तब ट्रांसफर की जाती हैं (जब गणना की बैंडविड्थ के साथ तुलना की जाती है)।
इतिहास
विशेषण के रूप में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1962 में उन उपकरणों के संदर्भ में किया गया था जो आईबीएम 360 की कोर मेमोरी के अतिरिक्त अन्य हैं। [6] एल्गोरिदम के संबंध में "आउट-ऑफ-कोर" शब्द का प्रारंभिक उपयोग 1971 में सामने आया था। [7]
यह भी देखें
- कैश-ओब्लिवियस एल्गोरिथ्म
- एक्सटर्नल मेमोरी ग्राफ़ ट्रैवर्सल
- ऑनलाइन एल्गोरिदम
- पैरेलल एक्सटर्नल मेमोरी
- स्ट्रीमिंग एल्गोरिदम
संदर्भ
- ↑ Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193. S2CID 2155038.
- ↑ 2.0 2.1 Vitter, J. S. (2008). बाहरी मेमोरी के लिए एल्गोरिदम और डेटा संरचनाएं (PDF). pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6.
{{cite book}}:|journal=ignored (help) - ↑ Zhang, Donghui; Tsotras, Vassilis J.; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y.; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3.
- ↑ 4.0 4.1 4.2 4.3 Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535. S2CID 6264984.
- ↑ Demaine, Erik (2002). कैश-ओब्लिवियस एल्गोरिदम और डेटा संरचनाएं (PDF). Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.
- ↑ नासा एसपी. NASA. 1962. p. 276.
- ↑ संकट में कंप्यूटर. ACM. 1971. p. 296.
