कैश, मुख्य स्मृति व द्वितीयक संचयन

स्मृति-अनुक्रम इसलिए है कि तेज़ स्मृति छोटी है और बड़ी स्मृति धीमी, और सम्पूर्ण विषय एक दाँव है: कि प्रोग्राम की अगली पहुँच उसकी पिछली के निकट है। उस दाँव के दो आधे नामित करने योग्य हैं, क्योंकि प्रश्न उन्हें पृथक् जाँचते हैं। कालिक स्थानिकता कहती है कि अब प्रयुक्त स्थान शीघ्र पुनः प्रयुक्त होगा, और शब्द कैश करना यही देता है। स्थानिक स्थानिकता कहती है कि उसके पड़ोसी भी प्रयुक्त होंगे, और सम्पूर्ण खंड कैश करना यही देता है — और इसीलिए खंड-आकार प्रत्येक पता-गणना में आता है। वहाँ से अध्याय अंकगणित है, और अंकगणित दिखने से सरल है यदि क्षेत्र सदा उसी क्रम में रखे जाएँ: खंड-विचलन खंड-आकार से आता है, अनुक्रमणिका समुच्चयों की संख्या से, और टैग जो शेष रहे। उन तीनों को उसी क्रम में लें और प्रत्येक मानचित्रण प्रश्न निकल आता है, वह एक परिणाम सहित जो लोगों को चकित करता है: नियत आकार के कैश हेतु सहचारिता बढ़ाने से टैग लंबा होता है, छोटा नहीं, क्योंकि कम समुच्चय का अर्थ कम अनुक्रमणिका-बिट है और पते का हिसाब कहीं तो देना होगा। अध्याय का दूसरा आधा औसत पहुँच-समय है, जहाँ एकमात्र वास्तविक जाल दो-स्तरीय अनुक्रम में स्थानीय व वैश्विक चूक-दर का भेद है — जो L2 अपने तक पहुँचने वाले का 20% चूकता है वह सभी पहुँचों का 2% चूक रहा है यदि L1 पहले ही 90% पकड़ चुका हो, और एक संख्या को दूसरी पढ़ना इस गणना के गलत होने का मानक तरीका है।

पता-विभाजन, तथा वह टैग जो बढ़ता है

एक कैश लें और केवल उसकी सहचारिता बदलें: 32-बिट पता, 64 KB कैश तथा 32-बाइट खंड, अतः खंड-विचलन 5 बिट है और कैश 64 KB / 32 B = 2048 पंक्तियाँ रखता है। समुच्चयों की संख्या 2048 को सहचारिता से भाग देकर मिलती है, अनुक्रमणिका log₂(समुच्चय) है, और टैग 32 में से शेष दो घटाकर।

एक 64 KB कैश, 32-बाइट खंड, 32-बिट पता — तीन मानचित्रणों में
मानचित्रणसमुच्चयअनुक्रमणिका बिटटैग बिट
प्रत्यक्ष-मानचित्रित (1-वे)20481116
4-वे समुच्चय सहचारी512918
पूर्णतः सहचारी1027
🎯 अधिक सहचारिता का अर्थ बड़ा टैग क्यों
पता 32 बिट है और प्रत्येक बिट का हिसाब देना होगा। पाँच किसी भी स्थिति में खंड-विचलन को जाते हैं। शेष अनुक्रमणिका व टैग में बँटते हैं, और अनुक्रमणिका केवल उतनी चौड़ी है जितनी समुच्चयों की संख्या — अतः पंक्तियों को चार के समुच्चयों में बाँटना समुच्चयों को 2048 से 512 कर देता है, जो दो अनुक्रमणिका-बिट हटाता है, और वे दो बिट लुप्त नहीं होते: वे टैग-बिट बन जाते हैं। पूर्णतः सहचारी कैश में एक समुच्चय, कोई अनुक्रमणिका नहीं, और तीनों में सबसे बड़ा टैग होता है। व्यावहारिक परिणाम वही है जो परीक्षा वस्तुतः चाहती है: सहचारिता संघर्ष-चूक घटाती है परंतु टैग संचयन व तुलनित्र हार्डवेयर की कीमत लेती है — पूर्णतः सहचारी कैश को टैग की तुलना एक साथ प्रत्येक पंक्ति से करनी पड़ती है, और इसीलिए वास्तविक कैश 4-वे या 8-वे पर रुक जाते हैं, अंत तक नहीं जाते।

औसत पहुँच-समय, तथा स्थानीय बनाम वैश्विक चूक-दर

एक स्तर हेतु, AMAT = हिट समय + चूक दर × चूक दंड। 1 ns हिट, 5% चूक-दर व 100 ns दंड के साथ, वह 1 + 0.05 × 100 = 6 ns है। दो स्तरों हेतु वही सूत्र नेस्ट होता है: AMAT = t(L1) + m(L1) × [t(L2) + m(L2) × t(स्मृति)]। 10% चूकते 1 ns L1, अपने तक पहुँचने वाले का 20% चूकते 10 ns L2, तथा 100 ns स्मृति के साथ: 1 + 0.10 × (10 + 0.20 × 100) = 4 ns — एक-स्तरीय स्थिति से तेज़, और स्तर जोड़ने का अभिप्राय वही है।

⚠️ स्थानीय चूक-दर व वैश्विक चूक-दर भिन्न संख्याएँ हैं
ऊपर के उदाहरण में L2 अपने तक पहुँचने वाली पहुँचों का 20% चूकता है — वही उसकी स्थानीय चूक-दर है, और नेस्टेड सूत्र में वही संख्या रखनी है। परंतु सभी पहुँचों का केवल 10% उस तक पहुँचता ही है, अतः L2 सभी पहुँचों का 0.10 × 0.20 = 2% चूकता है, और वह उसकी वैश्विक चूक-दर है। दोनों उसी कैश के विषय में सही कथन हैं और प्रश्न आपको एक देकर दूसरी पूछेगा। संकेत शब्दों में है: "L2 की चूक-दर 20% है" प्रायः सदा स्थानीय है, जबकि "स्मृति-संदर्भों का 2% मुख्य स्मृति तक जाता है" वैश्विक है। जहाँ सूत्र को स्थानीय चाहिए वहाँ वैश्विक रखना दंड को बहुत कम आँकता है, और परिणामी AMAT स्पष्टतः गलत के बजाय अत्युत्तम होता है — इसीलिए त्रुटि विवेक-जाँच से बच जाती है।
लेखन नीतियाँ तथा प्रत्येक की लागत
नीतिलेखन हिट परलागत
राइट-थ्रूकैश तथा स्मृति दोनों अद्यतनप्रत्येक लेखन पर स्मृति-यातायात; डर्टी बिट नहीं चाहिए
राइट-बैककेवल कैश अद्यतन, उसे डर्टी चिह्नितनिष्कासन पर स्मृति एक बार लिखी; प्रति पंक्ति डर्टी बिट चाहिए

द्वितीयक संचयन अनुक्रम पूर्ण करता है, और उसका पहुँच-समय तीन असंबद्ध चीज़ों का योग है: शीर्ष हिलाने हेतु खोज-समय, सेक्टर को घुमाकर लाने हेतु घूर्णन-विलंबता, तथा बाइटों हेतु अंतरण-समय। औसत घूर्णन-विलंबता आधा चक्कर है, अतः 7200 rpm पर वह 0.5 × 60/7200 से = 4.17 ms है — जानने योग्य आँकड़ा, क्योंकि अभ्यर्थी उसी पद को सर्वाधिक बार छोड़ते हैं। 8 ms खोज तथा वह विलंबता तथा 100 MB/s पर 4 KB मिलकर लगभग 12.2 ms होते हैं, और उत्तर का आकार ही शिक्षा है: अंतरण पूर्णांकन-त्रुटि है और यांत्रिकी प्रभावी है।

मुख्य बिंदु

  • क्षेत्र हर बार एक ही क्रम में रखें: खंड-विचलन खंड-आकार से, अनुक्रमणिका समुच्चय-संख्या से, टैग शेष।
  • नियत कैश आकार हेतु सहचारिता बढ़ाना अनुक्रमणिका-बिट घटाता है और अतः टैग बढ़ाता है — 1-वे, 4-वे, पूर्ण हेतु 16, 18, 27 बिट।
  • सहचारिता कम संघर्ष-चूक देती है और टैग संचयन तथा तुलनित्रों की कीमत लेती है, इसीलिए कैश 4- या 8-वे पर रुकते हैं।
  • AMAT = हिट समय + चूक दर × चूक दंड, और दो स्तरों हेतु वही सूत्र नेस्ट होता है।
  • स्थानीय चूक-दर उस स्तर तक पहुँचने वाली पहुँचों की है; वैश्विक दर सभी पहुँचों की — 10% × 20% = 2%।
  • राइट-थ्रू को डर्टी बिट नहीं चाहिए और वह हर बार स्मृति लिखता है; राइट-बैक को चाहिए और वह निष्कासन पर लिखता है।
  • डिस्क समय खोज + घूर्णन-विलंबता + अंतरण है; 7200 rpm पर औसत विलंबता 4.17 ms है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. 64 KB, 4-वे समुच्चय-सहचारी कैश में 32-बाइट खंड व 32-बिट पता है। प्रत्येक पंक्ति को कितने टैग बिट चाहिए?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 18

    32-बाइट खंड 5-बिट विचलन देता है। कैश 64 KB / 32 B = 2048 पंक्तियाँ रखता है, और 4-वे समूहन 2048 / 4 = 512 समुच्चय बनाता है, अतः अनुक्रमणिका log₂512 = 9 बिट। टैग 32 − 5 − 9 = 18 बिट। स्वयं को जाँचने योग्य संख्या उसी कैश का प्रत्यक्ष-मानचित्रित संस्करण है, जिसमें 2048 समुच्चय, 11-बिट अनुक्रमणिका व 16-बिट टैग है: सहचारिता बढ़ाने ने दो बिट अनुक्रमणिका से टैग में भेजे। यदि सहचारिता बढ़ने पर आपका उत्तर घटा, तो अनुक्रमणिका व टैग आपस में बदल गए हैं।

  2. नियत क्षमता व खंड-आकार के कैश हेतु सहचारिता बढ़ाने से:

    1. अनुक्रमणिका बिट बढ़ते हैं व टैग बिट घटते हैं
    2. अनुक्रमणिका बिट घटते हैं व टैग बिट बढ़ते हैं
    3. दोनों अपरिवर्तित रहते हैं
    4. दोनों बढ़ते हैं
    उत्तर देखें

    उत्तर: B — अनुक्रमणिका बिट घटते हैं व टैग बिट बढ़ते हैं

    क्षमता व खंड-आकार पंक्तियों की संख्या नियत करते हैं, अतः सहचारिता बढ़ाना केवल समुच्चयों की संख्या घटा सकता है — और अनुक्रमणिका ठीक उतनी चौड़ी है जितनी समुच्चय चुनने हेतु आवश्यक। कम समुच्चय का अर्थ कम अनुक्रमणिका-बिट, और चूँकि पता-लंबाई नियत है, अनुक्रमणिका से हटा प्रत्येक बिट टैग में आ जाता है। विकल्प A वही अंतर्ज्ञान है जिसके साथ अधिकांश अभ्यर्थी आते हैं, इस तर्क पर कि "अधिक सहचारिता का अर्थ देखने के अधिक स्थान, अतः चौड़ी अनुक्रमणिका"; विपरीत सत्य है, क्योंकि सहचारिता समुच्चय जोड़ने के बजाय समुच्चय के भीतर अधिक पंक्तियाँ रखती है। विकल्प D नियत पता-लंबाई हेतु असंभव है — तीनों क्षेत्रों का योग सदा उसी के बराबर होना चाहिए।

  3. L1 का हिट समय 1 ns व चूक-दर 10% है। L2 का हिट समय 10 ns है और वह अपने तक पहुँचने वाली पहुँचों का 20% चूकता है। मुख्य स्मृति 100 ns लेती है। औसत स्मृति पहुँच-समय ns में क्या है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 4

    सूत्र नेस्ट होता है: AMAT = 1 + 0.10 × (10 + 0.20 × 100) = 1 + 0.10 × 30 = 4 ns। 20%, L2 की स्थानीय चूक-दर है — उन पहुँचों की जो L2 तक पहुँचती हैं — और ठीक वही कोष्ठक के भीतर आती है। उसे वैश्विक दर मानकर 1 + 0.10 × 10 + 0.20 × 100 लिखने पर 22 ns मिलता है, और L2 के दंड को उसके हिट समय में जोड़ने के बजाय उसका स्थान लेने वाला मानने पर 3 ns; दोनों सामान्य हैं। यह भी ध्यान दें कि स्तर जोड़ने से लाभ हुआ: उसी L1 व 100 ns दंड वाला एक-स्तरीय कैश 1 + 0.10 × 100 = 11 ns होता।

  4. पिछले प्रश्न के अनुक्रम में, सभी स्मृति-पहुँचों का कितना अंश मुख्य स्मृति तक पहुँचता है?

    1. 20%
    2. 10%
    3. 2%
    4. 30%
    उत्तर देखें

    उत्तर: C — 2%

    कोई पहुँच मुख्य स्मृति तक तभी पहुँचती है जब वह दोनों स्तर चूके: 10% L1 चूकते हैं, और उनका 20% L2 चूकता है, अतः 0.10 × 0.20 = 2%। वह L2 की वैश्विक चूक-दर है, और वह उस 20% स्थानीय दर से भिन्न संख्या है जो पिछले प्रश्न में दी गई थी। विकल्प A स्थानीय दर को वैश्विक की भाँति प्रस्तुत करता है, जो इस विषय की एकमात्र सर्वाधिक सामान्य त्रुटि है; विकल्प B, L1 की चूक-दर है, जो स्मृति के बजाय L2 तक पहुँचने वाला अंश है। यह जानना कि प्रश्न ने दोनों में कौन-सी दी है, अधिकांश काम है — "अपने तक पहुँचने वाली पहुँचों का 20% चूकता है" रचना से ही स्थानीय है।

  5. राइट-थ्रू की तुलना में राइट-बैक कैश के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

    1. उसे प्रति कैश-पंक्ति एक डर्टी बिट चाहिए
    2. उसी पंक्ति पर बारंबार लेखन हेतु वह कम स्मृति-लेखन यातायात उत्पन्न करता है
    3. मुख्य स्मृति सदा वर्तमान मान रखती है
    4. संशोधित पंक्ति के निष्कासन हेतु स्मृति-लेखन आवश्यक है
    उत्तर देखें

    उत्तर: A — उसे प्रति कैश-पंक्ति एक डर्टी बिट चाहिए; B — उसी पंक्ति पर बारंबार लेखन हेतु वह कम स्मृति-लेखन यातायात उत्पन्न करता है; D — संशोधित पंक्ति के निष्कासन हेतु स्मृति-लेखन आवश्यक है

    A, B व D, जो एक ही अभिकल्प के तीन मुख हैं। राइट-बैक केवल कैश अद्यतन करता है और पंक्ति को डर्टी चिह्नित करता है (A), अतः उसी पंक्ति पर दस लेखन दस के बजाय एक स्मृति-लेखन लेते हैं (B), और वह स्थगित लेखन पंक्ति के निष्कासित होने पर होना ही पड़ता है (D)। C राइट-थ्रू का गुण है, और ठीक वही राइट-बैक छोड़ देता है — निष्कासन तक स्मृति बासी रहती है, और इसीलिए राइट-बैक कैश DMA व बहुसंसाधक संगति को जटिल करता है: सीधे स्मृति पढ़ता कोई अन्य कारक नवीनतम मान न देख सके। यातायात की बचत के बजाय प्रायः वही परिणाम है जिसकी ओर प्रश्न बढ़ रहा होता है।

  6. एक डिस्क 7200 rpm पर घूमती है। उसकी औसत घूर्णन-विलंबता है:

    1. 8.33 ms
    2. 4.17 ms
    3. 2.08 ms
    4. 7.2 ms
    उत्तर देखें

    उत्तर: B — 4.17 ms

    7200 rpm पर एक चक्कर 60/7200 से = 8.33 ms लेता है, और औसतन अभीष्ट सेक्टर आधा चक्कर दूर होता है, अतः औसत विलंबता 8.33 / 2 = 4.17 ms है। विकल्प A पूरा चक्कर है — निकृष्टतम स्थिति, औसत नहीं — और यहाँ सर्वाधिक सामान्य उत्तर वही है। भेद इसलिए महत्वपूर्ण है कि घूर्णन-विलंबता प्रायः वही पद है जिसे अभ्यर्थी पूर्णतः छोड़ देते हैं: 8 ms खोज तथा 4.17 ms विलंबता तथा 100 MB/s पर 4 KB अंतरित करने हेतु 0.04 ms मिलकर लगभग 12.2 ms है, और मध्य पद छोड़ना उसे एक-तिहाई कम आँकता है।

  7. क्षमता अचर रखते हुए कैश खंड-आकार बढ़ाने की प्रवृत्ति है:

    1. अनिवार्य चूक घटाना पर अंततः संघर्ष व क्षमता चूक बढ़ाना
    2. तीनों प्रकार की चूक असीम रूप से घटाना
    3. चूक-दर पर कोई प्रभाव न डालना
    4. अनिवार्य चूक बढ़ाना
    उत्तर देखें

    उत्तर: A — अनिवार्य चूक घटाना पर अंततः संघर्ष व क्षमता चूक बढ़ाना

    बड़ा खंड प्रति चूक अधिक पड़ोसी लाता है, अतः स्थानिक स्थानिकता का अधिक दोहन होता है और अनिवार्य चूक घटती हैं। परंतु क्षमता नियत है, अतः बड़े खंड का अर्थ कम पंक्तियाँ — आँकड़े रखने हेतु कम भिन्न स्थान — और एक बिंदु के बाद संघर्ष व क्षमता चूक, अनिवार्य चूक के घटने से तेज़ी से बढ़ती हैं। अतः चूक-दर का किसी मध्यवर्ती खंड-आकार पर न्यूनतम होता है, और यही U-आकार यह प्रश्न जाँच रहा है। विकल्प B नियत-क्षमता प्रतिबंध की अवहेलना करता है, और सम्पूर्ण प्रश्न उसी प्रतिबंध पर टिका है: कैश में कुछ भी बिना किसी अन्य के महँगा होने के सस्ता नहीं होता।

  8. 32-बाइट खंड व 32-बिट पते वाले 2048 पंक्तियों के पूर्णतः सहचारी कैश को कितने टैग बिट, तथा एक खोज हेतु कितने तुलनित्र चाहिए?

    1. 27 टैग बिट व 2048 तुलनित्र
    2. 16 टैग बिट व 1 तुलनित्र
    3. 27 टैग बिट व 1 तुलनित्र
    4. 11 टैग बिट व 2048 तुलनित्र
    उत्तर देखें

    उत्तर: A — 27 टैग बिट व 2048 तुलनित्र

    पूर्णतः सहचारी का अर्थ एक समुच्चय है, अतः कोई अनुक्रमणिका ही नहीं: 32 − 5 = 27 टैग बिट। और खोज सीमित करने हेतु कोई अनुक्रमणिका न होने पर टैग की तुलना 2048 पंक्तियों में प्रत्येक से एक साथ करनी होगी — 2048 तुलनित्र। वे दोनों संख्याएँ मिलकर पूर्ण सहचारिता की लागत हैं और वही कारण है कि वह TLB जैसे अत्यंत छोटे कैशों तक सीमित है। विकल्प B प्रत्यक्ष-मानचित्रित उत्तर है, जहाँ एक तुलनित्र पर्याप्त है क्योंकि अनुक्रमणिका ने वही एक पंक्ति पहले से चुन ली है जो मिल सकती थी।