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

rilm routing algorithm noc network 2843 1 الگوریتم مسیریابی RILM در شبکه روی تراشه (NOC)

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

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

الگوریتم مسیریابی RILM چیست ؟

الگوریتم RILM یک مسیریابی تحمل پذیر خطا در شبکه روی تراشه برای مهار کردن خطا در لینک های عمودی ضعیف هست که در مقاله Reconfigurable inter-layer routing mechanism for 3D multi-layer networks-on-chip در سال ۲۰۱۰ ارائه شده که این الگوریتم یک مسیریابی قابل اعتماد مناسب برای شبکه روی تراشه سه بعدی با همبندی های ناهمگن در لایه های مختلف می باشد که برای اجتناب از بن بست به کانال مجازی تکیه دارد. این الگوریتم مستقل از اینکه در لایه های افقی چه پروتکل مسیریابی و یا چه همبندی شبکه به کار رفته است، خطا های چند گانه را در لینک های عمودی تحمل می کند. لازم به ذکر است که لینک های عمودی در این الگوریتم جزئی است، به این مفهوم که در هرلایه فقط تعداد محدودی از گره ها دارای لینک عمودی هستند که به این گره ها گره های سه بعدی و به بقیه گره ها گره دوبعدی می گوییم.

فرضیات الگوریتم مسیریابی RILM :

  1. همه لینک ها دو جهته هستند.
  2. همه گره های بدون خطا در یک لایه یکسان به همدیگر متصل هستند، این بدان معنی است که گره ها در یک لایه از هم مجزا نیستند.
  3. بین هر جفت از لایه های مجاور حداقل یک لینک عمودی بدون خطا وجود دارد، به این مفهوم که لایه ها از هم مجزا نیستند.
  4. همه گره های بدون خطا در همسایگی یک گره ی دارای خطا از وضعیت آن گره مطلع هستند.
  5. هر دو گره ای که از طریق یک لینک خطا دار به هم متصل هستند از خطا آن لینک مطلع هستند.
  6. مسیریابی دوبعدی به کار رفته در هرلایه تحمل پذیر خطا و فاقد بن بست می باشد.

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

rilm routing algorithm noc network 2843 1 الگوریتم مسیریابی RILM در شبکه روی تراشه (NOC)

شکل ۱: مثالی از الگوریتم مسیریابی RILM

گره ۳۴ در لایه L2 گره منبع و گره ۱۲ در لایه L0 ، گره مقصد می لاشد؛ مسیر انتخابی نیز ۳۴ ، ۲۳ ، ۱۸ ، ۱۹ ، ۱۴ ، ۲ ، ۳ ، ۷ ، ۱۱ ، ۱۲ می باشد. همچنین در این شکل گره ها و لینک های خطا دار نیز نشان داده شده اند.

برای این که بسته را به سمت لایه مقصد بفرستیم، اگر گره منبع خود یک گره سه بعدی باشد بسته را به لایه مقصد می فرستد، در غیر این صورت بسته باید به سمت یک گره سه بعدی میانی در لایه منبع مسیر یابی شود. برای انجام این مسیریابی از درختی به نام VNT (vertical node tree) استفاده می کنیم. این درخت شامل همه گره هایی است که به گره سه بعدی متصل هستند. نکته دیگر اینکه این درخت در زمان شروع الگوریتم ساخته می شود. برای ساخت درخت VNT ابتدا یک گره سه بعدی دلخواه انتخاب شده و این گره پیام های اتصال را به همسایه های خود به صورت یک گام ارسال می کند و بقیه گره ها نیز به همین صورت این پیام را به گره های همسایه خود ارسال می کنند و به این صورت درخت VNT ساخته می شود. گره ها از اطلاعات این درخت برای یافتن گره سه بعدی میانی استفاده می کنند.

زمانی که خطا بوجود می آید باید فرآیند بازپیکربندی انجام شده و درخت VNT اصلاح شود. این مسئله را با مثالی که در شکل زیر نشان داده شده است شرح می دهیم.

rilm routing algorithm noc network 2843 2 الگوریتم مسیریابی RILM در شبکه روی تراشه (NOC)

شکل ۲: در این شکل a ساختار درخت VNT در وضعیت بدون اشکال و b وضعیت اشکال در گره دوبعدی و c وضعیت اشکال در گره سه بعدی را نشان می دهد.

در شکل بالا، a گره های ۵ و ۱۱ گره ها ی سه بعدی هستند، همانطور که در شکل بالا می بینید گره های همسایه که به فاصله یک گام از گره سه بعدی قرار دارند در VNT قرار می گیرند. در اینجا گره های ۱ تا ۲ در VNT5 و گره های ۱۰ تا ۱۸ در VNT17 قرار دارند. جهت پیکان های نشان داده شده از گره فرزند به گره والد می باشد.

در شکل بالا، b یک گره دوبعدی یعنی گره ، ۱۸ دچار خطا شده است. لذا در فرآیند بازپیکربندی گره های ۱۲ و ۱۵ اتصالشان قطع و سپس درخت VNT جدید بدین صورت تشکیل می شود که گره ۱۲ از طریق گره همسایه ۹ به VNT5 تعلق گرفته و گره ۱۵ از طریق گره ۱۳ به VNT17 تعلق می گیرد. همچنین در شکل بالا، c یک گره سه بعدی دچار خطا شده است، در این وضعیت در فرآیند بازپیکربندی همه گره ها به VNT5 تعلق می گیرد.

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

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

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