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

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

इतिहास

बीएसपी मॉडल 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)$.

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

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

यह भी देखें

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

बाहरी संबंध

• D.B. Skillicorn, Jonathan Hill, W. F. McColl, Questions and answers about BSP (1996)
• BSP Worldwide
• BSP related papers
• (in French) Bulk Synchronous Parallel ML ((in English) official website)
• Apache Hama
• Apache Giraph
• Paderborn University BSP library
• BSPonMPI
• MulticoreBSP