پیش‌نویس:شبکه پروانه‌ای

شبکه پروانه‌ای تکنیکیست که برای اتصال چندین کامپیوتر در یک شبکه پرسرعت استفاده می شود. این شکل از توپولوژی شبکه چند مرحله ای اتصال متقابل می تواند برای اتصال راس های مختلف در یک سیستم چند پردازنده ای استفاده شود. به سه دلیل شبکه متصل یک سیستم چند پردازنده ای با حافظه مشترک باید بر خلاف دیگر سیستم های شبکه مانند شبکه های محلی (LAN) یا اینترنت ^[۱] تاخیر کم و پهنای باند بالا داشته باشد:

پیام‌ها نسبتا کوتاه هستند، زیرا بیشتر پیام‌ها درخواست‌های پروتکل هماهنگی و پاسخ‌هایی بدون داده هستند.

پیام‌ها به طور مکرر تولید می‌شوند. زیرا هر خواندن-خطا یا نوشتن-خطا، پیام‌هایی برای هر راس تولید می کند تا انسجام حفظ شود. خواندن/نوشتن خطاها زمانی اتفاق می‌افتد که داده‌های درخواستی در حافظه پنهان پردازنده وجود نداشته باشد و باید از حافظه و یا از حافظه نهان پردازنده دیگری واکشی شوند.

پیام ها بطور مکرر تولید می شوند، بنابراین پنهان کردن تاخیر ارتباطی برای پردازنده‌ها مشکل می شود.

اجزاء

اجزای اصلی یک شبکه متصل عبارتند از: ^[۲]

رئوس پردازنده، که از یک یا چند پردازنده به همراه حافظه های پنهان ، حافظه ها و کمک های ارتباطی تشکیل شده اند.
گره های سوئیچینگ ( روتر )، که کمک ارتباطی گره های پردازنده متفاوت را در یک سیستم به هم متصل می کنند. در توپولوژی های چند مرحله ای، گره های سوئیچینگ سطح بالاتر به گره های سوئیچینگ سطح پایین تر متصل می شوند، همانطور که در شکل 1 نشان داده شده است، که گره های سوئیچینگ در رتبه 0 به طور مستقیم به گره های پردازنده متصل شده اند در حالی که گره های سوئیچینگ در رتبه 1 به گره های سوئیچینگ در رتبه 0 متصلند.
پیوندها، که سیم های فیزیکی ای بین دو گره هستند و می توانند یک طرفه یا دو طرفه باشند.

این شبکه های چند مرحله ای هزینه کمتری نسبت به یک نوار متقاطع دارند، اما از نظر تداخل در دسترسی نسبت به یک گذرگاه (باس) عملکرد بهتری ارائه می دهند. نسبت گره های سوئیچینگ به گره های پردازنده در شبکه پروانه ای بیشتر از یک است. چنین توپولوژیای ، که در آن نسبت گره های سوئیچینگ به گره های پردازنده بیشتر از یک باشد را توپولوژی غیر مستقیم می گویند. ^[۳]

نام این شبکه از اتصالات بین گره ها در دو رتبه مجاور (همانطور که در شکل 1 نشان داده شده است) که شبیه یک پروانه است، گرفته شده است. ادغام رتبه های بالا و پایین در یک رتبه واحد، شبکه پروانه پیچیده ایجاد می کند. در شکل 1، اگر گره های رتبه 3 به گره های رتبه 0 مربوطه متصل شوند، آنگاه به یک شبکه پروانه ای پیچیده تبدیل می شود.

BBN Butterfly ، یک کامپیوتر موازی عظیم است که توسط بولت، برانک و نیومن در دهه 1980 ساخته شد و از شبکه اتصال پروانه ای در آن استفاده می شد. ^[۴] بعداً در سال 1990، دستگاه Cray Research Cray C90 از یک شبکه پروانه ای برای برقراری ارتباط بین 16 پردازنده و 1024 بانک حافظه خود استفاده کرد. ^[۵]

ساخت شبکه پروانه‌ای

یک شبکه پروانه ای با p تعداد گره های پردازشگر به p(log₂ p + 1) گره سوئیچینگ نیاز دارد. شکل 1 شبکه ای را با 8 گره پردازنده نشان می دهد که شامل 32 گره سوئیچینگ است. هر گره به صورت N (رتبه، شماره ستون) نشان داده شده است. به عنوان مثال، گرهی در ستون 6 در رتبه 1 به عنوان (1،6) و گرهی در ستون 2 در رتبه 0 به عنوان (0،2) نمایش داده می شود.

برای هر "i" بزرگتر از صفر، یک گره سوئیچینگ N(i,j) به N(i-1, j) و N(i-1, m) متصل می شود، که در آن، m بیت معکوس در محل i ام از j است. مثلا، گره N(1،6) را در نظر بگیرید: i برابر با 1 و j برابر با 6 است، بنابراین با معکوس کردن i امین بیت 6، m حاصل می شود.

متغیر	نمایش باینری	نمایش اعشاری
j	110	6
m	010	2

در نتیجه، گره های متصل به N(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 ارسال می شود. در شکل 2، این موضوع با تکرار گره‌های پردازنده در زیر رتبه 3 نشان داده شده است. بسته ای که از طریق پیوند منتقل می شود به شکل زیر است:

پایانه	محموله	سرآیند

سرآیند (header) حاوی مقصد پیام است که پردازنده 2 (010 به صورت باینری) است. محموله (payload) پیام M است و پایانه(trailer) حاوی جمع‌آزما (checksum) است. بنابراین، پیام واقعی ارسال شده از پردازنده 5 این است:

checksum	M	010

پس از رسیدن به یک گره سوئیچینگ، یکی از دو پیوند خروجی بر اساس مهم ترین بیت آدرس مقصد انتخاب می شود. اگر این بیت صفر باشد، پیوند سمت چپ انتخاب می شود و اگر یک باشد، پیوند سمت راست انتخاب می شود. متعاقباً، این بیت از آدرس مقصد در بسته ارسالی توسط پیوند منتخب حذف می شود. این موضوع در شکل 2 نشان داده شده است.

بسته فوق به N(0,5) می رسد. از سرآیند بسته چپ ترین بیت برای تصمیم گیری جهت حذف می شود. از آنجایی که بیت صفر است، پیوند سمت چپ N(0،5) (که به N(1،1) متصل می شود) انتخاب می شود. سرآیند جدید '10' است.
بسته جدید به N(1,1) می رسد. از سرآیند بسته چپ ترین بیت برای تصمیم گیری جهت حذف می شود. از آنجایی که بیت یک است، پیوند سمت راست N(1،1) است (که به N(2،3) متصل می شود) انتخاب می شود. سرآیند جدید '0' است.
بسته جدید به N(2,3) می رسد. از سرآیند بسته چپ ترین بیت برای تصمیم گیری جهت حذف می شود. از آنجایی که بیت صفر است، پیوند سمت چپ N(2،3) (که به N(3،2) متصل می شود) انتخاب می شود. قسمت سرآیند خالی است.
پردازنده 2 بسته ای را دریافت می کند که اکنون فقط حاوی محموله "M" و جمع‌آزما است.

پارامترهای شبکه پروانه ای

چندین پارامتر به ارزیابی توپولوژی شبکه کمک می کنند. موارد برجسته آنها که مربوط به طراحی سیستم های چند پردازنده ای در مقیاس بزرگ هستند در زیر خلاصه شده اند و توضیحی در مورد نحوه محاسبه آنها برای یک شبکه پروانه ای با 8 گره پردازنده ،مطابق با شکل 1، ارائه شده است. ^[۶]

پهنای باند دو بخشی : حداکثر پهنای باند مورد نیاز برای حفظ ارتباط بین تمام گره‌های شبکه. این را می توان به عنوان حداقل تعداد پیوندهایی که نیاز است تا سیستم به دو قسمت مساوی تقسیم شود، تفسیر کرد. به عنوان مثال، شبکه پروانه ای 8 گره‌ای را می توان با قطع کردن 4 پیوند که از وسط متقاطع هستند به دو قسمت تقسیم کرد. بنابراین پهنای باند دو بخشی این سیستم خاص 4 است. این معیار معرف تنگنای پهنای باند است که ارتباطات کلی را محدود می کند.
قطر : بدترین زمان تاخیر (بین دو گره) ممکن در سیستم. می توان آن را بر حسب پرش شبکه، یعنی تعداد پیوندهایی که یک پیام برای رسیدن به گره مقصد باید طی کند، محاسبه کرد. به نظر می رسد که در شبکه پروانه ای 8 گره‌ای، N(0.0) و N(3،7) دورترین فاصله را دارند، اما پس از بررسی دوباره، مشخص می شود که به دلیل تقارن شبکه، عبور از هر گره رتبه صفری به هر گره رتبه سومی تنها به ۳ پرش نیاز است. بنابراین قطر این سیستم 3 است.
پیوندها : تعداد کل پیوندهای مورد نیاز برای ساخت کل ساختار شبکه. تعداد پیوندها نماینده هزینه کلی و پیچیدگی اجراست. شبکه ذکر شده در شکل 1 در مجموع به 48 پیوند نیاز دارد ( 16 پیوند بین هر کدام از رتبه های 0 و 1، رتبه های 1 و 2، رتبه های 2 و 3).
درجه : پیچیدگی هر گره سوئیچینگ در شبکه. این برابر است با تعداد پیوندهای ورودی/خروجی متصل به هر گره سوئیچینگ. گره های سوئیچینگ شبکه پروانه ای دو پیوند ورودی و دو پیوند خروجی دارند، از این رو یک شبکه 4 درجه ای است.

مقایسه با سایر توپولوژی های شبکه

در این بخش شبکه پروانه ای را با شبکه های آرایه خطی، حلقه، مش دوبعدی و شبکه فرا مکعبی مقایسه می کنیم. ^[۷] آرایه خطی را می توان به عنوان یک توپولوژی مش 1 بعدی نیز در نظر گرفت. پارامترهای مربوطه در جدول ^[۸] آورده شده اند ('p' تعداد گره های پردازنده را نشان می دهد).

Network parameters
توپولوژی	قطر	پهنای باند دو بخشی	پیوندها	درجه
آرایه خطی	p-1	1	p-1	2
حلقه	p/2	2	p	2
مش دو بعدی	2(p√ - 1)	p√	2(p√ - 1)p√	4
فرامکعب	log₂(p)	p/2	log₂(p) × (p/2)	log₂(p)
پروانه	log₂(p)	2^h, h = number of nodes in a single layer	log₂(p) × 2p	4

مزایای شبکه پروانه‌ای

شبکه های پروانه ای قطر کمتری نسبت به توپولوژی های دیگر مانند آرایه خطی، حلقه‌ای و مش دوبعدی دارند. این بدان معناست که در شبکه پروانه ای، پیامی که از یک پردازنده ارسال می شود با تعداد کمتری از پرش های شبکه به مقصد می رسد.
شبکه‌های پروانه‌ای نسبت به توپولوژی‌های دیگر پهنای باند دو بخشی بالاتری دارند. این بدان معناست که در شبکه پروانه ای، برای مختل شدن ارتباط سراسری، پیوندهای بیشتری باید شکسته شوند.
برد کامپیوتری بزرگتری دارد.

معایب شبکه پروانه‌ای

شبکه‌های پروانه‌ای پیچیده‌تر و پرهزینه‌تر از توپولوژی‌های دیگر هستند، چرا‌که تعداد پیوندهای مورد نیاز برای حفظ شبکه بیشتر است.

تفاوت بین توپولوژی‌ فرامکعبی و پروانه‌ای در پیاده‌سازی آنها نهفته است. شبکه پروانه ای یک ساختار متقارن دارد که در آن تمام گره های پردازنده بین دو رتبه از یکدیگر به یک اندازه فاصله دارند، در حالی که فرا مکعبی برای یک سیستم چند پردازنده ای به دلیل امکان وجود فواصل نابرابر بین گره‌ها مناسب تر است. با مشاهده تعداد پیوندهای مورد نیاز، ممکن است اینطور به نظر برسد که فرا مکعبی در مقایسه با شبکه پروانه ای ارزان تر و ساده تر است، اما وقتی تعداد گره های پردازنده از 16 بیشتر شود، هزینه و پیچیدگی گره سوئیچینگ (به صورت درجه نمایش داده شده) شبکه پروانه ای کمتر می شود، زیرا درجه آن مستقل از تعداد گره ها است.

در نتیجه، نمی توان هیچ توپولوژی شبکه واحدی را برتر از بقیه دانست. تصمیم گیری باید بر اساس عواملی نظیر تعداد گره‌های پردازنده در سیستم، الزامات تأخیر پهنای باند، هزینه و مقیاس‌پذیری گرفته شود.

همچنین ببینید

منابع

Solihin, Yan (October 2009). Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Publishing & Consulting LLC. ISBN 978-0-9841630-0-7.

ارجاعات

↑ Solihin 2009, pp. 371–372.
↑ Solihin 2009, pp. 373–374.
↑ Leighton, F.Thomson (1992). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.
↑ T., LeBlanc; M., Scott; C., Brown (1988-01-01). Large-Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor (Report). Butterfly Project. hdl:1802/15082.
↑ Jadhav, Sunitha S (2009). Advanced Computer Architecture and Computing. Technical Publications. pp. Section 3–22. ISBN 9788184315721.
↑ 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.

[FOOTNOTESolihin2009371–372-1] Solihin 2009, pp. 371–372.

[FOOTNOTESolihin2009373–374-2] Solihin 2009, pp. 373–374.

[:0-3] Leighton, F.Thomson (1992). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.

[4] T., LeBlanc; M., Scott; C., Brown (1988-01-01). Large-Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor (Report). Butterfly Project. hdl:1802/15082.

[5] Jadhav, Sunitha S (2009). Advanced Computer Architecture and Computing. Technical Publications. pp. Section 3–22. ISBN 9788184315721.

[FOOTNOTESolihin2009377–378-6] Solihin 2009, pp. 377–378.

[7] M. Arjomand, H. Sarbazi-Azad, "Performance Evaluation of Butterfly on-Chip Network for MPSoCs", International SoC Design Conference, pp. 1–296-1-299, 2008

[FOOTNOTESolihin2009379–380-8] Solihin 2009, pp. 379–380.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]