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

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

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

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

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

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

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

شکل ۲: مثالی از الگوریتم مسیریابی تحمل پذیر اشکال AFRA

اهداف الگوریتم AFRA :

  • سهولت: این الگوریتم در غیاب اشکال از zxy و در حضور اشکال از zxy استفاده می کند، لذا AFRA یک الگوریتم قطعی است و بر همین اساس مسیریابی در شبکه که برای این الگوریتم پیاده سازی می شود، بر خلاف مسیریابی که برای الگوریتم های تطبیقی استفاده می شود، دارای ساختار ساده ای است.
  • کارایی خوب: در AFRA فرض شده است که همه اشکال ها یک جهته هستند، به این معنی که همه اشکال ها یا در لینک های بالایی و یا همه در لینک های پایینی اتفاق می افتند. این مسئله باعث می شود تا بن بست نداشته باشیم و دیگر نیاز به کانال مجازی نداریم و این مسئله باعث کارایی بالاتر و همچنین صرفه جویی در سخت افزار مورد استفاده می شود.
  • قوی مندی: طبق اندازه گیری هایی که برای این الگوریتم انجام شده است، در حضور تعداد اشکال زیاد این الگوریتم تا میزان مناسبی کارایی خود را از دست نمی دهد. و این مسئله ایجاد قوی مندی می کند.

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

شکل ۳: یک چرخه وابستگی فرض شده در AFRA

روند عملکرد الگوریتم مسیریابی AFRA

الگوریتم مسیریابی در AFRA به این صورت می باشد که در غیاب اشکال از zxy و در حضور اشکال از xzxy استفاده می کند، به این مفهوم که یک گره میانی در لایه افقی انتخاب شده و بسته به آن فرستاده شده و از آن گره، الگوریتم zxy اجرا می شود. گره میانی گره ای است که دارای بعد y و z یکسان با گره منبع باشد. و همچنین تمام لینک های عمودی متناظر با این گره در لایه های مختلف سالم باشند. ممکن است چند گره پتانسیل این را داشته باشند که گره میانی باشند، برای اینکه بهترین آن ها را انتخاب کنیم گره ای را انتخاب می کنیم که روی مسیر کمینه باشد و اگر هیچکدام از آن گره ها بروی مسیر کمینه نباشد گره ای را انتخاب می کنیم که دارای کمترین شماره باشد.

لینک های عمودی در الگوریتم AFRA

مسئله ای که باید در الگوریتم AFRA در نظر بگیریم این است که هر گره باید اطلاعات لینک های عمودی متناظر خود در لایه های مختلف و همه گره هایی که در سطر متناظر با این گره قراردارند را بداند، برای مثال در یک توری ۸*۸*۴ سربار اطلاعاتی روش AFRA برای هر مسیر یاب برابر ۸*(۴-۱)=۲۴ می باشد که این مقدار زیادی نیست.

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

شکل ۴: مثالی از الگوریتم مسیریابی تحمل پذیر اشکال AFRA

البته در مسیریابی AFRA دو ضعف دیده می شود. نخست اینکه این الگوریتم فقط بر لینک های عمودی تکیه دارد و دوم اینکه وضعیت ازدحام در آن بررسی نشده است. الگوریتم مسیریابی AFRA در مقاله ای با عنوان AFRA: A Low Cost High Performance Reliable Routing for 3D Mesh NoCs ارائه شده که در ادامه قابل دانلود می باشد.


مشاهده ویدئو در این باره

خوشحال خواهیم شد اگر نظر خودتون رو درباره این مطلب ثبت کنید

خطا!دکمه ریفریش را بزنید