मेमोरी-बाउंड फ़ंक्शन

मेमोरी बाउंड एक ऐसी स्थिति को संदर्भित करता है जिसमें किसी कम्प्यूटेशनल समस्या को पूरा करने का समय मुख्य रूप से कार्यशील आंकड़े को रखने के लिए आवश्यक मुक्त कंप्यूटर मेमोरी की मात्रा से तय होता है। यह एल्गोरिदम के विपरीत है जो गणना-बद्ध हैं, जहां प्राथमिक संगणना चरणों की संख्या निर्णायक कारक है।

मेमोरी और संगणना सीमाओं को कभी-कभी एक दूसरे के विरुद्ध विक्रय किया जा सकता है, उदाहरण प्रारंभिक परिणामों को सहेजकर और पुन: उपयोग करके या लुकअप तालिकाओं का उपयोग करके किया जा सकता है।

मेमोरी-बाउंड फ़ंक्शंस और मेमोरी फ़ंक्शंस

मेमोरी-बाउंड फ़ंक्शंस और मेमोरी फ़ंक्शंस संबंधित हैं जिसमें दोनों में व्यापक मेमोरी एक्सेस सम्मिलित है, लेकिन दोनों के बीच एक अंतर सम्मिलित है।

मेमोरी फ़ंक्शंस एक गतिक क्रमादेशन तकनीक का उपयोग करते हैं जिसे मेमोइज़ेशन कहा जाता है जिससे कि पुनरावर्तन की अक्षमता को दूर किया जा सके। यह उप-समस्याओं के समाधान की गणना और भंडारण के सरल विचार पर आधारित है जिससे कि बाद में इष्टतम उप-संरचना को फिर से गणना किए बिना समाधानों का पुन: उपयोग किया जा सके। मेमोइज़ेशन का लाभ उठाने वाला सबसे प्रसिद्ध उदाहरण कलन विधि है जो फाइबोनैचि संख्याओं की गणना करता है। निम्नलिखित स्यूडोकोड पुनरावर्तन और संस्मरण का उपयोग करता है, और रैखिक सीपीयू समय में चलता है:Index.php?title=रैखिक समय

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

उपरोक्त की तुलना एल्गोरिदम से करें जो केवल रिकर्सन का उपयोग करता है, और घातीय समय सीपीयू समय में चलता है:

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

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

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

स्पैम को रोकने के लिए मेमोरी-बाउंड फ़ंक्शंस का उपयोग करना

मेमोरी-बाउंड फ़ंक्शंस प्रूफ-ऑफ़-वर्क सिस्टम में उपयोगी हो सकते हैं जो स्पैम को रोक सकता है, इंटरनेट पर संक्रामक के अनुपात की समस्या बन गया है।

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

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

दुरुपयोग से बचाने वाली मूल योजना इस प्रकार है:
S को प्रेषक, R को प्राप्तकर्ता और M एक ई-मेल है। यदि R, S से ई-मेल प्राप्त करने के लिए पहले से सहमत हैं , तब M सामान्य तरीके से प्रेषित किया जाता है। अन्यथा, S कुछ फ़ंक्शन G(M) की गणना करता है R को (M, G(M)) भेजता है। यदि हाँ, R, M. को स्वीकार करता है। अन्यथा, R, M को अस्वीकार करता है। दाईं ओर का आंकड़ा उन स्थितियों को दर्शाता है जिनमें कोई पूर्व समझौता नहीं था।

फ़ंक्शन G() का चयन इस प्रकार किया जाता है कि R द्वारा सत्यापन अपेक्षाकृत तेज़ (मिलीसेकंड लेते हुए) होता है और ऐसा होता है कि S द्वारा गणना द्वारा कुछ धीमी होती है (कम से कम कई सेकंड सम्मिलित होते हैं)। इसलिए, S को बिना किसी पूर्व समझौते के कई प्राप्तकर्ताओं को M भेजने से निराशजनक किया जाएगा: कंप्यूटिंग के समय और कंप्यूटिंग संसाधनों दोनों के संदर्भ में लागत G() स्पैमर के लिए बार-बार बहुत निषेधात्मक हो जाएगी जो कई मिलियन ई-मेल भेजने का इरादा रखता है।

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

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

यह भी देखें

• कंप्यूटर आर्किटेक्चर
• सीपीयू-बाउंड
• गतिशील प्रोग्रामिंग
• I/O बाउंड
• संस्मरण
• मेमोरी-हार्ड फ़ंक्शन
• इष्टतम सबस्ट्रक्चर
• कार्य का प्रमाण
• पुनरावर्तन
• मेमोरी बाधा

संदर्भ

• Abadi, M., Burrows, M., Manasse, M., & Wobber, T. (2005, May). Moderately Hard, Memory-bound Functions, ACM Transactions on Internet Technology.
• Dwork, C., Goldberg, A., & Naor, M. (2003). On Memory-Bound Functions for Fighting Spam, Advances in Cryptology.
• Hellman, M. E. (1980). A Cryptanalytic Time-Memory Trade Off, IEEE Transactionson Information Theory.

बाहरी संबंध

• Implementation of a Memory Bound function
• Computer Architecture
• How Computer Memory Works
• Dynamic Programming
• सीपीयू Bound vs. I/O Bound
• Spam – FTC Consumer Information