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

الگوریتم مسیریابی FTDR سه بعدی

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

معرفی الگوریتم مسیریابی FTDR

الگوریتم مسیریابی FTDR که در سال 2011 در مقاله ای با عنوان A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip معرفی شد، یک الگوریتم تحمل پذیر خطا با سربار کم می باشد که در آن از یک جدول برای لایه توری دو بعدی (افقی) و دو بردار وضعیت TSV به جای Global Routing استفاده شده است. در این الگوریتم از ساختار Nostrum استفاده شده است. در این مقاله اشکال ها به دو دسته اشکال های افقی و اشکال های عمودی (TSV) تقسیم بندی می شوند، یک بردار 6 بیتی هم برای وضعیت اشکالی 6 لینک متصل به میان گذر استفاده می شود.

شکل 2: یک شبکه روی تراشه مش بندی شده

برای گرفتن وضیعت TSV هر میان گذر شامل دو بردار n بیتی است که وضیعت TSV را در خود ذحیره می کند (لینک بالایی و پایینی لایه فعلی) در هر سیکل میان گذر با استفاده از بردار وضیعت TSV که از همسایه هایش می گیرد بروز رسانی می شود. در این الگوریتم هر بسته از 128 بیت تشکیل شده است که در شکل زیر نشان داده شده است.

شکل 3: ساختار بسته در الگوریتم FTDR سه بعدی

در شکل فوق V بیت درستی است D-x و D-y و D-z آدرس مقصد و HC تعداد گام ها را مشخص می کند و payload نیز محتوای خود بسته را مشخص می کند، TV نشان می دهد آیا آدرس موقتی درست هست یا خیر و T-z و T-y و T-x آدرس موقتی هستند. الگوریتم به دو بخش تقسیم می شود، بخش اول مسیریابی در لایه حاضر و دومی مسیریابی بین لایه ها است. مسیریابی در لایه افقی از الگوریتم مسیریابی FTDR استفاده می کند و همچنین برای حرکت در بین لایه های عمودی قوانینی تعریف شده است که در زیر می آوریم:

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

مراحل الگوریتم عملکرد الگوریتم مسیریابی FTDR

• اگر بسته به مقصد رسیده باشد، میان گذر بسته را به سمت پورت محلی می فرستد، در غیر این صورت اگر TV=1 (یعنی آدرس موقتی در هست) و بسته به یک میان گذر واسط رسیده باشد. مسیر تولیدی به یک مسیر عمودی (بالا و پایین) قرار می گیرد و TV را برابر صفر قرار می دهیم، اگر بسته به یک میان گذر واسط نرسیده باشد، میان گذر فعلی با استفاده از جدول مسیریابی، مسیر تولیدی را به سمت میان گذر واسط پیدا می کند. (با استفاده از آدرس موقتی البته با این شرط که TV=1 می باشد).
• اگر هم به یک گره واسط نرسیدیم و هم TV=0 هست، آنگاه با استفاده از جدول مسیریابی و بردار وضعیت آدرس یک میان گذر واسط را پیدا کرده و آدرسش را در بسته فعلی قرار داده و TV آن را برابر یک قرار می دهیم و بسته را به سمت میان گذر واسط حرکت می دهیم.
• اگر مسیر تولیدی پورت مورد نظرش آزاد نباشد، بسته را به سمت یک پورت آزاد با کمترین بار ترافیکی هدایت می کنیم. اگر دو مسیر تولیدی همزمان هم داشته باشیم، بسته را به سمت میان گذری با بار ترافیکی کمتر هدایت می کنیم.

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

شکل 4: مثالی از الگوریتم مسیریابی تحمل پذیر خطا FTDR 3D