الگوریتم مسیریابی HAMFA در شبکه روی تراشه (NOC)

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

در این بخش معرفی الگوریتم مسیریابی HAMFA را آماده کردیم که یکی از روش های مسیریابی در شبکه های NOC می باشد و در سال 2013 معرفی شده که مقاله مرجع آن نیز در ادامه همین پست برای دانلود رایگان قرار داده شده است.

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

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

شکل 2: یک لایه دو بعدی از شبکه توری 4*4*4

بن بست در مسیر هامیلتونی

مسیر هامیلتونی ضمانت می کند که در هنگام مسیریابی بسته ها بن بست ایجاد نشود، در روش HAMFA به هر گره یک برچسب از 0 تا N-1 تعداد گره ها در شبکه می باشد. وقتی که برچسب گره مقصد بزرگتر از برچسب گره منبع باشد الگوریتم مسیریابی در زیر شبکه کانال بزرگ واقع شده است و در غیر این صورت گوییم که مسیریابی در زیر شبکه کانال کوچک واقع شده است. در شکل زیر، یک توری 3*3*3 را می بینید که در آن به هر گره یک برچسب تعلق گرفته است. شکل زیر، b کانال بزرگ و c کانال کوچک زیر شبکه را نشان می دهد.

شکل 3: (a) یک شبکه توری 3*3*3 با برچسب شماره برای هر گره – (b) کانال بزرگ – (c) کانال کوچک

روند مسیریابی الگوریتم HAMFA

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

شکل 4: تنظیمات برای پورت خروجی در الگوریتم HAMFA

در این الگوریتم لزوما به مسیر کمینه دست پیدا نمی کنیم، بلکه در حضور اشکال ممکن است که مسیر انتخابی غیر کمینه باشد. در ارزیابی های انجام شده برای این الگوریتم نشان داده شده است که الگوریتم HAMFA قادر است تا همه تک اشکال های یک جهته را تحمل کند، بدون اینکه برای جلوگیری از بن بست از کانال مجازی استفاده کند.

الگوریتم مسیریابی HAMFA در مقاله ای با عنوان Fault-Tolerant Routing Algorithm for 3D NoC Using Hamiltonian Path Strategy ارائه شده که در ادامه قابل دانلود می باشد.