कैश प्रीफेचिंग

From Vigyanwiki
Revision as of 15:13, 1 March 2023 by alpha>Neeraja (added Category:Vigyan Ready using HotCat)

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

डेटा बनाम निर्देश कैश प्रीफ़ेचिंग

कैश प्रीफ़ेचिंग या तो कैश में डेटा या निर्देश प्राप्त कर सकता है।

  • डेटा प्रीफ़ेचिंग डेटा को आवश्यक होने से पूर्व ही प्राप्त कर लेता है। क्योंकि डेटा अभिगम पैटर्न निर्देश पैटर्न की तुलना में कम नियमितता दिखाते हैं, यथार्थ डेटा प्रीफ़ेचिंग सामान्यतः निर्देश प्रीफ़ेचिंग की तुलना में अधिक चुनौतीपूर्ण होता है।
  • निर्देश प्रीफ़ेचिंग निर्देशों को निष्पादित करने से पूर्व उन्हें प्राप्त करता है। इंस्ट्रक्शन प्रीफ़ेच के किसी रूप का उपयोग करने वाले पूर्व मेनस्ट्रीम माइक्रोप्रोसेसर इंटेल 8086(छह बाइट्स) और मोटोरोला 68000(चार बाइट्स) थे। वर्तमान वर्षों में, सभी उच्च-निष्पादन वाले प्रोसेसर प्रीफ़ेचिंग तकनीकों का उपयोग करते हैं।

हार्डवेयर बनाम सॉफ्टवेयर कैश प्रीफेचिंग

कैश प्रीफेचिंग या तो हार्डवेयर या सॉफ्टवेयर द्वारा पूरा किया जा सकता है।[3]

  • हार्डवेयर आधारित प्रीफेचिंग सामान्यतः प्रोसेसर में एक समर्पित हार्डवेयर तंत्र के द्वारा पूरा किया जाता है जो निष्पादन प्रोग्राम द्वारा अनुरोध किए जा रहे निर्देशों या डेटा के स्ट्रीम को देखता है, अगले कुछ अवयवों को पहचानता है जो इस स्ट्रीम के आधार पर प्रोग्राम की आवश्यकता हो सकती है और प्रोसेसर के कैश में प्रीफ़ेच करता है।[4]
  • सॉफ़्टवेयर आधारित प्रीफ़ेचिंग सामान्यतः संकलक द्वारा कोड का विश्लेषण करके और संकलन के समय प्रोग्राम में अतिरिक्त प्रीफ़ेच निर्देश सम्मिलित करके पूरा किया जाता है।[5]


हार्डवेयर प्रीफेचिंग की विधियां

स्ट्रीम बफ़र्स

  • एलन जे स्मिथ द्वारा प्रस्तावित वन ब्लॉक लुकहेड(ओबीएल) योजना की अवधारणा के आधार पर स्ट्रीम बफ़र्स विकसित किए गए थे।[1]
  • स्ट्रीम डेटा बफ़र उपयोग में आने वाली सबसे सामान्य हार्डवेयर आधारित प्रीफ़ेचिंग तकनीकों में से एक है। यह तकनीक मूल रूप से 1990 में नॉर्मन जोप्पी द्वारा प्रस्तावित की गई थी[6] और तब से इस पद्धति के कई रूप विकसित किए गए हैं।[7][8][9] मूल विचार यह है कि कैश मिस एड्रेस(और बाद के एड्रेसेस) को गहराई . इस बफ़र को स्ट्रीम बफ़र कहा जाता है और कैश से अलग होता है। प्रोसेसर तब स्ट्रीम बफर से डेटा/निर्देशों का उपभोग करता है यदि प्रीफ़ेच किए गए ब्लॉक से जुड़े एड्रेस प्रोसेसर पर निष्पादित प्रोग्राम द्वारा उत्पन्न अनुरोधित एड्रेस से मेल खाते हैं। नीचे दिया गया चित्र इस व्यवस्था को दिखाता है:
मूल रूप से प्रस्तावित एक विशिष्ट स्ट्रीम बफर सेटअप

* जब भी प्रीफैच मैकेनिज्म किसी मेमोरी ब्लॉक पर एक मिस का पता लगाता है, A कहते हैं, यह मिस्ड ब्लॉक से आगे के ब्लॉक को प्रीफेच करना प्रारम्भ करने के लिए एक स्ट्रीम आवंटित करता है। यदि स्ट्रीम बफ़र में 4 ब्लॉक हो सकते हैं, तो हम A+1, A+2, A+3, A+4 को प्रीफ़ेच करेंगे और आवंटित स्ट्रीम बफ़र में उन्हें धारण करेंगे। यदि प्रोसेसर A+1 का उपभोग करता है, तो इसे स्ट्रीम बफर से प्रोसेसर के कैश में ले जाया जाएगा। स्ट्रीम बफ़र की प्रथम प्रविष्टि अब A+2 होगी और इसी प्रकार आगे भी। क्रमिक ब्लॉकों को प्रीफ़ेच करने के इस पैटर्न को अनुक्रमिक प्रीफ़ेचिंग कहा जाता है। इसका मुख्य रूप से उपयोग तब किया जाता है जब सन्निहित स्थानों को प्रीफ़ेच किया जाना हो। उदाहरण के लिए, निर्देशों को प्रीफ़ेच करते समय इसका उपयोग किया जाता है।

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


स्ट्राइड प्रीफेचिंग

इस प्रकार का प्रीफेचिंग मेमोरी अभिगम के एड्रेसेस के बीच डेल्टा की निरीक्षण करता है और इसके भीतर पैटर्न की अन्वेषण करता है।

नियमित प्रगति

इस पैटर्न में, एड्रेस को अलग-अलग ब्लॉक करने के लिए निरंतर मेमोरी अभिगम किए जाते हैं।[3][12] इस विषय में, प्रीफ़ेचर की गणना करता है और प्रीफ़ेचिंग के लिए मेमोरी एड्रेस की गणना करने के लिए इसका उपयोग करता है। जैसे: यदि 4 है, प्रीफ़ेच किया जाने वाला पता A+4 होगा।

अनियमित प्रगति

इस विषय में, निरंतर मेमोरी अभिगम के एड्रेसेस के बीच का डेल्टा परिवर्तनशील है परन्तु फिर भी एक पैटर्न का अनुसरण करता है। कुछ प्रीफेचर डिजाइन[9][13][14] भविष्य की पहुंच के लिए भविष्यवाणी करने और प्रीफेच करने के लिए इस गुण का लाभ उठाएं।

अस्थायी प्रीफेचिंग

प्रीफ़ेचर का यह वर्ग उन मेमोरी अभिगम स्ट्रीम की अन्वेषण करता है जो समय के साथ दोहराई जाती हैं।[15][16] उदा. मेमोरी की इस स्ट्रीम में: N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ....; स्ट्रीम A,B,C समय के साथ दोहरा रही है। अन्य डिज़ाइन भिन्नताओं ने अधिक कुशल, निष्पादनकारी कार्यान्वयन प्रदान करने का प्रयास किया है।[17][18]


सहयोगात्मक प्रीफेचिंग

कंप्यूटर एप्लिकेशन विभिन्न प्रकार के अभिगम पैटर्न उत्पन्न करते हैं। इन अनुप्रयोगों को निष्पादित करने के लिए उपयोग किए जाने वाले प्रोसेसर और मेमोरी उप प्रणाली वास्तु-कला उनके द्वारा उत्पन्न मेमोरी अभिगम पैटर्न को और स्पष्ट करते हैं। इसलिए, प्रीफ़ेचिंग योजनाओं की प्रभावशीलता और दक्षता प्रायः एप्लिकेशन और उन्हें निष्पादित करने के लिए उपयोग किए जाने वाले वास्तु-कला पर निर्भर करती है।[19] वर्तमान में किए गए अनुसंधान[20][21] उत्तम प्रीफ़ेचिंग व्याप्ति और सटीकता के लिए कई प्रीफ़ेचिंग योजनाओं का सहक्रियात्मक रूप से उपयोग करने के लिए सहयोगी तंत्र के निर्माण पर ध्यान केंद्रित किया है।

सॉफ्टवेयर प्रीफेचिंग की विधियां

संकलक निर्देशित प्रीफेचिंग

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

ये प्रीफ़ेच नॉन-ब्लॉकिंग मेमोरी संचालन हैं, अर्थात ये मेमोरी अभिगम वास्तविक मेमोरी अभिगम में अंतःक्षेप नहीं करते हैं। वे प्रोसेसर की स्थिति को नहीं बदलते हैं या पृष्ठ दोष का कारण नहीं बनते हैं।

सॉफ़्टवेयर प्रीफ़ेचिंग का एक मुख्य लाभ यह है कि यह अनिवार्य कैश मिस की संख्या को कम करता है।[3]

निम्न उदाहरण दिखाता है कि कैश निष्पादन को उत्तम बनाने के लिए प्रीफ़ेच निर्देश को कोड में कैसे जोड़ा जाएगा।

जैसा कि नीचे दिखाया गया है लूप के लिए विचार करें: 

for (int i=0; i<1024; i++) {
    array1[i] = 2 * array1[i];
}

प्रत्येक पुनरावृत्ति पर, iवें सरणी का अवयव ऐरे 1 अभिगम किया गया है। इसलिए, हम उन अवयवों को प्रीफ़ेच कर सकते हैं जिन्हें भविष्य के पुनरावृत्तियों में अभिगम किया जा रहा है, जैसा कि नीचे दिखाया गया है: 

for (int i=0; i<1024; i++) {
     prefetch (array1 [i + k]);
     array1[i] = 2 * array1[i];
}

यहाँ, प्रीफ़ेच स्ट्राइड, दो कारकों पर निर्भर करता है, कैश मिस दंड और 'for' लूप के एकल पुनरावृत्ति को निष्पादित करने में लगने वाला समय। उदाहरण के लिए, यदि लूप के एक पुनरावृत्ति को निष्पादित करने में 7 चक्र लगते हैं, और कैश मिस दंड 49 चक्र है, तो हमारे समीप होना चाहिए - जिसका अर्थ है कि हम 7 अवयवों को आगे बढ़ाते हैं। पूर्व पुनरावृत्ति के साथ, i 0 होगा, इसलिए हम 7वें अवयव को प्रीफ़ेच करते हैं। अब, इस व्यवस्था के साथ, पूर्व 7 अभिगम(i=0->6) अभी भी मिस होंगे(सरलीकृत धारणा के अंतर्गत कि ऐरे1 का प्रत्येक अवयव स्वयं की एक अलग कैश क्रम में है)।

हार्डवेयर और सॉफ्टवेयर प्रीफेचिंग की तुलना

  • जबकि सॉफ़्टवेयर प्रीफ़ेचिंग के लिए प्रोग्रामर या संकलक अंतःक्षेप की आवश्यकता होती है, हार्डवेयर प्रीफ़ेचिंग के लिए विशेष हार्डवेयर तंत्र की आवश्यकता होती है।[3]
  • सॉफ़्टवेयर प्रीफ़ेचिंग मात्र लूपों के साथ ठीक प्रकार से काम करता है जहां नियमित ऐरे अभिगम होता है क्योंकि प्रोग्रामर को प्रीफ़ेच निर्देशों को कोड करना पड़ता है, जबकि हार्डवेयर प्रीफ़ेचर कार्यावधि(प्रोग्राम जीवनचक्र चरण) पर प्रोग्राम के गतिविधि के आधार पर गतिशील रूप से काम करते हैं।[3]
  • सॉफ़्टवेयर प्रीफ़ेचिंग की तुलना में हार्डवेयर प्रीफ़ेचिंग में सीपीयू उपरि भी कम होता है।[22]


कैश प्रीफ़ेचिंग के मापन

कैश प्रीफ़ेचिंग को आंकने के लिए तीन मुख्य मापन हैं[3]


व्याप्ति

व्याप्ति कुल मिसेस का वह अंश है जो प्रीफ़ेचिंग के कारण समाप्त हो जाते हैं, अर्थात

,

जहां,


सटीकता

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

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

समयबद्धता

समयबद्धता की गुणात्मक परिभाषा यह है कि किसी ब्लॉक को वस्तुत: संदर्भित किए जाने की तुलना में कितनी जल्दी प्रीफ़ेच किया जाता है। समयबद्धता को और समझाने के लिए एक उदाहरण इस प्रकार है:

एक फॉर लूप पर विचार करें जहां प्रत्येक पुनरावृत्ति को निष्पादित करने के लिए 3 चक्र लगते हैं और 'प्रीफेच' संचालन में 12 चक्र लगते हैं। इसका तात्पर्य है कि प्रीफ़ेच किए गए डेटा के उपयोगी होने के लिए, हमें प्रीफ़ेच प्रारम्भ करना होगा समयबद्धता बनाए रखने के लिए इसके उपयोग से पूर्व पुनरावृत्तियों।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Smith, Alan Jay (1982-09-01). "Cache Memories". ACM Comput. Surv. 14 (3): 473–530. doi:10.1145/356887.356892. ISSN 0360-0300. S2CID 6023466.
  2. ↑ Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min; Luo, Youlong (2020-09-01). "Adaptive priority-based cache replacement and prediction-based cache prefetching in edge computing environment". Journal of Network and Computer Applications (in English). 165: 102715. doi:10.1016/j.jnca.2020.102715. S2CID 219506427.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Solihin, Yan (2016). Fundamentals of parallel multicore architecture. Boca Raton, FL: CRC Press, Taylor & Francis Group. p. 163. ISBN 978-1482211184.
  4. ↑ Baer, Jean-Loup; Chen, Tien-Fu (1991-01-01). An Effective On-chip Preloading Scheme to Reduce Data Access Penalty. 1991 ACM/IEEE Conference on Supercomputing. Albuquerque, NM, USA: ACM. pp. 176–186. CiteSeerX 10.1.1.642.703. doi:10.1145/125826.125932. ISBN 978-0897914598.
  5. ↑ Kennedy, Porterfield, Allan (1989-01-01). Software methods for improvement of cache performance on supercomputer applications (Thesis). Rice University. hdl:1911/19069.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
  6. ↑ 6.0 6.1 6.2 Jouppi, Norman P. (1990). "Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers". Proceedings of the 17th annual international symposium on Computer Architecture - ISCA '90. New York, New York, USA: ACM Press. pp. 364–373. CiteSeerX 10.1.1.37.6114. doi:10.1145/325164.325162. ISBN 0-89791-366-3.
  7. ↑ Chen, Tien-Fu; Baer, Jean-Loup (1995-05-01). "Effective hardware-based data prefetching for high-performance processors". IEEE Transactions on Computers. 44 (5): 609–623. doi:10.1109/12.381947. ISSN 0018-9340. S2CID 1450745.
  8. ↑ Palacharla, S.; Kessler, R. E. (1994-01-01). Evaluating Stream Buffers As a Secondary Cache Replacement. 21st Annual International Symposium on Computer Architecture. Chicago, IL, USA: IEEE Computer Society Press. pp. 24–33. CiteSeerX 10.1.1.92.3031. doi:10.1109/ISCA.1994.288164. ISBN 978-0818655104.
  9. ↑ 9.0 9.1 Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). "Storage Efficient Hardware Prefetching using Delta-Correlating Prediction Tables". Journal of Instruction-Level Parallelism (13): 1–16. CiteSeerX 10.1.1.229.3483.
  10. ↑ Ishii, Yasuo; Inaba, Mary; Hiraki, Kei (2009-06-08). "Access map pattern matching for data cache prefetch". Proceedings of the 23rd International Conference on Supercomputing. ICS '09. New York, NY, USA: Association for Computing Machinery. pp. 499–500. doi:10.1145/1542275.1542349. ISBN 978-1-60558-498-0. S2CID 37841036.
  11. ↑ Srinath, Santhosh; Mutlu, Onur; Kim, Hyesoon; Patt, Yale N. (February 2007). Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers. 2007 IEEE 13th International Symposium on High Performance Computer Architecture. pp. 63–74. doi:10.1109/HPCA.2007.346185. ISBN 978-1-4244-0804-7. S2CID 6909725.
  12. ↑ Kondguli, Sushant; Huang, Michael (November 2017). T2: A Highly Accurate and Energy Efficient Stride Prefetcher. 2017 IEEE International Conference on Computer Design (ICCD). pp. 373–376. doi:10.1109/ICCD.2017.64. ISBN 978-1-5386-2254-4. S2CID 11055312.
  13. ↑ Shevgoor, Manjunath; Koladiya, Sahil; Balasubramonian, Rajeev; Wilkerson, Chris; Pugsley, Seth H; Chishti, Zeshan (December 2015). Efficiently prefetching complex address patterns. 2015 48th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). pp. 141–152. doi:10.1145/2830772.2830793. ISBN 9781450340342. S2CID 15294463.
  14. ↑ Kim, Jinchun; Pugsley, Seth H.; Gratz, Paul V.; Reddy, A.L. Narasimha; Wilkerson, Chris; Chishti, Zeshan (October 2016). Path confidence based lookahead prefetching. 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). pp. 1–12. doi:10.1109/MICRO.2016.7783763. ISBN 978-1-5090-3508-3. S2CID 1097472.
  15. ↑ Joseph, Doug; Grunwald, Dirk (1997-05-01). "Prefetching using Markov predictors". Proceedings of the 24th Annual International Symposium on Computer Architecture. ISCA '97. New York, NY, USA: Association for Computing Machinery. pp. 252–263. doi:10.1145/264107.264207. ISBN 978-0-89791-901-2. S2CID 434419.
  16. ↑ Collins, J.; Sair, S.; Calder, B.; Tullsen, D.M. (November 2002). Pointer cache assisted prefetching. 35th Annual IEEE/ACM International Symposium on Microarchitecture, 2002. (MICRO-35). Proceedings. pp. 62–73. doi:10.1109/MICRO.2002.1176239. ISBN 0-7695-1859-1. S2CID 5608519.
  17. ↑ Jain, Akanksha; Lin, Calvin (2013-12-07). "Linearizing irregular memory accesses for improved correlated prefetching". Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. MICRO-46. New York, NY, USA: Association for Computing Machinery. pp. 247–259. doi:10.1145/2540708.2540730. ISBN 978-1-4503-2638-4. S2CID 196831.
  18. ↑ "Making Temporal Prefetchers Practical: The MISB Prefetcher - Research Articles - Arm Research - Arm Community". community.arm.com (in English). Retrieved 2022-03-16.
  19. ↑ Kim, Jinchun; Teran, Elvira; Gratz, Paul V.; Jiménez, Daniel A.; Pugsley, Seth H.; Wilkerson, Chris (2017-05-12). "Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy". ACM SIGPLAN Notices (in English). 52 (4): 737–749. doi:10.1145/3093336.3037701. ISSN 0362-1340.
  20. ↑ Kondguli, Sushant; Huang, Michael (2018-06-02). "Division of labor: a more effective approach to prefetching". Proceedings of the 45th Annual International Symposium on Computer Architecture. ISCA '18. Los Angeles, California: IEEE Press. pp. 83–95. doi:10.1109/ISCA.2018.00018. ISBN 978-1-5386-5984-7. S2CID 50777324.
  21. ↑ Pakalapati, Samuel; Panda, Biswabandan (May 2020). Bouquet of Instruction Pointers: Instruction Pointer Classifier-based Spatial Hardware Prefetching. 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). pp. 118–131. doi:10.1109/ISCA45697.2020.00021. ISBN 978-1-7281-4661-4. S2CID 218683672.
  22. ↑ Callahan, David; Kennedy, Ken; Porterfield, Allan (1991-01-01). Software Prefetching. Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. Santa Clara, CA, USA: ACM. pp. 40–52. doi:10.1145/106972.106979. ISBN 978-0897913805.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कैश_प्रीफेचिंग&oldid=98631’