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

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

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

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

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

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

 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
 }

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

• कंप्यूटर आर्किटेक्चर
• सीपीयू-बाध्य
• गतिशील प्रोग्रामिंग
• I/O बाउंड|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
• CPU Bound vs. I/O Bound
• Spam – FTC Consumer Information