🏒 🥟 💆🏿 इंटेल के बारे में कहानी आपके कोड प्रतियोगिता में तेजी लाती है 🐩 🙇 😃

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

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

प्रतियोगिता की विशेषताएं

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

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

शर्त

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

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

एल्गोरिथ्म

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

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

वर्टेक्स टाइप एन्यूमरेशन

enum { FROM_ANY = 0, FROM_THIS = 1, FIRST_THIS = 2, FROM_ALLIANCE = 3, FIRST_ALLIANCE = 4 };

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

एक जोड़ी उड़ानों के लिए शीर्ष को जोड़ने वाला कोड

 void wire_two_flights(Graph &g, Flight* f1, Flight* f2, int i1, int i2) { #define P_B(t) push_back(make_pair(getCostWithDiscount(f2, t), i2 + t)) if(f1->company == f2->company) { g[i1 + FIRST_THIS].P_B(FROM_THIS); g[i1 + FROM_THIS].P_B(FROM_THIS); g[i1 + FROM_ALLIANCE].P_B(FROM_THIS); } else if(alliances[f1->company][f2->company]) { g[i1 + FIRST_ALLIANCE].P_B(FROM_ALLIANCE); g[i1 + FIRST_ALLIANCE].P_B(FIRST_THIS); g[i1 + FROM_ALLIANCE].P_B(FROM_ALLIANCE); g[i1 + FROM_ALLIANCE].P_B(FIRST_THIS); g[i1 + FROM_THIS].P_B(FROM_ALLIANCE); g[i1 + FROM_THIS].P_B(FIRST_THIS); } else { g[i1 + FROM_ANY].P_B(FROM_ANY); g[i1 + FROM_ANY].P_B(FIRST_THIS); g[i1 + FROM_ANY].P_B(FIRST_ALLIANCE); g[i1 + FROM_ALLIANCE].P_B(FROM_ANY); g[i1 + FROM_ALLIANCE].P_B(FIRST_THIS); g[i1 + FROM_ALLIANCE].P_B(FIRST_ALLIANCE); g[i1 + FROM_THIS].P_B(FROM_ANY); g[i1 + FROM_THIS].P_B(FIRST_THIS); g[i1 + FROM_THIS].P_B(FIRST_ALLIANCE); } }

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

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

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

अनुकूलन

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

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

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

तेजी से समय रूपांतरण

 vector<time_t> tc(100000); time_t get_time(int year, int month) { size_t key = 13 * year + month; if(key >= tc.size()){ tc.resize(key * 2); } if (tc[key] == 0) { tm time; time.tm_year = year - 1900; time.tm_mon = month - 1; time.tm_mday = 0; time.tm_hour = time.tm_min = time.tm_sec = 0; time_t res = mktime(&time); tc[key] = res; } return tc[key]; } time_t convert_to_timestamp(int day, int month, int year, int hour, int minute, int seconde) { time_t res = get_time(year, month); res += (day) * 60 * 60 * 24; res += hour * 60 * 60; res += minute * 60; res += seconde; return res; }

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

समानता

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

कोड

हमारे समाधान के लिए कोड C ++ में मैक्रोज़ के साथ एक पूरी तरह से अपठनीय हैश है, लेकिन हम अभी भी इसके लिए एक लिंक देते हैं। इस तरह के कार्यों में, यह कोड की पूरी तरह से प्राकृतिक स्थिति है, लेकिन हम निश्चित रूप से, एक ही शैली में बड़ी परियोजनाओं को लिखने के लिए प्रोत्साहित नहीं करते हैं।

निष्कर्ष।

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

हम सभी को रोचक कार्यों और प्रभावी समाधानों की कामना करते हैं!

पुनश्च
विजेताओं की पूरी सूची इंटेल वेबसाइट पर है ।

इंटेल के बारे में कहानी आपके कोड प्रतियोगिता में तेजी लाती है