बाइनरी मॉड्यूलर डेटाफ्लो मशीन
बाइनरी मॉड्यूलर डेटाफ्लो मशीन (बीएमडीएफएम) एक सॉफ्टवेयर पैकेज है जो एकल अनुप्रयोगों के निष्पादन को गति देने के लिए कई प्रोसेसरों का उपयोग करके साझा मेमोरी सिमेट्रिक मल्टीप्रोसेसिंग (एसएमपी) कंप्यूटरों पर समानांतर में एप्लिकेशन चलाने में सक्षम बनाता है। बीएमडीएफएम स्वचालित रूप से पूर्व अनुक्रमिक कार्यक्रम से प्राप्त डेटाफ्लो निर्देश अनुक्रमों के स्थिर और मुख्य रूप से गतिशील शेड्यूलिंग के कारण समांतरता को पहचानता है और इसका प्रयोग करता है।
बीएमडीएफएम डायनेमिक शेड्यूलिंग सबसिस्टम अनुप्रयोगों के लिए पारदर्शी डेटाफ्लो सिमेंटिक्स प्रदान करने के लिए एक टैग-टोकन डेटाफ्लो मशीन का सममित मल्टीप्रोसेसिंग (एसएमपी) अनुकरण करता है। समानांतर निष्पादन के लिए कोई निर्देश आवश्यक नहीं है।
पृष्ठभूमि
वर्तमान समानांतर साझा मेमोरी एसएमपी जटिल मशीनें हैं, जहां उच्च प्रदर्शन प्राप्त करने के लिए बड़ी संख्या में आर्किटेक्चर संबंधी पहलुओं को एक साथ संबोधित किया जाना चाहिए। तकनीकी कंप्यूटिंग के लिए हालिया कमोडिटी एसएमपी मशीनों में कई कसकर युग्मित कोर हो सकते हैं (अच्छे उदाहरण हैं इंटेल (कोर या एक्सॉन) या आईबीएम (पावर) से मल्टी-कोर प्रोसेसर पर आधारित एसएमपी मशीनें)। कंप्यूटर निर्माताओं की घोषणाओं के मुताबिक प्रत्येक एसएमपी नोड में कोर की संख्या हर कुछ वर्षों में दोगुनी करने की योजना है।
मल्टी-कोर प्रोसेसर का उद्देश्य सॉफ्टवेयर द्वारा पहचाने गए थ्रेड-लेवल समानता की सुविधा उठाना है। इसलिए, सबसे चुनौतीपूर्ण कार्य समानांतर में एप्लिकेशन प्रोग्राम को प्रोसेस करने के लिए मल्टी-कोर प्रोसेसर की शक्ति का उपयोग करने का एक प्रभावी तरीका खोजना है। फोर्क-जॉइन रनटाइम लाइब्रेरी के साथ स्थिर समांतरता के मौजूदा ओपनएमपी प्रतिमान लूप-गहन नियमित सरणी-आधारित कंप्यूटेशंस के लिए बहुत अच्छी तरह से काम करता है, हालांकि, संकलन-समय समांतरता विधियां सामान्य रूप से कमजोर हैं और अनियमित अनुप्रयोगों के लिए लगभग अनुपयुक्त हैं:
- ऐसे कई ऑपरेशन हैं जो एक गैर-नियतात्मक समय लेते हैं जिससे यह जानना मुश्किल हो जाता है कि डेटा के कुछ भाग कब उपलब्ध होंगे।
- बहु-स्तरीय कैश के साथ मेमोरी पदानुक्रम में अप्रत्याशित मेमोरी एक्सेस विलंबता होती है।
- एक बहु-उपयोगकर्ता मोड अन्य लोगों के कोड संसाधनों का उपयोग कर सकते हैं या गणना के एक हिस्से को इस तरह से धीमा कर सकते हैं कि संकलक इसका हिसाब नहीं लगा सकता।
- संकलन-समय अंतर-प्रक्रियात्मक और क्रॉस-सशर्त अनुकूलन कठिन हैं (प्रायः असंभव) क्योंकि संकलक यह पता नहीं लगा सकते हैं कि सशर्त किस तरह से जाएगा या फ़ंक्शन कॉल में अनुकूलन नहीं कर सकता है।
बीएमडीएफएम का पारदर्शी डेटाफ्लो सिमेंटिक्स
बीएमडीएफएम तकनीक मुख्य रूप से गतिशील शेड्यूलिंग का उपयोग एक आवेदन कार्यक्रम के समानांतरता का फायदा उठाने के लिए करती है, इस प्रकार, बीएमडीएफएम संकलन-समय विधियों के उल्लिखित नुकसान से बचाता है।[1][2] बीएमडीएफएम मल्टी-कोर एसएमपी के लिए समानांतर प्रोग्रामिंग परिस्थिति है जो प्रदान करता है:
- परम्परागत प्रोग्रामिंग प्रतिमान को समानांतर निष्पादन के लिए किसी निर्देश की आवश्यकता नहीं है।
- स्वचालित रूप से सिस्टम में सभी उपलब्ध मल्टी-कोर प्रोसेसर का उपयोग करके प्राकृतिक और लोड संतुलित तरीके से समानता का पारदर्शी (निहित) दोहन।
बीएमडीएफएम ज्ञात आर्किटेक्चरल सिद्धांतों के फायदों को सिंगल हाइब्रिड आर्किटेक्चर में जोड़ता है जो नगण्य गतिशील शेड्यूलिंग ओवरहेड और कोई बाधा नहीं होने वाले अनुप्रयोगों के निहित समांतरता का फायदा उठाने में सक्षम है। मुख्य रूप से, मूल डेटा प्रवाह सिद्धांत का उपयोग किया जाता है। डेटाफ्लो सिद्धांत कहता है: "एक निर्देश या फ़ंक्शन को उसके सभी तर्क तैयार होते ही निष्पादित किया जा सकता है। डेटाफ्लो मशीन रनटाइम पर डेटा के हर हिस्से के लिए टैग का प्रबंधन करती है। जब डेटा की गणना की जाती है तो डेटा को रेडी टैग के साथ चिह्नित किया जाता है। तैयार तर्कों के साथ निर्देश निष्पादित हो जाते हैं, उनके परिणाम डेटा तैयार होते हैं"।
बीएमडीएफएम की मुख्य विशेषता शीर्ष स्तर पर एक पारंपरिक प्रोग्रामिंग प्रतिमान प्रदान करना है, तथाकथित पारदर्शी डेटाफ्लो शब्दार्थ। उपयोगकर्ता बीएमडीएफएम को वर्चुअल मशीन (वीएम) के रूप में समझता है, जो समानांतर में एप्लिकेशन प्रोग्राम के सभी स्टेटमेंट चलाता है, जिसमें सभी समानांतर और सिंक्रनाइज़िंग तंत्र पूरी तरह से पारदर्शी होते हैं। एप्लिकेशन प्रोग्राम के स्टेटमेंट सामान्य ऑपरेटर होते हैं, जिनमें से कोई भी थ्रेडेड प्रोग्राम सम्मिलित हो सकता है: इसमें वेरिएबल असाइनमेंट, कंडीशनल प्रोसेसिंग, लूप्स, फंक्शन कॉल्स आदि सम्मिलित हैं।
मान लीजिए कि हमारे पास नीचे दिखाया गया कोड ब्लॉक है:
(setq a (foo0 i)) # a = foo0(i);
(setq b (foo1 (+ i 1))) # b = foo1(i+1);
(setq b (++ b)) # b++;
(outf "a = %d\n" a) # printf("a = %d\n", a);
(outf "b = %d\n" b) # printf("b = %d\n", b);
पहले दो कथन स्वतंत्र हैं, इसलिए बीएमडीएफएम का डेटाफ्लो इंजन उन्हें विभिन्न प्रोसेसर या प्रोसेसर के कोर पर चला सकता है। दो अंतिम कथन समानांतर में भी चल सकते हैं लेकिन केवल "a" और "b" की गणना के बाद। डेटा प्रवाह इंजन रनटाइम पर गतिशील रूप से डेटा प्रवाह ग्राफ़ बनाने की क्षमता के कारण स्वचालित रूप से निर्भरताओं को पहचानता है। इसके अतिरिक्त, डेटाफ्लो इंजन आउटपुट स्ट्रीम को क्रमिक रूप से परिणामों को आउटपुट करने के लिए सही ढंग से आदेश देता है। इस प्रकार आउट-ऑफ़-ऑर्डर प्रोसेसिंग के बाद भी परिणाम स्वाभाविक रूप से दिखाई देंगे।
मान लीजिए कि उपरोक्त कोड खंड अब लूप में नेस्ट किया गया है:
(for i 1 1 N (progn # for (i = 1; i <= N; i++) {
(setq a (foo0 i)) # a = foo0(i);
(setq b (foo1 (+ i 1))) # b = foo1(i + 1);
(setq b (++ b)) # b++;
(outf "a = %d\n" a) # printf("a = %d\n", a);
(outf "b = %d\n" b) # printf("b = %d\n", b);
)) # }
बीएमडीएफएम का डेटाफ्लो इंजन प्रत्येक पुनरावृत्ति के लिए अद्वितीय संदर्भों के तहत चर "a" और "b" रखेगा। दरअसल, ये चरों की अलग-अलग प्रतियां हैं। एक संदर्भ चर तब तक मौजूद रहता है जब तक इसे निर्देश उपभोक्ताओं द्वारा संदर्भित नहीं किया जाता है। बाद में गैर-संदर्भित संदर्भ रनटाइम पर गार्बेज एकत्र किए जाएंगे। इसलिए, डेटाफ्लो इंजन पुनरावृत्ति और वैश्विक समानता के साथ-साथ कई पुनरावृत्तियों को एक साथ चलाने के भीतर स्थानीय समानांतरता दोनों का लाभ उठा सकता है।
आर्किटेक्चर
बीएमडीएफएम एक सुविधाजनक समांतर प्रोग्रामिंग वातावरण है और कई आर्किटेक्चर प्रतिमानों (वॉन-न्यूमैन, एसएमपी और डेटाफ्लो) के एमआईएमडी एकीकरण के कारण बहु-कोर एसएमपी के लिए एक कुशल रनटाइम इंजन है:
- सबसे पहले, यह एक हाइब्रिड डेटाफ्लो एमुलेटर है जो कमोडिटी एसएमपी पर मल्टीथ्रेडेड रूप से चल रहा है। एसएमपी एमआईएमडी सुनिश्चित करता है जबकि डेटाफ्लो अंतर्निहित समांतरता का उपयोग करता है।
- दूसरे पर, यह एक हाइब्रिड मल्टीथ्रेडेड डेटाफ्लो रनटाइम इंजन है जिसे वॉन-न्यूमैन फ्रंट-एंड वीएम द्वारा नियंत्रित किया जाता है। डेटाफ्लो रनटाइम इंजन टैग-टोकन प्रासंगिक समानांतर निर्देशों (प्रतिबंधित फोर्क-जॉइन प्रतिमान के विपरीत) को निष्पादित करता है, जबकि वॉन-न्यूमैन फ्रंट-एंड वीएम संदर्भों को आरंभ करता है और डेटाफ्लो रनटाइम इंजन को निर्देशों के मार्शल क्लस्टर के साथ फीड करता है।
- तीसरे पर, यह स्थिर और गतिशील समांतरता का एक संकर है। वॉन-न्यूमैन फ्रंट-एंड वीएम एक एप्लिकेशन को निर्देशों के समानांतर मार्शल्ड क्लस्टर में विभाजित करने की कोशिश करता है, जबकि डेटाफ्लो रनटाइम इंजन गतिशील रूप से स्थिर समानांतर विधियों को पूरा करता है।
बीएमडीएफएम समानांतर रनटाइम इंजन (पारंपरिक फोर्क-जॉइन रनटाइम लाइब्रेरी के बजाय) अनियमित अनुप्रयोगों को स्वचालित रूप से समानांतर में चलाने में सक्षम होने की भूमिका में उपयोग के लिए है। शीर्ष पर पारदर्शी डेटाफ्लो शब्दार्थ के कारण, बीएमडीएफएम अनुप्रयोग प्रोग्रामर के लिए एक सरल समानांतर तकनीक है और साथ ही, मल्टी-कोर एसएमपी कंप्यूटरों के लिए समानांतर प्रोग्रामिंग और संकलन तकनीक के लिए बहुत बेहतर है।
बीएमडीएफएम की मूल अवधारणा अंतर्निहित कमोडिटी एसएमपी हार्डवेयर पर निर्भर करती है, जो बाजार में उपलब्ध है। सामान्यतः, एसएमपी विक्रेता एक एसवीआर4/पॉज़िक्स यूनिक्स इंटरफ़ेस (लिनक्स, एचपी-यूएक्स, सनोस/सोलारिस, ट्रू64ओएसएफ1, आईआरआईएक्स, ऐक्स, बीएसडी, मैकओएस, इत्यादि) के साथ अपना स्वयं का एसएमपी ऑपरेटिंग सिस्टम (ओएस) प्रदान करते हैं। एक एसएमपी ओएस के शीर्ष पर, मल्टीथ्रेडेड डेटाफ्लो रनटाइम इंजन डेटाफ्लो मशीन का एक सॉफ्टवेयर अनुकरण करता है। इस तरह की वर्चुअल मशीन में वर्चुअल मशीन भाषा और सी के लिए पारंपरिक प्रोग्रामिंग के लिए पारदर्शी डेटाफ्लो शब्दार्थ प्रदान करने के लिए इंटरफेस हैं।
बीएमडीएफएम को कई आर्किटेक्चर सिद्धांतों के मिश्रण के रूप में बनाया गया है:
- एमआईएमडी (मल्टीपल इंस्ट्रक्शन स्ट्रीम, मल्टीपल डेटा स्ट्रीम), जो कमोडिटी एसएमपी द्वारा कायम है।
- डेटाफ्लो एमुलेशन द्वारा अंतर्निहित समानांतर निष्पादन सुनिश्चित किया जाता है।
- वॉन-न्यूमैन कम्प्यूटेशनल सिद्धांत फ्रंट-एंड कंट्रोल वर्चुअल मशीन को लागू करने के लिए अच्छा है।
एप्लिकेशन प्रोग्राम (इनपुट अनुक्रमिक प्रोग्राम) को तीन चरणों में संसाधित किया जाता है: प्रारंभिक कोड पुनर्गठन (कोड पुनर्गठित), बयानों का स्थिर निर्धारण (स्थिर अनुसूचक) और संकलन/लोडिंग (संकलक, लोडर)। स्टैटिक शेड्यूलिंग चरणों के बाद का आउटपुट एक मल्टीपल क्लस्टर फ्लो होता है जो मल्टीथ्रेडेड इंजन को इंटरफ़ेस के माध्यम से इस तरह से डिज़ाइन किया जाता है कि अड़चनों से बचा जा सके। मल्टीपल क्लस्टर्स फ्लो को एक संकलित इनपुट प्रोग्राम के रूप में माना जा सकता है जो मार्शल्ड क्लस्टर्स में विभाजित होता है, जिसमें सभी पते हल किए जाते हैं और संदर्भ जानकारी के साथ विस्तारित होते हैं। मार्शल्ड क्लस्टर्स में विभाजित करने से उन्हें बहु-थ्रेडेड रूप से लोड करने की अनुमति मिलती है। प्रसंग की जानकारी पुनरावृत्तियों को समानांतर में संसाधित करने देती है। आउट-ऑफ़-ऑर्डर प्रोसेसिंग के बाद श्रोता थ्रेड आउटपुट स्ट्रीम का आदेश देता है।
बीएमडीएफएम डायनेमिक शेड्यूलिंग सबसिस्टम टैग-टोकन डेटाफ्लो मशीन का एक कुशल एसएमपी एमुलेटर है। साझा मेमोरी पूल को तीन मुख्य भागों में विभाजित किया गया है: इनपुट/आउटपुट रिंग बफर पोर्ट (आईओआरबीपी), डेटा बफर (डीबी), और ऑपरेशन कतार (ओक्यू)। फ्रंट-एंड कंट्रोल वर्चुअल मशीन एक इनपुट एप्लिकेशन प्रोग्राम को स्टेटिक रूप से शेड्यूल करती है और आईओआरबीपी में इनपुट प्रोग्राम के क्लस्टर्ड निर्देश और डेटा डालती है। रिंग बफ़र सर्विस प्रोसेस (आईओआरबीपी प्रोक) डेटा को डीबी में और निर्देश को ओक्यू में ले जाता है। ऑपरेशन कतार सेवा प्रक्रियाएँ (ओक्यू प्रोक) निर्देशों को निष्पादन के लिए तैयार के रूप में टैग करती हैं यदि आवश्यक ऑपरेंड का डेटा पहुँच योग्य हो। निष्पादन प्रक्रियाएं (सीपीयू प्रोसी) निर्देशों को निष्पादित करती हैं, जिन्हें डीबी या आईओआरबीपी में तैयार और आउटपुट गणना किए गए डेटा के रूप में टैग किया जाता है। इसके अतिरिक्त, आईओआरबीपी प्रोक और ओक्यू प्रोक संदर्भों को संसाधित करने के बाद मेमोरी को मुक्त करने के लिए जिम्मेदार हैं। संदर्भ एक विशेष विशिष्ट पहचानकर्ता है जो टैग किए गए टोकन डेटाफ्लो आर्किटेक्चर के अनुसार विभिन्न पुनरावृत्ति निकायों के भीतर डेटा की एक प्रति का प्रतिनिधित्व करता है। यह गतिशील अनुसूचक को समानांतर में कई पुनरावृत्तियों को संभालने की अनुमति देता है।
एक एसएमपी ओएस के तहत चल रही प्रक्रियाएं सभी उपलब्ध वास्तविक मशीन प्रोसेसर और प्रोसेसर कोर का प्रयोग कर लेंगी। कई प्रक्रियाओं को समवर्ती रूप से एक ही डेटा तक पहुंचने की अनुमति देने के लिए, बीएमडीएफएम डायनेमिक शेड्यूलर एसवीआर4 / पॉज़िक्स सेमाफोर संचालन के माध्यम से साझा मेमोरी पूल में ऑब्जेक्ट को लॉक करता है। लॉकिंग नीति एकाधिक रीड-ओनली एक्सेस और संशोधन के लिए विशेष एक्सेस प्रदान करती है।
समर्थित प्लेटफॉर्म
एएनएसआई सी और पॉज़िक्स का समर्थन करने वाली प्रत्येक मशीन; यूनिक्स सिस्टम वी (एसवीआर4) बीएमडीएफएम चला सकता है।
बीएमडीएफएम को पूर्ण बहु-थ्रेडेड संस्करणों के लिए प्रदान किया गया है:
- x86: लिनक्स/32, फ्रीबीएसडी/32, ओपनबीएसडी/32, नेटबीएसडी/32, मैकओएस/32, सनोस/32, यूनिक्सवेयर/32, मिनिक्स/32, एंड्रॉइड/32, विन-सिगविन/32, विन-विन/32, विन-एसएफयू-एसयूए/32;
- x86-64: लाइनक्स/64, फ्रीबीएसडी/64, ओपनबीएसडी/64, नेटबीएसडी/64, मैकओएस/64, सनओएस/64, एंड्रॉइड/64, विन-सिगविन/64;
- वैक्स: अल्ट्रिक्स/32;
- डीईसी अल्फा: ट्रू64ओएसएफ1/64, लिनक्स/64, फ्रीबीएसडी/64, ओपनबीएसडी/64;
- आईए-64: एचपी-यूएक्स/32, एचपी-यूएक्स/64, लाइनक्स/64, फ्रीबीएसडी/64;
- झियोन फी: लिनक्स/64;
- एमसीएसटी-एल्ब्रस: लिनक्स/32, लिनक्स/64;
- पीए-आरआईएससी: एचपी-यूएक्स/32, एचपी-यूएक्स/64, लाइनेक्स/32;
- स्पार्क: सनओएस/32, सनओएस/64, लिनक्स/32, लिनक्स/64, फ्रीबीएसडी/64, ओपनबीएसडी/64;
- एमआईपीएस: आईआरआईएक्स/32, आईआरआईएक्स/64, लिनक्स/32, लिनक्स/64;
- एमआईपीसेल: लिनक्स/32, लिनक्स/64, एंड्रॉइड/32, एंड्रॉइड/64;
- पावरपीसी: एआईक्स/32, एआईक्स/64, मैकओएस/32, मैकओएस/64, लिनक्स/32, लिनक्स/64, फ्रीबीएसडी/32, फ्रीबीएसडी/64;
- पावरपीसीएल: लिनक्स/32, लिनक्स/64;
- एस/390: लिनक्स/32, लिनक्स/64;
- एम 68000: लिनक्स/32;
- एआरएम: लिनक्स / 32, लिनक्स / 64, फ्रीबीएसडी / 64, एंड्रॉइड / 32, एंड्रॉइड / 64, मैकओएस / 64;
- एमआईपीएस आर्किटेक्चर: लिनक्स/64;
- आरआईएससी-वी: लिनक्स/32, लिनक्स/64;
- और x86 के लिए एक सीमित सिंगल-थ्रेडेड संस्करण: विन/32।
यह भी देखें
- डेटाफ्लो
- समानांतर कंप्यूटिंग
- सममित मल्टीप्रोसेसिंग
संदर्भ
- ↑ Pochayevets, Oleksandr (2006). BMDFM: A Hybrid Dataflow Runtime Parallelization Environment for Shared Memory Multiprocessors (Thesis). Technical University of Munich (TUM), Germany (published February 25, 2006).
- ↑ "urn:nbn:de:bvb:91-diss20060316-1748151609". URN NBN Resolver for Germany and Switzerland. March 22, 2006.
