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

From Vigyanwiki
Revision as of 17:27, 17 February 2023 by alpha>Indicwiki (Created page with "{{short description|Computer processing technique to boost memory performance}} कैशे प्रीफेटिंग एक ऐसी तकनीक है जिस...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

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

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

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

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

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


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

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

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

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

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


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

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

नियमित कदम

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

अनियमित कदम

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

टेम्पोरल प्रीफेटिंग

प्रीफ़ेचर का यह वर्ग उन मेमोरी एक्सेस स्ट्रीम की तलाश करता है जो समय के साथ दोहराई जाती हैं।[15][16] उदा. स्मृति की इस धारा में: एन, ए, बी, सी, ई, जी, एच, ए, बी, सी, आई, जे, के, ए, बी, सी, एल, एम, एन, ओ, ए, बी , सी, ....; धारा A,B,C समय के साथ दोहरा रही है। अन्य डिज़ाइन भिन्नताओं ने अधिक कुशल, प्रदर्शनकारी कार्यान्वयन प्रदान करने का प्रयास किया है।[17][18]


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

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

सॉफ्टवेयर प्रीफेटिंग के तरीके

कंपाइलर निर्देशित प्रीफेटिंग

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

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

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

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

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

के लिए (इंट आई = 0; मैं <1024; मैं ++) {
    सरणी 1 [i] = 2 * सरणी 1 [i];
}

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

के लिए (इंट आई = 0; मैं <1024; मैं ++) {
    प्रीफ़ेच (array1 [i + k]);
    सरणी 1 [i] = 2 * सरणी 1 [i];
}

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

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

  • जबकि सॉफ़्टवेयर प्रीफ़ेचिंग के लिए प्रोग्रामर या संकलक हस्तक्षेप की आवश्यकता होती है, हार्डवेयर प्रीफ़ेचिंग के लिए विशेष हार्डवेयर तंत्र की आवश्यकता होती है।[3]* सॉफ़्टवेयर प्रीफ़ेचिंग केवल लूप्स के साथ अच्छी तरह से काम करता है जहां नियमित ऐरे एक्सेस होता है क्योंकि प्रोग्रामर को प्रीफ़ेच निर्देशों को कोड करना पड़ता है, जबकि हार्डवेयर प्रीफ़ेचर रन टाइम (प्रोग्राम जीवनचक्र चरण) पर प्रोग्राम के व्यवहार के आधार पर गतिशील रूप से काम करते हैं।[3]* सॉफ़्टवेयर प्रीफ़ेचिंग की तुलना में हार्डवेयर प्रीफ़ेचिंग में CPU ओवरहेड भी कम होता है।[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=98626’