कॉन्करेन्ट हैश टेबल: Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
[[File:Concurent hashtable.svg|thumb|310px|right|समान हैश तालिका तक कंकररेंट एक्सेस।]]'''कंकररेंट (कंकररेंट) हैश टेबल''' या '''कंकररेंट हैश मैप''' हैश टेबल्स का कार्यान्वयन है जो [[हैश फंकशन]] का उपयोग करके एकाधिक थ्रेड्स द्वारा कंकररेंट एक्सेस की अनुमति देता है।<ref name="maier">{{cite journal | last1 = Maier | first1 = Tobias| last2 = Sanders| first2 = Peter| last3 = Dementiev| first3 = Roman| date = March 2019| title = Concurrent Hash Tables: Fast and General(?)! | journal = ACM Transactions on Parallel Computing | volume = 5 | issue = 4 | at = Article 16 | doi = 10.1145/3309206 | publisher = ACM | location = New York, NY, USA | s2cid = 67870641 | issn = 2329-4949}}</ref><ref name="shun">{{cite conference | last1 = Shun | first1 = Julian | last2 = Blelloch | first2 = Guy E. | year = 2014 | title = नियतत्ववाद के लिए चरण-समवर्ती हैश तालिकाएँ| book-title = SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures | isbn = 978-1-4503-2821-0 | pages = 96–107 | doi = 10.1145/2612669.2612687 | publisher = ACM |location=New York
[[File:Concurent hashtable.svg|thumb|310px|right|समान हैश टेबल तक कंकररेंट एक्सेस।]]'''कंकररेंट (कंकररेंट) हैश टेबल''' या '''कंकररेंट हैश मैप''' हैश टेबल्स का कार्यान्वयन है जो [[हैश फंकशन]] का उपयोग करके एकाधिक थ्रेड्स द्वारा कंकररेंट एक्सेस की अनुमति देता है।<ref name="maier">{{cite journal | last1 = Maier | first1 = Tobias| last2 = Sanders| first2 = Peter| last3 = Dementiev| first3 = Roman| date = March 2019| title = Concurrent Hash Tables: Fast and General(?)! | journal = ACM Transactions on Parallel Computing | volume = 5 | issue = 4 | at = Article 16 | doi = 10.1145/3309206 | publisher = ACM | location = New York, NY, USA | s2cid = 67870641 | issn = 2329-4949}}</ref><ref name="shun">{{cite conference | last1 = Shun | first1 = Julian | last2 = Blelloch | first2 = Guy E. | year = 2014 | title = नियतत्ववाद के लिए चरण-समवर्ती हैश तालिकाएँ| book-title = SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures | isbn = 978-1-4503-2821-0 | pages = 96–107 | doi = 10.1145/2612669.2612687 | publisher = ACM |location=New York
}}</ref>
}}</ref>


कंकररेंट हैश तालिकाएँ [[समवर्ती कंप्यूटिंग|कंकररेंट कंप्यूटिंग]] में उपयोग के लिए एक प्रमुख [[समवर्ती डेटा संरचना|कंकररेंट डेटा संरचना]] का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।<ref name="maier" />
कंकररेंट हैश टेबल्स [[समवर्ती कंप्यूटिंग|कंकररेंट कंप्यूटिंग]] में उपयोग के लिए एक प्रमुख [[समवर्ती डेटा संरचना|कंकररेंट डेटा संरचना]] का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।<ref name="maier" />


कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से तालिका को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग [[ओवरहेड (कंप्यूटिंग)|ओवरहेड]] का उत्पादन होता है।<ref name="maier" /> विवाद के प्रभावों को कम करने के लिए कई समाधान मौजूद हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।<ref name="maier" /><ref name="shun" /><ref name="Li">
कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से टेबल को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग [[ओवरहेड (कंप्यूटिंग)|ओवरहेड]] का उत्पादन होता है।<ref name="maier" /> विवाद के प्रभावों को कम करने के लिए कई समाधान मौजूद हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।<ref name="maier" /><ref name="shun" /><ref name="Li">
{{cite conference | last1 = Li | first1 = Xiaozhou | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | last4 = Freedman | first4 = Michael J. | year = 2014 | title = Algorithmic Improvements for Fast Concurrent Cuckoo Hashing | book-title = Proceedings of the Ninth European Conference on Computer Systems | conference = EuroSys '14 | isbn = 978-1-4503-2704-6 | at = Article No. 27 | doi = 10.1145/2592798.2592820 | publisher = ACM |location=New York}}</ref><ref name="Triplett">
{{cite conference | last1 = Li | first1 = Xiaozhou | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | last4 = Freedman | first4 = Michael J. | year = 2014 | title = Algorithmic Improvements for Fast Concurrent Cuckoo Hashing | book-title = Proceedings of the Ninth European Conference on Computer Systems | conference = EuroSys '14 | isbn = 978-1-4503-2704-6 | at = Article No. 27 | doi = 10.1145/2592798.2592820 | publisher = ACM |location=New York}}</ref><ref name="Triplett">
{{cite conference | last1 = Triplett | first1 = Josh  | last2 = McKenney | first2 = Paul E. | last3 = Walpole | first3 = Jonathan | year = 2011 | title = Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming | url = http://dl.acm.org/citation.cfm?id=2002181.2002192 | book-title = USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference | page = 11 | publisher = USENIX Association |location=Berkeley, CA}}</ref>
{{cite conference | last1 = Triplett | first1 = Josh  | last2 = McKenney | first2 = Paul E. | last3 = Walpole | first3 = Jonathan | year = 2011 | title = Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming | url = http://dl.acm.org/citation.cfm?id=2002181.2002192 | book-title = USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference | page = 11 | publisher = USENIX Association |location=Berkeley, CA}}</ref>
Line 10: Line 10:
उनके अनुक्रमिक समकक्ष के साथ, कंकररेंट हैश तालिकाओं को सामान्यीकृत किया जा सकता है और व्यापक अनुप्रयोगों में फिट करने के लिए विस्तारित किया जा सकता है, जैसे कि कुंजी और मूल्यों के लिए अधिक जटिल डेटा प्रकारों का उपयोग करने की अनुमति देना। हालाँकि, ये सामान्यीकरण प्रदर्शन पर नकारात्मक प्रभाव डाल सकते हैं और इस प्रकार इन्हें एप्लिकेशन की आवश्यकताओं के अनुसार चुना जाना चाहिए।<ref name="maier" />
उनके अनुक्रमिक समकक्ष के साथ, कंकररेंट हैश तालिकाओं को सामान्यीकृत किया जा सकता है और व्यापक अनुप्रयोगों में फिट करने के लिए विस्तारित किया जा सकता है, जैसे कि कुंजी और मूल्यों के लिए अधिक जटिल डेटा प्रकारों का उपयोग करने की अनुमति देना। हालाँकि, ये सामान्यीकरण प्रदर्शन पर नकारात्मक प्रभाव डाल सकते हैं और इस प्रकार इन्हें एप्लिकेशन की आवश्यकताओं के अनुसार चुना जाना चाहिए।<ref name="maier" />
==कंकररेंट हैशिंग==
==कंकररेंट हैशिंग==
कंकररेंट हैश तालिकाएँ बनाते समय, चुने हुए हैशिंग एल्गोरिदम के साथ तालिका तक पहुँचने वाले कार्यों को एक संघर्ष समाधान रणनीति जोड़कर कंकररेंट के लिए अनुकूलित करने की आवश्यकता होती है। इस तरह की रणनीति के लिए एक्सेस को इस तरह से प्रबंधित करने की आवश्यकता होती है कि उनके कारण होने वाले टकराव के परिणामस्वरूप भ्रष्ट डेटा न हो, जबकि समानांतर में उपयोग किए जाने पर आदर्श रूप से उनकी दक्षता बढ़ जाती है।
कंकररेंट हैश टेबल्स बनाते समय, चुने हुए हैशिंग एल्गोरिथ्म के साथ टेबल तक पहुँचने वाले कार्यों को एक संघर्ष समाधान रणनीति जोड़कर कंकररेंट के लिए अनुकूलित करने की आवश्यकता होती है। इस तरह की रणनीति के लिए एक्सेस को इस तरह से प्रबंधित करने की आवश्यकता होती है कि उनके कारण होने वाले टकराव के परिणामस्वरूप भ्रष्ट डेटा न हो, जबकि आदर्श रूप से समानांतर में उपयोग किए जाने पर उनकी दक्षता बढ़ जाती है। हेर्लिही और शेविट[<ref>{{cite book |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |title=मल्टीप्रोसेसर प्रोग्रामिंग की कला|year=2008 |publisher=Morgan Kaufmann Publishers Inc. |location=San Francisco, CA, USA |isbn=978-0-12-370591-4 |pages=316–325 |chapter=Chapter 13: Concurrent Hashing and Natural Parallelism}}</ref> वर्णन करते हैं कि इस तरह की रणनीति के बिना हैश टेबल तक कैसे पहुंच बनाई जाती है - इसके उदाहरण में कुक्कू हैशिंग एल्गोरिदम के बुनियादी कार्यान्वयन पर आधारित है - कंकररेंट उपयोग फैन एट अल के लिए अनुकूलित किया जा सकता है।<ref name="Fan">{{cite conference | last1 = Fan | first1 = Bin | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | year = 2013 | title = MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing | url = http://dl.acm.org/citation.cfm?id=2482626.2482662 | book-title = nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation | pages = 371–384 | publisher = USENIX Association |location=Berkeley, CA}}</ref> इसके अलावा, कुक्कू हैशिंग पर आधारित एक टेबल एक्सेस योजना का वर्णन करें जो न केवल कंकररेंट है बल्कि कैश इलाके के साथ-साथ सम्मिलन के थ्रूपुट में सुधार करते हुए अपने हैशिंग फ़ंक्शन की स्पेस दक्षता को भी बनाए रखती है।
हेर्लिही और शेविट<ref>{{cite book |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |title=मल्टीप्रोसेसर प्रोग्रामिंग की कला|year=2008 |publisher=Morgan Kaufmann Publishers Inc. |location=San Francisco, CA, USA |isbn=978-0-12-370591-4 |pages=316–325 |chapter=Chapter 13: Concurrent Hashing and Natural Parallelism}}</ref> वर्णन करें कि इस तरह की रणनीति के बिना हैश तालिका तक पहुंच को कैसे - [[कोयल हैशिंग]] एल्गोरिदम के बुनियादी कार्यान्वयन के आधार पर इसके उदाहरण में - कंकररेंट उपयोग के लिए अनुकूलित किया जा सकता है। फैन एट अल.<ref name="Fan">{{cite conference | last1 = Fan | first1 = Bin | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | year = 2013 | title = MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing | url = http://dl.acm.org/citation.cfm?id=2482626.2482662 | book-title = nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation | pages = 371–384 | publisher = USENIX Association |location=Berkeley, CA}}</ref>
आगे कुक्कू हैशिंग पर आधारित एक टेबल एक्सेस योजना का वर्णन करें जो न केवल कंकररेंट है, बल्कि कैश लोकैलिटी के साथ-साथ सम्मिलन के थ्रूपुट में सुधार करते हुए इसके हैशिंग फ़ंक्शन की स्पेस दक्षता को भी बनाए रखती है।


जब हैश टेबल आकार में बंधे नहीं होते हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें संशोधित तालिका के नए कुंजी-स्थान को प्रतिबिंबित करने के लिए उपयोग किए गए हैश फ़ंक्शन को संशोधित करना शामिल है। मैयर एट अल द्वारा एक कंकररेंट बढ़ते एल्गोरिदम का वर्णन किया गया है।<ref name="maier" />
जब हैश टेबल्स आकार में बंधी नहीं होती हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें परिवर्तित टेबल के नए कुंजी स्थान को प्रतिबिंबित करने के लिए प्रयुक्त हैश फ़ंक्शन को संशोधित करना शामिल है। एक कंकररेंट बढ़ते एल्गोरिथ्म का वर्णन मैयर एट अल द्वारा किया गया है।<ref name="maier" />
 
मेगा के.वी<ref>Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "[http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-15-1.pdf Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores".] Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.</ref> एक उच्च प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और [[ओक रिज नेशनल लैब]] द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।<ref>Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla;  Imam, Neenaand; and Newburn, Chris J.  (2018) "[https://www.csm.ornl.gov/workshops/openshmem2018/presentations/openshmem2018-NVIDIA-ORNL.pdf Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM".].</ref>


मेगा-केवी <ref>Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "[http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-15-1.pdf Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores".] Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.</ref> एक उच्च-प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और [[ओक रिज नेशनल लैब]] द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।<ref>Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla;  Imam, Neenaand; and Newburn, Chris J.  (2018) "[https://www.csm.ornl.gov/workshops/openshmem2018/presentations/openshmem2018-NVIDIA-ORNL.pdf Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM".].</ref>


==विवाद प्रबंधन==
==विवाद प्रबंधन==
[[File:Concurrent hashtable conflict.svg|thumb|310px|right|कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।]]किसी भी कंकररेंट डेटा संरचना की तरह, कंकररेंट हैश तालिकाएँ विवाद के परिणामस्वरूप कंकररेंट कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।<ref name="Li" />इसके उदाहरण [[एबीए समस्या]], [[दौड़ की स्थिति]] और [[गतिरोध]] हैं।
[[File:Concurrent hashtable conflict.svg|thumb|310px|right|कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।]]किसी भी कंकररेंट डेटा संरचना की तरह, कंकररेंट हैश टेबल्स विवाद के परिणामस्वरूप कंकररेंट कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।<ref name="Li" />इसके उदाहरण [[एबीए समस्या]], [[दौड़ की स्थिति]] और [[गतिरोध]] हैं।
ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह कंकररेंट हैश तालिका के कार्यान्वयन पर निर्भर करता है; विशेष रूप से तालिका किस संचालन को कंकररेंट रूप से चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी भी अन्य कंकररेंट डेटा संरचना के समान होता है, अर्थात् तालिका पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि कंकररेंट रूप से उपयोग किए जाने पर अनुक्रमिक समाधान की तुलना में यह अधिक कुशल हो। इसे कंकररेंट नियंत्रण के रूप में भी जाना जाता है।
ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह कंकररेंट हैश टेबल के कार्यान्वयन पर निर्भर करता है; विशेष रूप से टेबल किस संचालन को कंकररेंट रूप से चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी भी अन्य कंकररेंट डेटा संरचना के समान होता है, अर्थात् टेबल पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि कंकररेंट रूप से उपयोग किए जाने पर अनुक्रमिक समाधान की तुलना में यह अधिक कुशल हो। इसे कंकररेंट नियंत्रण के रूप में भी जाना जाता है।


===परमाणु निर्देश===
===परमाणु निर्देश===
तुलना-और-स्वैप या [[लाएँ-और-जोड़ें]] जैसे [[परमाणु (कंप्यूटर विज्ञान)]] [[निर्देश (कंप्यूटर विज्ञान)]] का उपयोग करके, विवाद के कारण होने वाली समस्याओं को यह सुनिश्चित करके कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक एक्सेस पूरा हो जाता है। तुलना-और-स्वैप जैसे ऑपरेशन अक्सर सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि तालिका के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।<ref name="maier" />
तुलना-और-स्वैप या [[लाएँ-और-जोड़ें]] जैसे [[परमाणु (कंप्यूटर विज्ञान)]] [[निर्देश (कंप्यूटर विज्ञान)]] का उपयोग करके, विवाद के कारण होने वाली समस्याओं को यह सुनिश्चित करके कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक एक्सेस पूरा हो जाता है। तुलना-और-स्वैप जैसे ऑपरेशन अक्सर सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि टेबल के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।<ref name="maier" />


तथाकथित हार्डवेयर [[ लेन-देन संबंधी स्मृति ]] (एचटीएम) का उपयोग करके, टेबल संचालन को काफी हद तक [[डेटाबेस लेनदेन]] की तरह सोचा जा सकता है,<ref name="Li" />परमाणुता सुनिश्चित करना। व्यवहार में HTM का एक उदाहरण [[लेन-देन तुल्यकालन एक्सटेंशन]] हैं।
तथाकथित हार्डवेयर [[ लेन-देन संबंधी स्मृति ]] (एचटीएम) का उपयोग करके, टेबल संचालन को काफी हद तक [[डेटाबेस लेनदेन]] की तरह सोचा जा सकता है,<ref name="Li" />परमाणुता सुनिश्चित करना। व्यवहार में HTM का एक उदाहरण [[लेन-देन तुल्यकालन एक्सटेंशन]] हैं।


===लॉकिंग===
===लॉकिंग===
[[लॉक (कंप्यूटर विज्ञान)]] की मदद से, तालिका या उसके भीतर मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,<ref name="maier" /><ref name="Fan" />विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, तो इस प्रकार उन पहुंचों को अवरुद्ध कर दिया जाता है जो अन्यथा प्रतिस्पर्धा नहीं कर सकतीं और बिना किसी समस्या के निष्पादित हो सकती हैं। लाइवलॉक, डेडलॉक या [[भुखमरी (कंप्यूटर विज्ञान)]] जैसी और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं।<ref name="Li" />
[[लॉक (कंप्यूटर विज्ञान)]] की मदद से, टेबल या उसके भीतर मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,<ref name="maier" /><ref name="Fan" />विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, तो इस प्रकार उन पहुंचों को अवरुद्ध कर दिया जाता है जो अन्यथा प्रतिस्पर्धा नहीं कर सकतीं और बिना किसी समस्या के निष्पादित हो सकती हैं। लाइवलॉक, डेडलॉक या [[भुखमरी (कंप्यूटर विज्ञान)]] जैसी और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं।<ref name="Li" />




===चरण कंकररेंट===
===चरण कंकररेंट===
[[File:Phase concurrent hashtable.svg|thumb|310px|right|कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।]]एक चरण कंकररेंट हैश तालिका समूह चरण बनाकर पहुँचता है जिसमें केवल एक प्रकार के ऑपरेशन की अनुमति होती है (यानी एक शुद्ध लेखन-चरण), इसके बाद सभी थ्रेड्स में तालिका स्थिति का सिंक्रनाइज़ेशन (कंप्यूटर विज्ञान) होता है। इसके लिए एक औपचारिक रूप से सिद्ध एल्गोरिदम शुन और ब्लेलोच द्वारा दिया गया है।<ref name="shun" />
[[File:Phase concurrent hashtable.svg|thumb|310px|right|कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।]]एक चरण कंकररेंट हैश टेबल समूह चरण बनाकर पहुँचता है जिसमें केवल एक प्रकार के ऑपरेशन की अनुमति होती है (यानी एक शुद्ध लेखन-चरण), इसके बाद सभी थ्रेड्स में टेबल स्थिति का सिंक्रनाइज़ेशन (कंप्यूटर विज्ञान) होता है। इसके लिए एक औपचारिक रूप से सिद्ध एल्गोरिदम शुन और ब्लेलोच द्वारा दिया गया है।<ref name="shun" />




Line 46: Line 43:


==प्रदर्शन विश्लेषण==
==प्रदर्शन विश्लेषण==
मैयर एट अल.<ref name="maier" />विभिन्न कंकररेंट हैश तालिका कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-मामलों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:
मैयर एट अल.<ref name="maier" />विभिन्न कंकररेंट हैश टेबल कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-मामलों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:


{| class="wikitable"
{| class="wikitable"
Line 68: Line 65:
जैसा कि अपेक्षित था, कम विवाद हर ऑपरेशन में सकारात्मक व्यवहार की ओर ले जाता है, जबकि जब लेखन की बात आती है तो उच्च विवाद समस्याग्रस्त हो जाता है।
जैसा कि अपेक्षित था, कम विवाद हर ऑपरेशन में सकारात्मक व्यवहार की ओर ले जाता है, जबकि जब लेखन की बात आती है तो उच्च विवाद समस्याग्रस्त हो जाता है।
हालाँकि उत्तरार्द्ध सामान्य रूप से उच्च विवाद की समस्या है, जिसमें प्रतिस्पर्धी पहुंच को प्रतिबंधित करने वाले कंकररेंट नियंत्रण की प्राकृतिक आवश्यकता के कारण कंकररेंट गणना का लाभ नकार दिया जाता है। परिणामी ओवरहेड आदर्श अनुक्रमिक संस्करण की तुलना में खराब प्रदर्शन का कारण बनता है।
हालाँकि उत्तरार्द्ध सामान्य रूप से उच्च विवाद की समस्या है, जिसमें प्रतिस्पर्धी पहुंच को प्रतिबंधित करने वाले कंकररेंट नियंत्रण की प्राकृतिक आवश्यकता के कारण कंकररेंट गणना का लाभ नकार दिया जाता है। परिणामी ओवरहेड आदर्श अनुक्रमिक संस्करण की तुलना में खराब प्रदर्शन का कारण बनता है।
इसके बावजूद, ऐसे उच्च विवाद परिदृश्यों में भी कंकररेंट हैश तालिकाएँ अभी भी अमूल्य साबित होती हैं, जब यह देखा जाता है कि एक अच्छी तरह से डिज़ाइन किया गया कार्यान्वयन अभी भी डेटा को कंकररेंट रूप से पढ़ने के लिए कंकररेंट के लाभों का लाभ उठाकर बहुत उच्च गति प्राप्त कर सकता है।
इसके बावजूद, ऐसे उच्च विवाद परिदृश्यों में भी कंकररेंट हैश टेबल्स अभी भी अमूल्य साबित होती हैं, जब यह देखा जाता है कि एक अच्छी तरह से डिज़ाइन किया गया कार्यान्वयन अभी भी डेटा को कंकररेंट रूप से पढ़ने के लिए कंकररेंट के लाभों का लाभ उठाकर बहुत उच्च गति प्राप्त कर सकता है।


हालाँकि, कंकररेंट हैश तालिकाओं के वास्तविक उपयोग-मामले अक्सर एक ही ऑपरेशन के केवल अनुक्रम नहीं होते हैं, बल्कि कई प्रकारों का मिश्रण होते हैं।
हालाँकि, कंकररेंट हैश तालिकाओं के वास्तविक उपयोग-मामले अक्सर एक ही ऑपरेशन के केवल अनुक्रम नहीं होते हैं, बल्कि कई प्रकारों का मिश्रण होते हैं।
जैसे, जब का मिश्रण <code>insert</code> और <code>find</code> संचालन में स्पीडअप का उपयोग किया जाता है और कंकररेंट हैश तालिकाओं की परिणामी उपयोगिता अधिक स्पष्ट हो जाती है, खासकर जब अवलोकन किया जाता है <code>find</code> भारी कार्यभार.
जैसे, जब का मिश्रण <code>insert</code> और <code>find</code> संचालन में स्पीडअप का उपयोग किया जाता है और कंकररेंट हैश तालिकाओं की परिणामी उपयोगिता अधिक स्पष्ट हो जाती है, खासकर जब अवलोकन किया जाता है <code>find</code> भारी कार्यभार.


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


==कार्यान्वयन==
==कार्यान्वयन==
Line 79: Line 76:
* {{proper name|libcuckoo}} C (प्रोग्रामिंग भाषा)/[[C++]] के लिए कंकररेंट हैश टेबल प्रदान करता है जो कंकररेंट पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी GitHub पर उपलब्ध है।<ref>[https://github.com/efficient/libcuckoo GitHub repository for libcuckoo]</ref>
* {{proper name|libcuckoo}} C (प्रोग्रामिंग भाषा)/[[C++]] के लिए कंकररेंट हैश टेबल प्रदान करता है जो कंकररेंट पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी GitHub पर उपलब्ध है।<ref>[https://github.com/efficient/libcuckoo GitHub repository for libcuckoo]</ref>
* [[थ्रेडिंग बिल्डिंग ब्लॉक्स]] C++ के लिए कंकररेंट अव्यवस्थित मानचित्र प्रदान करते हैं जो कंकररेंट प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और [[C++11]] के समान शैली में रखे जाते हैं। <code>std::unordered_map</code> इंटरफेस। इसमें कंकररेंट अव्यवस्थित मल्टीमैप्स शामिल हैं, जो कंकररेंट अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को मौजूद रहने की अनुमति देते हैं।<ref>[https://software.intel.com/en-us/node/506171 Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation]</ref> इसके अतिरिक्त, कंकररेंट हैश मानचित्र प्रदान किए जाते हैं जो कंकररेंट अव्यवस्थित मानचित्र पर निर्मित होते हैं और कंकररेंट विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग होती है।<ref>[https://software.intel.com/en-us/node/506191 Threading Building Blocks concurrent_hash_map documentation]</ref>
* [[थ्रेडिंग बिल्डिंग ब्लॉक्स]] C++ के लिए कंकररेंट अव्यवस्थित मानचित्र प्रदान करते हैं जो कंकररेंट प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और [[C++11]] के समान शैली में रखे जाते हैं। <code>std::unordered_map</code> इंटरफेस। इसमें कंकररेंट अव्यवस्थित मल्टीमैप्स शामिल हैं, जो कंकररेंट अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को मौजूद रहने की अनुमति देते हैं।<ref>[https://software.intel.com/en-us/node/506171 Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation]</ref> इसके अतिरिक्त, कंकररेंट हैश मानचित्र प्रदान किए जाते हैं जो कंकररेंट अव्यवस्थित मानचित्र पर निर्मित होते हैं और कंकररेंट विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग होती है।<ref>[https://software.intel.com/en-us/node/506191 Threading Building Blocks concurrent_hash_map documentation]</ref>
* ग्रोथ तथाकथित ''लोकगीत'' कार्यान्वयन के आधार पर C++ के लिए कंकररेंट बढ़ती हैश तालिकाएँ प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, विभिन्न प्रकार की बढ़ती हैश तालिकाएँ दी गई हैं। ये कार्यान्वयन कंकररेंट रीड, इंसर्ट, अपडेट (विशेष रूप से कुंजी पर वर्तमान मान के आधार पर मान अपडेट करना) और निष्कासन (टॉम्बस्टोन (प्रोग्रामिंग) का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, [[Intel TSX]] पर आधारित वेरिएंट उपलब्ध कराए गए हैं। लाइब्रेरी GitHub पर उपलब्ध है।<ref name="maier" /><ref>[https://github.com/TooBiased/growt GitHub repository for growt]</ref>
* ग्रोथ तथाकथित ''लोकगीत'' कार्यान्वयन के आधार पर C++ के लिए कंकररेंट बढ़ती हैश टेबल्स प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, विभिन्न प्रकार की बढ़ती हैश टेबल्स दी गई हैं। ये कार्यान्वयन कंकररेंट रीड, इंसर्ट, अपडेट (विशेष रूप से कुंजी पर वर्तमान मान के आधार पर मान अपडेट करना) और निष्कासन (टॉम्बस्टोन (प्रोग्रामिंग) का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, [[Intel TSX]] पर आधारित वेरिएंट उपलब्ध कराए गए हैं। लाइब्रेरी GitHub पर उपलब्ध है।<ref name="maier" /><ref>[https://github.com/TooBiased/growt GitHub repository for growt]</ref>
* फ़ॉली कंकररेंट हैश तालिकाएँ प्रदान करता है<ref>[https://github.com/facebook/folly/blob/master/folly/concurrency/ConcurrentHashMap.h GitHub page for implementation of concurrent hash maps in folly]</ref> [[C++14]] के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, [[शार्ड (डेटाबेस आर्किटेक्चर)]] लेखकों को सुनिश्चित करना। जैसा कि इसके GitHub पेज पर बताया गया है, यह लाइब्रेरी [[Facebook]] के लिए उपयोगी कार्यक्षमता प्रदान करती है।<ref>[https://github.com/facebook/folly GitHub repository for folly]</ref>
* फ़ॉली कंकररेंट हैश टेबल्स प्रदान करता है<ref>[https://github.com/facebook/folly/blob/master/folly/concurrency/ConcurrentHashMap.h GitHub page for implementation of concurrent hash maps in folly]</ref> [[C++14]] के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, [[शार्ड (डेटाबेस आर्किटेक्चर)]] लेखकों को सुनिश्चित करना। जैसा कि इसके GitHub पेज पर बताया गया है, यह लाइब्रेरी [[Facebook]] के लिए उपयोगी कार्यक्षमता प्रदान करती है।<ref>[https://github.com/facebook/folly GitHub repository for folly]</ref>
* जंक्शन तालिका के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश तालिकाओं के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी GitHub पर उपलब्ध है।<ref>[https://github.com/preshing/junction GitHub repository for Junction]</ref>
* जंक्शन टेबल के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश तालिकाओं के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी GitHub पर उपलब्ध है।<ref>[https://github.com/preshing/junction GitHub repository for Junction]</ref>




Revision as of 16:34, 19 July 2023

समान हैश टेबल तक कंकररेंट एक्सेस।

कंकररेंट (कंकररेंट) हैश टेबल या कंकररेंट हैश मैप हैश टेबल्स का कार्यान्वयन है जो हैश फंकशन का उपयोग करके एकाधिक थ्रेड्स द्वारा कंकररेंट एक्सेस की अनुमति देता है।[1][2]

कंकररेंट हैश टेबल्स कंकररेंट कंप्यूटिंग में उपयोग के लिए एक प्रमुख कंकररेंट डेटा संरचना का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।[1]

कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से टेबल को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग ओवरहेड का उत्पादन होता है।[1] विवाद के प्रभावों को कम करने के लिए कई समाधान मौजूद हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।[1][2][3][4]

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

कंकररेंट हैशिंग

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

जब हैश टेबल्स आकार में बंधी नहीं होती हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें परिवर्तित टेबल के नए कुंजी स्थान को प्रतिबिंबित करने के लिए प्रयुक्त हैश फ़ंक्शन को संशोधित करना शामिल है। एक कंकररेंट बढ़ते एल्गोरिथ्म का वर्णन मैयर एट अल द्वारा किया गया है।[1]

मेगा-केवी [7] एक उच्च-प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और ओक रिज नेशनल लैब द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।[8]

विवाद प्रबंधन

कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।

किसी भी कंकररेंट डेटा संरचना की तरह, कंकररेंट हैश टेबल्स विवाद के परिणामस्वरूप कंकररेंट कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।[3]इसके उदाहरण एबीए समस्या, दौड़ की स्थिति और गतिरोध हैं।

ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह कंकररेंट हैश टेबल के कार्यान्वयन पर निर्भर करता है; विशेष रूप से टेबल किस संचालन को कंकररेंट रूप से चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी भी अन्य कंकररेंट डेटा संरचना के समान होता है, अर्थात् टेबल पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि कंकररेंट रूप से उपयोग किए जाने पर अनुक्रमिक समाधान की तुलना में यह अधिक कुशल हो। इसे कंकररेंट नियंत्रण के रूप में भी जाना जाता है।

परमाणु निर्देश

तुलना-और-स्वैप या लाएँ-और-जोड़ें जैसे परमाणु (कंप्यूटर विज्ञान) निर्देश (कंप्यूटर विज्ञान) का उपयोग करके, विवाद के कारण होने वाली समस्याओं को यह सुनिश्चित करके कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक एक्सेस पूरा हो जाता है। तुलना-और-स्वैप जैसे ऑपरेशन अक्सर सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि टेबल के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।[1]

तथाकथित हार्डवेयर लेन-देन संबंधी स्मृति (एचटीएम) का उपयोग करके, टेबल संचालन को काफी हद तक डेटाबेस लेनदेन की तरह सोचा जा सकता है,[3]परमाणुता सुनिश्चित करना। व्यवहार में HTM का एक उदाहरण लेन-देन तुल्यकालन एक्सटेंशन हैं।

लॉकिंग

लॉक (कंप्यूटर विज्ञान) की मदद से, टेबल या उसके भीतर मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,[1][6]विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, तो इस प्रकार उन पहुंचों को अवरुद्ध कर दिया जाता है जो अन्यथा प्रतिस्पर्धा नहीं कर सकतीं और बिना किसी समस्या के निष्पादित हो सकती हैं। लाइवलॉक, डेडलॉक या भुखमरी (कंप्यूटर विज्ञान) जैसी और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं।[3]


चरण कंकररेंट

कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।

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


पढ़ें-कॉपी-अपडेट

लिनक्स कर्नेल के भीतर व्यापक रूप से उपयोग किया जाता है,[3]पढ़ें-कॉपी-अपडेट करें (आरसीयू) उन मामलों में विशेष रूप से उपयोगी है जहां पढ़ने की संख्या लिखने की संख्या से कहीं अधिक है।[4]


अनुप्रयोग

स्वाभाविक रूप से, जहां भी अनुक्रमिक हैश तालिकाएं उपयोगी होती हैं, वहां कंकररेंट हैश तालिकाओं का अनुप्रयोग होता है। यहां समवर्तीता से जो लाभ मिलता है, वह इन उपयोग-मामलों की संभावित गति के साथ-साथ बढ़ी हुई स्केलेबिलिटी में निहित है।[1]मल्टी-कोर प्रोसेसर जैसे हार्डवेयर को ध्यान में रखते हुए जो कंकररेंट गणना करने में अधिक सक्षम हो जाते हैं, इन अनुप्रयोगों के भीतर कंकररेंट डेटा संरचनाओं का महत्व लगातार बढ़ता है।[3]


प्रदर्शन विश्लेषण

मैयर एट अल.[1]विभिन्न कंकररेंट हैश टेबल कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-मामलों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:

Operation Contention Notes
Low High
find अद्वितीय खोजों के सफल और असफल दोनों होने पर बहुत तेज़ स्पीडअप, यहां तक ​​​​कि बहुत उच्च विवाद के साथ भी
insert उच्च स्पीडअप तक पहुंच गया, उच्च विवाद तब समस्याग्रस्त हो जाता है जब कुंजियाँ एक से अधिक मान रख सकती हैं (अन्यथा यदि कुंजी पहले से मौजूद है तो आवेषण को आसानी से खारिज कर दिया जाता है)
update जब विवाद कम रखा जाता है तो ओवरराइट और मौजूदा मूल्यों के संशोधन दोनों उच्च गति तक पहुंचते हैं, अन्यथा अनुक्रमिक से भी बदतर प्रदर्शन करते हैं
delete चरण संगामिति उच्चतम मापनीयता पर पहुंच गई; पूरी तरह से कंकररेंट कार्यान्वयन जहां delete उपयोग update समाधि का पत्थर (प्रोग्रामिंग) के साथ|डमी-तत्व काफी पीछे थे

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

हालाँकि, कंकररेंट हैश तालिकाओं के वास्तविक उपयोग-मामले अक्सर एक ही ऑपरेशन के केवल अनुक्रम नहीं होते हैं, बल्कि कई प्रकारों का मिश्रण होते हैं। जैसे, जब का मिश्रण insert और find संचालन में स्पीडअप का उपयोग किया जाता है और कंकररेंट हैश तालिकाओं की परिणामी उपयोगिता अधिक स्पष्ट हो जाती है, खासकर जब अवलोकन किया जाता है find भारी कार्यभार.

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

कार्यान्वयन

  • जावा (प्रोग्रामिंग भाषा) 1.5 के बाद से, कंकररेंट हैश मानचित्र जावा कंकररेंट मानचित्र के आधार पर प्रदान किए जाते हैं।[9]
  • libcuckoo C (प्रोग्रामिंग भाषा)/C++ के लिए कंकररेंट हैश टेबल प्रदान करता है जो कंकररेंट पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी GitHub पर उपलब्ध है।[10]
  • थ्रेडिंग बिल्डिंग ब्लॉक्स C++ के लिए कंकररेंट अव्यवस्थित मानचित्र प्रदान करते हैं जो कंकररेंट प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और C++11 के समान शैली में रखे जाते हैं। std::unordered_map इंटरफेस। इसमें कंकररेंट अव्यवस्थित मल्टीमैप्स शामिल हैं, जो कंकररेंट अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को मौजूद रहने की अनुमति देते हैं।[11] इसके अतिरिक्त, कंकररेंट हैश मानचित्र प्रदान किए जाते हैं जो कंकररेंट अव्यवस्थित मानचित्र पर निर्मित होते हैं और कंकररेंट विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग होती है।[12]
  • ग्रोथ तथाकथित लोकगीत कार्यान्वयन के आधार पर C++ के लिए कंकररेंट बढ़ती हैश टेबल्स प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, विभिन्न प्रकार की बढ़ती हैश टेबल्स दी गई हैं। ये कार्यान्वयन कंकररेंट रीड, इंसर्ट, अपडेट (विशेष रूप से कुंजी पर वर्तमान मान के आधार पर मान अपडेट करना) और निष्कासन (टॉम्बस्टोन (प्रोग्रामिंग) का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, Intel TSX पर आधारित वेरिएंट उपलब्ध कराए गए हैं। लाइब्रेरी GitHub पर उपलब्ध है।[1][13]
  • फ़ॉली कंकररेंट हैश टेबल्स प्रदान करता है[14] C++14 के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, शार्ड (डेटाबेस आर्किटेक्चर) लेखकों को सुनिश्चित करना। जैसा कि इसके GitHub पेज पर बताया गया है, यह लाइब्रेरी Facebook के लिए उपयोगी कार्यक्षमता प्रदान करती है।[15]
  • जंक्शन टेबल के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश तालिकाओं के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी GitHub पर उपलब्ध है।[16]


यह भी देखें

संदर्भ

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 Maier, Tobias; Sanders, Peter; Dementiev, Roman (March 2019). "Concurrent Hash Tables: Fast and General(?)!". ACM Transactions on Parallel Computing. New York, NY, USA: ACM. 5 (4). Article 16. doi:10.1145/3309206. ISSN 2329-4949. S2CID 67870641.
  2. ↑ 2.0 2.1 2.2 Shun, Julian; Blelloch, Guy E. (2014). "नियतत्ववाद के लिए चरण-समवर्ती हैश तालिकाएँ". SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures. New York: ACM. pp. 96–107. doi:10.1145/2612669.2612687. ISBN 978-1-4503-2821-0.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Li, Xiaozhou; Andersen, David G.; Kaminsky, Michael; Freedman, Michael J. (2014). "Algorithmic Improvements for Fast Concurrent Cuckoo Hashing". Proceedings of the Ninth European Conference on Computer Systems. EuroSys '14. New York: ACM. Article No. 27. doi:10.1145/2592798.2592820. ISBN 978-1-4503-2704-6.
  4. ↑ 4.0 4.1 Triplett, Josh; McKenney, Paul E.; Walpole, Jonathan (2011). "Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming". USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference. Berkeley, CA: USENIX Association. p. 11.
  5. ↑ Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". मल्टीप्रोसेसर प्रोग्रामिंग की कला. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 316–325. ISBN 978-0-12-370591-4.
  6. ↑ 6.0 6.1 Fan, Bin; Andersen, David G.; Kaminsky, Michael (2013). "MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing". nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association. pp. 371–384.
  7. ↑ Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores". Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.
  8. ↑ Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla; Imam, Neenaand; and Newburn, Chris J. (2018) "Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM"..
  9. ↑ Java ConcurrentHashMap documentation
  10. ↑ GitHub repository for libcuckoo
  11. ↑ Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation
  12. ↑ Threading Building Blocks concurrent_hash_map documentation
  13. ↑ GitHub repository for growt
  14. ↑ GitHub page for implementation of concurrent hash maps in folly
  15. ↑ GitHub repository for folly
  16. ↑ GitHub repository for Junction


अग्रिम पठन

  • Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 299–328. ISBN 978-0-12-370591-4.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कॉन्करेन्ट_हैश_टेबल&oldid=229567’