मैं वर्तमान में बाइनरी खोज के कार्यान्वयन की प्रोफाइलिंग कर रहा हूं। इसे मापने के लिए कुछ विशेष निर्देशों का उपयोग करके मैंने देखा कि कोड में लगभग 20% गलत भविष्यवाणी दर है। मैं उत्सुक हूं कि यह जांचने का कोई तरीका है कि इस वजह से मैं कितने चक्र खो रहा हूं। यह एक एमआईपीएस आधारित वास्तुकला है।आप शाखा गलतफहमी के प्रभाव को कैसे मापते हैं?
इसे अपने सीपीयू के लिए दस्तावेज़ों में देखें। यदि आप विशेष रूप से यह जानकारी नहीं पा रहे हैं, तो सीपीयू की पाइपलाइन की लंबाई काफी अच्छी अनुमान है।
यह देखते हुए कि यह एमआईपीएस है और यह 300 मेगाहर्ट्ज सिस्टम है, मुझे लगता है कि यह काफी कम पाइपलाइन है। शायद 4-5 चरणों, इसलिए प्रति गलत भविष्यवाणी 3-4 चक्रों की लागत शायद एक उचित अनुमान है।
उस जानकारी के लिए अपने चश्मा देखें और यदि यह विफल हो जाता है, तो इसे एक अरब बार चलाएं और इसे अपने प्रोग्राम के बाहर समय दें (कुछ देखें)। फिर इसे मिस के बिना चलाएं और तुलना करें।
आप 0.2 * एन चक्र प्रति पुनरावृत्ति खो रहे हैं, जहां एन एक दुर्घटनाग्रस्त शाखा के बाद पाइपलाइनों को फ्लश करने के लिए चक्रों की संख्या है। मान लीजिए एन = 10 तो इसका मतलब है कि आप कुल पर दो प्रति घनत्व खो रहे हैं। जब तक आपके पास बहुत छोटा आंतरिक लूप नहीं है तो यह शायद एक महत्वपूर्ण प्रदर्शन हिट नहीं होने वाला है।
अच्छा ... यदि आपके पास प्रति पुनरावृत्ति की 20% गलत रिपोर्ट वाली शाखाएं हैं, तो समय जोड़ना शुरू हो सकता है;) – Goz
@Goz: हाँ, अच्छा बिंदु - मुझे लगता है कि जब मैं कहता हूं * लूप * या * पुनरावृत्ति * मेरा वास्तव में मतलब है इसमें एक आंशिक रूप से अनुमानित शाखा के साथ ब्लॉक करें, लेकिन एक लूप में एक से अधिक ऐसे ब्लॉक हो सकते हैं। –
बात करता है। चक्र तेजी से बढ़ते हैं और अधिक मूल्यवान होते हैं जब आपके पास केवल 300 मिलियन सेकेंड होते हैं। –
एक में आदेश सीपीयू आप
पर (जो आम तौर पर पाइप लाइन के कुछ हिस्से की एक समारोह है) mispredicts की संख्या और mispredict लागत का एक उत्पाद के रूप में अनुमानित mispredict लागत की गणना करने में सक्षम हो सकता है पर एक आधुनिक out-of-order सीपीयू, हालांकि, सामान्य गणना आमतौर पर संभव नहीं है। उड़ान में बड़ी संख्या में निर्देश हो सकते हैं, जिनमें से कुछ केवल गलत तरीके से फंस गए हैं। आस-पास का कोड निर्भरता के एक या अधिक श्रृंखलाओं से विलंबता हो सकता है, या यह निष्पादन इकाइयों जैसे संसाधनों पर थ्रूपुट हो सकता है, थ्रूपुट का नाम बदल सकता है, या यह कहीं भी हो सकता है।
इस तरह के मूल पर, प्रदर्शन काउंटरों की मदद से, प्रति गलतता का जुर्माना निर्धारित करना बहुत मुश्किल है। आप इस विषय को समर्पित entire papers पा सकते हैं: उस व्यक्ति को पूरे बेंचमार्क में औसत 9 से 35 चक्रों का जुर्माना आकार मिलता है: यदि आप कोड के कुछ छोटे टुकड़े को देखते हैं तो सीमा भी बड़ी होगी: शून्य का जुर्माना आसान है प्रदर्शन करें, और आप एक परिदृश्य बना सकते हैं जहां दंड 100 चक्रों में है।
यह आपको कहां छोड़ देता है, बस अपनी बाइनरी खोज में गलत भविष्यवाणी लागत निर्धारित करने का प्रयास कर रहा है? खैर एक साधारण दृष्टिकोण सिर्फ गलत भविष्यवाणियों की संख्या को नियंत्रित करने और अंतर को मापने के लिए है! यदि आप अपना बेंचमार्क इनपुट सेट अप करते हैं, तो हमेशा एक ही शाखा पैटर्न का पालन करने के साथ शुरू होता है, यादृच्छिक पैटर्न रखने के सभी तरीके से, आप रनटाइम गिरावट बनाम गलत भविष्यवाणी गिनती कर सकते हैं। यदि आप करते हैं, तो अपना परिणाम साझा करें!
1 इस तरह के 86, एआरएम और बिजली आर्किटेक्चर की पेशकश वाली उड़ान में आधुनिक बड़ा कोर के मामले में दिए गए निर्देशों केसैकड़ों।
मजाकिया बात यह है कि एक द्विआधारी खोज के साथ आप 50% गलत अनुमानों की अपेक्षा करेंगे कि खोज मूल्य अधिक या छोटे से तुलना की जा रही है या नहीं। मुझे लगता है कि केवल 20% प्राप्त करना अन्य सशर्त अभिव्यक्तियों के कारण है (पेड़ में ट्रांसफर करने से पहले पॉइंटर्स की जांच करना? या पेड़ को संतुलित करना?)। मुझे नहीं लगता कि 20% मूल रूप से यादृच्छिक पसंद के लिए एक बड़ी गलतफहमी दर है। –
पर्याप्त सच है लेकिन कुछ भी 300 एमएचजेड सिस्टम पर मदद करता है। –