इस उदाहरण में प्रीफेच स्पीडअप क्यों अधिक नहीं है?

Question

इस this excellent paper के 6.3.2 में Ulrich Drepper सॉफ़्टवेयर प्रीफेचिंग के बारे में लिखता है। उनका कहना है कि यह "परिचित पॉइंटर पीछा ढांचा" है जिसे मैं इकट्ठा करता हूं वह वह परीक्षण है जो पहले यादृच्छिक पॉइंटर्स को घुमाने के बारे में देता है। यह उनके ग्राफ में समझ में आता है कि जब कार्य सेट कैश आकार से अधिक हो जाता है तो प्रदर्शन पूंछ बंद हो जाता है, क्योंकि तब हम मुख्य स्मृति को अधिक से अधिक बार जा रहे हैं।

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

मैं एक पेड़ के साथ _mm_prefetch उपयोग करने के लिए कोशिश कर रहा हूँ और मैं कोई उल्लेखनीय गति को देखते हैं। मैं कुछ इस तरह कर रहा हूँ:

_mm_prefetch((const char *)pNode->m_pLeft, _MM_HINT_T0); 
// do some work 
traverse(pNode->m_pLeft); 
traverse(pNode->m_pRight) 

अब जब कि केवल एक तरफ ट्रेवर्सल की मदद करनी चाहिए, लेकिन मैं सिर्फ प्रदर्शन में सब पर कोई परिवर्तन नहीं देखते हैं। मैंने परियोजना सेटिंग्स में एसएसई जोड़ा/आर्क किया था। मैं एक i7 4770 के साथ विजुअल स्टूडियो 2012 का उपयोग कर रहा हूं। this thread में कुछ लोग प्रीफेच के साथ केवल 1% स्पीडअप प्राप्त करने के बारे में भी बात करते हैं। मुख्य स्मृति में मौजूद डेटा की यादृच्छिक पहुंच के लिए prefetch चमत्कार क्यों काम नहीं करता है?

Answer 1

नोड आप कितना बड़ा करना चाहते हैं? चूंकि प्रीफ़ेचर 4K पृष्ठ सीमा से अधिक नहीं हो सकता है: यदि आपका नोड बड़ा है, तो आप डेटा के केवल एक हिस्से को प्री-लोड करेंगे, जबकि शेष डेटा केवल मिस ईवेंट के बाद लोड किया जाएगा।

Answer 2

प्रीफेच आपकी मुख्य मेमोरी के थ्रूपुट को बढ़ा नहीं सकता है, यह केवल आपको इसका उपयोग करने के करीब पहुंचने में मदद कर सकता है।

यदि आपका कोड किसी लिंक किए गए सूची में अगले नोड से डेटा का अनुरोध करने से पहले गणना पर कई चक्र खर्च करता है, तो यह स्मृति 100% व्यस्त नहीं रखेगा। जैसे ही पते ज्ञात हो, अगले नोड का एक प्रीफेच मदद करेगा, लेकिन अभी भी ऊपरी सीमा है। ऊपरी सीमा लगभग वही है जो आपको बिना किसी प्रीफेचिंग के प्राप्त होगी, लेकिन नोड लोड करने और पॉइंटर का पीछा करने के बीच कोई काम नहीं है। यानी मेमोरी सिस्टम परिणाम का 100% परिणाम ला रहा है।

उस पेपर के ग्राफ के अनुसार, काम के 160 चक्रों से पहले भी प्रीफेचिंग डेटा तैयार होने के लिए काफी आगे नहीं है। यादृच्छिक अभिगम विलंबता वास्तव में धीमी है, क्योंकि डीआरएएम को एक नया पृष्ठ, एक नई पंक्ति, और एक नया स्तंभ खोलना है।

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

यदि आपका कोड पहले से ही अगले नोड को पहले से लोड करता है, तो प्रीफेचिंग जादुई रूप से इसे तेज़ी से नहीं बना सकता है। Prefetching मदद करता है जब यह CPU गणना और स्मृति के लिए इंतजार के बीच ओवरलैप बढ़ा सकते हैं। या शायद आपके परीक्षणों में, ->left पॉइंटर्स अधिकतर अनुक्रमिक थे जब आपने स्मृति आवंटित की थी, इसलिए एचडब्ल्यू प्रीफेचिंग ने काम किया? यदि वृक्ष पर्याप्त उथले थे, तो बाईं ओर उतरने से पहले ->right नोड (अंतिम स्तर के कैश में, एल 1 में) prefetching एक जीत हो सकता है।

सॉफ्टवेयर प्रीफेचिंग केवल तभी जरूरी है जब एक्सेस पैटर्न CPUs हार्डवेयर प्रीफेचर्स के लिए पहचान योग्य नहीं है। (वे काफी अच्छे हैं, और एक सभ्य आकार के साथ पैटर्न को स्पॉट कर सकते हैं। और 10 आगे की धाराओं (बढ़ते पते) जैसे कुछ ट्रैक करें। http://agner.org/optimize/ विवरण के लिए जांचें।)