🚵🏽 ✋ 🤙🏿 गलती से भविष्यवाणी की गई ब्रांचिंग से प्रोग्राम निष्पादन समय में काफी वृद्धि हो सकती है 👨🏾 🧗🏿 🤜🏼

आधुनिक प्रोसेसर सुपरसेलकर हैं, अर्थात, वे एक साथ कई निर्देशों को निष्पादित करने में सक्षम हैं। उदाहरण के लिए, कुछ प्रोसेसर प्रति चक्र चार से छह निर्देशों से प्रक्रिया कर सकते हैं। इसके अलावा, कई ऐसे प्रोसेसर निर्देश को शुरू करने में सक्षम हैं: वे कोड में स्थित आदेशों के साथ काम करना शुरू कर सकते हैं।

इसी समय, कोड में अक्सर शाखाएं होती हैं ( if–then )। ऐसी शाखाओं को अक्सर "बदलाव" के रूप में लागू किया जाता है, जिसमें प्रोसेसर या तो कोड के नीचे निर्देशों को निष्पादित करने के लिए आगे बढ़ता है या वर्तमान पथ को जारी रखता है।

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

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

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

अगर भविष्यवाणी करना कठिन है तो क्या होगा?

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

आइए एक सरल कोड देखें, जिसमें हम यादृच्छिक पूर्णांक को आउटपुट सरणी में लिखते हैं:

 while (howmany != 0) { out[index] = random(); index += 1; howmany--; }

हम 3 चक्रों के लिए औसतन एक उपयुक्त यादृच्छिक संख्या उत्पन्न कर सकते हैं। यही है, यादृच्छिक संख्या जनरेटर की कुल देरी 10 चक्रों के बराबर हो सकती है। लेकिन हमारा प्रोसेसर सुपरस्लेकर है, यानी हम एक साथ कई रैंडम नंबर कैलकुलेशन कर सकते हैं। इसलिए, हम लगभग हर 3 चक्र में एक नया यादृच्छिक संख्या उत्पन्न कर पाएंगे।

चलो फ़ंक्शन को थोड़ा बदल दें ताकि केवल विषम संख्याएं सरणी के लिए लिखी जाएं:

 while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }

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

मैंने स्काइलेक प्रोसेसर पर C ++ में इन दो कार्यों को बेंचमार्क किया:

सभी यादृच्छिक संख्याओं को रिकॉर्ड करें	पूर्णांक पर 3.3 चक्र
केवल अजीब यादृच्छिक संख्याएं लिखना	पूर्णांक पर 15 चक्र

दूसरा फ़ंक्शन लगभग पांच गुना अधिक समय तक काम करता है!

क्या यहां कुछ भी तय किया जा सकता है? हां, हम सिर्फ ब्रांचिंग को खत्म कर सकते हैं। एक अजीब पूर्णांक को इस तरह से चित्रित किया जा सकता है कि यह एक बिटवाइज़ लॉजिकल हो और 1 के बराबर मूल्य के साथ। यादृच्छिक मान अजीब होने पर ही सरणी सूचकांक को एक से बढ़ाना है।

 while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }

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

सभी यादृच्छिक संख्याओं को रिकॉर्ड करें	पूर्णांक पर 3.3 चक्र
केवल अजीब यादृच्छिक संख्या लिखना	पूर्णांक पर 15 चक्र
ब्रांचिंग को खत्म कर दिया	प्रति पूर्णांक 3.8 चक्र

क्या कंपाइलर इस समस्या को अपने आप हल कर सकता है? सामान्य तौर पर, उत्तर नहीं है। कभी-कभी कंपाइलर्स में ब्रांचिंग को पूरी तरह से खत्म करने के विकल्प होते हैं, भले ही सोर्स कोड में एक if-then हो। उदाहरण के लिए, ब्रांचिंग को कभी-कभी "सशर्त चाल" या अन्य अंकगणितीय चाल के साथ बदला जा सकता है। हालांकि, ऐसी चालें कंपाइलरों में उपयोग के लिए असुरक्षित हैं।

एक महत्वपूर्ण निष्कर्ष: गलत तरीके से भविष्यवाणी की गई ब्रांचिंग एक महत्वहीन समस्या नहीं है, इसका बहुत प्रभाव पड़ता है।

मेरा स्रोत कोड Github पर है ।

बेंचमार्क बनाना एक मुश्किल काम है: प्रोसेसर ब्रांचिंग की भविष्यवाणी करना सीखते हैं

[नोट। अनुवाद: यह हिस्सा लेखक का एक अलग लेख था, लेकिन मैंने इसे पिछले एक के साथ जोड़ दिया, क्योंकि उनके पास एक सामान्य विषय है।]

पिछले भाग में, मैंने दिखाया कि किसी प्रोग्राम का अधिकांश निष्पादन समय गलत शाखा भविष्यवाणी के कारण हो सकता है। मेरा बेंचमार्क एक सरणी के लिए 64 मिलियन यादृच्छिक पूर्णांक मान लिखना था। जब मैंने केवल विषम यादृच्छिक संख्याओं को रिकॉर्ड करने की कोशिश की, तो गलत भविष्यवाणियों के कारण प्रदर्शन बहुत कम हो गया।

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

परीक्षणों की संख्या	गलत ढंग से अनुमानित शाखाएँ (इंटेल स्काईलेक)
1	48%
2	38%
3	28%
4	22%
5	14%

जैसा कि नीचे दिए गए ग्राफ़ से देखा जा सकता है, "प्रशिक्षण" आगे भी जारी है। धीरे-धीरे, त्रुटिपूर्ण पूर्वानुमानित शाखाओं का अनुपात लगभग 2% तक गिर जाता है।

यही है, अगर हम एक ही कार्य द्वारा लिए गए समय को मापना जारी रखते हैं, तो यह कम और कम हो जाता है, क्योंकि प्रोसेसर परिणाम का बेहतर अनुमान लगाने के लिए सीखता है। "प्रशिक्षण" की गुणवत्ता विशिष्ट प्रोसेसर मॉडल पर निर्भर करती है, लेकिन यह अपेक्षा की जाती है कि नए प्रोसेसर बेहतर सीखें।

नवीनतम AMD सर्वर प्रोसेसर 10 से कम प्रयासों में लगभग पूरी तरह से ब्रांचिंग (0.1% के भीतर) की भविष्यवाणी करते हैं।

परीक्षणों की संख्या	गलत रूप से अनुमानित शाखाएँ (AMD रोम)
1	52%
2	18%
3	6%
4	2%
5	1%
6	0.3%
7	0.15%
8	0.15%
9	0.1%

एएमडी रोम पर यह आदर्श भविष्यवाणी तब गायब हो जाती है जब समस्या में मूल्यों की संख्या 2000 से 10,000 तक बढ़ जाती है: सबसे अच्छी भविष्यवाणी 0.1% की त्रुटियों के अंश से 33% तक बदल जाती है।

छोटे कार्यों के लिए आपको संभवतः बेंचमार्किंग कोड को ब्रांचिंग से बचना चाहिए।

मेरा जीथूब कोड ।

आभार : एएमडी रोम वेल एरवन द्वारा प्रदान किया गया।

अतिरिक्त पढ़ना : (आंशिक रूप से) TAgged ज्यामितीय इतिहास लंबाई शाखा भविष्यवाणी (Seznec et al।) के लिए एक मामला ।

गलती से भविष्यवाणी की गई ब्रांचिंग से प्रोग्राम निष्पादन समय में काफी वृद्धि हो सकती है

अगर भविष्यवाणी करना कठिन है तो क्या होगा?

बेंचमार्क बनाना एक मुश्किल काम है: प्रोसेसर ब्रांचिंग की भविष्यवाणी करना सीखते हैं

More articles: