कंप्यूटर्स को अनुकूलित करने का तरीका तय करता है कि लूप को कब और कितना अनलॉक करना है?

Question

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

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

Answer 1

एक संकलक एक पाश उतारना अनुकूलन करता है, यह कैसे जो कारक द्वारा निर्धारित किया जाता है पाश या मौसम उतारना करने के लिए पूरे पाश उतारना या नहीं।

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

चूंकि यह एक अंतरिक्ष-प्रदर्शन ट्रेडऑफ है, इस कार्यक्रम को बेहतर बनाने में यह ऑप्टिमाइज़ेशन तकनीक कितनी प्रभावशाली है?

यह इनपुट (आपके प्रोग्राम) पर काफी हद तक निर्भर करता है। यह धीमा हो सकता है (सामान्य नहीं) या यह कई गुना तेजी से हो सकता है। एक प्रोग्राम को बेहतरीन रूप से चलाने के लिए लिखना और जो ऑप्टिमाइज़र को अपना काम करने में सक्षम बनाता है।

इसके अलावा, यह

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

यदि आप जानना चाहते हैं कि विकल्प आपके ऐप, प्रोफाइल में मदद करता है या नहीं।

यदि आपको उससे अधिक की आवश्यकता है, तो आपको इष्टतम कार्यक्रम लिखने के बारे में जानने के लिए कुछ समय आरक्षित करना चाहिए, क्योंकि विषय काफी जटिल है।

Answer 2

जब यह है (मेरी राय में) अच्छा एक पाश उतारना करने के लिए:

पाश कम है और संभवतः इस्तेमाल किया सभी चर प्रोसेसर रजिस्टर में कर रहे हैं। अनलॉकिंग चर के बाद 'डुप्लीकेट' हैं लेकिन अभी भी रजिस्टरों में हैं इसलिए कोई मेमोरी (या कैश) जुर्माना नहीं है।

लूप (अज्ञात पाश अनोल नंबर के साथ) कम से कम कुछ या दर्जन बार निष्पादित किया जाएगा, इसलिए उस पूरे लूप को निर्देश कैश में अनलॉक करने के लिए औचित्य है।

अगर पाश कम है (एक या बस कुछ intructions) यह करने के लिए कि यह फिर से निष्पादित किया जाना चाहिए कम अक्सर निष्पादित किया जाता है के लिए क्योंकि कोड unrolling के लिए बहुत फायदेमंद हो सकता है।

Answer 3

सरल विश्लेषण निर्देशों की गणना करना है - एक 2 निर्देश लूप अनलोल किया गया 10 गुना में 11/20 स्पीडअप के 20 उपज के बजाय 11 निर्देश हैं। लेकिन आधुनिक प्रोसेसर आर्किटेक्चर के साथ यह बहुत जटिल है; कैश आकार और प्रोसेसर निर्देश पाइपलाइन की विशेषताओं के आधार पर। यह संभव है कि उपरोक्त उदाहरण 2x के बजाय 10x तेज चलाएगा। यह भी संभव है कि 10x के बजाय 1000x अनलॉक करना धीमा हो जाएगा। एक विशिष्ट प्रोसेसर को लक्षित किए बिना, कंपाइलर्स (या प्रोजेमा जिन्हें आप उनके लिए लिखते हैं) बस अनुमान लगा रहे हैं।

Answer 4

ठीक है, सब से पहले, मुझे पता नहीं कैसे compilers यह स्वचालित रूप से करता है। और मुझे पूरा यकीन है कि कम से कम 10s हैं यदि 100 से अधिक एल्गोरिदम नहीं हैं जिन्हें कंपेलरों को चुनना है।
और यह शायद संकलक-विशिष्ट है वैसे भी।

लेकिन, मैं इसकी प्रभावशीलता की गणना करने में आपकी सहायता कर सकता हूं।

बस ध्यान दें कि इस तकनीक को आम तौर पर आप एक महान प्रदर्शन को बढ़ावा देने नहीं देता है।
लेकिन बार-बार लूप गणना में और उच्च प्रतिशत प्रदर्शन दे सकता है।
ऐसा इसलिए है क्योंकि आमतौर पर लूप के अंदर फ़ंक्शन लूप की स्थिति जांच से अधिक गणना समय लेता है।

तो, मान लीजिए कि हम, एक निरंतर के साथ एक सरल पाश है क्योंकि आप भी कॉपी-पेस्ट करने के लिए आलसी थे या सिर्फ यह लगेगा सोचा बेहतर:

for (int i = 0; i < 5; i++) 
{ 
    DoSomething(); 
} 

यहाँ आप पूर्णांक तुलना है , incrementations, और DoSomethig() कॉल।
तो अगर DoSomething() अपेक्षाकृत जल्दी है, तो हम संचालन मिला है।

DoSomething(); 
DoSomething(); 
DoSomething(); 
DoSomething(); 
DoSomething(); 

अब स्थिरांक यह आसान है के साथ

, इसलिए की सुविधा देता है देखें कि यह कैसे एक चर के साथ काम करेगा:
अब अगर आप इस उतारना होगा, आप इसे सिर्फ 5 संचालन करने के लिए कम कर देंगे

for (int i = 0; i < n; i++) 
{ 
    DoSomething(); 
} 

यहाँ आप n पूर्णांक तुलना, n incrementations, और n DoSomethig() कॉल = 3n है। अब, हम इसे पूरी तरह से नहीं उतारना कर सकते हैं, लेकिन हम एक निरंतर कारक (उच्च n होने की उम्मीद है, और अधिक हम इसे उतारना चाहिए) द्वारा इसे उतारना सकता है: यहाँ

int i; 
for (i = 0; i < n; i = i+3) 
{ 
    DoSomething(); 
    DoSomething(); 
    DoSomething(); 
} 
if (i - n == 2) 
{ 
    DoSomething(); // We passed n by to, so there's one more left 
} 
else if (i - n == 1) 
{ 
    DoSomething(); //We passed n by only 1, so there's two more left 
    DoSomething(); 
} 

अब हमारे पास यहाँ आप n/3 + 2 पूर्णांक तुलना, n/3 incrementations, और n DoSomethig() कॉल = (1 2/3) * n है।
हमने खुद को (1 1/3) * एन संचालन बचाया। जो लगभग आधा गणना गणना समय में कटौती करता है।

एफवाईआई, एक और साफ अनोलिंग तकनीक को Duff's device कहा जाता है।
लेकिन यह बहुत संकलक और भाषा-कार्यान्वयन विशिष्ट है। ऐसी भाषाएं हैं जहां यह वास्तव में बदतर होगी।