डायरेक्टरी बेस्ड कैशे कोहेरेन्स: Difference between revisions

From Vigyanwiki
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Scalable coherance technique}}
{{Short description|Scalable coherance technique}}


[[कंप्यूटर इंजीनियरिंग]] में, '''डायरेक्टरी-आधारित कैश कोहेरेंस''' एक प्रकार का कैश कोहेरेंस तंत्र है, जहां बस स्नूपिंग के स्थान पर कैश को प्रबंधित करने के लिए निर्देशिकाओं का उपयोग किया जाता है। [[ प्रसारण (नेटवर्किंग) |प्रसारण (नेटवर्किंग)]] के उपयोग के कारण [[बस जासूसी|बस स्नूपिंग]] के विधि की व्यर्थ माप पर हैं। इन विधियों का उपयोग कंप्यूटर के प्रदर्शन और निर्देशिका सिस्टम की [[ scalability |स्केलेबिलिटी]] दोनों को लक्षित करने के लिए किया जा सकता है।<ref name=CMPAMDUWPaper>{{Cite journal|last1=Reihnhart|first1=Steven|last2=Basu|first2=Arkaprava|last3=Beckmann|first3=Bradford|last4=Hill|first4=Mark|date=2013-07-11|title=CMP Directory Coherence: One Granularity Does Not Fit All|url=http://research.cs.wisc.edu/multifacet/papers/tr1798_region_coherence.pdf}}</ref>
[[कंप्यूटर इंजीनियरिंग]] में, '''डायरेक्टरी-बेस्ड कैशे कोहेरेंस''' एक प्रकार का कैशे कोहेरेंस तंत्र है, जहां बस स्नूपिंग के स्थान पर कैशे को प्रबंधित करने के लिए डायरेक्टरीओं का उपयोग किया जाता है। [[ प्रसारण (नेटवर्किंग) |प्रसारण (नेटवर्किंग)]] के उपयोग के कारण बस स्नूपिंग के विधि की व्यर्थ माप पर हैं। इन विधियों का उपयोग कंप्यूटर के प्रदर्शन और डायरेक्टरी सिस्टम की स्केलेबिलिटी दोनों को लक्षित करने के लिए किया जा सकता है।<ref name=CMPAMDUWPaper>{{Cite journal|last1=Reihnhart|first1=Steven|last2=Basu|first2=Arkaprava|last3=Beckmann|first3=Bradford|last4=Hill|first4=Mark|date=2013-07-11|title=CMP Directory Coherence: One Granularity Does Not Fit All|url=http://research.cs.wisc.edu/multifacet/papers/tr1798_region_coherence.pdf}}</ref>


== पूर्ण बिट वेक्टर प्रारूप ==
== फुल बिट वेक्टर फॉर्मेट ==
[[File:Full bit vector format diagram.jpg|thumb|पूर्ण बिट वेक्टर निर्देशिका प्रारूप का आरेख, जहां ई=अनन्य, एस=साझा, एम=संशोधित, और यू=अनकैश्ड]]इस प्रकार से पूर्ण [[ अंश |बिट]] वेक्टर प्रारूप में, कंप्यूटर मेमोरी में प्रत्येक संभावित [[कैश लाइन]] के लिए, एक बिट का उपयोग यह ट्रैक करने के लिए किया जाता है कि क्या प्रत्येक व्यक्तिगत [[सेंट्रल प्रोसेसिंग यूनिट]] में वह लाइन उसके [[कैश (कंप्यूटिंग)]] में संग्रहीत है।<ref name=SolihinBook2015>{{Cite book|title=समानांतर मल्टीकोर आर्किटेक्चर के मूल सिद्धांत|last=Solihin|first=Yan|publisher=Solihin Publishing and Consulting, LLC|date=2015-10-09|isbn=978-1-4822-1118-4|location=Raleigh, North Carolina|pages=331–335}}</ref> और पूर्ण बिट वेक्टर प्रारूप प्रयुक्त करने के लिए अधिक सरल संरचना है, किन्तु सबसे कम स्केलेबल है।<ref name=CMPAMDUWPaper/> [[एसजीआई उत्पत्ति 2000]] प्रोसेसर की संख्या के आधार पर पूर्ण बिट वेक्टर और मोटे बिट वेक्टर के संयोजन का उपयोग करता है।<ref name="SGI2000OriginPaper">{{Cite conference|last1=Laudon|first1=James|last2=Lenoski|first2=Daniel|date=1997-06-01|title=The SGI Origin: a ccNUMA highly scalable serve|url=http://dl.acm.org/citation.cfm?id=264206|conference=Proceedings of the 24th annual international symposium on Computer architecture}}</ref>
[[File:Full bit vector format diagram.jpg|thumb|पूर्ण बिट वेक्टर डायरेक्टरी फॉर्मेट का आरेख, जहां ई=अनन्य, एस=साझा, एम=संशोधित, और यू=अनकैशे्ड]]इस प्रकार से फुल बिट वेक्टर फॉर्मेट में, कंप्यूटर मेमोरी में प्रत्येक संभावित कैशे लाइन के लिए, एक बिट का उपयोग यह ट्रैक करने के लिए किया जाता है कि क्या प्रत्येक व्यक्तिगत [[सेंट्रल प्रोसेसिंग यूनिट]] में वह लाइन उसके [[कैश (कंप्यूटिंग)|कैशे (कंप्यूटिंग)]] में संग्रहीत है।<ref name=SolihinBook2015>{{Cite book|title=समानांतर मल्टीकोर आर्किटेक्चर के मूल सिद्धांत|last=Solihin|first=Yan|publisher=Solihin Publishing and Consulting, LLC|date=2015-10-09|isbn=978-1-4822-1118-4|location=Raleigh, North Carolina|pages=331–335}}</ref> और फुल बिट वेक्टर फॉर्मेट प्रयुक्त करने के लिए अधिक सरल संरचना है, किन्तु सबसे कम स्केलेबल है।<ref name=CMPAMDUWPaper/> एसजीआई उत्पत्ति 2000 प्रोसेसर की संख्या के आधार पर पूर्ण बिट वेक्टर और कोर्से बिट वेक्टर के संयोजन का उपयोग करता है।<ref name="SGI2000OriginPaper">{{Cite conference|last1=Laudon|first1=James|last2=Lenoski|first2=Daniel|date=1997-06-01|title=The SGI Origin: a ccNUMA highly scalable serve|url=http://dl.acm.org/citation.cfm?id=264206|conference=Proceedings of the 24th annual international symposium on Computer architecture}}</ref>
किन्तु प्रत्येक निर्देशिका प्रविष्टि में निर्देशिका की स्थिति को ट्रैक करने के लिए बिट्स के साथ-साथ प्रति प्रोसेसर प्रति कैश लाइन में एक बिट संग्रहीत होना चाहिए। इससे कुल आवश्यक आकार (प्रोसेसर की संख्या)×कैश लाइनों की संख्या, स्टोरेज [[ओवरहेड (कंप्यूटिंग)]] अनुपात (प्रोसेसर की संख्या)/(कैश ब्लॉक आकार×8) हो जाता है।
किन्तु प्रत्येक डायरेक्टरी प्रविष्टि में डायरेक्टरी की स्थिति को ट्रैक करने के लिए बिट्स के साथ-साथ प्रति प्रोसेसर प्रति कैशे लाइन में एक बिट संग्रहीत होना चाहिए। इससे कुल आवश्यक आकार (प्रोसेसर की संख्या)×कैशे लाइनों की संख्या, स्टोरेज [[ओवरहेड (कंप्यूटिंग)]] अनुपात (प्रोसेसर की संख्या)/(कैशे ब्लॉक आकार×8) हो जाता है।  


इस प्रकार से यह देखा जा सकता है कि निर्देशिका ओवरहेड प्रोसेसर की संख्या के साथ रैखिक रूप से स्केल करती है। चूंकि यह कम संख्या में प्रोसेसर के लिए उचित हो सकता है, किन्तु जब उच्च सिस्टम में इसे प्रयुक्त किया जाता है तो निर्देशिका के लिए आकार की आवश्यकताएं अत्यधिक हो जाती हैं। अतः उदाहरण के लिए, 32 बाइट्स और 1024 प्रोसेसर के ब्लॉक आकार के साथ, स्टोरेज ओवरहेड अनुपात 1024/(32×8) = 400% हो जाता है।<ref name=SolihinBook2015/>
इस प्रकार से यह देखा जा सकता है कि डायरेक्टरी ओवरहेड प्रोसेसर की संख्या के साथ रैखिक रूप से स्केल करती है। चूंकि यह कम संख्या में प्रोसेसर के लिए उचित हो सकता है, किन्तु जब उच्च सिस्टम में इसे प्रयुक्त किया जाता है तो डायरेक्टरी के लिए आकार की आवश्यकताएं अत्यधिक हो जाती हैं। अतः उदाहरण के लिए, 32 बाइट्स और 1024 प्रोसेसर के ब्लॉक आकार के साथ, स्टोरेज ओवरहेड अनुपात 1024/(32×8) = 400% हो जाता है।<ref name=SolihinBook2015/>




== मोटे बिट वेक्टर प्रारूप ==
== कोर्से बिट वेक्टर फॉर्मेट ==
[[File:Coarse bit vector format diagram.jpg|thumb|मोटे बिट वेक्टर निर्देशिका प्रारूप का आरेख]]मोटे बिट वेक्टर प्रारूप में पूर्ण बिट वेक्टर प्रारूप के समान संरचना होती है, चूंकि प्रत्येक कैश लाइन के लिए प्रति प्रोसेसर एक बिट को ट्रैक करने के अतिरिक्त, निर्देशिका अनेक प्रोसेसर को नोड (कंप्यूटर साइंस) में समूहित करती है, यह संग्रहीत करती है कि कैश लाइन नोड में संग्रहीत है या नहीं एक पंक्ति के अतिरिक्त. यह [[बस (कंप्यूटिंग)]] ट्रैफ़िक की बचत (प्रति नोड प्रोसेसर) × (कुल लाइनें) स्थान के बिट्स की निवेश पर आकार आवश्यकताओं में सुधार करता है।<ref name="SGI2000OriginPaper"/> इस प्रकार अनुपात ओवरहेड समान है, बस प्रोसेसर की संख्या को प्रोसेसर समूहों की संख्या से परिवर्तित कर दिया गया है। जब समूह में एक प्रोसेसर के समीप उपस्तिथ कैश लाइन के लिए बस अनुरोध किया जाता है, तो निर्देशिका केवल कैश में सम्मिलित होने के अतिरिक्त नोड में प्रत्येक प्रोसेसर में सिग्नल प्रसारित करती है, जिससे नोड्स पर अनावश्यक ट्रैफ़िक उत्पन्न होता है, जिसमें डेटा कैश नहीं होता है।<ref name=SolihinBook2015/>
[[File:Coarse bit vector format diagram.jpg|thumb|कोर्से बिट वेक्टर डायरेक्टरी फॉर्मेट का आरेख]]कोर्से बिट वेक्टर फॉर्मेट में फुल बिट वेक्टर फॉर्मेट के समान संरचना होती है, चूंकि प्रत्येक कैशे लाइन के लिए प्रति प्रोसेसर एक बिट को ट्रैक करने के अतिरिक्त, डायरेक्टरी अनेक प्रोसेसर को नोड (कंप्यूटर साइंस) में समूहित करती है, यह संग्रहीत करती है कि कैशे लाइन नोड में संग्रहीत है या नहीं एक पंक्ति के अतिरिक्त. यह [[बस (कंप्यूटिंग)]] ट्रैफ़िक की बचत (प्रति नोड प्रोसेसर) × (कुल लाइनें) स्थान के बिट्स की निवेश पर आकार आवश्यकताओं में सुधार करता है।<ref name="SGI2000OriginPaper"/> इस प्रकार अनुपात ओवरहेड समान है, बस प्रोसेसर की संख्या को प्रोसेसर समूहों की संख्या से परिवर्तित कर दिया गया है। जब समूह में एक प्रोसेसर के समीप उपस्तिथ कैशे लाइन के लिए बस अनुरोध किया जाता है, तो डायरेक्टरी केवल कैशे में सम्मिलित होने के अतिरिक्त नोड में प्रत्येक प्रोसेसर में सिग्नल प्रसारित करती है, जिससे नोड्स पर अनावश्यक ट्रैफ़िक उत्पन्न होता है, जिसमें डेटा कैशे नहीं होता है।<ref name=SolihinBook2015/>  


इस स्तिथि में निर्देशिका प्रविष्टि प्रत्येक कैश लाइन के लिए प्रोसेसर के समूह के लिए एक बिट का उपयोग करती है। और पूर्ण बिट वेक्टर प्रारूप के समान उदाहरण के लिए यदि हम एक समूह के रूप में 8 प्रोसेसर के लिए एक बिट पर विचार करते हैं, तो स्टोरेज ओवरहेड 128/(32×8)=50% होगा। यह पूर्ण बिट वेक्टर प्रारूप की तुलना में महत्वपूर्ण सुधार है।
इस स्तिथि में डायरेक्टरी प्रविष्टि प्रत्येक कैशे लाइन के लिए प्रोसेसर के समूह के लिए एक बिट का उपयोग करती है। और फुल बिट वेक्टर फॉर्मेट के समान उदाहरण के लिए यदि हम एक समूह के रूप में 8 प्रोसेसर के लिए एक बिट पर विचार करते हैं, तो स्टोरेज ओवरहेड 128/(32×8)=50% होगा। यह फुल बिट वेक्टर फॉर्मेट की तुलना में महत्वपूर्ण सुधार है।  


==विरल निर्देशिका प्रारूप==
==स्पर्स डायरेक्टरी फॉर्मेट ==
इस प्रकार से कैश किसी विशेष समय में मुख्य मेमोरी में केवल ब्लॉकों का एक छोटा उपसमूह संग्रहीत करता है। इसलिए निर्देशिका में अधिकांश प्रविष्टियाँ अनकैश्ड ब्लॉक से संबंधित होंगी। विरल निर्देशिका प्रारूप में निर्देशिका में केवल कैश्ड ब्लॉकों को संग्रहीत करके अपव्यय को कम किया जाता है।<ref name=SolihinBook2015/> एक प्रोसेसर पर विचार करें जिसका कैश आकार 64KB है, ब्लॉक आकार 32 बाइट्स है और मुख्य मेमोरी आकार 4MB है। इस प्रकार से विरल निर्देशिका प्रारूप में निर्देशिका में प्रविष्टियों की अधिकतम संख्या 2048 है। यदि निर्देशिका में मेमोरी के सभी ब्लॉकों के लिए एक प्रविष्टि है, तो निर्देशिका में प्रविष्टियों की संख्या 131072 होगी। इस प्रकार यह स्पष्ट है कि स्टोरेज में सुधार हुआ है विरल निर्देशिका प्रारूप द्वारा प्रदान किया गया अधिक महत्वपूर्ण है।
इस प्रकार से कैशे किसी विशेष समय में मुख्य मेमोरी में केवल ब्लॉकों का एक छोटा उपसमूह संग्रहीत करता है। इसलिए डायरेक्टरी में अधिकांश प्रविष्टियाँ अनकैशे्ड ब्लॉक से संबंधित होंगी। स्पर्स डायरेक्टरी फॉर्मेट में डायरेक्टरी में केवल कैशे्ड ब्लॉकों को संग्रहीत करके अपव्यय को कम किया जाता है।<ref name=SolihinBook2015/> एक प्रोसेसर पर विचार करें जिसका कैशे आकार 64KB है, ब्लॉक आकार 32 बाइट्स है और मुख्य मेमोरी आकार 4MB है। इस प्रकार से स्पर्स डायरेक्टरी फॉर्मेट में डायरेक्टरी में प्रविष्टियों की अधिकतम संख्या 2048 है। यदि डायरेक्टरी में मेमोरी के सभी ब्लॉकों के लिए एक प्रविष्टि है, तो डायरेक्टरी में प्रविष्टियों की संख्या 131072 होगी। इस प्रकार यह स्पष्ट है कि स्टोरेज में सुधार हुआ है स्पर्स डायरेक्टरी फॉर्मेट द्वारा प्रदान किया गया अधिक महत्वपूर्ण है।


==संख्या-संतुलित [[ द्विआधारी वृक्ष |बाइनरी ट्री]] प्रारूप==
==नंबर-बैलेंस्ड बाइनरी ट्री फॉर्मेट ==
इस प्रारूप में निर्देशिका को विकेंद्रीकृत किया जाता है और मेमोरी ब्लॉक साझा करने वाले कैश के मध्य वितरित किया जाता है। और मेमोरी ब्लॉक साझा करने वाले विभिन्न कैश को बाइनरी ट्री के रूप में व्यवस्थित किया जाता है। कैश जो मेमोरी ब्लॉक तक सबसे पहले पहुंचता है वह रूट नोड (डेटा संरचना) है। इसलिए प्रत्येक मेमोरी ब्लॉक में रूट नोड जानकारी (एचईएडी) और शेयरिंग काउंटर फ़ील्ड (एससी) होती है। एससी फ़ील्ड में ब्लॉक साझा करने वाले कैश की संख्या होती है। प्रत्येक कैश प्रविष्टि में अगले साझाकरण कैश के लिए [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] होता है जिसे एल-सीएचडी और आर-सीएचडी के नाम से जाना जाता है। इस निर्देशिका के लिए एक शर्त यह है कि बाइनरी ट्री की संख्या संतुलित होनी चाहिए, यानी बाएं उप ट्री में नोड्स की संख्या दाएं उप ट्री में नोड्स की संख्या के बराबर या उससे एक अधिक होनी चाहिए। सभी सबट्री की संख्या भी संतुलित होनी चाहिए।<ref>{{Cite journal|last1=Seo|first1=Dae-Wha|last2=Cho|first2=Jung Wan|date=1993-01-01|title=संख्या-संतुलित बाइनरी ट्री का उपयोग करके निर्देशिका-आधारित कैश सुसंगतता योजना|journal=Microprocessing and Microprogramming|volume=37|issue=1|pages=37–40|doi=10.1016/0165-6074(93)90011-9}}</ref>
इस फॉर्मेट में डायरेक्टरी को विकेंद्रीकृत किया जाता है और मेमोरी ब्लॉक साझा करने वाले कैशे के मध्य वितरित किया जाता है। और मेमोरी ब्लॉक साझा करने वाले विभिन्न कैशे को बाइनरी ट्री के रूप में व्यवस्थित किया जाता है। कैशे जो मेमोरी ब्लॉक तक सबसे पहले पहुंचता है वह रूट नोड (डेटा संरचना) है। इसलिए प्रत्येक मेमोरी ब्लॉक में रूट नोड जानकारी (एचईएडी) और शेयरिंग काउंटर फ़ील्ड (एससी) होती है। एससी फ़ील्ड में ब्लॉक साझा करने वाले कैशे की संख्या होती है। प्रत्येक कैशे प्रविष्टि में अगले साझाकरण कैशे के लिए [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] होता है जिसे एल-सीएचडी और आर-सीएचडी के नाम से जाना जाता है। इस डायरेक्टरी के लिए एक नियम यह है कि बाइनरी ट्री की संख्या बैलेंस्ड होनी चाहिए, यानी बाएं उप ट्री में नोड्स की संख्या दाएं उप ट्री में नोड्स की संख्या के समान या उससे एक अधिक होनी चाहिए। इस प्रकार से सभी सबट्री की संख्या भी बैलेंस्ड होनी चाहिए।<ref>{{Cite journal|last1=Seo|first1=Dae-Wha|last2=Cho|first2=Jung Wan|date=1993-01-01|title=संख्या-संतुलित बाइनरी ट्री का उपयोग करके निर्देशिका-आधारित कैश सुसंगतता योजना|journal=Microprocessing and Microprogramming|volume=37|issue=1|pages=37–40|doi=10.1016/0165-6074(93)90011-9}}</ref>
==श्रृंखलाबद्ध निर्देशिका प्रारूप==
==चैन डायरेक्टरी फॉर्मेट==
इस प्रारूप में मेमोरी निर्देशिका पॉइंटर को नवीनतम कैश में रखती है जिसने ब्लॉक तक पहुंच बनाई है और प्रत्येक कैश में पिछले कैश में पॉइंटर होता है जो की ब्लॉक तक पहुंचता है। इसलिए जब कोई प्रोसेसर मेमोरी में किसी ब्लॉक को लिखने का अनुरोध भेजता है, तो प्रोसेसर पॉइंटर्स की श्रृंखला के नीचे [[कैश अमान्यकरण]] भेजता है। इस निर्देशिका में जब कैश ब्लॉक को प्रतिस्थापित किया जाता है तो हमें निर्देशिका को परिवर्तित के लिए लिंक की गई सूची को ग्राफ़ ट्रैवर्सल करने की आवश्यकता होती है जो लेटेंसी (इंजीनियरिंग) या कंप्यूटर हार्डवेयर और ऑपरेटिंग सिस्टम को बढ़ाती है। इसे रोकने के लिए अब दोहरी रूप से लिंक की गई सूचियों का व्यापक रूप से उपयोग किया जाता है, जिसमें प्रत्येक कैश्ड कॉपी में पिछले और अगले कैश के लिए पॉइंटर्स होते हैं जो ब्लॉक तक पहुंचते हैं।<ref>{{Cite journal|last1=Chaiken|first1=D.|last2=Fields|first2=C.|last3=Kurihara|first3=K.|last4=Agarwal|first4=A.|date=1990-06-01|title=बड़े पैमाने के मल्टीप्रोसेसरों में निर्देशिका-आधारित कैश सुसंगतता|journal=Computer|volume=23|issue=6|pages=49–58|doi=10.1109/2.55500|issn=0018-9162|citeseerx=10.1.1.461.8404|s2cid=683311 }}</ref>
इस फॉर्मेट में मेमोरी डायरेक्टरी पॉइंटर को नवीनतम कैशे में रखती है जिसने ब्लॉक तक पहुंच बनाई है और प्रत्येक कैशे में पिछले कैशे में पॉइंटर होता है जो की ब्लॉक तक पहुंचता है। इसलिए जब कोई प्रोसेसर मेमोरी में किसी ब्लॉक को लिखने का अनुरोध भेजता है, तो प्रोसेसर पॉइंटर्स की श्रृंखला के नीचे कैशे अमान्यकरण भेजता है। इस डायरेक्टरी में जब कैशे ब्लॉक को प्रतिस्थापित किया जाता है तो हमें डायरेक्टरी को परिवर्तित के लिए लिंक की गई सूची को ग्राफ़ ट्रैवर्सल करने की आवश्यकता होती है जो लेटेंसी (इंजीनियरिंग) या कंप्यूटर हार्डवेयर और ऑपरेटिंग सिस्टम को बढ़ाती है। इसे रोकने के लिए अब दोहरी रूप से लिंक की गई सूचियों का व्यापक रूप से उपयोग किया जाता है, जिसमें प्रत्येक कैशे्ड कॉपी में पिछले और अगले कैशे के लिए पॉइंटर्स होते हैं जो ब्लॉक तक पहुंचते हैं।<ref>{{Cite journal|last1=Chaiken|first1=D.|last2=Fields|first2=C.|last3=Kurihara|first3=K.|last4=Agarwal|first4=A.|date=1990-06-01|title=बड़े पैमाने के मल्टीप्रोसेसरों में निर्देशिका-आधारित कैश सुसंगतता|journal=Computer|volume=23|issue=6|pages=49–58|doi=10.1109/2.55500|issn=0018-9162|citeseerx=10.1.1.461.8404|s2cid=683311 }}</ref>
== सीमित सूचक प्रारूप ==
== लिमिटेड पॉइंटर फॉर्मेट ==
सीमित पॉइंटर प्रारूप डेटा को कैश करने वाले प्रोसेसर को ट्रैक करने के लिए पॉइंटर्स की एक निर्धारित संख्या का उपयोग करता है। जब कोई नया प्रोसेसर किसी ब्लॉक को कैश करता है, तो उस प्रोसेसर को इंगित करने के लिए पूल से एक फ्री पॉइंटर चुना जाता है। ऐसे स्तिथियों को संभालने के लिए कुछ विकल्प हैं जब शेयर करने वालों की संख्या फ्री पॉइंटर्स की संख्या से अधिक हो जाती है। और एक विधि नवीन अनुरोधकर्ता के लिए इसके पॉइंटर का उपयोग करके किसी भागीदार को अमान्य करना है, चूंकि यह उन स्तिथियों में बहुमूल्य हो सकता है जहां किसी ब्लॉक में उच्च संख्या में रीडर्स हों, जैसे कि लॉक। और अन्य विधि यह है कि सभी ब्लॉकों के लिए मुफ्त पॉइंटर्स का एक अलग पूल उपलब्ध हो। इस प्रकार से यह विधि सामान्यतः प्रभावी होती है क्योंकि बड़ी संख्या में प्रोसेसर द्वारा साझा किए गए ब्लॉक की संख्या सामान्य रूप से अधिक बड़ी नहीं होती है।<ref name=SolihinBook2015/>
लिमिटेड पॉइंटर फॉर्मेट डेटा को कैशे करने वाले प्रोसेसर को ट्रैक करने के लिए पॉइंटर्स की एक निर्धारित संख्या का उपयोग करता है। जब कोई नया प्रोसेसर किसी ब्लॉक को कैशे करता है, तो उस प्रोसेसर को इंगित करने के लिए पूल से एक फ्री पॉइंटर चुना जाता है। ऐसे स्तिथियों को संभालने के लिए कुछ विकल्प हैं जब शेयर करने वालों की संख्या फ्री पॉइंटर्स की संख्या से अधिक हो जाती है। और एक विधि नवीन अनुरोधकर्ता के लिए इसके पॉइंटर का उपयोग करके किसी भागीदार को अमान्य करना है, चूंकि यह उन स्तिथियों में बहुमूल्य हो सकता है जहां किसी ब्लॉक में उच्च संख्या में रीडर्स हों, जैसे कि लॉक। और अन्य विधि यह है कि सभी ब्लॉकों के लिए मुफ्त पॉइंटर्स का एक अलग पूल उपलब्ध हो। इस प्रकार से यह विधि सामान्यतः प्रभावी होती है क्योंकि बड़ी संख्या में प्रोसेसर द्वारा साझा किए गए ब्लॉक की संख्या सामान्य रूप से अधिक बड़ी नहीं होती है।<ref name=SolihinBook2015/>




Line 35: Line 37:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 16/08/2023]]
[[Category:Created On 16/08/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:30, 10 October 2023

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

फुल बिट वेक्टर फॉर्मेट

पूर्ण बिट वेक्टर डायरेक्टरी फॉर्मेट का आरेख, जहां ई=अनन्य, एस=साझा, एम=संशोधित, और यू=अनकैशे्ड

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

किन्तु प्रत्येक डायरेक्टरी प्रविष्टि में डायरेक्टरी की स्थिति को ट्रैक करने के लिए बिट्स के साथ-साथ प्रति प्रोसेसर प्रति कैशे लाइन में एक बिट संग्रहीत होना चाहिए। इससे कुल आवश्यक आकार (प्रोसेसर की संख्या)×कैशे लाइनों की संख्या, स्टोरेज ओवरहेड (कंप्यूटिंग) अनुपात (प्रोसेसर की संख्या)/(कैशे ब्लॉक आकार×8) हो जाता है।

इस प्रकार से यह देखा जा सकता है कि डायरेक्टरी ओवरहेड प्रोसेसर की संख्या के साथ रैखिक रूप से स्केल करती है। चूंकि यह कम संख्या में प्रोसेसर के लिए उचित हो सकता है, किन्तु जब उच्च सिस्टम में इसे प्रयुक्त किया जाता है तो डायरेक्टरी के लिए आकार की आवश्यकताएं अत्यधिक हो जाती हैं। अतः उदाहरण के लिए, 32 बाइट्स और 1024 प्रोसेसर के ब्लॉक आकार के साथ, स्टोरेज ओवरहेड अनुपात 1024/(32×8) = 400% हो जाता है।[2]


कोर्से बिट वेक्टर फॉर्मेट

कोर्से बिट वेक्टर डायरेक्टरी फॉर्मेट का आरेख

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

इस स्तिथि में डायरेक्टरी प्रविष्टि प्रत्येक कैशे लाइन के लिए प्रोसेसर के समूह के लिए एक बिट का उपयोग करती है। और फुल बिट वेक्टर फॉर्मेट के समान उदाहरण के लिए यदि हम एक समूह के रूप में 8 प्रोसेसर के लिए एक बिट पर विचार करते हैं, तो स्टोरेज ओवरहेड 128/(32×8)=50% होगा। यह फुल बिट वेक्टर फॉर्मेट की तुलना में महत्वपूर्ण सुधार है।

स्पर्स डायरेक्टरी फॉर्मेट

इस प्रकार से कैशे किसी विशेष समय में मुख्य मेमोरी में केवल ब्लॉकों का एक छोटा उपसमूह संग्रहीत करता है। इसलिए डायरेक्टरी में अधिकांश प्रविष्टियाँ अनकैशे्ड ब्लॉक से संबंधित होंगी। स्पर्स डायरेक्टरी फॉर्मेट में डायरेक्टरी में केवल कैशे्ड ब्लॉकों को संग्रहीत करके अपव्यय को कम किया जाता है।[2] एक प्रोसेसर पर विचार करें जिसका कैशे आकार 64KB है, ब्लॉक आकार 32 बाइट्स है और मुख्य मेमोरी आकार 4MB है। इस प्रकार से स्पर्स डायरेक्टरी फॉर्मेट में डायरेक्टरी में प्रविष्टियों की अधिकतम संख्या 2048 है। यदि डायरेक्टरी में मेमोरी के सभी ब्लॉकों के लिए एक प्रविष्टि है, तो डायरेक्टरी में प्रविष्टियों की संख्या 131072 होगी। इस प्रकार यह स्पष्ट है कि स्टोरेज में सुधार हुआ है स्पर्स डायरेक्टरी फॉर्मेट द्वारा प्रदान किया गया अधिक महत्वपूर्ण है।

नंबर-बैलेंस्ड बाइनरी ट्री फॉर्मेट

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

चैन डायरेक्टरी फॉर्मेट

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

लिमिटेड पॉइंटर फॉर्मेट

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


संदर्भ

  1. 1.0 1.1 Reihnhart, Steven; Basu, Arkaprava; Beckmann, Bradford; Hill, Mark (2013-07-11). "CMP Directory Coherence: One Granularity Does Not Fit All" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
  2. 2.0 2.1 2.2 2.3 2.4 Solihin, Yan (2015-10-09). समानांतर मल्टीकोर आर्किटेक्चर के मूल सिद्धांत. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. pp. 331–335. ISBN 978-1-4822-1118-4.
  3. 3.0 3.1 Laudon, James; Lenoski, Daniel (1997-06-01). The SGI Origin: a ccNUMA highly scalable serve. Proceedings of the 24th annual international symposium on Computer architecture.
  4. Seo, Dae-Wha; Cho, Jung Wan (1993-01-01). "संख्या-संतुलित बाइनरी ट्री का उपयोग करके निर्देशिका-आधारित कैश सुसंगतता योजना". Microprocessing and Microprogramming. 37 (1): 37–40. doi:10.1016/0165-6074(93)90011-9.
  5. Chaiken, D.; Fields, C.; Kurihara, K.; Agarwal, A. (1990-06-01). "बड़े पैमाने के मल्टीप्रोसेसरों में निर्देशिका-आधारित कैश सुसंगतता". Computer. 23 (6): 49–58. CiteSeerX 10.1.1.461.8404. doi:10.1109/2.55500. ISSN 0018-9162. S2CID 683311.