कैश विशेषताओं का प्रयोग

कुछ मामलों में (उदाहरण के लिए, किसी विशिष्ट कंप्यूटर के लिए प्रोग्राम को फाइन-ट्यूनिंग के लिए) यह कैश सबसिस्टम की विशेषताओं को जानने के लिए उपयोगी है: स्तरों की संख्या, प्रत्येक स्तर तक पहुंच का समय, उनके आकार और सहकारिता, आदि।

एक बार के अनुकूलन के लिए, कंप्यूटर पर विनिर्देशों में आवश्यक मान पाए जा सकते हैं, लेकिन जब स्वचालित अनुकूलन की आवश्यकता होती है (उदाहरण के लिए, विधानसभा और कार्यक्रम की स्थापना के दौरान), तो विशेषताओं को एक विशेष परीक्षण सूट के परिणामों द्वारा अप्रत्यक्ष रूप से निर्धारित किया जाना है।

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

एक ग्राफ का एक उदाहरण जो एक वास्तविक प्रणाली पर इस कार्यक्रम द्वारा प्राप्त किया गया था:



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

प्रत्येक ब्लॉक के लिए, एक टैग संग्रहीत किया जाता है जिसमें मुख्य मेमोरी में ब्लॉक में संग्रहीत डेटा का पता होता है। मेमोरी को एक्सेस करते समय, वांछित सेट के टैग के साथ वांछित सेट के सभी टैग की तुलना की जाती है। उदाहरण के लिए, 4 विंडो में 32 ब्लॉक के कैश के लिए:







इस तथ्य के कारण कि सेट को पते के कम से कम महत्वपूर्ण बिट्स द्वारा चुना गया है, मेमोरी में एक निरंतर सरणी कैश में लगातार स्थित होगी। उदाहरण के लिए, यदि ब्लॉक का आकार 64 बाइट्स है, और सरणी का पहला ब्लॉक सेट 0 में है:







यदि सरणी को पूरे कैश में रखा गया है, तो जब इसे एक्सेस किया जाता है, तो कोई भी याद नहीं होती है: सरणी के प्रत्येक बाद का ब्लॉक अगली फ्री वेव में गिरता है। सरणी से गुजरने के बाद, इसे कैश से पढ़ा जाएगा, और मेमोरी के अगले स्तर तक नई पहुंच की आवश्यकता नहीं होगी।

यदि सरणी का आकार कैश के आकार से अधिक है, तो LRU नियम के अनुसार, सरणी के पहले ब्लॉकों को उसके अंतिम ब्लॉकों से बदल दिया जाएगा। उदाहरण के लिए, यदि किसी सरणी में 35 ब्लॉक हैं, तो पहले तीन ब्लॉक बाहर निकाले जाएंगे:







अब, सरणी के माध्यम से दूसरे पास के दौरान, पहले तीन सेट अगले मेमोरी स्तर से एक नए तरीके से भरे जाएंगे, और शेष पांच सेट सीधे कैश से पढ़े जाएंगे। दूसरे पास के अंत में, अंतिम तीन ब्लॉक फिर से सरणी के पहले ब्लॉकों को सुपरडेड करेंगे:







इस प्रकार, प्रत्येक बाद के पास के साथ, 20 ब्लॉक कैश से पढ़ा जाएगा, और शेष 15 अगले मेमोरी स्तर से। जब सरणी का आकार कैश के आकार को एक पूरी लहर (हमारे उदाहरण में, 8 ब्लॉक द्वारा) से अधिक हो जाता है, तो पास के बीच का डेटा कैश में संग्रहीत नहीं किया जाएगा: प्रत्येक कॉल एक मिस को ले जाएगा और अगले स्तर की मेमोरी से एक नया ब्लॉक पढ़ने के लिए।



सूखे अवशेषों में हमारे पास क्या है?

• जबकि ऐरे कैश से छोटा है, एक्सेस टाइम स्थिर रहेगा (0% मिसे)
• जब सरणी एक लहर से कम कैश से बड़ी होती है, तो पहुंच का समय "अधिशेष" के आकार पर निर्भर करेगा
• जब ऐरे एक या एक से अधिक कैशे से बड़ा होता है, तो उस तक पहुंचने का समय स्थिर (100% मिसे) होगा

इसलिए, कैश का प्रत्येक स्तर ग्राफ पर एक "चरण" से मेल खाता है, और कैश का आकार चरण के बाएं किनारे है । शुरुआत में ग्राफ पर, दो चरण हैं - 32KB और लगभग 4MB, जिसका अर्थ है कि कैश दो-स्तरीय है।

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



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



सरणी के आकार पर पहुंच समय की निर्भरता का विश्लेषण किया जाता है। चरण आकार के बारे में क्या? पहला महत्वपूर्ण तथ्य: समान सरणी आकार के लिए, चरण का आकार प्रकोपों ​​की संख्या को प्रभावित नहीं करता है। यदि चरण ब्लॉक आकार से बड़ा है, तो पूरे सरणी को कैश में नहीं पढ़ा जाएगा, लेकिन व्यक्तिगत ब्लॉक; सेट का एक हिस्सा मुक्त रहेगा। किसी भी स्थिति में, हम 0% मिसेज़ तब तक प्राप्त करते हैं जब तक कि ऐरे कैश से कम न हो जाए, और ऐरे एक और तरीका होने पर 100% छूट जाए। उदाहरण के लिए, 36 ब्लॉक की एक सरणी के लिए, और 128 बाइट्स (2 ब्लॉक) का एक चरण:







प्रत्येक पास पर, 0 और 2 के सेट में एक मिस होता है, और 10 ब्लॉक को नए तरीके से मेमोरी से पढ़ा जाता है। सेट 4 और 6 (8 ब्लॉक) की सामग्री पास के बीच बचाई जाती है, और सीधे कैश से पढ़ी जाती है। हमारे पास 10/18 = 56% मिस हैं। यदि चरण 256 बाइट्स (4 ब्लॉक) है:







प्रत्येक पास पर, सेट 0 में एक मिस होता है, और 5 ब्लॉक को नए तरीके से मेमोरी से पढ़ा जाता है। सेट 4 (4 ब्लॉक) की सामग्री पास से बचाई जाती है, और सीधे कैश से पढ़ी जाती है। हमारे पास 5/9 = 56% मिस हैं।



यदि चरण का आकार पंखे के आकार से अधिक हो जाता है, तो स्थिति कुछ हद तक बदल जाती है: इस मामले में, "छूटे हुए" प्रशंसक मुक्त रहते हैं, और सरणी के सभी रीड ब्लॉक कैश में रखे जाते हैं, भले ही सरणी स्वयं कैश आकार से बड़ा हो। उदाहरण के लिए, 64 ब्लॉक की एक सरणी के लिए, और किलोबाइट्स (16 ब्लॉक) में एक कदम, केवल चार ब्लॉक पढ़े जाते हैं, और वे सभी एक ही सेट में आते हैं:







एक समान स्थिति हमेशा एक पूरी तरह से साहचर्य कैश के साथ होती है, जिसमें प्रशंसक का आकार ब्लॉक के आकार से मेल खाता है। इस तरह के मार्ग की एक विशिष्ट विशेषता यह है कि कदम के आकार के आधार पर कदम की बाईं ओर बदलाव होता है: दो बार बड़े कदम के रूप में दो बार बड़े "स्पष्ट" कैश आकार से मेल खाती है, क्योंकि पढ़ने के दौरान हर दूसरी लहर "स्किप" होती है।



शुरुआत में ग्राफ में, चरणों के बाएं किनारे सभी चरण आकारों के लिए मेल खाते हैं - जिसका अर्थ है कि प्रत्येक कैश का आकार अधिकतम किए गए चरण आकारों की तुलना में बड़ा है, और कम से कम 4 KB है। L1 कैश के लिए, हम एक ऊर्ध्वाधर कदम देखते हैं: 32KB की एक सरणी के लिए 0% छूट, और 36KB की एक सरणी के लिए 100% छूट। जैसा कि हमने ऊपर देखा, इसका मतलब है कि 4KB पूरक पूरे तरीके से भरता है; इसलिए, प्रशंसक का आकार बिल्कुल 4KB है, अर्थात। L1 कैश आठ-आठ।



L2 कैश के लिए, हम लगभग 12MB तक एक रैखिक वृद्धि देखते हैं, अर्थात्। कैश के आकार को दोगुना करने के लिए, जो एक गैर-सहयोगी कैश से मेल खाती है। हालांकि, प्रोसेसर विनिर्देश बताता है कि L2 कैश 24-वे है, अर्थात। 256KB के आकार के साथ। हम यह निष्कर्ष निकाल सकते हैं कि या तो कैश का कार्यान्वयन विनिर्देश को पूरा नहीं करता है (क्या किसी ने इस पर ध्यान दिया होगा?), या प्रशंसक का चयन करने के लिए एल्गोरिथ्म LRU से अलग है। किसी भी मामले में, यह ध्यान देने योग्य है कि कैश का वास्तविक पहुंच समय जब एक बड़े सरणी के माध्यम से साइकिल चलाना बेहतर हो जाता है (चापलूसी कदम) की तुलना में अगर कैश वास्तव में एक 24-रास्ता LRU था।



और कुछ दिलचस्प घटनाएं जो चार्ट पर देखी जा सकती हैं। 1 एमबी सरणी से शुरू होकर, मेमोरी तक पहुंच का समय स्टेप साइज पर निर्भर करता है - जैसा कि हमने ऊपर देखा, यह कैश मिस की घटना से नहीं समझाया जा सकता है। एक समान तस्वीर देखी जाएगी यदि चरण का आकार ब्लॉक आकार से छोटा था: तो कैश ओवरफ्लो के बाद, मिसाइलों की संख्या 100% तक नहीं पहुंचती है, लेकिन चरण के आकार के आधार पर एक निम्न स्तर। एक आधे-ब्लॉक के चरण के लिए हमें 50% की छूट मिलती है (अगले स्तर की मेमोरी से ब्लॉक के प्रत्येक पढ़ने के बाद, हम कैश से अगला सरणी तत्व पढ़ते हैं); एक चौथाई ब्लॉक कदम के लिए हमें 25% मिसेज़ (मेमोरी से प्रत्येक ब्लॉक पढ़ने के बाद - कैश से तीन रीड्स), आदि मिलते हैं। कैश में कई किलोबाइट के ब्लॉक कैसे हो सकते हैं?



जैसा कि आप अनुमान लगा सकते हैं, यह स्मृति का पेजिंग संगठन है, और DTLB अतिप्रवाह है। 1 एमबी 256 चार-किलोबाइट पृष्ठ हैं; इसलिए, हमारे DTLB की क्षमता 256 रिकॉर्ड है। जब सरणी 1 एमबी से अधिक हो जाती है, तो हर बार जब आप किसी तत्व को पढ़ते हैं, तो सरणी के वास्तविक डेटा को पढ़ने के अलावा, आपको मेमोरी से पेज टेबल एंट्री (PTE) भी पढ़ना होगा। 512 बाइट्स के एक चरण के लिए, हर PTE पढ़ने के बाद, DTLB में सात हिट्स, और 12% मिसेस मुश्किल से पहुंच के समय को सरणी तक बढ़ाते हैं। दूसरी ओर, 4KB के एक चरण के लिए, प्रत्येक PTE रीडिंग मेमोरी (DTLB में 100% छूट) से की जाती है, और एक्सेस टाइम में काफी वृद्धि होती है। हम देखते हैं कि DTLB में 100% मिसेज़ तुरंत हासिल नहीं की जाती हैं, लेकिन आकार में 1280KB की एक सरणी पर, अर्थात् DTLB की क्षमता का एक चौथाई। हम इससे निष्कर्ष निकालते हैं कि DTLB फोर-लेन है।



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

नव वर्ष की शुभकामनाएँ, Habrovsk!