شبکه‌های اتصال چند مرحله‌ای کیست؟ توضیح بده.
شبکه‌های اتصال چند مرحله‌ای ( MINs ) دسته ای از شبکه‌های کامپیوتری پرسرعت می باشند که عموما از عناصر پردازشی (PE) در یک انتهای شبکه و عناصر حافظه (MEs) در انتهای دیگر تشکیل شده‌اند که به وسیله عناصر سوئیچینگ (SE) به هم متصل می‌شوند. عناصر کلیدزنی معمولاً به صورت مرحله‌ای به یکدیگر متصل می‌شوند، از این رو اینگونه نام گذاری شده اند.MIN ها عموما در محاسبات با کارایی بالا یا محاسبات موازی به عنوان یک اتصال کم تاخیر (برخلاف شبکه های سوئیچینگ بسته مرسوم) استفاده می شوند، گرچه می توانند در بالای شبکه سوئیچینگ بسته پیاده سازی شوند. با وجود اینکه شبکه معمولاً برای اهداف مسیریابی استفاده می‌شود، اما می‌تواند به عنوان یک پردازشگر مشترک برای پردازنده‌های واقعی در مواردی مانند مرتب‌سازی، جابجایی چرخه ای ، همانند یک شبکه ی کامل و بی نقص و مرتب سازی بیتونیک کاربرد داشته باشد.پس زمینه.شبکه های ارتباط متقابل برای متصل سازی گره ها، که در آن گره ها می توانند یک پردازنده تنها یا گروهی از پردازنده ها باشند، به بقیه گره ها استفاده می شوند.شبکه های به هم متصل را می توان با توجه به توپولوژی آنها در دسته های مختلف طبقه بندی کرد. توپولوژی الگویی می باشد که در آن یک گره به دیگر گره ها متصل می شود.دو دسته توپولوژی اصلی وجود دارد: استاتیک و پویا.شبکه های به هم متصل استاتیک به صورت سیم کشی سخت هستند و نمی توانند پیکربندی خود را تغییر دهند. یک اتصال استاتیک منظم عموما در شبکه های کوچکی که از زوج گره های آزاد تشکیل شده اند استفاده می شود. ساختار منظم نشان می دهد که گره ها در اشکالی خاص مرتب شده اند و این اشکال در سراسر شبکه حفظ می شوند.مثال هایی از شبکه به هم متصل منظم استاتیک عبارتند از: در شبکه های متصل پویا، گره ها به وسیله ی آرایه ای از عناصر ساده کلیدزنی به هم متصل هستند. ین اتصال را به وسیله الگوریتم های مسیریابی می توان تغییر داد، به طوری که مسیر یک گره به دیگر گره ها را عوض کرد. اتصالات پویا را می توان به صورت زیر دسته بندی کرد:اتصالات کلید ماتریسی.در کلید ماتریسی یک مسیر اختصاصی از یک پردازنده به پردازنده های دیگر وجود دارد. بنابراین، اگر n ورودی و m خروجی وجود داشته باشد، ما به تعداد حاصل ضرب n و m کلید نیاز خواهیم داشت تا یک ماتریس را تعیین کنیم.اگر تعداد خروجی ها افزایش یابد، تعداد کلید ها با ضریب n افزایش می یابد. این افزایش کلیدها برای شبکه های بزرگ می تواند مشکل ساز شود.جایگزینی برای این طرح تغییر مرحله ای است.شبکه اتصال تک مرحله ای.در یک شبکه اتصال تک مرحله ای، گره های ورودی با یک مرحله که شامل کلیدها می باشد، به خروجی متصل می شوند.شکل زیر شبکه 8*8 تک مرحله ای که شامل کلیدها می باشد را با استفاده از تبادل شافل نشان می دهد.همانطور که قابل مشاهده است، از یک ترکیب، همه ورودی ها نمی توانند به همه خروجی ها متصل شوند. برای اتصال همه ورودی‌ها به همه خروجی‌ها، چندین بار ترکیب نیاز است.شبکه اتصال چند مرحله ای.یک شبکه اتصال چند مرحله ای از کلید های چند مرحله ای آبشاری تشکیل می شود. این کلید ها می توانند از الگوریتم مسیریابی خود یا الگوریتم کنترل شده توسط یک هدایت کننده متمرکز استفاده کنند تا یک شبکه کاملاً به هم پیوسته را ایجاد کنند.شبکه های متصل چندمرحله ای را می توان به سه دسته طبقه تقسیم بندی کرد:تعداد عناصر کلیدزنی مورد نیاز برای ایجاد یک شبکه غیر مسدود بسیار زیاد است و پس از آن شبکه غیرمسدود قابل تنظیم مجدد قرار دارد. مسدود کردن شبکه از حداقل عناصر کلیدزنی استفاده می کند.مثال ها.شبکه های متصل چند مرحله ای انواع مختلفی دارند.شبکه امگا.یک شبکه امگا از چند مرحله عناصر کلیدزنی 2*2 تشکیل شده است. هر ورودی با یک اتصال اختصاصی به یک خروجی متصل شده است. یک شبکه امگا N*N، تعداد log(N) مراحل و تعداد N/2 عناصر کلیدزنی در هر مرحله برای جابجایی کامل بین مراحل دارد. بنابراین شبکه دارای پیچیدگی (N log(N)) است. هر عنصر کلیدزنی می تواند الگوریتم کلیدزنی مخصوص خود را استفاده کند. یک شبکه امگا 8*8 را در نظر بگیرید. به تعداد 40320=!8 نگاشت یک به یک ورودی به خروجی خواهد بود. 12 عنصر کلیدزنی برای جایگشت کل که تعداد آن 4096=12^2 می باشد، وجود دارد. بنابراین، این شبکه یک شبکه مسدود کننده است.شبکه clos.یک شبکه Clos دارای 3 مرحله برای انتقال از N ورودی به N خروجی می باشد. مرحله اول به تعداد r=N/n کلیدهای متقاطع دارد و سایز هر کلید n*m است. مرحله دوم کلیدهای m با سایز r*r و در مرحله آخر کلیدهای r با سایز m*n هستند. اگر m &gt;= 2n-1 باشد،شبکه clos، یک شبکه کاملا غیرمسدود خواهد بود. تعداد اتصالات این شبکه بیشتر از شبکه امگا و بسیار کمتر از شبکه crossbar است.شبکه Beneš.شبکه Beneš یک شبکه غیر مسدود قابل تنظیم مجدد می باشد که از شبکه Clos با مقداردهی اولیه n = m = 2 به دست آمده است. در این شبکه(2log(N) - 1) مرحله وجود دارد که هر مرحله تعداد N/2 کلید متقاطع 2*2 دارد. یک شبکه Beneš 8*8 دارای 5 مرحله عناصر کلیدزنی است و در هر مرحله 4 عنصر کلیدزنی وجود دارد. سه مرحله میانی شامل دو شبکه 4*4 Benes هستند. شبکه 4*4 Beneš، می تواند به صورت بازگشتی هر ورودی را به هر خروجی متصل کند.