समानांतर कम्प्यूटिंग त्वरण

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

यह सोचना तर्कसंगत है कि यदि एक प्रोसेसर n सेकंड में काम करता है, तो चार प्रोसेसर n / 4 सेकंड खर्च करेंगे। शब्द "स्पीडअप फैक्टर" उस समय का अनुपात है जो एक प्रोसेसर उस समय एक नौकरी पर खर्च करता है जो एक मल्टीप्रोसेसर सिस्टम उसी नौकरी पर खर्च करता है।

एस (पी) = टी _एस / टी _पी

गणना के लिए, सबसे इष्टतम टी _एस का उपयोग करना महत्वपूर्ण है, अर्थात, संभव गैर-समानांतर एल्गोरिदम का सबसे अच्छा।

अब बुरी खबर: इस त्वरण की एक सीमा है। इसे Amdahl's Law (Amdahl's Law) कहा जाता है और यहाँ इसका सार है: यह वही है जो किसी भी कार्य को साधारण सिंगल-प्रोसेसर सिस्टम पर दिखता है:





संपूर्ण निष्पादन समय, जो पहले से ही हमारे लिए परिचित है, T _s , उस हिस्से से बना होता है, जिसे कई प्रोसेसरों पर बांटा जा सकता है (समानांतर) - (1-f) T _s , और वह भाग जो समानांतर नहीं किया जा सकता है (सीरियल) - fT _s ।

कई प्रोसेसर के लिए एक ही कार्य का लेआउट कैसा दिखेगा?



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

त्वरण कारक की गणना सूत्र द्वारा की जाती है:



यही है, यह सब इस बात पर निर्भर करता है कि हम प्रोग्राम के किस टुकड़े को समानांतर कर सकते हैं (प्रतिशत में f का अर्थ है सीरियल कोड की मात्रा)। यदि f = 0%, अर्थात, बिल्कुल सभी कोड समानांतर है (जो व्यावहारिक रूप से नहीं हो सकता है), तो हम जितना अधिक प्रोसेसर का उपयोग करेंगे, कार्य तेजी से पूरा होगा और अनुपात रैखिक होगा: हम इसे 10 गुना तेज चाहते हैं - हम दस प्रोसेसर का उपयोग करते हैं, हम चाहते हैं एक लाख गुना तेज - हम एक लाख प्रोसेसर खरीदते हैं। लेकिन यह सीरियल कोड के 5% को छोड़ने और 95% को समानांतर करने के लायक है, फिर त्वरण कारक 20 के बराबर होगा और आप उच्चतर कूद नहीं सकते। यहां तक ​​कि अगर हम उस मिलियन में एक और मिलियन प्रोसेसर खरीदते हैं, तो भी प्रोग्राम 20 गुना तेजी से चलेगा। यहाँ विभिन्न प्रतिशतों के उदाहरणों के साथ यह दुखद तथ्य चार्ट पर दिखता है:



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

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



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

यहाँ एक और उदाहरण है - डेटाबेस के लिए एक प्रश्न:

मॉडल = "नागरिक" और वर्ष = 2001 और (रंग = "महान" या रंग = "सफेद");

अनुरोध ऐसे आधार से 2001 के सभी हरे या सफेद सिविक प्राप्त करने की कोशिश कर रहा है:



इस तरह के कार्य को तीन भागों में विघटित किया जा सकता है: एक प्रोसेसर 2001 के सभी सिविक की एक तालिका बनाएगा, एक अन्य प्रोसेसर सभी सफेद और हरे रंग की मशीनों की तालिका बनाएगा (ये दो प्रश्न समानांतर में जा सकते हैं), जिसके बाद इन दो तालिकाओं के जुड़ने का परिणाम होगा।



आप अनुरोध की संरचना को बदल सकते हैं, जो संगामिति को प्रभावित कर सकता है



इन भागों के बाद के वितरण के लिए अलग-अलग प्रोसेसर में भागों में कार्य के विभाजन को अपघटन कहा जाता है। वेक्टर द्वारा मैट्रिक्स को गुणा करना एक समस्या का परिणाम विघटित करने का एक उदाहरण है: परिणाम (वेक्टर वाई) को कई स्वतंत्र भागों में विभाजित किया गया था और प्रत्येक को दूसरे से अलग से गणना की गई थी। मैट्रिक्स गुणन के साथ भी यही किया जा सकता है:

हमारा पहला समानांतर कार्यक्रम

हम अपने पहले समानांतर कार्यक्रम को लिखने के लिए Cilk का उपयोग करेंगे। यह एक प्रोग्रामिंग भाषा है जो अनिवार्य रूप से कार्यों को समानांतर और सिंक्रनाइज़ करने के लिए सुविधाजनक उपकरणों के साथ सी है। CILk को 1994 में MIT में विकसित किया गया था, स्वतंत्र और स्वतंत्र था, लेकिन 2006 तक इसका व्यवसायीकरण शुरू हो गया, C ++ को समर्थन देना शुरू कर दिया, और एक साल पहले इसे इंटेल द्वारा गिबल्ट के साथ खरीदा गया था, जो निश्चित रूप से, मल्टी-कोर सिस्टम के लिए एक अच्छी भाषा होना फायदेमंद है। : आखिरकार, वे स्वयं ऐसी प्रणाली का उत्पादन करते हैं। मुझे यकीन नहीं है कि मुफ्त में कंपाइलर कैसे प्राप्त किया जाए, हमारे विश्वविद्यालय में छात्रों के लिए एक शैक्षणिक संस्करण है (Cilk डेवलपर प्रोफेसर का एक अच्छा दोस्त है), इसलिए यदि आप इसे नहीं पा सकते हैं तो मैं माफी चाहता हूं। लेकिन खोज करने के लिए, मुझे लगता है, इसके लायक है, क्योंकि Cilk बहुत सरल और सुविधाजनक है! Pthreads से तुलना न करें। प्रोग्रामिंग शुरू करने के लिए हम सभी को पता होना चाहिए कि तीन कीवर्ड हैं: cilk , spawn और सिंक ।

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

int fib (int n){ if (n<2) return n; else { int x, y; x = fib (n-1); y = fib (n-2); return (x+y); } } 

और यहाँ Cilk पर एक ही कार्यक्रम है:

 cilk int fib (int n){ if (n<2) return n; else { int x, y; x = spawn fib (n-1); y = spawn fib (n-2); sync; return (x+y); } } 

अंतर नोटिस? ,)

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

x = स्पॉन फ़ाइब (n-1);

दूसरे कर्नेल पर चलता है, और तुरंत लाइन y = स्पॉन फ़ाइब (n-2) चलाता है। परिणाम लौटने से पहले ( रिटर्न (x + y) ), आपको निष्पादन पूर्ण होने तक प्रतीक्षा करने की आवश्यकता है, अन्यथा चर x और y में सही मान नहीं होंगे। यह सिंक कमांड द्वारा किया जाता है - जैसा कि नाम का अर्थ है।

वास्तव में आसान है?

इस तरह के एक कार्यक्रम में बहुत सारे कोर लोड होंगे! यहाँ बताया गया है कि यह एल्गोरिथ्म n = 4 के लिए कैसे काम करता है:



कोड हाइलाइट किए गए रंग ग्राफ नोड्स के रंगों के अनुरूप हैं। ग्राफ के प्रत्येक स्तर को एक साथ निष्पादित किया जाता है, अर्थात, n = 4 के लिए पहली कॉल दो कार्यों को बुलाती है - 3 और 2 के लिए, वे बदले में - क्रमशः 2 और 1 के लिए और 1 और 0 के लिए।



यहाँ इस कार्यक्रम के लिए स्रोत कोड है :

अगले लेख में, हम इस बारे में बात करेंगे कि समानांतर एल्गोरिदम की मापनीयता की गणना कैसे की जाती है, किस प्रकार का शेड्यूलिंग उपलब्ध है और जिसका उपयोग cilk में किया जाता है, साथ ही छँटाई और समानांतर गतिशील प्रोग्रामिंग पर भी स्पर्श किया जाता है।