"ढीली 40 कोर?" या एक्सेलेर 2011 सरल समानांतर प्रोग्रामिंग प्रतियोगिता

हबर पर उच्च शिक्षा के बारे में राय व्यक्त करने के सप्ताह को जारी रखते हुए, मैं प्रतियोगिता के बारे में बताऊंगा, जो काम के बीच में कहीं है, (इसलिए सम्मानित अलेक्जेंडरलीन द्वारा इनकार किया गया है) और सीखने की क्षमता (इसलिए उपयोगकर्ता habzzov एलेक्सन द्वारा प्रचारित)।

और मैं आपको Acceler8 समानांतर प्रोग्रामिंग प्रतियोगिता के बारे में बताऊंगा । हां, यह एक प्रतियोगिता है जिसमें न केवल सीखने का अवसर है, बल्कि "छोटे" पुरस्कारों में से एक के लिए काम करने का अवसर है: 2 शक्तिशाली लैपटॉप एचपी और 10 एसस नेटबुक ।
अपने हाथ की कोशिश करना चाहते हैं?

पहली नज़र में, इस बार प्रतियोगिता काफी सरल है: आपको केवल एक प्रोग्रामिंग समस्या को हल करने की आवश्यकता है।
दूसरी नज़र में, समाधान समानांतर और संभवतः स्केलेबल होना चाहिए।
तो हम किस बारे में बात कर रहे हैं?

संक्षेप में कार्य के बारे में

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

फैसले के बारे में संक्षेप में

यह स्पष्ट है कि कार्य अनुक्रमिक माथे खोज द्वारा हल किया गया है, लेकिन समाधान बहुत धीमा होगा:

int maxSum = A[0][0]; int maxI0 = 0, maxJ0 = 0, maxI1 = 1, maxJ1 = 1; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) for (int width = 1; width <= M - i; width++) for (int height = 1; height <= N - j; height++) { int currentSum = sum_subarray(A, i, j, i + width, j + height); if (currentSum > maxSum) { maxSum = currentSum; maxI0 = i; maxJ0 = j; maxI1 = i + width - 1; maxJ1 = j + height - 1; } } cout << "Max subarray: [" << maxI0 << "][" << maxJ0 << "] .. [" << maxI1 << "][" << maxJ1 << "]"; cout << endl << "Max value = " << maxSum << endl; cout << "Area = " << (maxI1 - maxI0 + 1) * (maxJ1 - maxJ0 + 1) << endl; 

जाहिर है, यह दृष्टिकोण "सभी महाकाव्य में नहीं है।"

समझदारी से फैसला कैसे करें

इस कार्य के लिए कई दृष्टिकोण हैं।

• सबसे पहले, आप डेली वन एल्गोरिथम में वर्णित दिलचस्प कैशिंग (मैट्रिक्स गुणों के आधार पर) का उपयोग कर सकते हैं:
  सबसे पहले, एक मध्यवर्ती मैट्रिक्स बी बनाएं, जो शुरू में शून्य से भरा होता है, जिसमें प्रत्येक तत्व बी [i] [जे] ऊपरी बाएं कोने (ए [0] [०]) से ए [आई] [जे] तक सबमेट्रिक्स तत्वों के योग को संग्रहीत करता है।
  अब किसी भी सबमेट्रिक्स में तत्वों का योग पाया जा सकता है
  

   sum = B[i2][j2]- B[i1-1][j2] - B[i2][j1-1] + B[i1-1][j1-1] 

  
  
• दूसरे, आप कडेन एल्गोरिदम का उपयोग करने की कोशिश कर सकते हैं, जो मूल रूप से एक आयामी सरणी, या पोर्ट के लिए लिखा गया है और stackoverflow.com के उपयोगकर्ताओं में से एक द्वारा दिए गए संशोधित एल्गोरिदम को समानांतर करता है।
• तीसरा, आप थोड़ा सोच सकते हैं और एक सुंदर, समानांतर और त्वरित समाधान लिख सकते हैं;)

हम सभी कार्ड प्रकट नहीं करेंगे। अब सब कुछ एक समान स्तर पर है - एक महीने का समय (निर्णय 15 नवंबर तक किए जाते हैं) और Google और पाठ्यपुस्तकों तक मुफ्त पहुंच।
आसान लगता है, है ना?
और सबसे स्वादिष्ट - एक नाश्ते के लिए।

हम स्केलेबिलिटी का मूल्यांकन कैसे करेंगे?

इस मुद्दे पर कई दृष्टिकोण और बहुत सारी बाढ़ आ रही है। हमने सबसे सरल समाधान लेने का फैसला किया, लेकिन वास्तविकता के सबसे करीब भी:
कोड का परीक्षण दो अलग-अलग प्लेटफार्मों पर किया जाएगा। पहला है मानदंड परीक्षण लैब 40-कोर मशीन, अच्छी तरह से ज्ञात हार्डवेयर विशेषताओं के साथ, एक प्रसिद्ध प्रोसेसर ब्रांड और दूसरे स्तर के कैश का एक प्रसिद्ध आकार (" एमटीएल कॉन्फ़िगरेशन देखें")। दूसरा एक छोटा सिस्टम है, जिसके बारे में लगभग कुछ भी नहीं पता है (2-4 कोर, मेमोरी के कई गिग्स - यह सारी जानकारी)।
क्या ऐसी स्थिति में समाधान का अनुकूलन करना मुश्किल है? हां।
दूसरी ओर - आप "छोटी मशीन" और MTL पर माध्यम से किसी की तुलना में तेजी से काम कर सकते हैं - यह जीतने के लिए पर्याप्त हो सकता है।
या हो सकता है कि कोई व्यक्ति दोनों मशीनों पर बेहतर परिणाम प्राप्त करेगा? यह समय दिखाएगा।
तो, रुचि रखने वालों के लिए, एक छोटा लिंक: प्रतियोगिता के लिए पंजीकरण । आप टिप्पणियों में सवाल लिख सकते हैं या प्रतियोगिता मंच पर छोड़ सकते हैं।

और, वह, महाकाव्य हो ! ;)