बाइनरी मॉड्यूलर डेटाफ्लो मशीन
बाइनरी मॉड्यूलर डेटाफ्लो मशीन (बीएमडीएफएम) एक सॉफ्टवेयर पैकेज है जो एकल अनुप्रयोगों के निष्पादन को गति देने के लिए कई प्रोसेसरों का उपयोग करके साझा मेमोरी सिमेट्रिक मल्टीप्रोसेसिंग (एसएमपी) कंप्यूटरों पर समानांतर में एक एप्लिकेशन चलाने में सक्षम बनाता है। बीएमडीएफएम स्वचालित रूप से पूर्व अनुक्रमिक कार्यक्रम से प्राप्त डेटाफ्लो निर्देश अनुक्रमों के स्थिर और मुख्य रूप से गतिशील शेड्यूलिंग के कारण समांतरता को पहचानता है और इसका एक्सप्लॉइट्स करता है।
बीएमडीएफएम डायनेमिक शेड्यूलिंग सबसिस्टम अनुप्रयोगों के लिए पारदर्शी डेटाफ्लो सिमेंटिक्स प्रदान करने के लिए एक टैग-टोकन डेटाफ्लो मशीन का एक सममित मल्टीप्रोसेसिंग (एसएमपी) अनुकरण करता है। समानांतर निष्पादन के लिए कोई निर्देश आवश्यक नहीं है।
पृष्ठभूमि
वर्तमान समानांतर साझा मेमोरी एसएमपी जटिल मशीनें हैं, जहां उच्च प्रदर्शन प्राप्त करने के लिए बड़ी संख्या में वास्तु संबंधी पहलुओं को एक साथ संबोधित किया जाना चाहिए। तकनीकी कंप्यूटिंग के लिए हालिया कमोडिटी एसएमपी मशीनों में कई कसकर युग्मित कोर हो सकते हैं (अच्छे उदाहरण हैं इंटेल (कोर या एक्सॉन) या आईबीएम (पावर) से मल्टी-कोर प्रोसेसर पर आधारित एसएमपी मशीनें)। कंप्यूटर निर्माताओं की घोषणाओं के मुताबिक प्रत्येक एसएमपी नोड में कोर की संख्या हर कुछ वर्षों में दोगुनी करने की योजना है।
मल्टी-कोर प्रोसेसर का उद्देश्य सॉफ्टवेयर द्वारा पहचाने गए थ्रेड-लेवल समानता की सुविधा उठाना है। इसलिए, सबसे चुनौतीपूर्ण कार्य समानांतर में एक एप्लिकेशन प्रोग्राम को प्रोसेस करने के लिए मल्टी-कोर प्रोसेसर की शक्ति का उपयोग करने का एक प्रभावी तरीका खोजना है। फोर्क-जॉइन रनटाइम लाइब्रेरी के साथ स्थिर समांतरता के मौजूदा ओपनएमपी प्रतिमान लूप-गहन नियमित सरणी-आधारित कंप्यूटेशंस के लिए बहुत अच्छी तरह से काम करता है, हालांकि, संकलन-समय समांतरता विधियां सामान्य रूप से कमजोर हैं और अनियमित अनुप्रयोगों के लिए लगभग अनुपयुक्त हैं:
- ऐसे कई ऑपरेशन हैं जो एक गैर-नियतात्मक समय लेते हैं जिससे यह जानना मुश्किल हो जाता है कि डेटा के कुछ भाग कब उपलब्ध होंगे।
- बहु-स्तरीय कैश के साथ मेमोरी पदानुक्रम में अप्रत्याशित मेमोरी एक्सेस विलंबता होती है।
- एक बहु-उपयोगकर्ता मोड अन्य लोगों के कोड संसाधनों का उपयोग कर सकते हैं या गणना के एक हिस्से को इस तरह से धीमा कर सकते हैं कि संकलक इसका हिसाब नहीं लगा सकता।
- संकलन-समय अंतर-प्रक्रियात्मक और क्रॉस-सशर्त अनुकूलन कठिन हैं (अक्सर असंभव) क्योंकि संकलक यह पता नहीं लगा सकते हैं कि सशर्त किस तरह से जाएगा या फ़ंक्शन कॉल में अनुकूलन नहीं कर सकता है।
बीएमडीएफएम का पारदर्शी डेटाफ्लो सिमेंटिक्स
BMDFM तकनीक मुख्य रूप से एक एप्लिकेशन प्रोग्राम की समानता का फायदा उठाने के लिए डायनेमिक शेड्यूलिंग का उपयोग करती है, इस प्रकार, BMDFM संकलन-समय विधियों के उल्लिखित नुकसान से बचा जाता है।[1][2] BMDFM मल्टी-कोर SMP के लिए एक समानांतर प्रोग्रामिंग वातावरण है जो प्रदान करता है:
- पारंपरिक प्रोग्रामिंग प्रतिमान समानांतर निष्पादन के लिए किसी निर्देश की आवश्यकता नहीं है।
- सिस्टम में स्वचालित रूप से सभी उपलब्ध मल्टी-कोर प्रोसेसर का उपयोग करके प्राकृतिक और लोड संतुलित तरीके से समानांतरता का पारदर्शी (अंतर्निहित) शोषण।
बीएमडीएफएम ज्ञात आर्किटेक्चरल सिद्धांतों के फायदों को एक सिंगल हाइब्रिड आर्किटेक्चर में जोड़ता है जो नगण्य गतिशील शेड्यूलिंग ओवरहेड और कोई बाधा नहीं होने वाले अनुप्रयोगों के अंतर्निहित समांतरता का फायदा उठाने में सक्षम है। मुख्य रूप से, बुनियादी डेटा प्रवाह सिद्धांत का उपयोग किया जाता है। डेटाफ्लो सिद्धांत कहता है: जैसे ही इसके सभी तर्क तैयार हो जाते हैं, एक निर्देश या फ़ंक्शन निष्पादित किया जा सकता है। एक डेटाफ्लो मशीन रनटाइम पर डेटा के प्रत्येक भाग के लिए टैग का प्रबंधन करती है। डेटा की गणना होने पर डेटा को तैयार टैग के साथ चिह्नित किया जाता है। तैयार तर्कों के साथ निर्देश उनके परिणाम डेटा को तैयार चिह्नित करते हुए निष्पादित हो जाते हैं।
बीएमडीएफएम की मुख्य विशेषता शीर्ष स्तर पर एक पारंपरिक प्रोग्रामिंग प्रतिमान प्रदान करना है, जिसे तथाकथित पारदर्शी डेटाफ्लो सिमेंटिक्स कहा जाता है। एक उपयोगकर्ता BMDFM को एक आभासी मशीन (VM) के रूप में समझता है, जो एक एप्लिकेशन प्रोग्राम के सभी स्टेटमेंट को समानांतर में चलाता है, जिसमें सभी समानांतर और सिंक्रनाइज़िंग तंत्र पूरी तरह से पारदर्शी होते हैं। एक एप्लिकेशन प्रोग्राम के स्टेटमेंट सामान्य ऑपरेटर होते हैं, जिनमें से कोई भी थ्रेडेड प्रोग्राम शामिल हो सकता है: इसमें वेरिएबल असाइनमेंट, कंडीशनल प्रोसेसिंग, लूप, फंक्शन कॉल आदि शामिल हैं।
मान लीजिए कि हमारे पास नीचे दिखाया गया कोड खंड है:
(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);
पहले दो बयान स्वतंत्र हैं, इसलिए बीएमडीएफएम का डेटाफ्लो इंजन उन्हें विभिन्न प्रोसेसर या प्रोसेसर के कोर पर चला सकता है। अंतिम दो बयान समानांतर में भी चल सकते हैं लेकिन ए और बी की गणना के बाद ही। डेटाफ्लो इंजन रनटाइम पर गतिशील रूप से डेटाफ्लो ग्राफ बनाने की क्षमता के कारण निर्भरता को स्वचालित रूप से पहचानता है। इसके अतिरिक्त, डेटाफ्लो इंजन आउटपुट स्ट्रीम को अनुक्रमिक रूप से परिणाम आउटपुट करने के लिए सही ढंग से आदेश देता है। इस प्रकार आउट-ऑफ-ऑर्डर प्रोसेसिंग के बाद भी परिणाम प्राकृतिक तरीके से दिखाई देंगे।
मान लीजिए कि उपरोक्त कोड खंड अब लूप में नेस्टेड है:
(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);
)) # }
BMDFM का डेटाफ्लो इंजन प्रत्येक पुनरावृत्ति के लिए चर a और b को अद्वितीय संदर्भों में रखेगा। दरअसल, ये वेरिएबल्स की अलग-अलग कॉपी हैं। एक संदर्भ चर तब तक मौजूद रहता है जब तक कि इसे निर्देश उपभोक्ताओं द्वारा संदर्भित नहीं किया जाता है। बाद में गैर-संदर्भित संदर्भ रनटाइम पर कचरा एकत्र किए जाएंगे। इसलिए, डेटाफ्लो इंजन पुनरावृत्ति और वैश्विक समानता के साथ-साथ एक साथ कई पुनरावृत्तियों को चलाने के भीतर स्थानीय समानता दोनों का फायदा उठा सकता है।
वास्तु
बीएमडीएफएम एक सुविधाजनक समांतर प्रोग्रामिंग वातावरण है और कई आर्किटेक्चर प्रतिमानों (वॉन-न्यूमैन, एसएमपी और डेटाफ्लो) के एमआईएमडी एकीकरण के कारण मल्टी-कोर एसएमपी के लिए एक कुशल रनटाइम इंजन है:
- सबसे पहले, यह एक हाइब्रिड डेटाफ्लो एमुलेटर है जो कमोडिटी एसएमपी पर मल्टीथ्रेडेड रूप से चल रहा है। एसएमपी एमआईएमडी सुनिश्चित करता है जबकि डेटाफ्लो अंतर्निहित समांतरता का शोषण करता है।
- दूसरे पर, यह एक हाइब्रिड मल्टीथ्रेडेड डेटाफ्लो रनटाइम इंजन है जिसे वॉन-न्यूमैन फ्रंट-एंड वीएम द्वारा नियंत्रित किया जाता है। डेटाफ्लो रनटाइम इंजन टैग-टोकन प्रासंगिक समानांतर निर्देशों (प्रतिबंधित फोर्क-जॉइन प्रतिमान के विपरीत) को निष्पादित करता है, जबकि वॉन-न्यूमैन फ्रंट-एंड वीएम संदर्भों को आरंभ करता है और डेटाफ्लो रनटाइम इंजन को निर्देशों के मार्शल क्लस्टर के साथ फीड करता है।
- तीसरे पर, यह स्थिर और गतिशील समांतरता का एक संकर है। वॉन-न्यूमैन फ्रंट-एंड वीएम एक एप्लिकेशन को निर्देशों के समानांतर मार्शल्ड क्लस्टर में विभाजित करने की कोशिश करता है, जबकि डेटाफ्लो रनटाइम इंजन गतिशील रूप से स्थिर समानांतर तरीकों को पूरा करता है।
BMDFM समानांतर रनटाइम इंजन (पारंपरिक फोर्क-जॉइन रनटाइम लाइब्रेरी के बजाय) अनियमित अनुप्रयोगों को समानांतर में स्वचालित रूप से चलाने में सक्षम होने की भूमिका में उपयोग के लिए अभिप्रेत है। शीर्ष पर पारदर्शी डेटाफ्लो शब्दार्थ के कारण, BMDFM अनुप्रयोग प्रोग्रामर के लिए एक सरल समानांतर तकनीक है और साथ ही, मल्टी-कोर SMP कंप्यूटरों के लिए एक बेहतर समानांतर प्रोग्रामिंग और संकलन तकनीक है।
बीएमडीएफएम की मूल अवधारणा अंतर्निहित कमोडिटी एसएमपी हार्डवेयर पर निर्भर करती है, जो बाजार में उपलब्ध है। आम तौर पर, SMP विक्रेता SVR4/POSIX UNIX इंटरफ़ेस (Linux, HP-UX, SunOS/Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS, आदि) के साथ अपना स्वयं का SMP ऑपरेटिंग सिस्टम (OS) प्रदान करते हैं। SMP OS के शीर्ष पर, मल्टीथ्रेडेड डेटाफ्लो रनटाइम इंजन डेटाफ्लो मशीन का एक सॉफ्टवेयर एमुलेशन करता है। इस तरह की वर्चुअल मशीन में वर्चुअल मशीन लैंग्वेज और सी के लिए पारंपरिक प्रोग्रामिंग के लिए पारदर्शी डेटाफ्लो शब्दार्थ प्रदान करने वाले इंटरफेस होते हैं।
बीएमडीएफएम कई वास्तुशिल्प सिद्धांतों के एक संकर के रूप में बनाया गया है:
- MIMD (मल्टीपल इंस्ट्रक्शन स्ट्रीम, मल्टीपल डेटा स्ट्रीम), जो कमोडिटी एसएमपी द्वारा कायम है।
- डेटाफ्लो एमुलेशन द्वारा अंतर्निहित समानांतर निष्पादन सुनिश्चित किया जाता है।
- फ्रंट-एंड कंट्रोल वर्चुअल मशीन को लागू करने के लिए वॉन-न्यूमैन कम्प्यूटेशनल सिद्धांत अच्छा है।
एक एप्लिकेशन प्रोग्राम (इनपुट अनुक्रमिक प्रोग्राम) को तीन चरणों में संसाधित किया जाता है: प्रारंभिक कोड पुनर्गठन (कोड पुनर्गठित), बयानों का स्थिर निर्धारण (स्थैतिक अनुसूचक) और संकलन/लोडिंग (कंपाइलर, लोडर)। स्टैटिक शेड्यूलिंग चरणों के बाद आउटपुट एक मल्टीपल क्लस्टर फ्लो होता है जो मल्टीथ्रेडेड इंजन को बाधाओं से बचने के लिए डिज़ाइन किए गए इंटरफ़ेस के माध्यम से फीड करता है। मल्टीपल क्लस्टर्स फ्लो को एक संकलित इनपुट प्रोग्राम के रूप में माना जा सकता है जो मार्शल्ड क्लस्टर्स में विभाजित होता है, जिसमें सभी पतों को हल किया जाता है और संदर्भ जानकारी के साथ विस्तारित किया जाता है। मार्शल्ड क्लस्टर्स में विभाजित करने से उन्हें मल्टीथ्रेडेड रूप से लोड किया जा सकता है। संदर्भ जानकारी पुनरावृत्तियों को समानांतर में संसाधित करने देती है। श्रोता थ्रेड आउट-ऑफ-ऑर्डर प्रोसेसिंग के बाद आउटपुट स्ट्रीम का आदेश देता है।
बीएमडीएफएम डायनेमिक शेड्यूलिंग सबसिस्टम टैग-टोकन डेटाफ्लो मशीन का एक कुशल एसएमपी एमुलेटर है। साझा मेमोरी पूल को तीन मुख्य भागों में बांटा गया है: इनपुट/आउटपुट रिंग बफर पोर्ट (IORBP), डेटा बफर (DB), और ऑपरेशन क्यू (OQ)। फ्रंट-एंड कंट्रोल वर्चुअल मशीन एक इनपुट एप्लिकेशन प्रोग्राम को स्थिर रूप से शेड्यूल करती है और IORBP में इनपुट प्रोग्राम के क्लस्टर निर्देश और डेटा डालती है। रिंग बफर सर्विस प्रोसेस (IORBP PROC) डेटा को DB में और निर्देशों को OQ में ले जाता है। ऑपरेशन कतार सेवा प्रक्रियाएँ (OQ PROC) निर्देशों को निष्पादन के लिए तैयार के रूप में टैग करती हैं यदि आवश्यक ऑपरेंड का डेटा सुलभ है। निष्पादन प्रक्रियाएं (CPU PROC) निर्देशों को निष्पादित करती हैं, जिन्हें DB या IORBP में तैयार और आउटपुट कंप्यूटेड डेटा के रूप में टैग किया जाता है। इसके अतिरिक्त, IORBP PROC और OQ PROC संदर्भों के संसाधित होने के बाद स्मृति को मुक्त करने के लिए जिम्मेदार हैं। संदर्भ एक विशेष अद्वितीय पहचानकर्ता है जो टैग किए गए टोकन डेटाफ्लो आर्किटेक्चर के अनुसार विभिन्न पुनरावृति निकायों के भीतर डेटा की एक प्रति का प्रतिनिधित्व करता है। यह डायनेमिक शेड्यूलर को समानांतर में कई पुनरावृत्तियों को संभालने की अनुमति देता है।
एसएमपी ओएस के तहत चलने वाली प्रक्रियाएं सभी उपलब्ध वास्तविक मशीन प्रोसेसर और प्रोसेसर कोर पर कब्जा कर लेंगी। एक ही डेटा को एक साथ एक्सेस करने वाली कई प्रक्रियाओं को अनुमति देने के लिए, BMDFM डायनेमिक शेड्यूलर SVR4/POSIX सेमाफोर ऑपरेशंस के माध्यम से साझा मेमोरी पूल में ऑब्जेक्ट को लॉक कर देता है। लॉकिंग पॉलिसी मल्टीपल रीड-ओनली एक्सेस और संशोधन के लिए एक्सक्लूसिव एक्सेस प्रदान करती है।
समर्थित प्लेटफॉर्म
एएनएसआई सी और पॉज़िक्स का समर्थन करने वाली प्रत्येक मशीन; UNIX सिस्टम V (SVR4) BMDFM चला सकता है।
बीएमडीएफएम को पूर्ण बहु-थ्रेडेड संस्करणों के लिए प्रदान किया गया है:
- x86: Linux/32, FreeBSD/32, OpenBSD/32, NetBSD/32, MacOS/32, SunOS/32, UnixWare/32, Minix/32, Android/32, Win-Cygwin/32, Win-UWIN/32 , विन-एसएफयू-एसयूए/32;
- x86-64: Linux/64, FreeBSD/64, OpenBSD/64, NetBSD/64, MacOS/64, SunOS/64, Android/64, Win-Cygwin/64;
- वैक्स: अल्ट्रिक्स/32;
- DEC अल्फा: Tru64OSF1/64, Linux/64, FreeBSD/64, OpenBSD/64;
- IA-64: HP-UX/32, HP-UX/64, Linux/64, FreeBSD/64;
- झियोन फी: लिनक्स/64;
- एल्ब्रस 2000|एमसीएसटी-एल्ब्रस: लिनक्स/32, लिनक्स/64;
- PA-RISC: HP-UX/32, HP-UX/64, Linux/32;
- स्पार्क: SunOS/32, SunOS/64, Linux/32, Linux/64, FreeBSD/64, OpenBSD/64;
- MIPS आर्किटेक्चर: IRIX/32, IRIX/64, Linux/32, Linux/64;
- MIPS आर्किटेक्चर: Linux/32, Linux/64, Android/32, Android/64;
- पावरपीसी: एआईक्स/32, एआईक्स/64, मैकओएस/32, मैकओएस/64, लिनक्स/32, लिनक्स/64, फ्रीबीएसडी/32, फ्रीबीएसडी/64;
- पावरपीसीएल: लिनक्स/32, लिनक्स/64;
- एस/390: लिनक्स/32, लिनक्स/64;
- M68000: Linux/32;
- ARM आर्किटेक्चर: Linux/32, Linux/64, FreeBSD/64, Android/32, Android/64, MacOS/64;
- एमआईपीएस आर्किटेक्चर: लिनक्स/64;
- RISC-वी ी: लिनक्स/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.
