2008-10-08 16 views
25

मैं वर्तमान में अगले 8 सप्ताह में एक ग्रेड-स्तरीय कंपाइलर पाठ्यक्रम के लिए एक परियोजना चुनने की प्रक्रिया में हूं। मैं अनुकूलन से संबंधित कुछ करना चाहता हूं क्योंकि मैंने पहले उस क्षेत्र में ज्यादा काम नहीं किया है, लेकिन मैदान में कुछ भी उचित खेल है।दिलचस्प कंपाइलर परियोजनाएं

आपके द्वारा किए गए सबसे दिलचस्प कंपाइलर से संबंधित प्रोजेक्ट क्या था? आपने सबसे ज्यादा क्या सीखा?


संपादित करें: आप अपने सभी महान सुझाव के लिए धन्यवाद। मैं इतने लंबे समय तक इसे अपडेट नहीं करने के लिए क्षमा चाहता हूं।

मैं जिस परियोजना को समाप्त कर रहा था वह एलएलवीएम पर एक सरल ऑटोवॉक्साइजेशन ऑप्टिमाइज़ेशन था। एलएलवीएम में वेक्टर प्रकार हैं, लेकिन सामने के अंत के समर्थन के बिना उनका लाभ उठाने का कोई तरीका नहीं प्रतीत होता। इस अनुकूलन ने सामान्य स्केलर कोड को वेक्टर कोड में परिवर्तित कर दिया।

चूंकि ऑटो-वेक्टरिज़ेशन लागू करने के लिए काफी कठिन अनुकूलन है, इसलिए हमने जितना संभव हो उतना दायरा सीमित कर दिया है। सबसे पहले, कोड में निर्देश स्तर समानांतरता का पर्दाफाश करने के लिए, हमने एक मानदंड लूप की तलाश की जो हमारे मानदंडों से मेल खाते थे, फिर उन्हें एक विशिष्ट संख्या में अनलॉक किया गया ताकि वे आसानी से वेक्टरिज़ेबल हो सकें। इसके बाद हमने लार्सन और अमरसिंघे द्वारा Exploiting Superword Level Parallelism with Multimedia Instruction Sets में पैकिंग एल्गोरिदम लागू किया।

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

+2

तो जय 8 सप्ताह से अधिक हो गया है। हमें बताएं कि क्या हुआ। –

+1

कोई खबर जय? मैं जल्द ही एक अंडरग्रेड कंपाइलर कोर्स पढ़ाना शुरू कर दूंगा और यह जानना दिलचस्प होगा कि आपने क्या किया। – fbinder

उत्तर

6

यदि आप अनुकूलन में रूचि रखते हैं, तो एसएसई और एमएमएक्स निर्देश सेट का उपयोग करके लूप का वेक्टरेशन दिलचस्प हो सकता है।

+0

मुझे संदेह है कि यह 8 सप्ताह के समय के फ्रेम में किया जा सकता है। स्वचालित वेक्टरेशन एक कुख्यात मुश्किल समस्या है, और यहां तक ​​कि जीसीसी में भी ऐसा नहीं है। – Calyth

+0

मुझे एक स्वीकृत उत्तर को चिह्नित करने से नफरत है क्योंकि ये सभी महान सुझाव हैं, और वास्तव में इस प्रश्न का सही जवाब नहीं है।हालांकि, यह वह परियोजना है जिसे हमने वास्तव में किया था, और यह एक बहुत ही रोचक परियोजना थी इसलिए मुझे लगता है कि मुझे यहां कुछ बिंदुएं देना चाहिए। –

+0

@ उत्प्रेरक, आप सही हैं, हम कभी भी 8 सप्ताह में पूर्ण ऑटोवेक्टरिज़ेशन ऑप्टिमाइज़ेशन लागू नहीं कर सकते थे। हमने इसे पूरी तरह से बेकार किए बिना जितना संभव हो सके हमारे अनुकूलन के दायरे को सीमित कर दिया। हम अभी भी अनुमान लगाए गए हम इसमें अधिक घंटे लगाएंगे। –

7

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

+0

पूरी तरह से आप के साथ। मुझे लगता है कि सरल भाषाएं उत्पन्न करना (या मौजूदा भाषाओं को अपनी इच्छित भाषा की तरह कार्य करना) एक बहुत ही बुनियादी कौशल है। –

4

मैंने एक बार प्रोग्रामिंग भाषा और वर्चुअल मशीन को चलाने के लिए लिखा था। भाषा 16 बिट विंडोज़ पर डीएलएल (यह ओएलई स्वचालन से पहले) में निहित विशेष रूप से लिखे गए फ़ंक्शन के लिए इंटरफ़ेस करने में सक्षम थी।

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

5

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

आज, एमएल जैसी शक्तिशाली भाषाओं के साथ, एक कंपाइलर करना बहुत आसान होना चाहिए।

आप जो करना चाहते हैं उस पर वास्तव में निर्भर होना चाहिए कि आपकी रुचि क्या है। अगर यह अनुकूलन में है, तो किसी प्रकार का सरल ढांचा ढूंढें जहां आपको केवल चिंता करने की आवश्यकता है।

मुझे लगता है कि आज सबसे उपयोगी क्षेत्र थ्रेडेड लक्ष्यों के लिए या केवल समय-समय पर संकलन के लिए संकलित होना है।

+0

अच्छा जवाब। मैं ऑप्टिमाइज़ेशन के बारे में अपने स्वयं के उत्तर में जो कुछ भी कहता हूं उसे जोड़ता हूं - यह अतिरंजित है। –

+0

हमने मोटोरोला 68000 का उपयोग किया जैसे कि यह एक स्टैक मशीन थी। आप उससे ज्यादा सरल नहीं हो सकते हैं। –

+0

मैं अक्सर चाहता हूं कि आईबीएम ने इंटेल के बजाए मोटोरोला को चुना हो। चीजें बहुत अलग होंगी। –

2

लूप का पता लगाने और पैरामीट्रिज्ड अनोलिंग को दिलचस्प बनाने के लिए काफी कठिन होना चाहिए। बहुत सेक्सी नहीं, लेकिन 8 सप्ताह में बहुत सेक्सी हो रही है आपको डूब जाएगी।

4

मेरे अंडरग्रेड कंपाइलर्स क्लास में, हमने पहली बार स्क्रैच से पास्कल जैसी भाषा के लिए एक रिकर्सिव-डेसेंट (टॉप-डाउन) पार्सर लिखा: लेक्सिकल एनालिज़र, पार्सर, सबकुछ।

सेमेस्टर के माध्यम से मिडवे के बारे में, हम लेक्स/वाईएसीसी या फ्लेक्स/बाइसन जैसे पार्सर/स्कैनर जेनरेटर पर फिसल गए। हमने एक कंपाइलर बनाया जो हमारे पास्कल सबसेट लेगा और उसे एक स्टैक मशीन के लिए असेंबली में संकलित करेगा (स्टैक मशीन उबेर सरल है, लेकिन सिद्धांत अभी भी वही हैं)।

यदि आप कंपाइलर्स में रुचि रखते हैं, तो मैं Dragon Book पर अत्यधिक अनुशंसा नहीं कर सकता। इसका उद्देश्य 1 सेमेस्टर अंडरग्रेड पाठ्यक्रम के लिए और स्नातक स्तर के पाठ्यक्रम के रूप में दूसरी छमाही के लिए उपयोग किया जाना है, और सिद्धांत और अनुकूलन के हर बिट को शामिल करता है जिसे आप कभी चाहें। जोएल likes it भी। =)

चीयर्स

4

एक मौजूदा गतिशील टाइप भाषा के लिए प्रकार निष्कर्ष पर विचार करें।

13

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

उसने कहा, मेरा पहला सुझाव कुछ लाइव वैरिएबल विश्लेषण का प्रयास करना होगा। एल्गोरिदम बहुत अच्छी तरह से स्थापित हैं, इसलिए आपको इसे अपने डेटा संरचनाओं आदि के लिए विशिष्ट रूप से कोड करने की आवश्यकता होगी।

इससे आपको मृत कोड निष्कासन का सीमित रूप मिल जाएगा। यही है, यदि आप पाते हैं कि एक चर घोषित किया गया है लेकिन कभी भी उपयोग नहीं किया जाता है, तो इसके लिए स्थान आवंटित न करें। यदि आप पाते हैं कि एक मान सेट है लेकिन कभी नहीं पढ़ा है, तो सेट उत्पन्न न करें।

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

2

आप आयरनशेम के लिए एक अनुकूलक लिख सकते हैं, क्योंकि यह वर्तमान में कुछ 'आंतरिक' कार्यों को छोड़कर मीठा झटका करता है। :)

8

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

यह वास्तव में पार्सर्स & कंपाइलर्स में मेरी रुचि को पिक्चर करता है, इसलिए मैंने कंपाइलर तकनीक में दिलचस्प नए विकास को बनाए रखने की कोशिश की है।

अनुकूलन के संबंध में

, यहाँ एक मजेदार लेख है कि मैं पिछले साल पढ़ा है:

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

इस पत्र में, लेखकों peephole अनुकूलन के स्वत: खोज (कई लोकप्रिय के प्रदर्शन को पीछे छोड़ के लिए एक तकनीक का वर्णन सी ++ कंपाइलर बैक-एंड) एक विशेषज्ञ के बिना विशेष केस कोड का एक गुच्छा लिखना है। उनकी तकनीक उच्च मूल्य वाले पेफोल प्रतिस्थापन खोजने के लिए असुरक्षित सीखने वाले एल्गोरिदम का उपयोग करती है।

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

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

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

Anyhoo ... जब आप उस परियोजना के साथ खत्म करते हैं तो मुझे बताएं! और मुझे अपने "पावती" खंड में उल्लेख करना न भूलें !! ;-)

2

अन्य रोचक परियोजनाओं शामिल हो सकता है:

  • खुला स्रोत सूर्य JVM करने के लिए एक पूंछ-कॉल अनुकूलन जोड़ें।

  • पाइथन या रूबी वीएम के लिए एक नामित वापसी मूल्य अनुकूलन (एनआरवीओ) जोड़ें।

  • जोड़ें जस्ट-इन-समय regex करने वाली बाईटकोड संकलन, अपने पसंदीदा लक्ष्य के लिए (नेट पहले से ही है। मैं बहुत यकीन है कि जावा नहीं कर रहा हूँ।)

+0

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

+0

टेल-कॉल ऑप्टिमाइज़ेशन को लक्ष्य को लक्षित करने की आवश्यकता नहीं है। जेवीएम एक अलग बाधा उत्पन्न करता है (ढेर आत्मनिरीक्षण), जिसे तंग किया जा सकता है (अपील और अन्य द्वारा एक पेपर था)। –

2

लेखन जब आपका अपनी भाषा एक मजेदार और पारंपरिक अकादमिक गतिविधि है, वहां पहले से ही बहुत खराब-लागू संकलक-संबंधित परियोजनाएं हैं। साथ ही, 8 सप्ताह पूरे भाषा कार्यान्वयन पर अच्छी नौकरी करने के लिए पर्याप्त समय नहीं है।

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

मेरा मानना ​​है कि तोता बाइटकोड दुभाषिया और विभिन्न नेट आयरन-भाषा पार्सर्स को भी सरल अनुकूलन से लाभ हो सकता है।

4

"ड्रैगन बुक" सुझावों के अतिरिक्त, मैं अत्यधिक अनुशंसा करता हूं कि "उन्नत कंपाइलर डिज़ाइन & कार्यान्वयन", स्टीवन एस द्वारा।मचनिक, जो मध्यवर्ती प्रतिनिधित्व, कोड-जनरेशन और अनुकूलन तकनीकों पर केंद्रित है।

4

शेड स्किन प्रोजेक्ट की मदद करने में देखें, जो पाइथन को सी ++ में संकलित करता है। मुझे लगता है कि गर्मियों में, मदद के लिए एक कॉल किया गया था। सी ++ के संकलन में सुधार करने के तरीकों का निर्धारण करना पाइथन कार्यक्रमों को असाधारण अनुकूलन प्रदान करेगा!

http://code.google.com/p/shedskin/

+0

मुझे लगता है कि आप "पायथन से सी ++" कहना चाहते थे। हाँ। अच्छी परियोजना –

+0

धन्यवाद। मैंने इसे ठीक कर दिया है! – torial

+0

भले ही मैं बहुत देर हो चुकी हूं, मैं शेड स्किन के समर्थन में इसे ऊपर उठा रहा हूं। मैंने यह सुझाव दिया होगा कि जब मैंने पूछा था कि मुझे यह प्रश्न मिला था। –

3

यहाँ एक और विचार है ... हालांकि यह अभी भी एक छोटे से बड़ा अस्पष्ट:

अधिकांश अनुकूलन संकलन समय पर (JIT संकलक, जो रनटाइम पर अनुकूलन को छोड़कर) किया जाता है। लेकिन लिंक-टाइम और इंस्टॉल-टाइम पर अनुकूलन के लिए कई अवसर भी हैं।

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

1

आकार/गति व्यापार बंद के लिए हेरिस्टिक परीक्षणों का उपयोग कर स्वचालित इनलाइन कोड पीढ़ी।

2

मैंने इसे अपने स्वयं के शिक्षण में किया है "रास्ता वापस जब"। मैं अन्य चीजों के रूप में ऑप्टिमाइज़ेशन पर इतना जोर नहीं देता, जैसे प्रकार अनुमान या जेआईटी या बाइटकोडिंग या ऑब्जेक्ट प्रारूप/डीबग समर्थन।

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

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

यह संकलक के सभी कोड का एक छोटा सा अंश है जो संकलक देखेंगे।

संपादित करें: अफसोस की बात है, मैं फोरट्रान कंपाइलर्स के साथ काम करने से बच नहीं सकता, जो निष्पक्षता से कोड को तबाह कर देता है, जिससे प्रदर्शन पर ईपीएसलॉन प्रभाव होने पर डीबग करना मुश्किल हो जाता है।

0

बी :: सीसी पर्ल कंपाइलर प्रकार जोड़ने और विश्लेषण करने से लाभान्वित होगा। मेरे पास अभी तक इसके लिए पर्याप्त समय नहीं है।

हाल ही में पर्याप्त समय था। http://blogs.perl.org/users/rurban/2011/02/use-types.html

संबंधित मुद्दे