شبکه‌های اتصال چند مرحله‌ای

شبکه‌های اتصال چند مرحله‌ای ( MINs ) دسته ای از شبکه‌های کامپیوتری پرسرعت می باشند که عموما از عناصر پردازشی (PE) در یک انتهای شبکه و عناصر حافظه (MEs) در انتهای دیگر تشکیل شده‌اند که به وسیله عناصر سوئیچینگ (SE) به هم متصل می‌شوند. عناصر کلیدزنی معمولاً به صورت مرحله‌ای به یکدیگر متصل می‌شوند، از این رو اینگونه نام گذاری شده اند.

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

پس زمینه

شبکه های ارتباط متقابل برای متصل سازی گره ها، که در آن گره ها می توانند یک پردازنده تنها یا گروهی از پردازنده ها باشند، به بقیه گره ها استفاده می شوند.

شبکه های به هم متصل را می توان با توجه به توپولوژی آنها در دسته های مختلف طبقه بندی کرد. توپولوژی الگویی می باشد که در آن یک گره به دیگر گره ها متصل می شود.

دو دسته توپولوژی اصلی وجود دارد: استاتیک و پویا.

شبکه های به هم متصل استاتیک به صورت سیم کشی سخت هستند و نمی توانند پیکربندی خود را تغییر دهند. یک اتصال استاتیک منظم عموما در شبکه های کوچکی که از زوج گره های آزاد تشکیل شده اند استفاده می شود. ساختار منظم نشان می دهد که گره ها در اشکالی خاص مرتب شده اند و این اشکال در سراسر شبکه حفظ می شوند.

مثال هایی از شبکه به هم متصل منظم استاتیک عبارتند از:

• شبکه کاملا متصل

  

  شبکه کاملا متصل

  در یک شبکه مش، چندین گره به یکدیگر متصل شده اند. هر گره در شبکه به گره دیگری در شبکه متصل است. این چیدمان امکان ارتباط مناسب داده ها بین گره ها را فراهم می کند. اما، به دلیل افزایش تعداد اتصالات گره، هزینه های ارتباطی زیاد است.
• باس مشترک

  

  شبکه باس مشترک

  توپولوژی این شبکه شامل اتصال گره ها با یکدیگر از طریق یک گذرگاه است. هر گره با استفاده از گذرگاه با گره دیگر ارتباط برقرار می کند. استفاده از گذرگاه اطمینان می دهد که هیچ داده ای به گره اشتباه ارسال نمی شود. اما، ترافیک گذرگاه یک پارامتر مهم است که می تواند سیستم را تحت تاثیر قرار دهد.
• حلقه

  

  شبکه حلقه

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

  

  شبکه درختی

  این توپولوژی شامل اتصال گره ها برای تشکیل یک درخت است. گره ها به هم متصل می شوند تا خوشه ها را تشکیل دهند و خوشه ها نیز به هم متصل می شوند تا درخت را تشکیل دهند. این روش باعث افزایش پیچیدگی در شبکه می شود.
• هایپر مکعب

  

  هایپر مکعب 4*4

  این توپولوژی از اتصال گره ها برای تشکیل مکعب تشکیل شده است. همچنین گره ها به گره های دیگر مکعب ها نیز متصل می شوند.
• پروانه

  

  شبکه پروانه

  این یکی از پیچیده ترین اتصالات گره ها است. همانطور که شکل نشان می دهد، گره ها از با توجه به رتبه بندی به هم متصل و در قالب یک ماتریس مرتب شده اند.

در شبکه های متصل پویا، گره ها به وسیله ی آرایه ای از عناصر ساده کلیدزنی به هم متصل هستند. ^[1]ین اتصال را به وسیله الگوریتم های مسیریابی می توان تغییر داد، به طوری که مسیر یک گره به دیگر گره ها را عوض کرد. اتصالات پویا را می توان به صورت زیر دسته بندی کرد:

• شبکه اتصال تک مرحله ای
• شبکه اتصال چند مرحله ای
• اتصالات سوئیچ کراس بار

اتصالات کلید ماتریسی

در کلید ماتریسی یک مسیر اختصاصی از یک پردازنده به پردازنده های دیگر وجود دارد. بنابراین، اگر n ورودی و m خروجی وجود داشته باشد، ما به تعداد حاصل ضرب n و m کلید نیاز خواهیم داشت تا یک ماتریس را تعیین کنیم.

اگر تعداد خروجی ها افزایش یابد، تعداد کلید ها با ضریب n افزایش می یابد. این افزایش کلیدها برای شبکه های بزرگ می تواند مشکل ساز شود.

شبکه ماتریسی

جایگزینی برای این طرح تغییر مرحله ای است.

شبکه اتصال تک مرحله ای

در یک شبکه اتصال تک مرحله ای، گره های ورودی با یک مرحله که شامل کلیدها می باشد، به خروجی متصل می شوند.

شکل زیر شبکه 8*8 تک مرحله ای که شامل کلیدها می باشد را با استفاده از تبادل شافل نشان می دهد.

شبکه تک مرحله ای 8*8

همانطور که قابل مشاهده است، از یک ترکیب، همه ورودی ها نمی توانند به همه خروجی ها متصل شوند. برای اتصال همه ورودی‌ها به همه خروجی‌ها، چندین بار ترکیب نیاز است.

شبکه اتصال چند مرحله ای

یک شبکه اتصال چند مرحله ای از کلید های چند مرحله ای آبشاری تشکیل می شود. این کلید ها می توانند از الگوریتم مسیریابی خود یا الگوریتم کنترل شده توسط یک هدایت کننده متمرکز استفاده کنند تا یک شبکه کاملاً به هم پیوسته را ایجاد کنند.

شبکه های متصل چندمرحله ای را می توان به سه دسته طبقه تقسیم بندی کرد:

1. غیر مسدود: یک شبکه غیر مسدود می تواند هر ورودی غیرفعال را به هر خروجی غیرفعال متصل کند، صرف نظر از اتصالاتی که قبلاً در سراسر شبکه برقرار شده است. شبکه ماتریسی نمونه ای از این نوع شبکه است.
2. غیرمسدود قابل تنظیم مجدد: این نوع شبکه می تواند با تنظیم مجدد اتصالات موجود خود، تمامی ارتباطات ممکن را بین ورودی ها و خروجی ها برقرار کند.
3. مسدود کردن: این نوع شبکه نمی تواند تمام ارتباطات ممکن بین ورودی ها و خروجی ها را برقرار کند. علت این است که اتصال بین یک ورودی آزاد به یک خروجی آزاد دیگر توسط یک اتصال موجود در شبکه مسدود می شود.

تعداد عناصر کلیدزنی مورد نیاز برای ایجاد یک شبکه غیر مسدود بسیار زیاد است و پس از آن شبکه غیرمسدود قابل تنظیم مجدد قرار دارد. مسدود کردن شبکه از حداقل عناصر کلیدزنی استفاده می کند.

مثال ها

شبکه های متصل چند مرحله ای انواع مختلفی دارند.

شبکه امگا

شبکه امگا

یک شبکه امگا از چند مرحله عناصر کلیدزنی 2*2 تشکیل شده است. هر ورودی با یک اتصال اختصاصی به یک خروجی متصل شده است. یک شبکه امگا N*N، تعداد log(N) مراحل و تعداد N/2 عناصر کلیدزنی در هر مرحله برای جابجایی کامل بین مراحل دارد. بنابراین شبکه دارای پیچیدگی (N log(N)) است. هر عنصر کلیدزنی می تواند الگوریتم کلیدزنی مخصوص خود را استفاده کند. یک شبکه امگا 8*8 را در نظر بگیرید. به تعداد 40320=!8 نگاشت یک به یک ورودی به خروجی خواهد بود. 12 عنصر کلیدزنی برای جایگشت کل که تعداد آن 4096=12^2 می باشد، وجود دارد. بنابراین، این شبکه یک شبکه مسدود کننده است.

شبکه clos

شبکه clos

یک شبکه Clos دارای 3 مرحله برای انتقال از N ورودی به N خروجی می باشد. مرحله اول به تعداد r=N/n کلیدهای متقاطع دارد و سایز هر کلید n*m است. مرحله دوم کلیدهای m با سایز r*r و در مرحله آخر کلیدهای r با سایز m*n هستند. اگر m >= 2n-1 باشد،شبکه clos، یک شبکه کاملا غیرمسدود خواهد بود. تعداد اتصالات این شبکه بیشتر از شبکه امگا و بسیار کمتر از شبکه crossbar است.

شبکه Beneš

شبکه Benes

شبکه Beneš یک شبکه غیر مسدود قابل تنظیم مجدد می باشد که از شبکه Clos با مقداردهی اولیه n = m = 2 به دست آمده است. در این شبکه(2log(N) - 1) مرحله وجود دارد که هر مرحله تعداد N/2 کلید متقاطع 2*2 دارد. یک شبکه Beneš 8*8 دارای 5 مرحله عناصر کلیدزنی است و در هر مرحله 4 عنصر کلیدزنی وجود دارد. سه مرحله میانی شامل دو شبکه 4*4 Benes هستند. شبکه 4*4 Beneš، می تواند به صورت بازگشتی هر ورودی را به هر خروجی متصل کند.

منابع

1. Blake, J. T.; Trivedi, K. S. (1989-11-01). "Multistage interconnection network reliability". IEEE Transactions on Computers. 38 (11): 1600–1604. doi:10.1109/12.42134. ISSN 0018-9340.

منابع