बल्क सिंक्रोनस पैरेलल: Difference between revisions

Latest revision as of 17:09, 29 July 2023

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

इतिहास

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

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

रुचि और गति बढ़ने के साथ, मैककॉल ने ऑक्सफोर्ड, हार्वर्ड, फ्लोरिडा, प्रिंसटन, बेल लैब्स, कोलंबिया और यूट्रेक्ट के समूह का नेतृत्व किया, जिसने 1996 में बीएसपी प्रोग्रामिंग के लिए बीएसपीलिब मानक विकसित और प्रकाशित किया गया था।

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

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

बीएसपी मॉडल

अवलोकन

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

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

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

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

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

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

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

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

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

संचार

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

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

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

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

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

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

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

बाधाएँ

बीएसपी मॉडल के एकतरफा संचार के लिए बैरियर सिंक्रोनाइज़ेशन की आवश्यकता होती है।

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

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

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

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

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

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

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

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

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

इस प्रकार, सुपरस्टेप की निवेश $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 के शीर्ष पर स्पष्ट बीएसपी प्रोग्रामिंग, साथ ही अन्य उच्च-प्रदर्शन समानांतर प्रोग्रामिंग मॉडल जोड़ने के लिए सक्रिय ओपन-सोर्स परियोजनाएं हैं। उदाहरण अपाचे हामा और अपाचे ग्राफ हैं।^[4]

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

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

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 लेस्ली जी. वैलेंट, समानांतर गणना के लिए एक ब्रिजिंग मॉडल, एसीएम के संचार, खंड 33 अंक 8, अगस्त 1990 [1]
↑ ^2.0 ^2.1 वैलेंट, एल.जी. (2011)। मल्टी-कोर कंप्यूटिंग के लिए एक ब्रिजिंग मॉडल। जर्नल ऑफ कंप्यूटर एंड सिस्टम साइंसेज, 77(1), 154-166 [2]
↑ Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [3].
↑ ^4.0 ^4.1 Apache Hama
↑ Pregel
↑ The Paderborn University BSP (PUB) Library - Design, Implementation and Performance Heinz Nixdorf Institute, Department of Computer Science, University of Paderborn, Germany, technical report Archived 2001-06-05 at the Wayback Machine.
↑ Jonathan Hill: The Oxford BSP Toolset, 1998.
↑ Wijnand J. Suijlen: BSPonMPI, 2006.
↑ MulticoreBSP for C: a high-performance library for shared-memory parallel programming by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), doi:10.1109/TPDS.2013.31.
↑ An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), doi:10.1002/cpe.1843.

बाहरी संबंध

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

[CACM_Valiant-1] 1.0 ^1.1 ^1.2 लेस्ली जी. वैलेंट, समानांतर गणना के लिए एक ब्रिजिंग मॉडल, एसीएम के संचार, खंड 33 अंक 8, अगस्त 1990 [1]

[JCSS_Valiant-2] 2.0 ^2.1 वैलेंट, एल.जी. (2011)। मल्टी-कोर कंप्यूटिंग के लिए एक ब्रिजिंग मॉडल। जर्नल ऑफ कंप्यूटर एंड सिस्टम साइंसेज, 77(1), 154-166 [2]

[Alpert-3] Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [3].

[hama-4] 4.0 ^4.1 Apache Hama

[5] Pregel

[PUB-6] The Paderborn University BSP (PUB) Library - Design, Implementation and Performance Heinz Nixdorf Institute, Department of Computer Science, University of Paderborn, Germany, technical report Archived 2001-06-05 at the Wayback Machine.

[hill-7] Jonathan Hill: The Oxford BSP Toolset, 1998.

[8] Wijnand J. Suijlen: BSPonMPI, 2006.

[Yze13-9] MulticoreBSP for C: a high-performance library for shared-memory parallel programming by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), doi:10.1109/TPDS.2013.31.

[Yze12-10] An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), doi:10.1002/cpe.1843.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
-बल्क सिंक्रोनस पैरेलल (बीएसपी) [[ सार मशीन ]] [[समानांतर एल्गोरिदम]] डिजाइन करने के लिए एक [[ब्रिजिंग मॉडल]] है। यह [[समानांतर रैंडम एक्सेस मशीन]] (PRAM) मॉडल के समान है, लेकिन PRAM के विपरीत, बीएसपी संचार और सिंक्रनाइज़ेशन को हल्के में नहीं लेता है। वास्तव में, अपेक्षित सिंक्रनाइज़ेशन और संचार की मात्रा निर्धारित करना बीएसपी एल्गोरिदम का विश्लेषण करने का एक महत्वपूर्ण हिस्सा है।
+'''बल्क सिंक्रोनस पैरेलल (बीएसपी)''' [[ सार मशीन |एब्सट्रैक्ट कंप्यूटर]] [[समानांतर एल्गोरिदम]] डिजाइन करने के लिए [[ब्रिजिंग मॉडल]] है। यह [[समानांतर रैंडम एक्सेस मशीन]] (पीआरएएम ) मॉडल के समान है, किन्तु पीआरएएम के विपरीत, बीएसपी संचार और सिंक्रनाइज़ेशन को हल्के में नहीं लेता है। इस प्रकार वास्तव में, अपेक्षित सिंक्रनाइज़ेशन और संचार की मात्रा निर्धारित करना बीएसपी एल्गोरिदम का विश्लेषण करने का महत्वपूर्ण भाग है।
 ==इतिहास==
-बीएसपी मॉडल 1980 के दशक के दौरान हार्वर्ड विश्वविद्यालय के [[लेस्ली वैलेंट]] द्वारा विकसित किया गया था। निश्चित लेख 1990 में प्रकाशित हुआ था।<ref name="CACM_Valiant">लेस्ली जी. वैलेंट, समानांतर गणना के लिए एक ब्रिजिंग मॉडल, एसीएम के संचार, खंड 33 अंक 8, अगस्त 1990 [http://portal.acm.org/cition.cfm?id=79173.79181]</ref>
+बीएसपी मॉडल वर्ष 1980 के दशक के समय हार्वर्ड विश्वविद्यालय के [[लेस्ली वैलेंट]] द्वारा विकसित किया गया था। इस प्रकार निश्चित लेख वर्ष 1990 में प्रकाशित हुआ था।<ref name="CACM_Valiant">लेस्ली जी. वैलेंट, समानांतर गणना के लिए एक ब्रिजिंग मॉडल, एसीएम के संचार, खंड 33 अंक 8, अगस्त 1990 [http://portal.acm.org/cition.cfm?id=79173.79181]</ref>
-और 1992 के बीच, [[ऑक्सफोर्ड विश्वविद्यालय]] के लेस्ली वैलेंट और बिल मैककॉल ने प्रिंसटन और हार्वर्ड में एक वितरित मेमोरी बीएसपी प्रोग्रामिंग मॉडल के विचारों पर काम किया। 1992 और 1997 के बीच, मैककॉल ने ऑक्सफ़ोर्ड में एक बड़ी शोध टीम का नेतृत्व किया, जिसने विभिन्न बीएसपी प्रोग्रामिंग लाइब्रेरी, भाषाएं और उपकरण विकसित किए, और कई बड़े पैमाने पर समानांतर बीएसपी एल्गोरिदम भी विकसित किए, जिनमें उच्च-प्रदर्शन संचार से बचने वाले समानांतर एल्गोरिदम के कई शुरुआती उदाहरण शामिल थे।
+वर्ष 1990 और 1992 के मध्य, [[ऑक्सफोर्ड विश्वविद्यालय]] के लेस्ली वैलेंट और बिल मैककॉल ने प्रिंसटन और हार्वर्ड में वितरित मेमोरी बीएसपी प्रोग्रामिंग मॉडल के विचारों पर काम किया। वर्ष 1992 और 1997 के मध्य, मैककॉल ने ऑक्सफ़ोर्ड में बड़ी शोध टीम का नेतृत्व किया, जिसमें विभिन्न बीएसपी प्रोग्रामिंग लाइब्रेरी, भाषाएं और उपकरण विकसित किए और अनेक बड़े पैमाने पर समानांतर बीएसपी एल्गोरिदम भी विकसित किए, जिनमें उच्च-प्रदर्शन संचार से बचने वाले समानांतर एल्गोरिदम भी विकसित किए, जिनमें उच्च-प्रदर्शन संचार से बचने वाले समानांतर एल्गोरिदम और पुनरावर्ती के अनेक प्रारम्भिक उदाहरण सम्मिलित थे। '''"अमर"''' समानांतर एल्गोरिदम जो सर्वोत्तम संभव प्रदर्शन और इष्टतम पैरामीट्रिक ट्रेडऑफ़ प्राप्त करते हैं।
-रेफरी नाम = स्केलेबल-कंप्यूटिंग >
+रुचि और गति बढ़ने के साथ, मैककॉल ने ऑक्सफोर्ड, हार्वर्ड, फ्लोरिडा, प्रिंसटन, बेल लैब्स, कोलंबिया और यूट्रेक्ट के समूह का नेतृत्व किया, जिसने 1996 में बीएसपी प्रोग्रामिंग के लिए बीएसपीलिब मानक विकसित और प्रकाशित किया गया था।
-डब्ल्यू एफ मैककॉल। स्केलेबल कंप्यूटिंग. कंप्यूटर विज्ञान आज: हालिया रुझान और विकास। जे वैन लीउवेन (संपादक)। एलएनसीएस वॉल्यूम 1000, स्प्रिंगर-वेरलाग पीपी.46-61 (1995)
-[https://link.springer.com/chapter/10.1007/BFb0015236]</ref>
-और पुनरावर्ती अमर समानांतर एल्गोरिदम जो सर्वोत्तम संभव प्रदर्शन और इष्टतम पैरामीट्रिक ट्रेडऑफ़ प्राप्त करते हैं।
-रेफरी नाम = मैककॉल-टिस्किन >
-डब्ल्यू एफ मैककॉल और ए टिस्किन। बीएसपी मॉडल में मेमोरी-कुशल मैट्रिक्स गुणन। एल्गोरिथमिका 24(3) पीपी.287-297 (1999)
-[https://link.springer.com/article/10.1007/PL00008264]</ref>
-रुचि और गति बढ़ने के साथ, मैककॉल ने ऑक्सफोर्ड, हार्वर्ड, फ्लोरिडा, प्रिंसटन, बेल लैब्स, कोलंबिया और यूट्रेक्ट के एक समूह का नेतृत्व किया, जिसने 1996 में बीएसपी प्रोग्रामिंग के लिए बीएसपीलिब मानक विकसित और प्रकाशित किया। रेफरी नाम = bsplib > जे एम डी हिल, डब्ल्यू एफ मैककॉल, डी सी स्टेफनेस्कु, एम डब्ल्यू गौड्रेउ, के लैंग, एस बी राव, टी सुएल, टी सैंटिलस और आर एच बिसेलिंग। बीएसपीलिब: बीएसपी प्रोग्रामिंग लाइब्रेरी। पैरेलल कंप्यूटिंग 24 (14) पीपी. 1947-1980 (1998) [https://dl.acm.org/doi/abs/10.1016/S0167-8191%2898%2900093-3]</ref>
+वैलेंट ने 2000 के दशक में बीएसपी मॉडल का विस्तार विकसित किया, जिससे वर्ष 2011 में मल्टी-बीएसपी मॉडल का प्रकाशन हुआ।<ref name="JCSS_Valiant">वैलेंट, एल.जी. (2011)। मल्टी-कोर कंप्यूटिंग के लिए एक ब्रिजिंग मॉडल। जर्नल ऑफ कंप्यूटर एंड सिस्टम साइंसेज, 77(1), 154-166 [https://dx.doi.org/10.1016/j.jcss.2010.06.012]</ref>
-वैलेंट ने 2000 के दशक में बीएसपी मॉडल का विस्तार विकसित किया, जिससे 2011 में मल्टी-बीएसपी मॉडल का प्रकाशन हुआ।<ref name="JCSS_Valiant">वैलेंट, एल.जी. (2011)। मल्टी-कोर कंप्यूटिंग के लिए एक ब्रिजिंग मॉडल। जर्नल ऑफ कंप्यूटर एंड सिस्टम साइंसेज, 77(1), 154-166 [https://dx.doi.org/10.1016/j.jcss.2010.06.012]</ref>
+वर्ष 2017 में, मैककॉल ने बीएसपी मॉडल का बड़ा नया विस्तार विकसित किया जो एआई, एनालिटिक्स और [[ सुपर कंप्यूटर |उच्च-प्रदर्शन कंप्यूटिंग (एचपीसी)]] में बड़े पैमाने पर समानांतर गणनाओं के लिए [[दोष सहिष्णुता]] और पूंछ सहिष्णुता प्रदान करता है।
-में, मैककॉल ने बीएसपी मॉडल का एक बड़ा नया विस्तार विकसित किया जो एआई, एनालिटिक्स और [[ सुपर कंप्यूटर ]] | उच्च-प्रदर्शन कंप्यूटिंग (एचपीसी) में बड़े पैमाने पर समानांतर गणनाओं के लिए [[दोष सहिष्णुता]] और पूंछ सहिष्णुता प्रदान करता है।
+=='''बीएसपी मॉडल'''==
-संदर्भ नाम = McC2017 > वैज्ञानिक कंप्यूटिंग के लिए समानांतर प्रसंस्करण पर 18वें SIAM सम्मेलन में बिल मैककॉल द्वारा उच्च प्रदर्शन क्लाउड कंप्यूटिंग के लिए एक ब्रिजिंग मॉडल (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 {{Webarchive|url=https://web.archive.org/web/20191211050948/http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 |date=2019-12-11 }}.</ref> यह भी देखें
-  रेफरी नाम = गणित-मॉडल-आर्क >
-बिल मैककॉल. गणित, मॉडल और वास्तुकला। अध्याय 1, पृ. 6-53. भविष्य कंप्यूटिंग और संचार के लिए गणित, लियाओ हेंग और बिल मैककॉल द्वारा संपादित। कैम्ब्रिज यूनिवर्सिटी प्रेस (2022)। [https://www.cambridge.org/core/books/abs/mathematics-for-future-computing-and- communications/mathematics-models-and-architectures/57F4ABDEC50A67BD0CE4911779933541]</ref>
-==बीएसपी मॉडल==
 === अवलोकन ===
-एक बीएसपी कंप्यूटर में निम्नलिखित शामिल हैं:
+एक बीएसपी कंप्यूटर में निम्नलिखित सम्मिलित हैं:
-* प्रसंस्करण और/या स्थानीय मेमोरी लेनदेन में सक्षम घटक (यानी, प्रोसेसर),
+* प्रसंस्करण और/या स्थानीय मेमोरी लेनदेन में सक्षम घटक (अर्थात, प्रोसेसर),
-* एक नेटवर्क जो ऐसे घटकों के जोड़े के बीच संदेशों को रूट करता है, और
+* एक नेटवर्क जो ऐसे घटकों के जोड़े के मध्य संदेशों को रूट करता है, और
 * एक हार्डवेयर सुविधा जो सभी या घटकों के सबसेट के सिंक्रनाइज़ेशन की अनुमति देती है।
-इसे आमतौर पर प्रोसेसर के एक सेट के रूप में समझा जाता है जो गणना के विभिन्न थ्रेड (कंप्यूटर विज्ञान) का पालन कर सकता है, प्रत्येक प्रोसेसर तेज़ स्थानीय मेमोरी से लैस होता है और एक संचार नेटवर्क द्वारा परस्पर जुड़ा होता है।
+इसे सामान्यतः प्रोसेसर के समूह के रूप में समझा जाता है जो गणना के विभिन्न थ्रेड (कंप्यूटर विज्ञान) का पालन कर सकता है, प्रत्येक प्रोसेसर तेज़ स्थानीय मेमोरी से लैस होता है और संचार नेटवर्क द्वारा परस्पर जुड़ा होता है।
-बीएसपी एल्गोरिदम तीसरी विशेषता पर बहुत अधिक निर्भर करता है; एक गणना वैश्विक सुपरस्टेप्स की एक श्रृंखला में आगे बढ़ती है, जिसमें तीन घटक होते हैं:
+बीएसपी एल्गोरिदम तीसरी विशेषता पर बहुत अधिक निर्भर करता है; एक गणना वैश्विक सुपरस्टेप्स की श्रृंखला में आगे बढ़ती है, जिसमें तीन घटक होते हैं:
-* समवर्ती गणना: प्रत्येक भाग लेने वाला प्रोसेसर स्थानीय गणना कर सकता है, यानी, प्रत्येक प्रक्रिया केवल प्रोसेसर की स्थानीय तेज़ मेमोरी में संग्रहीत मानों का उपयोग कर सकती है। गणना अन्य सभी की तुलना में अतुल्यकालिक रूप से होती है लेकिन संचार के साथ ओवरलैप हो सकती है।
+* समवर्ती गणना: प्रत्येक भाग लेने वाला प्रोसेसर स्थानीय गणना कर सकता है, अर्थात, प्रत्येक प्रक्रिया केवल प्रोसेसर की स्थानीय तेज़ मेमोरी में संग्रहीत मानों का उपयोग कर सकती है। गणना अन्य सभी की तुलना में अतुल्यकालिक रूप से होती है किन्तु संचार के साथ ओवरलैप हो सकती है।
 * संचार: दूरस्थ डेटा भंडारण की सुविधा के लिए प्रक्रियाएं डेटा का आदान-प्रदान करती हैं।
-* [[बैरियर (कंप्यूटर विज्ञान)]]: जब कोई प्रक्रिया इस बिंदु (बैरियर) तक पहुंचती है, तो यह तब तक प्रतीक्षा करती है जब तक कि अन्य सभी प्रक्रियाएं समान बैरियर तक नहीं पहुंच जातीं।
+* [[बैरियर (कंप्यूटर विज्ञान)|बैरियर सिंक्रोनाइज़ेशन]]: जब कोई प्रक्रिया इस बिंदु (बैरियर) तक पहुँचती है, तब यह तब तक प्रतीक्षा करती है जब तक कि अन्य सभी प्रक्रियाएं समान बैरियर तक नहीं पहुंच जातीं हैं।
-गणना और संचार क्रियाओं को समय पर आदेश देने की आवश्यकता नहीं है। संचार आमतौर पर दो-तरफा भेजने और प्राप्त करने वाले संदेश-पासिंग कॉल के बजाय एक तरफा पुट और जीईटी [[रिमोट डायरेक्ट मेमोरी एक्सेस]] (आरडीएमए) कॉल का रूप लेता है।
+गणना और संचार क्रियाओं को समय पर आदेश देने की आवश्यकता नहीं है। संचार सामान्यतः दो-तरफा भेजने और प्राप्त करने वाले संदेश-पासिंग कॉल के अतिरिक्त एक तरफा पुट और जीईटी [[रिमोट डायरेक्ट मेमोरी एक्सेस]] (आरडीएमए) कॉल का रूप लेता है।
-[[Image:bsp.wiki.fig1.svg|thumb|270px|बीएसपी का एक सुपरस्टेप. प्रक्रियाओं में रैखिक क्रम का अभाव होता है और इन्हें किसी भी तरह से प्रोसेसर में मैप किया जा सकता है]]बैरियर सिंक्रोनाइज़ेशन सुपरस्टेप का समापन करता है - यह सुनिश्चित करता है कि सभी एकतरफा संचार ठीक से संपन्न हो गए हैं। दो-तरफा संचार पर आधारित सिस्टम में भेजे गए प्रत्येक संदेश के लिए यह सिंक्रनाइज़ेशन लागत अंतर्निहित रूप से शामिल होती है। बैरियर सिंक्रोनाइज़ेशन विधि बीएसपी कंप्यूटर की हार्डवेयर सुविधा पर निर्भर करती है। वैलेंट के मूल पेपर में, यह सुविधा समय-समय पर जाँच करती है कि क्या वर्तमान सुपरस्टेप का अंत वैश्विक स्तर पर पहुँच गया है। इस चेक की अवधि को दर्शाया गया है <math>L</math>.<ref name="CACM_Valiant"/>
+[[Image:bsp.wiki.fig1.svg|thumb|270px|बीएसपी का सुपरस्टेप. प्रक्रियाओं में रैखिक क्रम का अभाव होता है और इन्हें किसी भी तरह से प्रोसेसर में मानचित्र किया जा सकता है]]बैरियर सिंक्रोनाइज़ेशन सुपरस्टेप का समापन करता है - यह सुनिश्चित करता है कि सभी एकतरफा संचार ठीक से संपन्न हो गए हैं। दो-तरफा संचार पर आधारित प्रणाली में भेजे गए प्रत्येक संदेश के लिए यह सिंक्रनाइज़ेशन निवेश अंतर्निहित रूप से सम्मिलित होती है। इस प्रकार बैरियर सिंक्रोनाइज़ेशन विधि बीएसपी कंप्यूटर की हार्डवेयर सुविधा पर निर्भर करती है। वैलेंट के मूल पेपर में, यह सुविधा समय-समय पर जाँच करती है कि क्या वर्तमान सुपरस्टेप का अंत वैश्विक स्तर पर पहुँच गया है। इस प्रकार इस चेक की अवधि को दर्शाया गया है <math>L</math>.<ref name="CACM_Valiant"/>
-बीएसपी मॉडल समस्या के अति-विघटन और प्रोसेसर की ओवरसब्सक्रिप्शन के माध्यम से वितरित-मेमोरी कंप्यूटिंग के लिए स्वचालित मेमोरी प्रबंधन के लिए भी उपयुक्त है। गणना को भौतिक प्रोसेसर की तुलना में अधिक तार्किक प्रक्रियाओं में विभाजित किया गया है, और प्रक्रियाओं को यादृच्छिक रूप से प्रोसेसर को सौंपा गया है। इस रणनीति को सांख्यिकीय रूप से दिखाया जा सकता है जिससे कार्य और संचार दोनों में लगभग पूर्ण भार संतुलन हो सकता है।
+बीएसपी मॉडल समस्या के अति-विघटन और प्रोसेसर की ओवरसब्सक्रिप्शन के माध्यम से वितरित-मेमोरी कंप्यूटिंग के लिए स्वचालित मेमोरी प्रबंधन के लिए भी उपयुक्त है। इस प्रकार गणना को भौतिक प्रोसेसर की तुलना में अधिक तार्किक प्रक्रियाओं में विभाजित किया गया है, और प्रक्रियाओं को यादृच्छिक रूप से प्रोसेसर को सौंपा गया है। इस प्रकार इस रणनीति को सांख्यिकीय रूप से दिखाया जा सकता है जिससे कार्य और संचार दोनों में लगभग पूर्ण भार संतुलन हो सकता है।
 ===संचार===
-कई समानांतर प्रोग्रामिंग प्रणालियों में, संचार को व्यक्तिगत क्रियाओं के स्तर पर माना जाता है, जैसे संदेश भेजना और प्राप्त करना या मेमोरी-टू-मेमोरी स्थानांतरण। इसके साथ काम करना मुश्किल है क्योंकि एक समानांतर कार्यक्रम में एक साथ कई संचार क्रियाएं होती हैं, और उनकी बातचीत आम तौर पर जटिल होती है। विशेष रूप से, किसी एकल संचार कार्रवाई को पूरा होने में कितना समय लगेगा, इसके बारे में बहुत कुछ कहना मुश्किल है।
+अनेक समानांतर प्रोग्रामिंग प्रणालियों में, संचार को व्यक्तिगत क्रियाओं के स्तर पर माना जाता है, जैसे संदेश भेजना और प्राप्त करना या मेमोरी-टू-मेमोरी स्थानांतरण करना हैं। इस प्रकार इसके साथ काम करना कठिनाई है क्योंकि समानांतर कार्यक्रम में साथ अनेक संचार क्रियाएं होती हैं, और उनकी बातचीत सामान्यतः जटिल होती है। इस प्रकार विशेष रूप से, किसी एकल संचार कार्रवाई को पूरा होने में कितना समय लगेगा, इसके बारे में बहुत कुछ कहना कठिनाई है।
-बीएसपी मॉडल सामूहिक रूप से संचार क्रियाओं पर विचार करता है। इसका प्रभाव यह होता है कि डेटा के एक सेट को संप्रेषित करने में लगने वाले समय की ऊपरी सीमा दी जा सकती है। बीएसपी सुपरस्टेप की सभी संचार क्रियाओं को एक इकाई मानता है और मानता है कि इस इकाई के हिस्से के रूप में भेजे गए सभी व्यक्तिगत संदेशों का एक निश्चित आकार होता है।
+बीएसपी मॉडल सामूहिक रूप से संचार क्रियाओं पर विचार करता है। इसका प्रभाव यह होता है कि डेटा के समूह को संप्रेषित करने में लगने वाले समय की ऊपरी सीमा दी जा सकती है। इस प्रकार बीएसपी सुपरस्टेप की सभी संचार क्रियाओं को इकाई मानता है और मानता है कि इस इकाई के हिस्से के रूप में भेजे गए सभी व्यक्तिगत संदेशों का निश्चित आकार होता है।
-किसी सुपरस्टेप के लिए इनकमिंग या आउटगोइंग संदेशों की अधिकतम संख्या को दर्शाया जाता है <math>h</math>. डेटा वितरित करने के लिए संचार नेटवर्क की क्षमता को एक पैरामीटर द्वारा कैप्चर किया जाता है <math>g</math>, इस प्रकार परिभाषित किया गया है कि इसमें समय लगता है <math>hg</math> एक प्रोसेसर को वितरित करने के लिए <math>h</math> आकार 1 के संदेश.
+किसी सुपरस्टेप के लिए इनकमिंग या आउटगोइंग संदेशों की अधिकतम संख्या को दर्शाया जाता है <math>h</math>. डेटा वितरित करने के लिए संचार नेटवर्क की क्षमता को पैरामीटर द्वारा कैप्चर किया जाता है <math>g</math>, इस प्रकार परिभाषित किया गया है कि इसमें समय लगता है <math>hg</math> प्रोसेसर को वितरित करने के लिए <math>h</math> आकार 1 के संदेश.
-लम्बा संदेश <math>m</math> स्पष्ट रूप से आकार 1 के संदेश को भेजने में अधिक समय लगता है। हालाँकि, बीएसपी मॉडल संदेश की लंबाई के बीच अंतर नहीं करता है <math>m</math> या <math>m</math> लंबाई के संदेश 1. किसी भी मामले में, लागत बताई गई है <math>mg</math>.
+लम्बा संदेश <math>m</math> स्पष्ट रूप से आकार 1 के संदेश को भेजने में अधिक समय लगता है। चूँकि, बीएसपी मॉडल संदेश की लंबाई के मध्य अंतर नहीं करता है <math>m</math> या <math>m</math> लंबाई के संदेश 1. किसी भी स्थितियोंमें, निवेश बताई गई है <math>mg</math>.
 पैरामीटर <math>g</math> निम्नलिखित पर निर्भर करता है:
-* संचार नेटवर्क के भीतर इंटरैक्ट करने के लिए उपयोग किए जाने वाले प्रोटोकॉल।
+* संचार नेटवर्क के अंदर इंटरैक्ट करने के लिए उपयोग किए जाने वाले प्रोटोकॉल।
 * प्रोसेसर और संचार नेटवर्क दोनों द्वारा बफर प्रबंधन।
 * नेटवर्क में प्रयुक्त रूटिंग रणनीति।
 * बीएसपी [[रनटाइम सिस्टम]]।
-व्यवहार में, <math>g</math> प्रत्येक समानांतर कंप्यूटर के लिए अनुभवजन्य रूप से निर्धारित किया जाता है। ध्यान दें कि <math>g</math> यह सामान्यीकृत एकल-शब्द डिलीवरी समय नहीं है, बल्कि निरंतर ट्रैफ़िक स्थितियों के तहत एकल-शब्द डिलीवरी समय है।
+व्यवहार में, <math>g</math> प्रत्येक समानांतर कंप्यूटर के लिए अनुभवजन्य रूप से निर्धारित किया जाता है। इस प्रकार ध्यान दें कि <math>g</math> यह सामान्यीकृत एकल-शब्द डिलीवरी समय नहीं है, किंतु निरंतर ट्रैफ़िक स्थितियों के अनुसार एकल-शब्द डिलीवरी समय है।
 ===बाधाएँ===
-{{Refimprove section|date=November 2013}}
+बीएसपी मॉडल के एकतरफा संचार के लिए बैरियर सिंक्रोनाइज़ेशन की आवश्यकता होती है।
-बीएसपी मॉडल के एकतरफा संचार के लिए बैरियर (कंप्यूटर विज्ञान) की आवश्यकता होती है।
+बाधाएं संभावित रूप से बहुमूल्य हैं किन्तु [[गतिरोध]] या लाइवलॉक की संभावना से बचें, क्योंकि बाधाएं सर्कुलर निर्भरता नहीं बना सकती हैं। इस प्रकार उनका पता लगाने और उनसे निपटने के उपकरण अनावश्यक हैं। बाधाएँ [[दोष-सहिष्णु प्रणाली]] के नवीन रूपों की भी अनुमति देती हैं.
-बैरियर (कंप्यूटर विज्ञान) संभावित रूप से महंगे हैं लेकिन [[गतिरोध]] या डेडलॉक की संभावना से बचें, क्योंकि बाधाएं सर्कुलर निर्भरता नहीं बना सकती हैं।<!-- link to deadlock detection? --> उनका पता लगाने और उनसे निपटने के उपकरण अनावश्यक हैं। बाधाएँ [[दोष-सहिष्णु प्रणाली]] के नवीन रूपों की भी अनुमति देती हैं{{Citation needed|reason=Checkpointing is an obvious example, but this is not novel. What is being referred to here?|date=February 2014}}.
-बैरियर सिंक्रोनाइज़ेशन की लागत कुछ मुद्दों से प्रभावित होती है:
+बैरियर सिंक्रोनाइज़ेशन की निवेश में कुछ विवादों से प्रभावित होती है:
-* भाग लेने वाली समवर्ती गणनाओं के पूरा होने के समय में भिन्नता के कारण लगाई गई लागत। उदाहरण लें जहां एक को छोड़कर सभी प्रक्रियाओं ने इस सुपरस्टेप के लिए अपना काम पूरा कर लिया है, और अंतिम प्रक्रिया की प्रतीक्षा कर रहे हैं, जिसे पूरा करने के लिए अभी भी बहुत काम बाकी है। एक कार्यान्वयन जो सबसे अच्छा कर सकता है वह यह सुनिश्चित करना है कि प्रत्येक प्रक्रिया लगभग समान समस्या आकार पर काम करती है।
+* भाग लेने वाली समवर्ती गणनाओं के पूरा होने के समय में भिन्नता के कारण लगाई गई निवेश। उदाहरण लें जहां को छोड़कर सभी प्रक्रियाओं ने इस सुपरस्टेप के लिए अपना काम पूरा कर लिया है, और अंतिम प्रक्रिया की प्रतीक्षा कर रहे हैं, जिसे पूरा करने के लिए अभी भी बहुत काम बाकी है। इस प्रकार कार्यान्वयन जो सबसे अच्छा कर सकता है वह यह सुनिश्चित करना है कि प्रत्येक प्रक्रिया लगभग समान समस्या आकार पर काम करती है।
-* सभी प्रोसेसरों में विश्व स्तर पर सुसंगत स्थिति तक पहुंचने की लागत। यह संचार नेटवर्क पर निर्भर करता है, लेकिन इस पर भी निर्भर करता है कि सिंक्रनाइज़ करने के लिए विशेष प्रयोजन हार्डवेयर उपलब्ध है या नहीं और प्रोसेसर द्वारा व्यवधान को किस तरह से नियंत्रित किया जाता है।
+* सभी प्रोसेसरों में विश्व स्तर पर सुसंगत स्थिति तक पहुंचने की निवेश। यह संचार नेटवर्क पर निर्भर करता है, किन्तु इस पर भी निर्भर करता है कि सिंक्रनाइज़ करने के लिए विशेष प्रयोजन हार्डवेयर उपलब्ध है या नहीं और प्रोसेसर द्वारा व्यवधान को किस तरह से नियंत्रित किया जाता है।
-बैरियर सिंक्रोनाइज़ेशन की लागत को इसके द्वारा निरूपित किया जाता है <math>l</math>. ध्यान दें कि <math>l<L</math> यदि बीएसपी कंप्यूटर का सिंक्रनाइज़ेशन तंत्र वैलेंट द्वारा सुझाए गए अनुसार है।<ref name=CACM_Valiant/>
+बैरियर सिंक्रोनाइज़ेशन की निवेश को इसके द्वारा निरूपित किया जाता है <math>l</math>. ध्यान दें कि <math>l<L</math> यदि बीएसपी कंप्यूटर का सिंक्रनाइज़ेशन तंत्र वैलेंट द्वारा सुझाए गए अनुसार है।<ref name=CACM_Valiant/>
-<!-- What could you measure to determine l? -->
-व्यवहार में, का एक मूल्य <math>l</math> अनुभवजन्य रूप से निर्धारित होता है।
-बड़े कंप्यूटरों पर, बैरियर महंगे होते हैं, और बड़े पैमाने पर यह तेजी से बढ़ रहा है। बीएसपी कंप्यूटिंग और उससे आगे के संदर्भ में मौजूदा एल्गोरिदम से सिंक्रनाइज़ेशन बिंदुओं को हटाने पर साहित्य का एक बड़ा संग्रह है। उदाहरण के लिए, कई एल्गोरिदम पहले से प्राप्त संदेशों की संख्या के साथ स्थानीय जानकारी की तुलना करके सुपरस्टेप के वैश्विक अंत का स्थानीय पता लगाने की अनुमति देते हैं। इससे संचार की न्यूनतम आवश्यक विलंबता की तुलना में वैश्विक सिंक्रनाइज़ेशन की लागत शून्य हो जाती है।<ref name="Alpert">Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.7784&rep=rep1&type=pdf].</ref> फिर भी भविष्य के सुपरकंप्यूटर आर्किटेक्चर और नेटवर्क इंटरकनेक्ट के लिए इस न्यूनतम विलंबता के और बढ़ने की उम्मीद है; समानांतर गणना के लिए अन्य मॉडलों के साथ बीएसपी मॉडल को इस प्रवृत्ति से निपटने के लिए अनुकूलन की आवश्यकता है। मल्टी-बीएसपी एक बीएसपी-आधारित समाधान है।<ref name=JCSS_Valiant/>
+व्यवहार में, का मूल्य <math>l</math> अनुभवजन्य रूप से निर्धारित होता है।
+बड़े कंप्यूटरों पर, बैरियर बहुमूल्य होते हैं, और बड़े पैमाने पर यह तेजी से बढ़ रहा है। बीएसपी कंप्यूटिंग और उससे आगे के संदर्भ में उपस्तिथा एल्गोरिदम से सिंक्रनाइज़ेशन बिंदुओं को हटाने पर साहित्य का बड़ा संग्रह है। इस प्रकार उदाहरण के लिए, अनेक एल्गोरिदम पहले से प्राप्त संदेशों की संख्या के साथ स्थानीय जानकारी की तुलना करके सुपरस्टेप के वैश्विक अंत का स्थानीय पता लगाने की अनुमति देते हैं। इससे संचार की न्यूनतम आवश्यक विलंबता की तुलना में वैश्विक सिंक्रनाइज़ेशन की निवेश शून्य हो जाती है।<ref name="Alpert">Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.7784&rep=rep1&type=pdf].</ref> फिर भी भविष्य के सुपरकंप्यूटर आर्किटेक्चर और नेटवर्क इंटरकनेक्ट के लिए इस न्यूनतम विलंबता के और बढ़ने की उम्मीद है; समानांतर गणना के लिए अन्य मॉडलों के साथ बीएसपी मॉडल को इस प्रवृत्ति से निपटने के लिए अनुकूलन की आवश्यकता है। इस प्रकार मल्टी-बीएसपी बीएसपी-आधारित समाधान है।<ref name=JCSS_Valiant/>
+===एल्गोरिदमिक निवेश===
+एक सुपरस्टेप की निवेश तीन शर्तों के योग के रूप में निर्धारित की जाती है:
+* सबसे लंबे समय तक चलने वाली स्थानीय गणना की निवेश
+* प्रोसेसरों के मध्य वैश्विक संचार की निवेश
+* सुपरस्टेप के अंत में बैरियर सिंक्रोनाइज़ेशन की निवेश
-===एल्गोरिदमिक लागत===
+इस प्रकार, सुपरस्टेप की निवेश <math>p</math> प्रोसेसर:
-एक सुपरस्टेप की लागत तीन शर्तों के योग के रूप में निर्धारित की जाती है:
-* सबसे लंबे समय तक चलने वाली स्थानीय गणना की लागत
-* प्रोसेसरों के बीच वैश्विक संचार की लागत
-* सुपरस्टेप के अंत में बैरियर सिंक्रोनाइज़ेशन की लागत
-इस प्रकार, एक सुपरस्टेप की लागत <math>p</math> प्रोसेसर:
 <math>
 max_{i = 1}^{p}(w_i) + max_{i=1}^{p}(h_i g) + l
 </math>
-कहाँ <math>w_i</math> प्रक्रिया में स्थानीय गणना की लागत है <math>i</math>, और <math>h_i</math> प्रक्रिया द्वारा भेजे गए या प्राप्त संदेशों की संख्या है <math>i</math>. ध्यान दें कि यहां सजातीय प्रोसेसर माने गए हैं। अभिव्यक्ति को इस प्रकार लिखा जाना अधिक सामान्य है <math>w + hg + l</math> कहाँ <math>w</math> और <math>h</math> मैक्सिमा हैं. संपूर्ण बीएसपी एल्गोरिदम की लागत प्रत्येक सुपरस्टेप की लागत का योग है।
+कहाँ <math>w_i</math> प्रक्रिया में स्थानीय गणना की निवेश है <math>i</math>, और <math>h_i</math> प्रक्रिया द्वारा भेजे गए या प्राप्त संदेशों की संख्या है <math>i</math>. ध्यान दें कि यहां सजातीय प्रोसेसर माने गए हैं। अभिव्यक्ति को इस प्रकार लिखा जाना अधिक सामान्य है <math>w + hg + l</math> कहाँ <math>w</math> और <math>h</math> मैक्सिमा हैं. संपूर्ण बीएसपी एल्गोरिदम की निवेश प्रत्येक सुपरस्टेप की निवेश का योग है।
 <math>
 W + Hg + Sl = \sum_{s=1}^{S}w_s + g \sum_{s=1}^{S}h_s + Sl
 </math>
 कहाँ <math>S</math> सुपरस्टेप्स की संख्या है.
-<math>W</math>, <math>H</math>, और <math>S</math> आमतौर पर ऐसे फ़ंक्शंस के रूप में तैयार किए जाते हैं जो समस्या के आकार के साथ भिन्न होते हैं। बीएसपी एल्गोरिदम की इन तीन विशेषताओं को आम तौर पर [[स्पर्शोन्मुख संकेतन]] के संदर्भ में वर्णित किया जाता है, उदाहरण के लिए, <math>H \in O(n/p)</math>.
+<math>W</math>, <math>H</math>, और <math>S</math> सामान्यतः ऐसे फ़ंक्शंस के रूप में तैयार किए जाते हैं जो समस्या के आकार के साथ भिन्न होते हैं। इस प्रकार बीएसपी एल्गोरिदम की इन तीन विशेषताओं को सामान्यतः [[स्पर्शोन्मुख संकेतन]] के संदर्भ में वर्णित किया जाता है, उदाहरण के लिए, <math>H \in O(n/p)</math>.
 ==विस्तार और उपयोग==
-बीएसपी में रुचि बढ़ गई है, [[Google]] ने इसे Pregel और [[MapReduce]] के माध्यम से बड़े पैमाने पर ग्राफ विश्लेषण के लिए एक प्रमुख तकनीक के रूप में अपनाया है। इसके अलावा, [[Hadoop]] की अगली पीढ़ी ने MapReduce मॉडल को Hadoop के बाकी बुनियादी ढांचे से अलग कर दिया है, अब Hadoop के शीर्ष पर स्पष्ट बीएसपी प्रोग्रामिंग, साथ ही अन्य उच्च-प्रदर्शन समानांतर प्रोग्रामिंग मॉडल जोड़ने के लिए सक्रिय ओपन-सोर्स परियोजनाएं हैं। उदाहरण [[अपाचे हामा]] और [[अपाचे गिरफ]] हैं।<ref name="hama">[http://hama.apache.org/ Apache Hama]</ref>
+बीएसपी में रुचि बढ़ गई है, [[Google|गूगल]] ने इसे Pregel और [[MapReduce]] के माध्यम से बड़े पैमाने पर ग्राफ विश्लेषण के लिए प्रमुख विधि के रूप में अपनाया है। इस प्रकार इसके अतिरिक्त, [[Hadoop]] की अगली पीढ़ी ने MapReduce मॉडल को Hadoop के बाकी मूलभूतढांचे से भिन्न कर दिया है, इस प्रकार अब Hadoop के शीर्ष पर स्पष्ट बीएसपी प्रोग्रामिंग, साथ ही अन्य उच्च-प्रदर्शन समानांतर प्रोग्रामिंग मॉडल जोड़ने के लिए सक्रिय ओपन-सोर्स परियोजनाएं हैं। उदाहरण [[अपाचे हामा]] और [[अपाचे गिरफ|अपाचे ग्राफ]] हैं।<ref name="hama">[http://hama.apache.org/ Apache Hama]</ref>
-विशिष्ट आर्किटेक्चर या कम्प्यूटेशनल प्रतिमानों के मॉडलिंग के लिए बीएसपी की अनुपयुक्तता के बारे में चिंताओं को दूर करने के लिए कई लेखकों द्वारा बीएसपी का विस्तार किया गया है। इसका एक उदाहरण विघटित बीएसपी मॉडल है। मॉडल का उपयोग कई नई प्रोग्रामिंग भाषाओं और इंटरफेस के निर्माण में भी किया गया है, जैसे बल्क सिंक्रोनस पैरेलल एमएल (बीएसएमएल), बीएसपीलिब, अपाचे हामा,<ref name="hama"/>और प्रीगेल.<ref>[http://dl.acm.org/citation.cfm?id=1582723 Pregel]</ref>
-बीएसपीलिब मानक का उल्लेखनीय कार्यान्वयन पैडरबोर्न विश्वविद्यालय बीएसपी पुस्तकालय है<ref name=PUB>The Paderborn University BSP (PUB) Library - Design, Implementation and Performance
+विशिष्ट आर्किटेक्चर या कम्प्यूटेशनल प्रतिमानों के मॉडलिंग के लिए बीएसपी की अनुपयुक्तता के बारे में चिंताओं को दूर करने के लिए अनेक लेखकों द्वारा बीएसपी का विस्तार किया गया है। इस प्रकार इसका उदाहरण विघटित बीएसपी मॉडल है। मॉडल का उपयोग अनेक नई प्रोग्रामिंग भाषाओं और इंटरफेस के निर्माण में भी किया गया है, जैसे बल्क सिंक्रोनस पैरेलल एमएल (बीएसएमएल), बीएसपीलिब, अपाचे हामा,<ref name="hama" />और प्रीगेल हैं।<ref>[http://dl.acm.org/citation.cfm?id=1582723 Pregel]</ref>
-Heinz Nixdorf Institute, Department of Computer Science, University of Paderborn, Germany, [http://www.uni-paderborn.de/fachbereich/AG/agmadh/PapersPostscript/inri.98.tr-rsfb-98-063.ps.gz technical report] {{Webarchive|url=https://web.archive.org/web/20010605075544/http://www.uni-paderborn.de/fachbereich/AG/agmadh/PapersPostscript/inri.98.tr-rsfb-98-063.ps.gz |date=2001-06-05 }}.</ref> और जोनाथन हिल द्वारा ऑक्सफोर्ड बीएसपी टूलसेट।<ref name="hill">Jonathan Hill: [http://www.bsp-worldwide.org/implmnts/oxtool/ The Oxford BSP Toolset], 1998.</ref> आधुनिक कार्यान्वयन में बीएसपीओनएमपीआई शामिल है<ref>Wijnand J. Suijlen: [http://bsponmpi.sourceforge.net BSPonMPI], 2006.</ref> (जो [[संदेश पासिंग इंटरफ़ेस]] के शीर्ष पर बीएसपी का अनुकरण करता है), और मल्टीकोरबीएसपी<ref name=Yze13>MulticoreBSP for C: a high-performance library for shared-memory parallel programming
-by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), [https://dx.doi.org/10.1109/TPDS.2013.31 doi:10.1109/TPDS.2013.31].</ref><ref name=Yze12>An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming
+बीएसपीलिब मानक का उल्लेखनीय कार्यान्वयन पैडरबोर्न विश्वविद्यालय बीएसपी पुस्तकालय है<ref name="PUB">The Paderborn University BSP (PUB) Library - Design, Implementation and Performance
-by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), [https://dx.doi.org/10.1002/cpe.1843 doi:10.1002/cpe.1843].</ref> (आधुनिक साझा-मेमोरी आर्किटेक्चर को लक्षित करने वाला एक नया कार्यान्वयन)। सी के लिए मल्टीकोरबीएसपी नेस्टेड बीएसपी रन शुरू करने की अपनी क्षमता के लिए विशेष रूप से उल्लेखनीय है, इस प्रकार स्पष्ट मल्टी-बीएसपी प्रोग्रामिंग की अनुमति मिलती है।
+Heinz Nixdorf Institute, Department of Computer Science, University of Paderborn, Germany, [http://www.uni-paderborn.de/fachbereich/AG/agmadh/PapersPostscript/inri.98.tr-rsfb-98-063.ps.gz technical report] {{Webarchive|url=https://web.archive.org/web/20010605075544/http://www.uni-paderborn.de/fachbereich/AG/agmadh/PapersPostscript/inri.98.tr-rsfb-98-063.ps.gz |date=2001-06-05 }}.</ref> और जोनाथन हिल द्वारा ऑक्सफोर्ड बीएसपी टूलसेट हैं।<ref name="hill">Jonathan Hill: [http://www.bsp-worldwide.org/implmnts/oxtool/ The Oxford BSP Toolset], 1998.</ref> आधुनिक कार्यान्वयन में बीएसपीओनएमपीआई सम्मिलित है<ref>Wijnand J. Suijlen: [http://bsponmpi.sourceforge.net BSPonMPI], 2006.</ref> (जो [[संदेश पासिंग इंटरफ़ेस]] के शीर्ष पर बीएसपी का अनुकरण करता है), और मल्टीकोरबीएसपी<ref name="Yze13">MulticoreBSP for C: a high-performance library for shared-memory parallel programming
+by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), [https://dx.doi.org/10.1109/TPDS.2013.31 doi:10.1109/TPDS.2013.31].</ref><ref name="Yze12">An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming
+by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), [https://dx.doi.org/10.1002/cpe.1843 doi:10.1002/cpe.1843].</ref> (आधुनिक साझा-मेमोरी आर्किटेक्चर को लक्षित करने वाला नया कार्यान्वयन) सम्मिलित हैं। इस प्रकार सी के लिए मल्टीकोरबीएसपी नेस्टेड बीएसपी रन प्रारंभ करने की अपनी क्षमता के लिए विशेष रूप से उल्लेखनीय है, इस प्रकार स्पष्ट मल्टी-बीएसपी प्रोग्रामिंग की अनुमति मिलती है।
 ==यह भी देखें==
@@ Line 122: / Line 112: @@
 ==संदर्भ==
 {{reflist}}
 ==बाहरी संबंध==
-* D.B. Skillicorn, Jonathan Hill, W. F. McColl, [ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Jonathan.Hill/SkillHillMcColl_QA.ps.gz Questions and answers about BSP]{{dead link|date=November 2016 |bot=InternetArchiveBot |fix-attempted=yes }} (1996)
+* डी.बी. स्किलिकॉर्न, जोनाथन हिल, डब्ल्यू. एफ. मैककॉल, [ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Jonathan.Hill/SkillHillMcColl_QA.ps.gz बीएसपी के बारे में सवाल और जवाब] (1996)
-* [http://www.bsp-worldwide.org/ BSP Worldwide]
+* [http://www.bsp-worldwide.org/ बीएसपी वर्ल्डवाइड]
-* [http://www.bsp-worldwide.org/implmnts/oxtool/papers.html BSP related papers]
+* [http://www.bsp-worldwide.org/implmnts/oxtool/papers.html बीएसपी से संबंधित कागजात]
-* {{in lang|fr}} [[:fr:BSML|Bulk Synchronous Parallel ML]] ({{in lang|en}} [http://frederic.loulergue.eu/research/bsml/index.html official website])
+* {{in lang|fr}} [[:fr:BSML|बल्क सिंक्रोनस समानांतर एमएल]] ({{in lang|en}} [http://frederic.loulergue.eu/research/bsml/index.html आधिकारिक वेबसाइट])
-* [http://hama.apache.org/ Apache Hama]
+* [http://hama.apache.org/ अपाचे हामा]
-* [http://giraph.apache.org/ Apache Giraph]
+* [http://giraph.apache.org/ अपाचे जिराफ]
-* [https://web.archive.org/web/20180129094236/http://www2.cs.uni-paderborn.de/~pub/ Paderborn University BSP library]
+* [https://web.archive.org/web/20180129094236/http://www2.cs.uni-paderborn.de/~pub/ पैडरबोर्न विश्वविद्यालय बीएसपी पुस्तकालय]
-* [http://bsponmpi.sourceforge.net BSPonMPI]
+* [http://bsponmpi.sourceforge.net बीएसपीओएनएमपीआई]
-* [http://www.multicorebsp.com MulticoreBSP]
+* [http://www.multicorebsp.com मल्टीकोर बीएसपी]
-[[Category: गणना के मॉडल]] [[Category: समानांतर कंप्यूटिंग]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with English-language sources (en)]]
+[[Category:Articles with French-language sources (fr)]]
 [[Category:Created On 07/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Webarchive template wayback links]]
+[[Category:गणना के मॉडल]]
+[[Category:समानांतर कंप्यूटिंग]]

Anonymous

Search

बल्क सिंक्रोनस पैरेलल: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:09, 29 July 2023

Contents

इतिहास