c++ "कैश-फ्रेंडली" कोड क्या है?




performance caching (8)

" कैश असभ्य कोड " और " कैश अनुकूल " कोड के बीच क्या अंतर है?

मैं कैसे सुनिश्चित कर सकता हूं कि मैं कैश-कुशल कोड लिखूं?


प्रोसेसर आज कैस्केडिंग मेमोरी क्षेत्रों के कई स्तरों के साथ काम करते हैं। तो सीपीयू में स्मृति की एक गुच्छा होगी जो सीपीयू चिप पर ही है। इस स्मृति में इसकी बहुत तेज़ी से पहुंच है। कैश के विभिन्न स्तर कैश के अगले स्तर की तुलना में धीमे पहुंच (और बड़े) होते हैं, जब तक कि आप सिस्टम मेमोरी नहीं प्राप्त करते हैं जो कि CPU पर नहीं है और अपेक्षाकृत धीमी है।

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

तो आज जब आप एक पता लाते हैं तो यह कैश के पहले स्तर की जांच करता है यह देखने के लिए कि क्या वह पहले से ही उस पते को कैश में पढ़ता है, अगर उसे यह नहीं मिला है, तो यह एक कैश मिस है और इसे अगले स्तर पर जाना है कैश इसे खोजने के लिए, जब तक इसे अंततः मुख्य स्मृति में बाहर जाना नहीं है।

कैश फ्रेंडली कोड मेमोरी में एक साथ पहुंचने की कोशिश करता है ताकि आप कैश मिस को कम कर सकें।

तो एक उदाहरण कल्पना की जाएगी कि आप एक विशाल 2 आयामी तालिका की प्रतिलिपि बनाना चाहते थे। यह स्मृति में लगातार पंक्ति तक पहुंचने के साथ आयोजित किया जाता है, और एक पंक्ति के बाद अगले दाएं का पालन करें।

यदि आपने बाएं से दाएं समय में तत्वों को एक पंक्ति की प्रतिलिपि बनाई है - यह कैश अनुकूल होगा। यदि आपने एक समय में तालिका को एक कॉलम कॉपी करने का निर्णय लिया है, तो आप सटीक मात्रा में स्मृति की प्रतिलिपि बनायेंगे - लेकिन यह कैश असभ्य होगा।


प्रारंभिक

आधुनिक कंप्यूटरों पर, केवल निम्नतम स्तर की मेमोरी संरचनाएं ( रजिस्टर्स ) डेटा को एकल घड़ी चक्रों में स्थानांतरित कर सकती हैं। हालांकि, रजिस्ट्रार बहुत महंगा हैं और अधिकांश कंप्यूटर कोर में कुछ दर्जन से भी कम रजिस्ट्रार हैं (कुछ सौ से शायद एक हजार बाइट्स कुल)। मेमोरी स्पेक्ट्रम ( डीआरएएम ) के दूसरे छोर पर, स्मृति बहुत सस्ता है (यानी सचमुच लाखों बार सस्ता ) लेकिन डेटा प्राप्त करने के अनुरोध के बाद सैकड़ों चक्र लेते हैं। सुपर फास्ट एंड महंगे और सुपर धीमी और सस्ते के बीच इस अंतर को पुल करने के लिए कैश यादें , एल 1, एल 2, एल 3 नाम की गति और लागत में हैं। विचार यह है कि अधिकांश निष्पादन कोड अक्सर चर के एक छोटे से सेट को मार देगा, और बाकी (चर का एक बड़ा सेट) अक्सर। यदि प्रोसेसर L1 कैश में डेटा नहीं ढूंढ पाता है, तो यह एल 2 कैश में दिखता है। यदि वहां नहीं है, तो एल 3 कैश, और यदि नहीं, तो मुख्य स्मृति। इनमें से प्रत्येक "मिस" समय पर महंगा है।

(समानता कैश मेमोरी सिस्टम मेमोरी है, क्योंकि सिस्टम मेमोरी हार्ड डिस्क स्टोरेज है। हार्ड डिस्क स्टोरेज सुपर सस्ता है, लेकिन बहुत धीमी है)।

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

डेटा हमेशा स्मृति पदानुक्रम के माध्यम से पुनर्प्राप्त किया जाता है (सबसे छोटा == सबसे धीमा करने के लिए सबसे तेज़)। एक कैश हिट / मिस आमतौर पर सीपीयू में उच्चतम स्तर के कैश में हिट / मिस को संदर्भित करता है - उच्चतम स्तर से मेरा मतलब सबसे बड़ा == धीमा है। कैश हिट रेट प्रदर्शन के लिए महत्वपूर्ण है, क्योंकि प्रत्येक कैश के परिणाम राम से डेटा लाने में चूक जाते हैं (या बदतर ...) जिसमें बहुत समय लगता है (रैम के लिए सैकड़ों चक्र, एचडीडी के लिए लाखों चक्र)। इसकी तुलना में, (उच्चतम स्तर) कैश से डेटा पढ़ने में आमतौर पर केवल कुछ मुट्ठी चक्र होते हैं।

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

इस विषय पर बहुत कुछ कहना है। यहां कैश, मेमोरी पदानुक्रम और उचित प्रोग्रामिंग के बारे में कुछ शानदार संदर्भ दिए गए हैं:

कैश-अनुकूल कोड के लिए मुख्य अवधारणाएं

कैश-फ्रेंडली कोड का एक बहुत ही महत्वपूर्ण पहलू इलाके के सिद्धांत के बारे में है , जिसका लक्ष्य कुशल कैशिंग को अनुमति देने के लिए स्मृति में बंद डेटा को बंद करना है। सीपीयू कैश के संदर्भ में, यह समझने के लिए कैश लाइनों से अवगत होना महत्वपूर्ण है कि यह कैसे काम करता है: कैश लाइन कैसे काम करती है?

कैशिंग को अनुकूलित करने के लिए निम्नलिखित विशेष पहलू उच्च महत्व वाले हैं:

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

उपयुक्त सी ++ कंटेनर का प्रयोग करें

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

इस यूट्यूब क्लिप में बजेर्न स्ट्राउस्ट्रप द्वारा इसका एक बहुत अच्छा उदाहरण दिया गया है (लिंक के लिए @ मोहम्मद अली बेदौन के लिए धन्यवाद!)।

डेटा संरचना और एल्गोरिदम डिजाइन में कैश की उपेक्षा न करें

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

डेटा की निहित संरचना को जानें और उसका फायदा उठाएं

एक और सरल उदाहरण, जो क्षेत्र में कई लोग कभी-कभी भूल जाते हैं, कॉलम-प्रमुख (उदा। fortran , matlab ) बनाम पंक्ति-प्रमुख क्रम (उदा। c , सी ++ ) दो आयामी सरणी संग्रहीत करने के लिए होता है। उदाहरण के लिए, निम्नलिखित मैट्रिक्स पर विचार करें:

1 2
3 4

पंक्ति-प्रमुख क्रम में, यह स्मृति में 1 2 3 4 रूप में संग्रहीत किया जाता है; स्तंभ-प्रमुख क्रम में इसे 1 3 2 4 रूप में संग्रहीत किया जाएगा। यह देखना आसान है कि इस आदेश का शोषण नहीं करने वाले कार्यान्वयन जल्दी से (आसानी से टालने योग्य!) कैश मुद्दों में भाग लेंगे। दुर्भाग्य से, मैं अपने डोमेन (मशीन लर्निंग) में अक्सर इस तरह की चीजें देखता हूं। @MatteoItalia ने इस उदाहरण को अपने जवाब में अधिक विस्तार से दिखाया।

स्मृति से मैट्रिक्स का एक निश्चित तत्व लाने पर, इसके आस-पास के तत्व भी कैश लाइन में संग्रहीत किए जाएंगे। अगर ऑर्डरिंग का शोषण किया जाता है, तो इसके परिणामस्वरूप कम मेमोरी एक्सेस हो जाएगी (क्योंकि आने वाले कंप्यूटेशंस के लिए आवश्यक अगले कुछ मान पहले से ही कैश लाइन में हैं)।

सादगी के लिए, मान लें कि कैश में एक कैश लाइन होती है जिसमें 2 मैट्रिक्स तत्व हो सकते हैं और जब किसी दिए गए तत्व को स्मृति से प्राप्त किया जाता है, तो अगला भी होता है। मान लें कि हम उपरोक्त उदाहरण 2x2 मैट्रिक्स में सभी तत्वों पर योग लेना चाहते हैं (इसे M कॉल करें):

ऑर्डरिंग का पता लगाना (उदाहरण के लिए पहले सी ++ में कॉलम इंडेक्स बदलना):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

आदेश का शोषण नहीं कर रहा है (उदाहरण के लिए पहले सी ++ में पंक्ति सूचकांक बदलना):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

इस सरल उदाहरण में, आदेश का शोषण लगभग दोगुनी निष्पादन गति (क्योंकि मेमोरी एक्सेस को रकम की गणना करने से अधिक चक्र की आवश्यकता होती है)। अभ्यास में प्रदर्शन अंतर बहुत बड़ा हो सकता है

अप्रत्याशित शाखाओं से बचें

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

यह यहां बहुत अच्छी तरह से समझाया गया है (लिंक के लिए @ 0x 9 0 के लिए धन्यवाद): एक अनुरक्षित सरणी की तुलना में एक क्रमबद्ध सरणी को संसाधित करना क्यों तेज़ है?

आभासी कार्यों से बचें

सी ++ के संदर्भ में, virtual विधियां कैश मिस के संबंध में एक विवादास्पद समस्या का प्रतिनिधित्व करती हैं (एक आम सहमति यह है कि प्रदर्शन के संदर्भ में उन्हें संभवतः टालना चाहिए)। वर्चुअल फ़ंक्शन लुक अप के दौरान कैश मिस को प्रेरित कर सकते हैं, लेकिन यह तब होता है जब विशिष्ट फ़ंक्शन को अक्सर नहीं कहा जाता है (अन्यथा इसे कैश किया जाएगा), इसलिए इसे कुछ लोगों द्वारा गैर-समस्या के रूप में माना जाता है। इस समस्या के संदर्भ में, जांचें: सी ++ कक्षा में वर्चुअल विधि होने की प्रदर्शन लागत क्या है?

सामान्य समस्यायें

मल्टीप्रोसेसर कैश वाले आधुनिक आर्किटेक्चर में एक आम समस्या को झूठी साझाकरण कहा जाता है। यह तब होता है जब प्रत्येक व्यक्तिगत प्रोसेसर किसी अन्य मेमोरी क्षेत्र में डेटा का उपयोग करने का प्रयास कर रहा है और उसी कैश लाइन में इसे स्टोर करने का प्रयास करता है। यह कैश लाइन का कारण बनता है - जिसमें डेटा होता है, दूसरा प्रोसेसर उपयोग कर सकता है - बार-बार ओवरराइट किया जा सकता है। प्रभावी रूप से, अलग-अलग धागे एक दूसरे को इस स्थिति में कैश मिस को प्रेरित करके प्रतीक्षा करते हैं। यह भी देखें (लिंक के लिए @ मैट के लिए धन्यवाद): लाइन आकार कैश करने के लिए कैसे और कब संरेखित करें?

रैम मेमोरी में खराब कैशिंग का एक चरम लक्षण (जो शायद इस संदर्भ में आपका मतलब नहीं है) तथाकथित thrashing । ऐसा तब होता है जब प्रक्रिया लगातार पृष्ठ दोष उत्पन्न करती है (उदाहरण के लिए स्मृति को एक्सेस करता है जो वर्तमान पृष्ठ में नहीं है) जिसके लिए डिस्क एक्सेस की आवश्यकता होती है।


ध्यान रखें कि कैश लगातार स्मृति को कैश नहीं करते हैं। उनके पास कई रेखाएं हैं (कम से कम 4) इसलिए असंतोषजनक और अतिव्यापी स्मृति अक्सर कुशलतापूर्वक संग्रहीत की जा सकती है।

उपरोक्त सभी उदाहरणों से क्या गुम है, मापित मानदंड है। प्रदर्शन के बारे में कई मिथक हैं। जब तक आप इसे माप नहीं लेते हैं, आपको नहीं पता। अपने कोड को तब तक जटिल न करें जब तक आपके पास कोई मापन सुधार न हो।


डेटा ओरिएंटेड डिजाइन की दुनिया में आपका स्वागत है। मूल मंत्र क्रमबद्ध करना, शाखाओं को हटा देना, बैच, virtual कॉल को खत्म करना - बेहतर इलाके की दिशा में सभी कदम।

चूंकि आपने सी ++ के साथ प्रश्न टैग किया है, यहां अनिवार्य सामान्य सी ++ बुल्शिट हैऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग के टोनी अल्ब्रेक्ट की समस्याएं इस विषय में भी एक महान परिचय है।


जैसा कि @ मार्क क्लैसेन ने उल्लेख किया है कि कैश अनुकूल कोड लिखने के तरीकों में से एक है उस संरचना का फायदा उठाना जिसमें हमारे डेटा को संग्रहीत किया जाता है। कैश अनुकूल कोड लिखने का एक और तरीका यह है कि: हमारे डेटा को संग्रहीत करने के तरीके को बदलें; फिर इस नई संरचना में संग्रहीत डेटा तक पहुंचने के लिए नया कोड लिखें।

यह समझ में आता है कि कैसे डेटाबेस सिस्टम तालिका के tuples रैखिकरण और उन्हें स्टोर। एक टेबल यानी पंक्ति स्टोर और कॉलम स्टोर के tuples को स्टोर करने के दो बुनियादी तरीके हैं। पंक्ति स्टोर में नाम के अनुसार सुझाव मिलता है कि टुपल्स पंक्ति के अनुसार संग्रहीत होते हैं। मान लीजिए कि int32_t key, char name[56] किए जाने वाले Product एक तालिका में 3 गुण हैं यानी int32_t key, char name[56] और int32_t price , इसलिए int32_t price का कुल आकार 64 बाइट है।

हम आकार एन के साथ Product structs की एक सरणी बनाकर मुख्य स्मृति में एक बहुत ही मूल पंक्ति स्टोर क्वेरी निष्पादन अनुकरण कर सकते हैं, जहां एन तालिका में पंक्तियों की संख्या है। इस तरह के मेमोरी लेआउट को structs की सरणी भी कहा जाता है। तो उत्पाद के लिए संरचना इस प्रकार हो सकती है:

struct Product
{
   int32_t key;
   char name[56];
   int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

इसी तरह हम मुख्य तालिका में एक मूलभूत कॉलम स्टोर क्वेरी निष्पादन अनुकरण कर सकते हैं, आकार तालिका के 3 सरणी बनाकर, Product तालिका के प्रत्येक विशेषता के लिए एक सरणी बनाकर। इस तरह के मेमोरी लेआउट को सरणी की संरचना भी कहा जाता है। इसलिए उत्पाद की प्रत्येक विशेषता के लिए 3 सरणी इस प्रकार हो सकती हैं:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

अब structs (पंक्ति लेआउट) और 3 अलग सरणी (कॉलम लेआउट) दोनों की सरणी लोड करने के बाद, हमारे पास हमारे टेबल पर मौजूद हमारे टेबल Product पर पंक्ति स्टोर और कॉलम स्टोर है।

अब हम कैश फ्रेंडली कोड भाग पर जाते हैं। मान लीजिए कि हमारी तालिका पर वर्कलोड ऐसा है कि हमारे पास मूल्य विशेषता पर एकत्रीकरण क्वेरी है। जैसे कि

SELECT SUM(price)
FROM PRODUCT

पंक्ति स्टोर के लिए हम उपरोक्त SQL क्वेरी को रूपांतरित कर सकते हैं

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

कॉलम स्टोर के लिए हम उपरोक्त SQL क्वेरी को कन्वर्ट कर सकते हैं

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

कॉलम स्टोर के लिए कोड इस क्वेरी में पंक्ति लेआउट के लिए कोड से तेज़ होगा क्योंकि इसे केवल गुणों का एक सबसेट चाहिए और कॉलम लेआउट में हम केवल वही कर रहे हैं यानी केवल मूल्य कॉलम तक पहुंच रहे हैं।

मान लीजिए कि कैश लाइन का आकार 64 बाइट है।

जब कैश लाइन पढ़ी जाती है तो पंक्ति लेआउट के मामले में, केवल 1 का मूल्य मान ( cacheline_size/product_struct_size = 64/64 = 1 ) tuple पढ़ा जाता है, क्योंकि हमारे बाइट 64 बाइट्स का आकार और यह हमारी पूरी कैश लाइन भरता है, इसलिए एक पंक्ति लेआउट के मामले में प्रत्येक tuple के लिए एक कैश मिस होता है।

जब कैश लाइन पढ़ी जाती है तो कॉलम लेआउट के मामले में, 16 का मूल्य मान ( cacheline_size/price_int_size = 64/4 = 16 ) tuples पढ़ा जाता है, क्योंकि स्मृति में संग्रहीत 16 संगत मूल्य मान कैश में लाए जाते हैं, इसलिए प्रत्येक के लिए कॉलम लेआउट के मामले में सोलहवीं एक कैश मिस ocurs tuple।

तो कॉलम लेआउट दिए गए प्रश्न के मामले में तेज़ होगा, और तालिका के कॉलम के सबसेट पर इस तरह के एकत्रीकरण प्रश्नों में तेज़ है। आप TPC-H बेंचमार्क से डेटा का उपयोग करके अपने लिए इस तरह के प्रयोग का प्रयास कर सकते हैं, और दोनों लेआउट के लिए रन टाइम की तुलना कर सकते हैं। स्तंभ उन्मुख डेटाबेस सिस्टम पर wikipedia लेख भी अच्छा है।

तो डेटाबेस सिस्टम में, यदि क्वेरी वर्कलोड पहले से ज्ञात है, तो हम अपने डेटा को लेआउट में स्टोर कर सकते हैं जो वर्कलोड में क्वेरी के अनुरूप होगा और इन लेआउट से डेटा एक्सेस करेगा। उपर्युक्त उदाहरण के मामले में हमने एक कॉलम लेआउट बनाया और गणना के लिए हमारे कोड को बदल दिया ताकि यह कैश अनुकूल हो।


ऑप्टिमाइज़िंग कैश उपयोग काफी हद तक दो कारकों तक आता है।

संदर्भ की लोकैलिटी

पहला कारक (जिसके लिए दूसरों ने पहले से ही संकेत दिया है) संदर्भ का इलाका है। संदर्भ की लोकैलिटी में वास्तव में दो आयाम हैं: अंतरिक्ष और समय।

  • स्थानिक

स्थानिक आयाम भी दो चीजों तक आता है: सबसे पहले, हम अपनी जानकारी को घनत्व से पैक करना चाहते हैं, इसलिए उस सीमित स्मृति में अधिक जानकारी फिट होगी। इसका मतलब है (उदाहरण के लिए) कि आपको पॉइंटर्स द्वारा जुड़े छोटे नोड्स के आधार पर डेटा संरचनाओं को उचित ठहराने के लिए कम्प्यूटेशनल जटिलता में एक बड़ा सुधार की आवश्यकता है।

दूसरा, हम ऐसी जानकारी चाहते हैं जिसे एक साथ संसाधित किया जाएगा। एक ठेठ कैश "लाइनों" में काम करता है, जिसका अर्थ है कि जब आप कुछ जानकारी तक पहुंचते हैं, तो पास के पते पर अन्य जानकारी कैश में लोड की गई हिस्से के साथ लोड की जाएगी। उदाहरण के लिए, जब मैं एक बाइट स्पर्श करता हूं, तो कैश उस के पास 128 या 256 बाइट लोड कर सकता है। इसका लाभ उठाने के लिए, आप आम तौर पर डेटा को उस संभावना को अधिकतम करने के लिए व्यवस्थित करना चाहते हैं जिसे आप उसी डेटा को भी उसी समय उपयोग करेंगे जो एक ही समय में लोड किया गया था।

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

  • पहर

समय आयाम का अर्थ है कि जब आप कुछ डेटा पर कुछ संचालन करते हैं, तो आप उस डेटा पर सभी कार्यों को एक साथ करने के लिए (जितना संभव हो) चाहते हैं।

चूंकि आपने इसे सी ++ के रूप में टैग किया है, इसलिए मैं अपेक्षाकृत कैश- std::valarray डिज़ाइन का क्लासिक उदाहरण इंगित करूंगा: std::valarrayvalarray अधिकांश अंकगणितीय ऑपरेटरों overloads, तो मैं (उदाहरण के लिए) a = b + c + d; कह सकते हैं a = b + c + d; (जहां a , b , c और d सभी वैलेर होते हैं) उन सरणी के तत्व-वार जोड़ के लिए।

इसके साथ समस्या यह है कि यह इनपुट की एक जोड़ी के माध्यम से चलता है, परिणाम अस्थायी में डालता है, इनपुट की एक और जोड़ी के माध्यम से चलता है, और इसी तरह। बहुत सारे डेटा के साथ, अगले गणना में उपयोग किए जाने से पहले एक गणना से परिणाम कैश से गायब हो सकता है, इसलिए हम अंतिम परिणाम प्राप्त करने से पहले डेटा को बार-बार पढ़ना (और लिखना) समाप्त कर देते हैं। यदि अंतिम परिणाम का प्रत्येक तत्व कुछ ऐसा होगा (a[n] + b[n]) * (c[n] + d[n]); , हम आम तौर पर a[n] , b[n] , c[n] और d[n] एक बार पढ़ना पसंद करेंगे, गणना करें, परिणाम लिखें, वृद्धि n और दोहराएं 'जब तक हम कर रहे हैं। 2

रेखा साझा करना

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

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

समस्या शायद स्पष्ट रूप से स्पष्ट है: प्रत्यक्ष-मैप किए गए कैश के लिए, एक ही कैश स्थान पर मानचित्र करने के लिए होने वाले दो ऑपरेंड खराब व्यवहार का कारण बन सकते हैं। एक एन-वे सेट सेट-एसोसिएटिव कैश 2 से एन + 1 तक की संख्या बढ़ाता है। अधिक "तरीकों" में कैश को व्यवस्थित करना अतिरिक्त सर्किटरी लेता है और आम तौर पर धीमा चलता है, इसलिए (उदाहरण के लिए) 8192-रास्ता सेट एसोसिएटिव कैश शायद ही कभी एक अच्छा समाधान है।

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

  • झूठी शेयरिंग

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

  1. जो लोग सी ++ को जानते हैं वे आश्चर्यचकित हो सकते हैं कि क्या यह अभिव्यक्ति टेम्पलेट्स जैसे कुछ के माध्यम से अनुकूलन के लिए खुला है। मुझे पूरा यकीन है कि जवाब यह है कि हाँ, यह किया जा सकता है और यदि यह था, तो यह शायद एक बहुत ही महत्वपूर्ण जीत होगी। मुझे ऐसा करने के बारे में पता नहीं है, हालांकि, और यह देखते हुए कि कितना कम valarray उपयोग किया जाता है, मैं कम से कम आश्चर्यचकित होता हूं कि कोई भी ऐसा करता है।

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

  3. हां, मैं सरलीकृत कर रहा हूं: अधिकांश कैश वास्तव में कम से कम हाल ही में उपयोग किए गए आइटम को सटीक रूप से मापते नहीं हैं, लेकिन वे कुछ ह्युरिस्टिक का उपयोग करते हैं जिसका उद्देश्य प्रत्येक पहुंच के लिए पूर्णकालिक-स्टैंप रखने के बिना उस के करीब होना है।


@Marc Claesen के उत्तर के अलावा, मुझे लगता है कि कैश-असभ्य कोड का एक निर्देशक क्लासिक उदाहरण कोड है जो पंक्ति-वार के बजाय सी बोली-आयामी सरणी (उदाहरण के लिए बिटमैप छवि) कॉलम-वार स्कैन करता है।

पंक्तियों के आस-पास के तत्व स्मृति में भी आसन्न हैं, इस प्रकार अनुक्रम में उन्हें एक्सेस करने का अर्थ है आरोही स्मृति क्रम में उन्हें एक्सेस करना; यह कैश-अनुकूल है, क्योंकि कैश मेमोरी के संगत ब्लॉक को प्रीफेच करता है।

इसके बजाए, कॉलम-वार जैसे तत्वों को एक्सेस करना कैश-असभ्य है, क्योंकि एक ही कॉलम के तत्व एक दूसरे से स्मृति में दूर हैं (विशेष रूप से, उनकी दूरी पंक्ति के आकार के बराबर होती है), इसलिए जब आप इस एक्सेस पैटर्न का उपयोग करते हैं मेमोरी में आस-पास के तत्वों को पुनः प्राप्त करने के कैश के संभावित प्रयास को संभावित रूप से स्मृति में चारों ओर कूद रहे हैं।

और प्रदर्शन को बर्बाद करने के लिए जो कुछ भी लगता है वह है

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

सेवा मेरे

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

यह प्रभाव छोटे कैश और / या बड़े सरणी के साथ काम करने वाले सिस्टम में काफी नाटकीय (गति में परिमाण के कई क्रम) हो सकता है (उदाहरण के लिए मौजूदा मशीनों पर 10+ मेगापिक्सेल 24 बीपीपी छवियां); इस कारण से, यदि आपको कई लंबवत स्कैन करना पड़ता है, तो अक्सर 90 डिग्री की छवि को घुमाने के लिए बेहतर होता है और बाद में विभिन्न विश्लेषण निष्पादित करता है, कैश-असभ्य कोड को केवल घूर्णन तक सीमित करता है।


बस इस पर पिलिंग: कैश-असभ्य बनाम कैश-फ्रेंडली कोड का क्लासिक उदाहरण मैट्रिक्स गुणा के "कैश अवरुद्ध" है।

बेवकूफ मैट्रिक्स गुणा दिखता है

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

यदि N बड़ा है, उदाहरण के लिए यदि N * sizeof(elemType) कैश आकार से अधिक है, तो src2[k][j] प्रत्येक पहुंच एक कैश मिस होगी।

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

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

यदि कैश लाइन आकार 64 बाइट्स है, और हम 32 बिट (4 बाइट) फ्लोट पर काम कर रहे हैं, तो प्रति कैश लाइन में 16 आइटम हैं। और इस सरल परिवर्तन के माध्यम से कैश की संख्या याद आती है लगभग 16 गुना कम हो जाती है।

फैनसीर ट्रांसफॉर्मेशन 2 डी टाइल्स पर काम करते हैं, कई कैश (एल 1, एल 2, टीएलबी) के लिए अनुकूलित करते हैं, और इसी तरह।

"कैश अवरुद्ध" googling के कुछ परिणाम:

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

एक अनुकूलित कैश ब्लॉकिंग एल्गोरिदम की एक अच्छी वीडियो एनीमेशन।

http://www.youtube.com/watch?v=IFWgwGMMrh0

लूप टाइलिंग बहुत करीबी से संबंधित है:

http://en.wikipedia.org/wiki/Loop_tiling





cpu-cache