बल्क सिंक्रोनस पैरेलल

बल्क सिंक्रोनस पैरेलल (बीएसपी) सार मशीन समानांतर एल्गोरिदम डिजाइन करने के लिए ब्रिजिंग मॉडल है। यह समानांतर रैंडम एक्सेस मशीन (पीआरएएम ) मॉडल के समान है, किन्तु पीआरएएम के विपरीत, बीएसपी संचार और सिंक्रनाइज़ेशन को हल्के में नहीं लेता है। इस प्रकार वास्तव में, अपेक्षित सिंक्रनाइज़ेशन और संचार की मात्रा निर्धारित करना बीएसपी एल्गोरिदम का विश्लेषण करने का महत्वपूर्ण हिस्सा है।

इतिहास

बीएसपी मॉडल वर्ष 1980 के दशक के समय हार्वर्ड विश्वविद्यालय के लेस्ली वैलेंट द्वारा विकसित किया गया था। इस प्रकार निश्चित लेख वर्ष 1990 में प्रकाशित हुआ था।

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

रेफरी नाम = स्केलेबल-कंप्यूटिंग >

डब्ल्यू एफ मैककॉल। स्केलेबल कंप्यूटिंग. कंप्यूटर विज्ञान आज: हालिया रुझान और विकास। जे वैन लीउवेन (संपादक)। एलएनसीएस वॉल्यूम 1000, स्प्रिंगर-वेरलाग पीपी.46-61 (1995)[4]</ref>

और पुनरावर्ती अमर समानांतर एल्गोरिदम जो सर्वोत्तम संभव प्रदर्शन और इष्टतम पैरामीट्रिक ट्रेडऑफ़ प्राप्त करते हैं।

रेफरी नाम = मैककॉल-टिस्किन >

डब्ल्यू एफ मैककॉल और ए टिस्किन। बीएसपी मॉडल में मेमोरी-कुशल आव्युह गुणन। एल्गोरिथमिका 24(3) पीपी.287-297 (1999)

[5]</ref>

रुचि और गति बढ़ने के साथ, मैककॉल ने ऑक्सफोर्ड, हार्वर्ड, फ्लोरिडा, प्रिंसटन, बेल लैब्स, कोलंबिया और यूट्रेक्ट के समूह का नेतृत्व किया, जिसने 1996 में बीएसपी प्रोग्रामिंग के लिए बीएसपीलिब मानक विकसित और प्रकाशित किया। रेफरी नाम = bsplib > जे एम डी हिल, डब्ल्यू एफ मैककॉल, डी सी स्टेफनेस्कु, एम डब्ल्यू गौड्रेउ, के लैंग, एस बी राव, टी सुएल, टी सैंटिलस और आर एच बिसेलिंग। बीएसपीलिब: बीएसपी प्रोग्रामिंग लाइब्रेरी। पैरेलल कंप्यूटिंग 24 (14) पीपी. 1947-1980 (1998) [6]</ref>

वैलेंट ने 2000 के दशक में बीएसपी मॉडल का विस्तार विकसित किया, जिससे वर्ष 2011 में मल्टी-बीएसपी मॉडल का प्रकाशन हुआ।

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

संदर्भ नाम = McC2017 > वैज्ञानिक कंप्यूटिंग के लिए समानांतर प्रसंस्करण पर 18वें SIAM सम्मेलन में बिल मैककॉल द्वारा उच्च प्रदर्शन क्लाउड कंप्यूटिंग के लिए ब्रिजिंग मॉडल (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 Archived 2019-12-11 at the Wayback Machine.</ref> यह भी देखें

 रेफरी नाम = गणित-मॉडल-आर्क >

बिल मैककॉल. गणित, मॉडल और वास्तुकला। अध्याय 1, पृ. 6-53. भविष्य कंप्यूटिंग और संचार के लिए गणित, लियाओ हेंग और बिल मैककॉल द्वारा संपादित। कैम्ब्रिज यूनिवर्सिटी प्रेस (2022)। communications/mathematics-models-and-architectures/57F4ABDEC50A67BD0CE4911779933541</ref>

बीएसपी मॉडल

अवलोकन

एक बीएसपी कंप्यूटर में निम्नलिखित सम्मिलित हैं:

• प्रसंस्करण और/या स्थानीय मेमोरी लेनदेन में सक्षम घटक (अर्थात, प्रोसेसर),
• एक नेटवर्क जो ऐसे घटकों के जोड़े के मध्य संदेशों को रूट करता है, और
• एक हार्डवेयर सुविधा जो सभी या घटकों के सबसेट के सिंक्रनाइज़ेशन की अनुमति देती है।

इसे सामान्यतः प्रोसेसर के समूह के रूप में समझा जाता है जो गणना के विभिन्न थ्रेड (कंप्यूटर विज्ञान) का पालन कर सकता है, प्रत्येक प्रोसेसर तेज़ स्थानीय मेमोरी से लैस होता है और संचार नेटवर्क द्वारा परस्पर जुड़ा होता है।

बीएसपी एल्गोरिदम तीसरी विशेषता पर बहुत अधिक निर्भर करता है; गणना वैश्विक सुपरस्टेप्स की श्रृंखला में आगे बढ़ती है, जिसमें तीन घटक होते हैं:

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

गणना और संचार क्रियाओं को समय पर आदेश देने की आवश्यकता नहीं है। संचार सामान्यतः दो-तरफा भेजने और प्राप्त करने वाले संदेश-पासिंग कॉल के अतिरिक्त तरफा पुट और जीईटी रिमोट डायरेक्ट मेमोरी एक्सेस (आरडीएमए) कॉल का रूप लेता है।

बीएसपी का सुपरस्टेप. प्रक्रियाओं में रैखिक क्रम का अभाव होता है और इन्हें किसी भी तरह से प्रोसेसर में मानचित्र किया जा सकता है

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

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

संचार

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

बीएसपी मॉडल सामूहिक रूप से संचार क्रियाओं पर विचार करता है। इसका प्रभाव यह होता है कि डेटा के समूह को संप्रेषित करने में लगने वाले समय की ऊपरी सीमा दी जा सकती है। इस प्रकार बीएसपी सुपरस्टेप की सभी संचार क्रियाओं को इकाई मानता है और मानता है कि इस इकाई के हिस्से के रूप में भेजे गए सभी व्यक्तिगत संदेशों का निश्चित आकार होता है।

किसी सुपरस्टेप के लिए इनकमिंग या आउटगोइंग संदेशों की अधिकतम संख्या को दर्शाया जाता है $h$. डेटा वितरित करने के लिए संचार नेटवर्क की क्षमता को पैरामीटर द्वारा कैप्चर किया जाता है $g$, इस प्रकार परिभाषित किया गया है कि इसमें समय लगता है $hg$ प्रोसेसर को वितरित करने के लिए $h$ आकार 1 के संदेश.

लम्बा संदेश $m$ स्पष्ट रूप से आकार 1 के संदेश को भेजने में अधिक समय लगता है। चूँकि, बीएसपी मॉडल संदेश की लंबाई के मध्य अंतर नहीं करता है $m$ या $m$ लंबाई के संदेश 1. किसी भी स्थितियोंमें, निवेश बताई गई है $mg$.

पैरामीटर $g$ निम्नलिखित पर निर्भर करता है:

• संचार नेटवर्क के अंदर इंटरैक्ट करने के लिए उपयोग किए जाने वाले प्रोटोकॉल।
• प्रोसेसर और संचार नेटवर्क दोनों द्वारा बफर प्रबंधन।
• नेटवर्क में प्रयुक्त रूटिंग रणनीति।
• बीएसपी रनटाइम सिस्टम।

व्यवहार में, $g$ प्रत्येक समानांतर कंप्यूटर के लिए अनुभवजन्य रूप से निर्धारित किया जाता है। ध्यान दें कि $g$ यह सामान्यीकृत एकल-शब्द डिलीवरी समय नहीं है, किंतु निरंतर ट्रैफ़िक स्थितियों के अनुसार एकल-शब्द डिलीवरी समय है।

बाधाएँ

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

बैरियर सिंक्रोनाइज़ेशन की निवेश कुछ विवादों से प्रभावित होती है:

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

बैरियर सिंक्रोनाइज़ेशन की निवेश को इसके द्वारा निरूपित किया जाता है $l$. ध्यान दें कि $l<L$ यदि बीएसपी कंप्यूटर का सिंक्रनाइज़ेशन तंत्र वैलेंट द्वारा सुझाए गए अनुसार है।

व्यवहार में, का मूल्य $l$ अनुभवजन्य रूप से निर्धारित होता है।

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

एल्गोरिदमिक निवेश

एक सुपरस्टेप की निवेश तीन शर्तबं के योग के रूप में निर्धारित की जाती है:

• सबसे लंबे समय तक चलने वाली स्थानीय गणना की निवेश
• प्रोसेसरों के मध्य वैश्विक संचार की निवेश
• सुपरस्टेप के अंत में बैरियर सिंक्रोनाइज़ेशन की निवेश

इस प्रकार, सुपरस्टेप की निवेश $p$ प्रोसेसर:

$max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l$ कहाँ $w_{i}$ प्रक्रिया में स्थानीय गणना की निवेश है $i$, और $h_{i}$ प्रक्रिया द्वारा भेजे गए या प्राप्त संदेशों की संख्या है $i$. ध्यान दें कि यहां सजातीय प्रोसेसर माने गए हैं। अभिव्यक्ति को इस प्रकार लिखा जाना अधिक सामान्य है $w+hg+l$ कहाँ $w$ और $h$ मैक्सिमा हैं. संपूर्ण बीएसपी एल्गोरिदम की निवेश प्रत्येक सुपरस्टेप की निवेश का योग है।

$W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl$ कहाँ $S$ सुपरस्टेप्स की संख्या है.

$W$, $H$, और $S$ सामान्यतः ऐसे फ़ंक्शंस के रूप में तैयार किए जाते हैं जो समस्या के आकार के साथ भिन्न होते हैं। बीएसपी एल्गोरिदम की इन तीन विशेषताओं को सामान्यतः स्पर्शोन्मुख संकेतन के संदर्भ में वर्णित किया जाता है, उदाहरण के लिए, $H\in O(n/p)$.

विस्तार और उपयोग

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

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

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

यह भी देखें

• स्वचालित पारस्परिक बहिष्करण
• अपाचे हमा
• अपाचे जिराफ
• कंप्यूटर क्लस्टर
• समवर्ती कंप्यूटिंग
• समवर्ती (कंप्यूटर विज्ञान)
• डेटाफ्लो प्रोग्रामिंग
• ग्रिड कंप्यूटिंग
• लॉगपी मशीन
• समानांतर कंप्यूटिंग
• समानांतर प्रोग्रामिंग मॉडल

बाहरी संबंध

• डी.बी. स्किलिकॉर्न, जोनाथन हिल, डब्ल्यू. एफ. मैककॉल, बीएसपी के बारे में सवाल और जवाब (1996)
• बीएसपी वर्ल्डवाइड
• बीएसपी से संबंधित कागजात
• (in French) बल्क सिंक्रोनस समानांतर एमएल ((in English) आधिकारिक वेबसाइट)
• अपाचे हामा
• अपाचे जिराफ
• पैडरबोर्न विश्वविद्यालय बीएसपी पुस्तकालय
• BSPonMPI
• मल्टीकोर बीएसपी