बटरफ्लाई नेटवर्क
बटरफ्लाई नेटवर्क कई कंप्यूटर को हाई-स्पीड नेटवर्क से जोड़ने की एक तकनीक है। मल्टीस्टेज इंटरकनेक्शन नेटवर्क टोपोलॉजी (इलेक्ट्रिकल सर्किट) के रूप का उपयोग मल्टीप्रोसेसर सिस्टम में विभिन्न नोड (नेटवर्किंग) को जोड़ने के लिए किया जा सकता है। एक साझा मेमोरी मल्टीप्रोसेसर सिस्टम के लिए इंटरकनेक्ट नेटवर्क में कम लेटेंसी (अभियांत्रिकी) और उच्च बैंडविड्थ (कंप्यूटिंग) होना चाहिए, अन्य नेटवर्क सिस्टम के विपरीत, जैसे स्थानीय क्षेत्र अंतरजाल | लोकल एरिया नेटवर्क (लेन) या इंटरनेट[1] तीन कारणों से:
- संदेश अपेक्षाकृत कम होते हैं क्योंकि अधिकांश संदेश मेमोरी सुसंगतता अनुरोध और डेटा के बिना प्रतिक्रियाएँ होती हैं।
- संदेश अनेक बार उत्पन्न होते हैं क्योंकि प्रत्येक रीड-मिस या राइट-मिस सिस्टम में प्रत्येक नोड को सुसंगतता सुनिश्चित करने के लिए संदेश उत्पन्न करता है। पढ़ने/लिखने की चूक तब होती है जब अनुरोधित डेटा प्रोसेसर के कैश (कंप्यूटिंग) में नहीं होता है और इसे या तो मेमोरी से या किसी अन्य प्रोसेसर के कैश से प्राप्त किया जाना चाहिए।
- संदेश अनेक बार उत्पन्न होते हैं, इसलिए प्रोसेसर के लिए संचार विलंब को छिपाना कठिन हो जाता है।
अवयव
इंटरकनेक्ट नेटवर्क के प्रमुख घटक हैं:[2]
- प्रोसेसर नोड्स, जिसमें उनके कैश (कंप्यूटिंग), यादें और संचार सहायता के साथ एक या एक से अधिक प्रोसेसर होते हैं।
- स्विचिंग नोड्स (राउटर (कंप्यूटिंग)), जो एक सिस्टम में विभिन्न प्रोसेसर नोड्स की संचार सहायता को जोड़ता है। मल्टीस्टेज टोपोलॉजी में, उच्च स्तरीय स्विचिंग नोड्स निचले स्तर के स्विचिंग नोड्स से कनेक्ट होते हैं जैसा कि चित्र 1 में दिखाया गया है, जहां रैंक 0 में स्विचिंग नोड्स सीधे प्रोसेसर नोड्स से कनेक्ट होते हैं जबकि रैंक 1 में नोड्स को रैंक 0 में स्विचिंग नोड्स से कनेक्ट करते हैं।
- लिंक, जो दो स्विचिंग नोड्स के बीच भौतिक तार हैं। वे एक-दिशात्मक या द्वि-दिशात्मक हो सकते हैं।
इन मल्टीस्टेज नेटवर्कों की लागत मल्टीस्टेज इंटरकनेक्शन नेटवर्क#क्रॉसबार स्विच कनेक्शन्स की समानता में कम होती है, किंतु बस (कंप्यूटिंग) की समानता में कम विवाद प्राप्त करते हैं। बटरफ्लाई नेटवर्क में नोड्स को प्रोसेसर नोड्स में बदलने का अनुपात एक से अधिक है। ऐसी टोपोलॉजी, जहां स्विचिंग नोड्स और प्रोसेसर नोड्स का अनुपात एक से अधिक होता है, अप्रत्यक्ष टोपोलॉजी कहलाती है।[3]
नेटवर्क का नाम दो आसन्न रैंकों में नोड्स के बीच कनेक्शन से प्राप्त होता है (जैसा कि चित्र 1 में दिखाया गया है), जो एक बटरफ्लाई आरेख जैसा दिखता है। ऊपर और नीचे के रैंकों को एक ही रैंक में मिलाने से रैप्ड बटरफ्लाई नेटवर्क बनता है।[3] आकृति 1 में, यदि रैंक 3 नोड्स संबंधित रैंक 0 नोड्स से वापस जुड़े हुए हैं, तो यह एक लपेटा हुआ बटरफ्लाई नेटवर्क बन जाता है।
बीबीएन बटरफ्लाई, 1980 के दशक में बोल्ट, बेरानेक और न्यूमैन द्वारा निर्मित एक विशाल समानांतर कंप्यूटर , एक बटरफ्लाई इंटरकनेक्ट नेटवर्क का उपयोग करता था।[4] बाद में 1990 में, क्रे की मशीन क्रे C90 ने अपने 16 प्रोसेसर और 1024 मेमोरी बैंकों के बीच संचार करने के लिए एक बटरफ्लाई नेटवर्क का उपयोग किया |
बटरफ्लाई नेटवर्क बिल्डिंग
p प्रोसेसर नोड्स वाले बटरफ्लाई नेटवर्क के लिए, p(log2 p + 1) स्विचिंग नोड्स। चित्र 1 में 8 प्रोसेसर नोड्स वाला एक नेटवर्क दिखाया गया है, जिसका अर्थ है 32 स्विचिंग नोड्स। यह प्रत्येक नोड को N(रैंक, कॉलम नंबर) के रूप में दर्शाता है। उदाहरण के लिए, रैंक 1 में कॉलम 6 पर नोड को (1,6) के रूप में दर्शाया गया है और रैंक 0 में कॉलम 2 पर नोड को (0,2) के रूप में दर्शाया गया है।[3]
शून्य से अधिक किसी भी 'i' के लिए, एक स्विचिंग नोड N(i,j) N(i-1, j) और N(i-1, m) से जुड़ जाता है, जहाँ, m, j के iवें स्थान पर विपरीत सा है j का स्थान। उदाहरण के लिए, नोड N(1,6) पर विचार करें: i बराबर 1 और j बराबर 6 है, इसलिए m को 6 के iवें बिट को विपरीत करके प्राप्त किया जाता है।
| चर | बाइनरी प्रतिनिधित्व | दशमलव प्रतिनिधित्व |
|---|---|---|
| j | 110 | 6 |
| m | 010 | 2 |
नतीजतन, एन (1,6) से जुड़े नोड्स हैं:
| N(i,j) | N(i-1,j) | N(i-1,m) |
| (1,6) | (0,6) | (0,2) |
इस प्रकार, N(0,6), N(1,6), N(0,2), N(1,2) एक बटरफ्लाई पैटर्न बनाते हैं। आकृति में कई बटरफ्लाई पैटर्न उपस्थित हैं और इसलिए, इस नेटवर्क को बटरफ्लाई नेटवर्क कहा जाता है।
बटरफ्लाई नेटवर्क रूटिंग
लिपटे हुए बटरफ्लाई नेटवर्क में (जिसका अर्थ है रैंक 0 रैंक 3 के साथ विलय हो जाता है), प्रोसेसर 5 से प्रोसेसर 2 तक एक संदेश भेजा जाता है।[3] चित्र 2 में, यह रैंक 3 के नीचे प्रोसेसर नोड्स की प्रतिकृति बनाकर दिखाया गया है। लिंक पर प्रसारित नेटवर्क पैकेट इस प्रकार है:
| हैडर | पेलोड | ट्रेलर |
हैडर (कंप्यूटिंग) में संदेश का अंत होता है, जो प्रोसेसर 2 (बाइनरी में 010) है। नेटवर्क पैकेट#पेलोड संदेश है, एम और ट्रेलर (कंप्यूटिंग) में अंततः, है। इसलिए, प्रोसेसर 5 से प्रेषित वास्तविक संदेश है:
| 010 | M | अंततः |
एक स्विचिंग नोड पर पहुंचने पर, अंत पते के सबसे महत्वपूर्ण बिट के आधार पर दो आउटपुट लिंक में से एक का चयन किया जाता है। यदि वह बिट शून्य है, तो बायाँ लिंक चुना जाता है। यदि वह बिट एक है, तो सही लिंक का चयन किया जाता है। इसके बाद, चयनित लिंक के माध्यम से प्रेषित पैकेट में अंत पते से इस बिट को हटा दिया जाता है। यह चित्र 2 में दिखाया गया है।
- उपरोक्त पैकेट एन (0,5) तक पहुंचता है। पैकेट के हेडर से यह दिशा तय करने के लिए सबसे बाएं हिस्से को हटा देता है। चूँकि यह एक शून्य है, N(0,5) का बायाँ लिंक (जो N(1,1) से जुड़ता है) चयनित हो जाता है। नया हेडर '10' है।
- नया पैकेट N(1,1) तक पहुंचता है। पैकेट के हेडर से यह दिशा तय करने के लिए सबसे बाएं हिस्से को हटा देता है। चूँकि यह एक है, N(1,1) का दायाँ लिंक (जो N(2,3) से जुड़ता है) चयनित हो जाता है। नया हेडर '0' है।
- नया पैकेट एन (2,3) तक पहुंचता है। पैकेट के हेडर से यह दिशा तय करने के लिए सबसे बाएं हिस्से को हटा देता है। चूँकि यह एक शून्य है, N(2,3) का बायाँ लिंक (जो N(3,2) से जुड़ता है) चयनित हो जाता है। हेडर फ़ील्ड खाली है।
- प्रोसेसर 2 पैकेट प्राप्त करता है, जिसमें अब केवल पेलोड 'एम' और चेकसम होता है।
बटरफ्लाई नेटवर्क पैरामीटर
कई पैरामीटर नेटवर्क टोपोलॉजी का मूल्यांकन करने में सहायता करते हैं। बड़े पैमाने के मल्टी-प्रोसेसर सिस्टम को डिजाइन करने में प्रासंगिक प्रमुख नीचे दिए गए हैं और चित्र 1 में दिखाए गए अनुसार 8 प्रोसेसर नोड्स वाले बटरफ्लाई नेटवर्क के लिए उनकी गणना कैसे की जाती है, इसकी व्याख्या प्रदान की गई है।[5]
- बिसेक्शन बैंडविड्थ: नेटवर्क में सभी नोड्स के बीच संचार को बनाए रखने के लिए आवश्यक अधिकतम बैंडविड्थ। इसे उन लिंक्स की न्यूनतम संख्या के रूप में समझा जा सकता है जिन्हें सिस्टम को दो समान भागों में विभाजित करने के लिए अलग करने की आवश्यकता होती है। उदाहरण के लिए, 8 नोड बटरफ्लाई नेटवर्क को 4 लिंक काटकर दो भागों में विभाजित किया जा सकता है जो बीच में आड़े आते हैं। इस प्रकार इस विशेष प्रणाली का द्विभाजन बैंडविड्थ 4 है। यह बैंडविड्थ टोंटी (सॉफ्टवेयर) का एक प्रतिनिधि उपाय है जो समग्र संचार को प्रतिबंधित करता है।
- नेटवर्क विज्ञान # नेटवर्क का व्यास: सिस्टम में सबसे खराब स्थिति लेटेंसी (अभियांत्रिकी) (दो नोड्स के बीच) संभव है। इसकी गणना नेटवर्क हॉप्स के संदर्भ में की जा सकती है, जो अंत नोड तक पहुंचने के लिए एक संदेश को यात्रा करने वाले लिंक की संख्या है। 8 नोड बटरफ्लाई नेटवर्क में, ऐसा प्रतीत होता है कि N(0,0) और N(3,7) सबसे दूर हैं, किंतु निरीक्षण पर, यह स्पष्ट है कि नेटवर्क की सममित प्रकृति के कारण, किसी भी रैंक 0 नोड से ट्रैवर्सिंग किसी भी रैंक 3 नोड के लिए केवल 3 हॉप्स की आवश्यकता होती है। अतः इस निकाय का व्यास 3 है।
- लिंक: संपूर्ण नेटवर्क संरचना के निर्माण के लिए आवश्यक लिंक की कुल संख्या है। यह समग्र मूल्य और अनु की जटिलता का सूचक है। चित्र 1 में दिखाए गए उदाहरण नेटवर्क में कुल 48 लिंक की आवश्यकता होती है (16 लिंक प्रत्येक रैंक 0 और 1 के बीच, रैंक 1 और 2, रैंक 2 और 3)।
- नेटवर्क साइंस # औसत डिग्री: नेटवर्क में प्रत्येक राउटर की जटिलता। यह प्रत्येक स्विचिंग नोड से जुड़े इन/आउट लिंक की संख्या के बराबर है। बटरफ्लाई नेटवर्क स्विचिंग नोड्स में 2 इनपुट लिंक और 2 आउटपुट लिंक होते हैं, इसलिए यह 4-डिग्री नेटवर्क है।
अन्य नेटवर्क टोपोलॉजी के साथ समानता
यह खंड बटरफ्लाई नेटवर्क की समानता लीनियर एरे, रिंग, जाल नेटवर्किंग , 2-D मेश और हाइपरक्यूब ग्राफ नेटवर्क से करता है।[6] ध्यान दें कि लीनियर ऐरे को 1-D मेश टोपोलॉजी माना जा सकता है। प्रासंगिक पैरामीटर तालिका में संकलित हैं[7] ('पी' प्रोसेसर नोड्स की संख्या का प्रतिनिधित्व करता है)।
| टोपोलॉजी | व्यास | बिसेक्शन बैंडविड्थ | लिंक | डिग्री |
|---|---|---|---|---|
| रैखिक सरणी | p-1 | 1 | p-1 | 2 |
| रिंग | p/2 | 2 | p | 2 |
| 2-D मेश | 2(√p - 1) | √p | 2√p(√p - 1) | 4 |
| अतिविम | log2(p) | p/2 | log2(p) × (p/2) | log2(p) |
| बटरफ्लाई | log2(p) | 2^h | log2(p) × 2p | 4 |
लाभ
- बटरफ्लाई नेटवर्क का व्यास अन्य टोपोलॉजी जैसे लीनियर एरे, रिंग और 2-D मेश से कम होता है। इसका तात्पर्य है कि बटरफ्लाई नेटवर्क में, एक प्रोसेसर से भेजा गया संदेश कम संख्या में नेटवर्क हॉप्स में अपने अंत तक पहुंचेगा।
- बटरफ्लाई नेटवर्क में अन्य टोपोलॉजी की समानता में उच्च द्विभाजन बैंडविड्थ है। इसका तात्पर्य है कि बटरफ्लाई नेटवर्क में, वैश्विक संचार को रोकने के लिए अधिक संख्या में लिंक को तोड़ने की आवश्यकता होती है।
- इसमें कंप्यूटर की बड़ी रेंज है।
हानि
- नेटवर्क को बनाए रखने के लिए आवश्यक लिंक की अधिक संख्या के कारण बटरफ्लाई नेटवर्क अन्य टोपोलॉजी की समानता में अधिक जटिल और महंगा है।
हाइपरक्यूब और बटरफ्लाई के बीच का अंतर उनके कार्यान्वयन में निहित है। बटरफ्लाई नेटवर्क में एक सममित संरचना होती है जहां दो रैंकों के बीच सभी प्रोसेसर नोड्स एक दूसरे के समान दूरी पर होते हैं, जबकि हाइपरक्यूब मल्टी-प्रोसेसर सिस्टम के लिए अधिक उपयुक्त होता है जो अपने नोड्स के बीच असमान दूरी की मांग करता है। आवश्यक लिंक की संख्या को देखते हुए, यह प्रतीत हो सकता है कि हाइपरक्यूब बटरफ्लाई नेटवर्क की समानता में सस्ता और सरल है, किंतु जैसे ही प्रोसेसर नोड्स की संख्या 16 से अधिक हो जाती है, बटरफ्लाई नेटवर्क की राउटर मूल्य और जटिलता (डिग्री द्वारा प्रतिनिधित्व) कम हो जाती है हाइपरक्यूब की समानता में क्योंकि इसकी डिग्री नोड्स की संख्या से स्वतंत्र है।
अंत में, सभी परिदृश्यों के लिए कोई एकल नेटवर्क टोपोलॉजी सर्वोत्तम नहीं है। निर्णय सिस्टम में प्रोसेसर नोड्स की संख्या, बैंडविड्थ-विलंबता आवश्यकताओं, मूल्य और मापनीयता जैसे कारकों के आधार पर किया जाता है।
यह भी देखें
- समानांतर कंप्यूटिंग
- नेटवर्क टोपोलॉजी
- जाल नेटवर्किंग
स्रोत
- Solihin, Yan (October 2009). पैरेलल कंप्यूटर आर्किटेक्चर के फंडामेंटल: मल्टीचिप और मल्टीकोर सिस्टम. Solihin Publishing & Consulting LLC. ISBN 978-0-9841630-0-7.
संदर्भ
- ↑ Solihin 2009, pp. 371–372.
- ↑ Solihin 2009, pp. 373–374.
- ↑ 3.0 3.1 3.2 3.3 Leighton, F.Thomson (1992). समानांतर एल्गोरिदम और आर्किटेक्चर का परिचय: ऐरे, पेड़, हाइपरक्यूब्स. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.
- ↑ T., LeBlanc; M., Scott; C., Brown (1988-01-01). बड़े पैमाने पर समानांतर प्रोग्रामिंग: बीबीएन तितली समानांतर प्रोसेसर के साथ अनुभव (Report). Butterfly Project. hdl:1802/15082.
- ↑ Solihin 2009, pp. 377–378.
- ↑ M. Arjomand, H. Sarbazi-Azad, "Performance Evaluation of Butterfly on-Chip Network for MPSoCs", International SoC Design Conference, pp. 1–296-1-299, 2008
- ↑ Solihin 2009, pp. 379–380.
