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

From Vigyanwiki
No edit summary
No edit summary
Line 5: Line 5:
== पूर्ण बिट वेक्टर प्रारूप ==
== पूर्ण बिट वेक्टर प्रारूप ==
[[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>
==श्रृंखलाबद्ध निर्देशिका प्रारूप==
==श्रृंखलाबद्ध निर्देशिका प्रारूप==

Revision as of 23:16, 4 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.