समानांतर एल्गोरिदम - मॉडल
डेटा और प्रोसेसिंग विधि को विभाजित करने और इंटरैक्शन को कम करने के लिए उपयुक्त रणनीति लागू करने के लिए एक रणनीति पर विचार करके एक समानांतर एल्गोरिथ्म का मॉडल विकसित किया गया है। इस अध्याय में, हम निम्नलिखित समानांतर एल्गोरिदम मॉडल पर चर्चा करेंगे -
- डेटा समानांतर मॉडल
- टास्क ग्राफ मॉडल
- काम पूल मॉडल
- मास्टर गुलाम मॉडल
- निर्माता उपभोक्ता या पाइपलाइन मॉडल
- हाइब्रिड मॉडल
डेटा समानांतर
डेटा समानांतर मॉडल में, कार्यों को प्रक्रियाओं को सौंपा गया है और प्रत्येक कार्य विभिन्न डेटा पर समान प्रकार के संचालन करता है। Data parallelism एकल संचालन का एक परिणाम है जो कई डेटा आइटम पर लागू किया जा रहा है।
डेटा-समानांतर मॉडल को साझा-पता स्थान और संदेश-पासिंग प्रतिमानों पर लागू किया जा सकता है। डेटा-समानांतर मॉडल में, बातचीत के ओवरहेड्स को एक स्थानीयता संरक्षण अपघटन का चयन करके, अनुकूलित सामूहिक इंटरैक्शन दिनचर्या का उपयोग करके, या कम्प्यूटेशन और इंटरैक्शन को ओवरलैप करके कम किया जा सकता है।
डेटा-समानांतर मॉडल समस्याओं की प्राथमिक विशेषता यह है कि समस्या के आकार के साथ डेटा समानांतरवाद की तीव्रता बढ़ जाती है, जो बदले में बड़ी समस्याओं को हल करने के लिए अधिक प्रक्रियाओं का उपयोग करना संभव बनाता है।
Example - घना मैट्रिक्स गुणन।
टास्क ग्राफ मॉडल
टास्क ग्राफ मॉडल में, समानता एक द्वारा व्यक्त की जाती है task graph। एक कार्य ग्राफ या तो तुच्छ या अनैतिक हो सकता है। इस मॉडल में, स्थानीयता को बढ़ावा देने या बातचीत की लागत को कम करने के लिए कार्यों के बीच संबंध का उपयोग किया जाता है। इस मॉडल को उन समस्याओं को हल करने के लिए लागू किया जाता है जिसमें कार्यों से जुड़े डेटा की मात्रा उनके साथ जुड़े गणना की संख्या की तुलना में बहुत बड़ी है। कार्यों के बीच डेटा आंदोलन की लागत में सुधार करने में मदद करने के लिए कार्यों को सौंपा गया है।
Examples - समानांतर त्वरित सॉर्ट, विरल मैट्रिक्स फैक्टराइजेशन, और डिवाइड-एंड-कॉनकेयर दृष्टिकोण के माध्यम से व्युत्पन्न समानांतर एल्गोरिदम।
यहां, समस्याओं को परमाणु कार्यों में विभाजित किया गया है और एक ग्राफ के रूप में लागू किया गया है। प्रत्येक कार्य नौकरी की एक स्वतंत्र इकाई है जिसमें एक या एक से अधिक कार्य पर निर्भरता होती है। एक कार्य के पूरा होने के बाद, एक पूर्ववर्ती कार्य का आउटपुट निर्भर कार्य को पारित किया जाता है। एंटेकेड टास्क वाला एक टास्क तभी शुरू होता है जब उसका पूरा एंटेकेड टास्क पूरा हो जाता है। अंतिम निर्भर कार्य पूरा होने पर ग्राफ का अंतिम आउटपुट प्राप्त होता है (उपरोक्त आकृति में टास्क 6)।
काम पूल मॉडल
कार्य पूल मॉडल में, कार्यों को लोड को संतुलित करने के लिए प्रक्रियाओं को गतिशील रूप से सौंपा गया है। इसलिए, कोई भी प्रक्रिया संभावित रूप से किसी भी कार्य को अंजाम दे सकती है। इस मॉडल का उपयोग तब किया जाता है जब कार्यों से जुड़े डेटा की मात्रा, कार्यों से जुड़े गणना की तुलना में छोटी होती है।
प्रक्रियाओं पर कार्यों का कोई वांछित पूर्व असाइनमेंट नहीं है। कार्यों का निरूपण केंद्रीकृत या विकेन्द्रीकृत है। कार्यों के संकेत एक भौतिक रूप से साझा सूची में, एक प्राथमिकता कतार में, या हैश टेबल या पेड़ में सहेजे जाते हैं, या उन्हें भौतिक रूप से वितरित डेटा संरचना में सहेजा जा सकता है।
कार्य शुरुआत में उपलब्ध हो सकता है, या गतिशील रूप से उत्पन्न हो सकता है। यदि कार्य गतिशील रूप से उत्पन्न होता है और कार्य का विकेंद्रीकृत असाइनमेंट किया जाता है, तो एक समाप्ति का पता लगाने वाले एल्गोरिथ्म की आवश्यकता होती है ताकि सभी प्रक्रियाएं वास्तव में पूरे कार्यक्रम के पूरा होने का पता लगा सकें और अधिक कार्यों की तलाश करना बंद कर सकें।
Example - समानांतर पेड़ खोज
मास्टर-स्लेव मॉडल
मास्टर-स्लेव मॉडल में, एक या अधिक मास्टर प्रक्रियाएं कार्य उत्पन्न करती हैं और इसे दास प्रक्रियाओं के लिए आवंटित करती हैं। कार्य पहले से आवंटित किए जा सकते हैं यदि -
- मास्टर कार्यों की मात्रा का अनुमान लगा सकता है, या
- एक यादृच्छिक असाइनमेंट लोड को संतुलित करने का संतोषजनक काम कर सकता है, या
- दासों को अलग-अलग समय में कार्य के छोटे टुकड़े सौंपे जाते हैं।
यह मॉडल आम तौर पर समान रूप से उपयुक्त है shared-address-space या message-passing paradigms, चूंकि बातचीत स्वाभाविक रूप से दो तरह से होती है।
कुछ मामलों में, एक कार्य को चरणों में पूरा करने की आवश्यकता हो सकती है, और अगले चरण में कार्य उत्पन्न होने से पहले प्रत्येक चरण में कार्य पूरा होना चाहिए। मास्टर-स्लेव मॉडल को सामान्यीकृत किया जा सकता हैhierarchical या multi-level master-slave model जिसमें शीर्ष स्तर का मास्टर कार्यों के बड़े हिस्से को दूसरे स्तर के मास्टर को खिलाता है, जो अपने स्वयं के दासों के बीच कार्यों को आगे बढ़ाता है और कार्य का एक हिस्सा खुद कर सकता है।
मास्टर-दास मॉडल का उपयोग करने में सावधानियां
यह सुनिश्चित करने के लिए ध्यान रखा जाना चाहिए कि मास्टर एक भीड़ बिंदु न बन जाए। यदि कार्य बहुत छोटे हैं या श्रमिक तुलनात्मक रूप से तेज़ हैं तो ऐसा हो सकता है।
कार्यों को इस तरह से चुना जाना चाहिए कि कार्य करने की लागत संचार की लागत और सिंक्रनाइज़ेशन की लागत पर हावी हो।
एसिंक्रोनस इंटरैक्शन ओवरलैप इंटरैक्शन और मास्टर द्वारा कार्य पीढ़ी के साथ जुड़े गणना में मदद कर सकता है।
पाइपलाइन मॉडल
इसे के रूप में भी जाना जाता है producer-consumer model। यहां डेटा का एक सेट प्रक्रियाओं की एक श्रृंखला के माध्यम से पारित किया जाता है, जिनमें से प्रत्येक उस पर कुछ कार्य करता है। यहां, नए डेटा का आगमन कतार में एक प्रक्रिया द्वारा एक नए कार्य के निष्पादन को उत्पन्न करता है। प्रक्रियाएं रैखिक या बहुआयामी सरणियों, पेड़ों या चक्रों के साथ या बिना सामान्य रेखांकन के आकार में एक कतार बना सकती हैं।
यह मॉडल उत्पादकों और उपभोक्ताओं की एक श्रृंखला है। कतार में प्रत्येक प्रक्रिया को कतार में पूर्ववर्ती प्रक्रिया के लिए डेटा आइटम के अनुक्रम के उपभोक्ता के रूप में माना जा सकता है और कतार में इसके बाद की प्रक्रिया के लिए डेटा के एक निर्माता के रूप में। कतार को एक रैखिक श्रृंखला होने की आवश्यकता नहीं है; यह एक निर्देशित ग्राफ हो सकता है। इस मॉडल पर लागू होने वाली सबसे सामान्य इंटरैक्शन मिनिमाइजेशन तकनीक कम्प्यूटेशन के साथ इंटरैक्शन को ओवरलैप कर रही है।
Example - समानांतर एलयू फैक्टराइजेशन एल्गोरिदम।
हाइब्रिड मॉडल
हाइब्रिड एल्गोरिथम मॉडल की आवश्यकता तब होती है जब किसी समस्या को हल करने के लिए एक से अधिक मॉडल की आवश्यकता हो सकती है।
एक हाइब्रिड मॉडल या तो कई मॉडलों से बना हो सकता है जो पदानुक्रमित रूप से लागू किए गए हों या एक समानांतर एल्गोरिथम के विभिन्न चरणों में कई मॉडल क्रमिक रूप से लागू होते हैं।
Example - समानांतर त्वरित प्रकार