उच्च स्तरीय अनुकूलन के एक उदाहरण के रूप में लूप ब्रेकिंग

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

लूप ऑप्टिमाइज़ेशन का मूल विचार

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

पाश अनुकूलन प्रदर्शन का एक सरल उदाहरण

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

#include <stdio.h> #include <stdlib.h> #define N 1000 int main() { int i,j,rep; int volatile nnn; float **a1,**a2,**a3; float **b1,**b2, **b3; double **c1, **c2, **c3; double sum1,sum2,sum3; nnn = 2000; // upper bound for repeat loop .... // memory allocation and initialization for(rep=0;rep<nnn;rep++) { #ifndef PERF for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } #else for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); } for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); } for(j=1;j<N-1;j++) for(i=0;i<N;i++) { sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } #endif } printf("%lf %lf %lf \n",sum1,sum2,sum3); ... //deallocation } 

मैं –O1 विकल्प के साथ इंटेल कंपाइलर का उपयोग करूंगा। कंपाइलर इस विकल्प के बारे में (icl –help) कहता है:
/ O1 अधिकतम गति के लिए ऑप्टिमाइज़ करते हैं, लेकिन कुछ ऑप्टिमाइज़ेशन को अक्षम करते हैं जो एक छोटे गति लाभ के लिए कोड आकार बढ़ाते हैं
वास्तव में, इस विकल्प के साथ, कंपाइलर लूप ऑप्टिमाइज़ेशन नहीं करता है, जिसमें ऑटो-वेक्टराइजेशन शामिल है। इसलिए, वह प्रस्तावित प्रयोग में हस्तक्षेप नहीं करेगा।
-DPERF विकल्प के साथ संकलन के परिणामस्वरूप और इसके बिना, दो निष्पादन योग्य फाइलें बनाई जाएंगी।

icl -O1 distr.c -Fedistr.exe
icl -O1 -DPERF distr.c -Fedistr2.exe

Windows Server 2008 R2 एंटरप्राइज़ और Intel Xeon X5570 प्रोसेसर पर चलने वाली मेरी प्रयोगशाला मशीन पर, परिणामी परीक्षणों के निष्पादन का समय इस प्रकार है:

distr.exe: 38.8 सेकंड
distr2.exe: 31.2 सेकंड

दूसरे चक्र का प्रदर्शन काफी बेहतर है। आइए इंटेल VTune एम्पलीफायर XE2013 द्वारा किए गए सामान्य अन्वेषण कार्यक्रम को देखें और दोनों कार्यक्रमों के परिणामों की तुलना करें।



मुझे आश्चर्य है कि यहाँ क्या मामला है?
एक विशेष गाइड "इंटेल @ कोर टीएम i7 प्रोसेसर और इंटेल @ एक्सॉन टीएम 5500 प्रोसेसर के लिए प्रदर्शन विश्लेषण गाइड" है जिसमें आप कंप्यूटिंग कोर के विश्लेषण के तरीके सीख सकते हैं। वीटीएन एम्पलीफायर में विभिन्न घटनाओं का एक संक्षिप्त विवरण भी शामिल है। इसलिए, यदि यहां दिए गए कुछ नामों के अर्थ के बारे में प्रश्न हैं, तो आप इस जानकारी को संदर्भित कर सकते हैं। मुझे भी खुशी होगी अगर कोई मुझे सही करता है या मुझे अतिरिक्त विचार देता है कि चक्र का अनुकूलन ऐसा प्रभाव क्यों दिखाता है।

रिपोर्ट की तुलना करते समय, हम इस तथ्य पर ध्यान दे सकते हैं कि कार्यक्रम के दोनों संस्करणों के लिए INST_RETIRED.ANY लगभग समान है। यानी कोई चमत्कार नहीं था (जैसे वैश्वीकरण) और दोनों मामलों में किए गए काम की मात्रा लगभग बराबर है। लेकिन एक ही समय में, अनुकूलित संस्करण में, सीपीआई दर बहुत बेहतर है और आपको यह समझने की आवश्यकता है कि यह कैसे हुआ।
कार्यक्रम के किसी एक विकल्प में रिमोट ड्राम द्वारा सेवित एलएलसी लोड मिसेज की एक दिलचस्प उपस्थिति। सिद्धांत रूप में, यह समस्या बहु-थ्रेडेड अनुप्रयोगों के लिए विशिष्ट है और किसी अन्य कोर से संबंधित मेमोरी की कंप्यूटिंग कोर के उपयोग से जुड़ी है, जो असमान मेमोरी एक्सेस (NUMA) के साथ कंप्यूटिंग आर्किटेक्चर के लिए विशिष्ट है। इस मामले में, यह स्थिति विभिन्न कंप्यूटिंग कोर में कंप्यूटिंग प्रक्रिया के प्रवासन के कारण दिखाई देती है। तारों का गठन इसलिए हुआ कि दूसरा प्रोग्राम कंप्यूटिंग कोर के माध्यम से कम सफलतापूर्वक चला गया। आप एक प्रोग्राम को एक विशिष्ट कम्प्यूटेशनल कोर से बाँध सकते हैं ताकि ऑपरेटिंग सिस्टम के कारण गुठली के बीच ये स्विचिंग परिणाम को प्रभावित न करें। निम्नलिखित प्रयोग एक विशिष्ट कोर के संदर्भ में किए गए थे।
मैं मानक मेमोरी एक्सेस विश्लेषण का उपयोग नहीं करूंगा, जिसके लिए विभिन्न घटनाओं को वीथ्यून एम्पलीफायर में नेहेल्म वास्तुकला के लिए परिभाषित किया गया है, लेकिन मैं अपने स्वयं के कार्यक्रमों के सेट को ले जाऊंगा और उन्हें अपने कार्यक्रम के दो संशोधनों के लिए तुलना करूंगा। मुझे निम्नलिखित विश्लेषण के बारे में मिला:



यह आश्चर्यजनक है कि मेमोरी डाउनलोड की संख्या बदल गई है (MEM_INST_RETIRED.LOADS)। हालांकि, यदि आप प्रोग्राम के दोनों संस्करणों के कोडांतरक की तुलना करते हैं, तो मूल संस्करण में मेमोरी के साथ काम करने के निर्देशों की संख्या वास्तव में अधिक है। ऐसा इसलिए है क्योंकि एक ही समय में बड़ी संख्या में सरणियों के साथ काम करते समय, मध्यवर्ती परिणामों को संग्रहीत करने के लिए पर्याप्त रजिस्टर नहीं होते हैं और प्रोग्राम स्टैक और रजिस्टरों के बीच एक निरंतर विनिमय होता है। संभवतः, यह समस्या महत्वपूर्ण नहीं होनी चाहिए, क्योंकि निरंतर उपयोग के कारण स्टैक कैश में होगा।
यदि हम मेमोरी सबसिस्टम के संगठन को याद करते हैं, तो कंप्यूटिंग कोर में 32KB का L1 डेटा कैश है। कार्यक्रम के प्रारंभिक संस्करण में, प्रत्येक पुनरावृत्ति पर हम बड़ी संख्या में विभिन्न डेटा धाराओं के साथ काम करते हैं। यानी प्रत्येक पुनरावृत्ति पर हमें 27 स्थानों a1 [j-1] [i], a1 [j] [i], a1 [j + 1] [i], a2 [j-1] [i], ... को पढ़ने की आवश्यकता है। c1 [j + 1] [i] लेकिन इस डेटा का एक हिस्सा j के ऊपर पिछले चलना पर कैश सबसिस्टम में लोड किया जाना चाहिए। A1 [j + 1] [:], a2 [j + 1] [:], a3 [j + 1] [:], b1 [j + 1] [:], ..., c3 [ j + 1] [:]। फ्लोट का आकार 4 बाइट्स है, डबल का आकार 8 बाइट्स है। मैट्रिक्स की पंक्ति में तत्वों की संख्या -1000 है। हमें लगता है कि 4000 * 3 + 4000 * 3 + 8000 * 3 = ~ 47KB डेटा को प्रत्येक सेशन में कैश सबसिस्टम में रखा जाना चाहिए। जाहिर है, कार्यक्रम के प्रारंभिक संस्करण में, प्रत्येक पुनरावृत्ति पर, एल 1 डी कैश पूरी तरह से अपडेट किया गया है। संशोधित संस्करण में, प्रत्येक पुनरावृत्ति पर, वास्तविक मैट्रिक्स के लिए ~ 12KB और वास्तविक दोहरी परिशुद्धता के लिए ~ 24KB अपडेट किए जाते हैं, अर्थात्। पिछले पुनरावृत्तियों में पढ़े गए डेटा को आंशिक रूप से मेमोरी में संग्रहीत किया जाना चाहिए। इसे L1D_CACHE_LD.I_STATE ईवेंट (कैश मिस) के अनुपात की तुलना L1D_CACHE_LD.MESI (कैश हिट की कुल संख्या) के अनुपात से किया जा सकता है। "धीमी" संस्करण में, यह अनुपात ~ 13.6% है। "तेज" संस्करण में - ~ ​​7%। नतीजतन, संशोधित संस्करण में लंबे समय तक प्रतीक्षा के साथ कम देरी है।

हार्डवेयर प्रीफ़ैच डिवाइस को भी इस गणना के प्रदर्शन को प्रभावित करना चाहिए। प्रीफैच डिवाइस हैं जो एल 1 और एल 2 कैश के साथ काम करते हैं। जानकारी को दस्तावेज़ीकरण से चमकाया जा सकता है कि वे सर्वशक्तिमान नहीं हैं और विभिन्न आर्किटेक्चर पर डेटा धाराओं की एक अलग संख्या का समर्थन करते हैं। एक विशिष्ट सरणी स्ट्रिंग, जैसे कि [j] [i], एक ऐसी डेटा स्ट्रीम है। एक साथ सेवा किए गए थ्रेड्स की एक निश्चित संख्या तक पहुंचने के बाद, थ्रेड्स दिखाई देना चाहिए, जिसके लिए प्रीफेटिंग काम नहीं करता है। इसके अलावा, यह संभव है कि बड़ी संख्या में थ्रेड्स के साथ, हार्डवेयर प्रीफ़ैचिंग सभी पर काम करना बंद कर देगा। इसलिए, मैंने एक नए तरह का विश्लेषण बनाया जिसमें मैंने L1D और L2 हार्डवेयर प्रीफ़ैच डिवाइस के संचालन से संबंधित घटनाओं को रखा:



मेरी राय में, यह विश्लेषण निम्नलिखित दर्शाता है। "अच्छा" मामले में L1D प्रीफैच डिवाइस द्वारा उत्पन्न होने वाले प्रश्नों (L1D_PREFETCH.REQUESTS) की संख्या "धीमी" मामले में इससे भी अधिक है। हालांकि यह अजीब है, यह एक मार्जिन के साथ इस विचार की पुष्टि करता है कि प्रीफ़ेचर डेटा धाराओं की सेवा करने की अपनी क्षमता में सीमित है। L2 कैश के लिए प्रीफ़ैचिंग डिवाइस के रूप में, दो दिलचस्प घटनाएं हैं: L2_DATA_RQSTS.DEMAND.MESI (L2 डेटा डिमांड रिक्वेस्ट) और L2_DATA_RQSTS.PREETCH.MESI (सभी L2 डेटा प्रीफ़ैक्टर)।
यानी मेमोरी एक्सेस का एक हिस्सा प्रीफ़च डिवाइस द्वारा परोसा जाता है, और मेमोरी एक्सेस का दूसरा भाग कंप्यूटिंग कोर के लिए एक आश्चर्य है। और यहां फिर से एक दिलचस्प तस्वीर देखी गई है। "अच्छे" मामले में, प्रीफ़ैच डिवाइस काफी अधिक सक्रिय अनुरोध उत्पन्न करता है। यह भी महत्वपूर्ण है कि "खराब" मामला गैर-सेवारत क्वेरी प्रीफैच डिवाइसों से लगभग दोगुना है।

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

और इस मामले में कंपाइलर क्या करता है?

यह जांचने का समय है कि इस मामले में इंटेल कंपाइलर क्या अनुकूलन करता है। हमें एक समान पायदान पर रखने के लिए, हम कंपाइलर से ऑटो-वैरिफिकेशन करने का अवसर लेंगे। (यहाँ मैं एक बदबूदार स्माइली लगाना चाहता हूँ।)

icl -O2 / Qvec- distr.c -Fedistr_comp.exe
समय distr_comp.exe
...
कमांड के लिए CPU समय: 'distr_comp.exe'
असली 41.799 सेकंड

आपके पास यह है - –ओ 1 विकल्प के साथ संकलक -ओ 2 की तुलना में बेहतर प्रदर्शन दिखाता है। यह स्पष्ट नहीं है कि परीक्षण कैसे अनुकूलित किया गया था। एक विकल्प / Qopt_report है। यदि आप इसका उपयोग करते हैं, तो आप देख सकते हैं कि संकलक ने लूप का विभाजन किया है:

लूप लाइन में 54 पर ऋण वितरण

अतिरिक्त विश्लेषण (डंप का उपयोग करने की क्षमता) की मदद से, आप समझ सकते हैं कि विभाजन कितने मोटे तौर पर किया गया था:

 for(j=1;j<N-1;j++) { for(i=0;i<N;i++) { sum3 = sum3 + (c1[j][i]+c2[j][i]+c3[j][i]); sum3 = sum3 - (c1[j-1][i]+c2[j-1][i]+c3[j-1][i]); sum3 = sum3 - (c1[j+1][i]+c2[j+1][i]+c3[j+1][i]); } for(i=0;i<N;i++) { sum1 = sum1 + (a1[j][i]+a2[j][i]+a3[j][i]); sum2 = sum2 + (b1[j][i]+b2[j][i]+b3[j][i]); sum1 = sum1 - (a1[j-1][i]+a2[j-1][i]+a3[j-1][i]); sum2 = sum2 - (b1[j-1][i]+b2[j-1][i]+b3[j-1][i]); sum1 = sum1 - (a1[j+1][i]+a2[j+1][i]+a3[j+1][i]); sum2 = sum2 - (b1[j+1][i]+b2[j+1][i]+b3[j+1][i]); } } 

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

किसी भी तरह से संकलक को कड़वी गोली को मीठा करने के लिए, आइए देखें कि इस मामले में ऑटोवैक्टराइजेशन क्या देगा:

icl -O2 distr.c -Fedistr_compvec.exe
कमांड के लिए CPU समय: 'distr_compvec.exe'
वास्तविक 24.020 सेकंड

निष्कर्ष:

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