साझा करना हमेशा उपयोगी नहीं होता: कैश मेमोरी के साथ काम का अनुकूलन करना

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

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

नीचे हम बहु-थ्रेडेड कार्यक्रमों के प्रदर्शन की समस्याओं के एक सरल लेकिन सांकेतिक मामले पर विचार करेंगे, और फिर मैं थ्रेड के बीच कैश के अलग होने के कारण कंप्यूटिंग दक्षता के नुकसान से बचने के लिए कुछ सामान्य सिफारिशें दूंगा।


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

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


एक समस्या के लिए शर्तें:
दो या अधिक धागे एक ही कैश लाइन में लिखते हैं;
एक धागा लिखता है, बाकी कैश लाइन से पढ़ते हैं;
एक धागा लिखता है, शेष कोर में, एचडब्ल्यू प्रीफ़ेचर ने काम किया।


यह पता चल सकता है कि विभिन्न संरचनाओं के क्षेत्रों में चर स्मृति में इतने स्थित हैं कि, प्रोसेसर के एल 1 कैश में पढ़ा जा रहा है, वे एक ही कैश लाइन में हैं, जैसा कि आंकड़े में है। इसी समय, यदि थ्रेड्स में से एक इसकी संरचना के क्षेत्र को संशोधित करता है, तो कैश प्रोसेसर के प्रोटोकॉल के अनुसार पूरी कैश लाइन, शेष प्रोसेसर कोर के लिए अमान्य घोषित की जाती है। एक और धागा अब इस संरचना का उपयोग करने में सक्षम नहीं होगा, इस तथ्य के बावजूद कि यह पहले से ही अपने कोर के एल 1 कैश में निहित है। P4 जैसे पुराने प्रोसेसर में, ऐसी स्थिति में, मुख्य मेमोरी के साथ एक लंबे सिंक्रोनाइज़ेशन की आवश्यकता होगी, अर्थात संशोधित डेटा को मुख्य मेमोरी में भेजा जाएगा और फिर दूसरे कोर के L1 कैश में पढ़ा जाएगा। प्रोसेसर की वर्तमान पीढ़ी (कोडेन सैंडी ब्रिज) में, तुल्यकालन तंत्र एक सामान्य तृतीय-स्तरीय कैश (या LLC - अंतिम स्तर कैश) का उपयोग करता है, जो कैश सबसिस्टम के लिए समावेशी है और जिसमें L2 और L1 दोनों में स्थित सभी डेटा शामिल हैं सभी प्रोसेसर कोर। इस प्रकार, सिंक्रनाइज़ेशन मुख्य मेमोरी के साथ नहीं होता है, लेकिन एलएलसी के साथ, जो कैश सुसंगतता तंत्र के प्रोटोकॉल के कार्यान्वयन का हिस्सा है, जो बहुत तेज है। लेकिन यह अभी भी होता है, और इसमें कुछ समय लगता है, हालांकि सिर्फ कुछ दर्जन प्रोसेसर चक्रों में मापा जाता है। और यदि कैश लाइन में डेटा विभिन्न भौतिक प्रोसेसर पर चलने वाले थ्रेड्स के बीच साझा किया जाता है? फिर एलएलसी विभिन्न चिप्स के बीच सिंक्रनाइज़ करना आवश्यक होगा, और यह बहुत लंबा है - सैकड़ों चक्र। अब मान लीजिए कि कार्यक्रम केवल इस तथ्य से संबंधित है कि एक चक्र में यह किसी भी स्रोत से प्राप्त डेटा के प्रवाह को संसाधित करता है। चक्र के प्रत्येक पुनरावृत्ति पर सैकड़ों घड़ी चक्र खोने से, हम कई बार अपना प्रदर्शन खोने का जोखिम उठाते हैं।

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

एक लूप में एक स्ट्रीम फ़ंक्शन दो सरणियों के माध्यम से चलता है [i] और b [i], अपने मूल्यों को सरणी इंडेक्स से गुणा करता है और धाराओं के स्थानीय चर में स्थानीयसम [tid] जोड़ता है। प्रभाव को बढ़ाने के लिए, यह ऑपरेशन कई बार (ITERATIONS) किया जाता है।

int work(void *pArg) { int j = 0, i = 0; int tid = (int) pArg; for (j = 0; j < ITERATIONS; j++){ for (i = tid; i < MAXSIZE; i+= NUM_PROCS){ a[i] = i + a[i] * b[i]; localSum[tid] += a[i];}} } 

परेशानी यह है कि धाराओं के बीच डेटा को अलग करने के लिए, लूप इंडेक्स को इंटरलेक्ट करने की विधि को चुना जाता है। यही है, अगर दो धाराएँ हमारे लिए काम करती हैं, तो पहला, सरणियों के तत्वों को संदर्भित करेगा [0] और b [0], तत्वों के लिए दूसरा [1] और b [1], पहला से एक [2] और b [2] ], दूसरा - एक [3] और बी [3], और इसी तरह। सरणी के तत्व [i] थ्रेड द्वारा संशोधित किए गए हैं। यह देखना मुश्किल नहीं है कि सरणी के 16 तत्व एक कैश लाइन में गिर जाएंगे, और धागे एक साथ पड़ोसी तत्वों तक पहुंच जाएंगे, प्रोसेसर कैश सिंक्रोनाइज़ेशन तंत्र के "मन को चला रहा है"।



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



यदि किसी को इस मीट्रिक के पीछे क्या दिलचस्पी है, तो जटिल प्रोफाइलिंग के दौरान, उपकरण अन्य हार्डवेयर काउंटरों के बीच काउंटर डेटा एकत्र करता है:
MEM_LOAD_UOPS_LLC_HIT_RETIRED.XSNP_HITM_PS - लोडिंग (लोड) का पूरा काउंटर (PS) ऑपरेशन (OUPS) (LOAD), डेटा (MEM), जो LLC में (HIT) और संशोधित (M) हो गया है। एक "सटीक" काउंटर का मतलब है कि नमूने में इस तरह के एक काउंटर द्वारा एकत्र किए गए डेटा को निर्देश के बाद निर्देश सूचक (आईपी) को संदर्भित करता है, जो कि वही डाउनलोड था जो कैश सिंक्रनाइज़ेशन का कारण बना। इस मीट्रिक पर आंकड़े एकत्र करने के बाद, हम कुछ सटीकता के साथ निर्देश का पता बता सकते हैं, और, तदनुसार, स्रोत कोड की पंक्ति जहां रीडिंग बनाई गई थी। वीटीएन एम्पलीफायर एक्सई दिखा सकता है कि कौन सी स्ट्रीम इस डेटा को पढ़ती हैं, और फिर हमें पहले से ही पता लगाना चाहिए कि मल्टीथ्रेड डेटा एक्सेस कैसे लागू किया जाता है और स्थिति को कैसे ठीक किया जाए।



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

 int work(void *pArg) { int j = 0, i = 0; int tid = (int) pArg; for (j = 0; j < ITERATIONS; j++){ chunks = MAXSIZE / NUM_PROCS; for (i = tid * chunks; i < (tid + 1) * chunks; i++){ a[i] = i + a[i] * b[i]; localSum[tid] += a[i];}} } 

गलत बंटवारा

कोई झूठा बंटवारा नहीं

गलत साझाकरण के मामले में और सही कोड में सरणी तत्वों तक थ्रेड एक्सेस की तुलना

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

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

यदि आप बहु-थ्रेडेड मोड में डेटा संरचनाओं के साथ काम करते हैं, तो उनके आकार पर ध्यान दें। संरचना के आकार को 64 बाइट्स बढ़ाने के लिए पैडिंग का उपयोग करें:

 struct data_packet { int address[4]; int data[8]; int attribute; int padding[3]; } 

संरेखित पते पर संरचनाओं के लिए स्मृति आवंटित करें:

 __declspec(align(64)) struct data_packet sendpack 

सरणी संरचनाओं के बजाय संरचनाओं की सरणियों का उपयोग करें:

 data_packet sendpack[NUM]; 

के बजाय

 struct data_packet { int address[4][NUM]; int data[8][NUM]; int attribute[NUM]; } 

जैसा कि आप देख सकते हैं, बाद के मामले में, खेतों में से एक को संशोधित करने वाले धागे कैश सिंक्रनाइज़ेशन तंत्र को ट्रिगर करेंगे।

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

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

PS मेरे उदाहरण का प्रयास करें, और मुझे बताएं कि आपके प्लेटफ़ॉर्म पर परीक्षण की गति कितने प्रतिशत बढ़ी है।