"2012 की समानांतर प्रोग्रामिंग प्रतियोगिता में तेजी लाने" या "6 अल्ट्राबुक और 10 एसएसडी सभी के लिए पर्याप्त होंगे!"

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

आप किस बारे में बात कर रहे हैं?

आपको एक संदर्भ स्ट्रिंग दी गई है (उदाहरण के लिए, यह: GATGAGCATGTGTTGAATCCTCA ) और कई लंबे इनपुट स्ट्रिंग्स (उनमें से एक है: GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT यह संदर्भ और इनपुट तार के प्रत्येक जोड़े के लिए सबसे लंबे समय तक सामान्य सबस्ट्रिंग खोजने और उनके "निर्देशांक" को वापस करने के लिए आवश्यक है। उदाहरण में, उत्तर होगा (5 13 15 23) और (5 13 44 52) , अर्थात्, दो पदार्थ पाए जाते हैं:

 #  ,       ,  '-1' ref = 'GATGAGCATGTGTTGAATCCTCA' input = 'GTCCTCCAGTTTGTAGCATGTGTATTTATGTCCTCCAGTTTGTAGCATGTGTATTTAT' ref[(5 - 1):13] == input[(15 - 1):23] #True ref[(5 - 1):13] == input[(44 - 1):52] #True 

आपके निपटान में एक संदर्भ कोड है जो सही ढंग से है, लेकिन बहुत धीरे से इस समस्या को क्रूर बल के साथ हल करता है।
क्या वह सरल है?

कैसे तय करें?

यहां मस्ती शुरू होती है। मैं कई विकल्प पेश करूंगा जो उपयोगी हो सकते हैं:

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

क्या चुनना है? मुझे एक संकेत चाहिए!

आप क्या चुन सकते हैं, हम सलाह नहीं दे सकते। किसी को pthreads पर लिखना पसंद है, किसी को OpenMP पर, और किसी को TBB और शायद MKL से समानांतर कार्यों का उपयोग करना पसंद है।
एक बात निश्चित है - बहुत ही स्मार्ट विचारों और विचारों पर अक्सर हमारे मंच पर चर्चा की जाती है। उदाहरण के लिए, यह SSE4.2 में दिए गए निर्देशों को देखने लायक है।

मैं किस पर लिख सकता हूं?

दुर्भाग्य से, सभी प्रोग्रामिंग भाषाओं का समर्थन करने के लिए हमारी स्वचालित परीक्षण प्रणाली बहुत छोटी है।
इस बार हमने उसे C ++ (अजगर और जावा स्क्रिप्ट के लिए मेरे सच्चे प्यार के बावजूद) को समझना सिखाया, इसलिए मुझे अच्छे पुराने C ++ में लिखना होगा।
विकास प्लेटफ़ॉर्म किसी भी हो सकता है, लेकिन कोड को एक लिनक्स मशीन (डेबियन स्टेबल - कर्नेल 2.6.32) के साथ gcc इंस्टॉल किया जाएगा (pthreads प्रेमियों के लिए संस्करण 4.6.2) और इंटेल समानांतर स्टूडियो XE 2011 (इंटेल के लिए) कंपाइलर, हमारे प्रोसेसर के लिए कोड का अनुकूलन)।

पुरस्कारों का क्या? मुझे एक अल्ट्राबुक चाहिए!

पहले तीन टीमों ने सबसे तेज़ कोड लिखा और 16 मई से पहले समाधान भेजा, हम असूस ज़ेनबुक यूएक्स 31 ई प्रति प्रतिभागी देंगे।
दूसरी तीन टीमें - SSD 320 सीरीज 80Gb पर ।
इंटेल सॉफ्टवेयर नेटवर्क पर सबसे दिलचस्प ब्लॉग पोस्ट लिखने वाले अन्य 4 प्रतिभागियों को भी एसएसडी मिलेगा।

इसलिए, एक बार फिर से: एक कार्य , एक महीने, 6 अल्ट्राबुक और 10 एसएसडी रूस और सीआईएस के सर्वश्रेष्ठ प्रतिभागियों के लिए।

भाग लेने का फैसला करने वाले सभी को शुभकामनाएँ!

प्रतियोगिता के आयोजक और न्यायाधीश टिप्पणियों में आपके किसी भी प्रश्न का उत्तर देने के लिए तैयार हैं।