تحمل پذیری خطا در الگوریتم های مسیریابی شبکه روی تراشه (NOC)

تحمل پذیری خطا در الگوریتم های مسیریابی شبکه NOC

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

الگوریتم مسیریابی احتمالی

الگوریتم های احتمالی با افزونگی داده از طریق تولید بسته های تکراری و فرستادن آنها به مقصد از راه های مختلف، علاوه بر مسیریابی، به سطحی از تحمل پذیری خطا می رسند. در این الگوریتم ها هر گره بسته های ورودی را با احتمالی مشخص به گره های همسایه ارسال می کند. اولین تحقیق منتشر شده درباره این نوع الگوریتم در شبکه روی تراشه و در واقع اولین مسیریابی تحمل پذیر خطا برای شبکه روی تراشه، در سال 2002 میلادی بوده که در آن با استفاده از یک سری ارتباطات تصادفی بر پایه پروتکل های تصادفی گاسیپ (الگوریتم فلادینگ احتمالی) بسته ها را به مقصد می رساند. در این الگوریتم هر زمان که پیغامی دریافت می شود، با احتمال p به همسایه ها ارسال شده و با احتمال (1-p) دور انداخته می شود. پس از گذشت زمان کافی ، هر گره در شبکه به احتمال زیاد چند نسخه یکسان از پیغام را دریافت می کند. این نوع مسیریابی برای تحمل هم خطا های دائمی و هم خطا های گذرا مناسب است.

در مقاله ای با عنوان Fault tolerant algorithms for network-on-chip interconnect که در سال 2004 ارائه شده، دو گونه دیگر از مسیریابی احتمالی به نام فلادینگ هدایت شده و پیمایش تصادفی افزونه برای تحمل پذیری توام خطا های گذرا و دائمی معرفی شده است. در نوع اول احتمال ارسال یک پیغام به هر کانال خروجی یکسان نبوده بلکه وابسته به مقصد پیغام ، متغیر است. گره هایی که پیغام را به مقصد نزدیکتر می کنند. این روش در واقع اصلاح شده روش ارائه شده در مقاله On-chip stochastic communication و مقاله Towards on-chip fault-tolerant communication می باشد که هر دو در سال 2003 ارائه شده اند. در نوع دوم تعداد مشخص و محدودی پیغام یکسان تنها از گره مبدا وارد شبکه می شود در بقیه گره ها این نسخه های یکسان بدون تکرار شدن، به صورت احتمالی مسیر های مختلفی را طی می کنند و در واقع هر گره پس از دریافت هر پیغام الزاما آن را از یکی از کانال های خروجی خود ارسال می نماید.

تحقیقات بعدی در مقاله A novel reliable routing algorithm for network on chips و مقاله Smart-flooding: a novel scheme for fault-tolerant NoCs مسیریابی دیگری از نوع فلادینگ را ارائه می کند. مشکل اصلی این نوع الگوریتم ها این است که تنها برای ترافیک کم مفید بوده و شبکه با افزایش بار ترافیکی زود به اشباع می رسد. زیرا بسته های تکراری افزوده شده مقداری از عرض باند شبکه را مصرف می کنند. علاوه بر این، زمان انتقال بسته ها قابل پیش بینی نبوده و عدم رخداد بن بست در آنها بررسی و مشخص نشده است.

الگوریتم های مسیریابی غیر احتمالی

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

الگوریتم های غیر احتمالی تحمل پذیر خطا همانند مسیریابی های دیگر می توانند از نوع مسیریابی مبتنی بر مبدا مانند روش های ارائه شده در مقاله Fault tolerant source routing for network-on-chip و مقاله A lightweight fault-tolerant mechanism for network-on-chip یا از نوع مسیریابی توزیع شده مانند روش مقاله Fault tolerant distributed routing algorithms for mesh networks-on-chip و مقاله Logic-based distributed routing for NoCs باشند.

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

مشکل این روش عدم مقیاس پذیری آن بر حسب تاخیر و دیر کرد شبکه ، مساحت و توان مصرفی هنگام افزایش اندازه شبکه است که در نتیجه برای شبکه های روی تراشه در حال غیر کاربردی شدن است. با این حال با توجه به قابلیت بالای این نوع روش برای تحمل پذیری خطا ، نمونه های متنوعی از آن در طراحی شبکه های روی تراشه قابل اعتماد شده است که نمونه ای از آنها در مقاله Degradable mesh-based on chip networks using programmable routing tables و مقاله ault-tolerant architecture and deflection routing for degradable NoC switches ارائه شده اند.

الگوریتم های مسیر یابی تحمل پذیر خطا

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