بخشی از مقاله
چکیده
این مقاله به معرفی روتر مسیریاب در محیط شبکه بر تراشه میپردازد که این روتر بر پایه fpga طراحیشده و با الهام گرفتن از قوانین کلونی مورچگان سعی در بهبود زمان ارتباط بین نودها در شبکه بر تراشهای شده و بهنوعی کارایی شبکه را نیز افزایش دهد .در این مقاله متد ارائهشده در نرمافزار ise Xilinx 12.1 شبیهسازی و سنتز شده است.
الگوریتم مسیریابیکاملاً تطبیقی در توپولوژی مش 15*15 بررسیشده و زمان مسیریابی با چند الگوریتم مسیریابی مشهور مورد ارزیابی قرارگرفته است و سرعت این متد در مقایسه با کارهای انجامگرفته بیشتر و توان مصرفی کمتر میباشد و در عین حال مساحت مصرفی تراشه متد پیشنهادی در حدود 1/3 برابر کمتر از مسیریابی بر اساس متد فازی و مدل استاندارد میباشد .
-1 مقدمه
در دنیای امروزی برخی از مشکلات وجود دارند که با فرمول های ریاضی و یا یک راه حل مشخص و عادی نمی توان آنان را حل کرد، یا تحلیلی برای آن وجود ندارد و یا به طوری که مسئله آن قدر پیچیده به نظر می رسد که به دلیل تعدد راه حل ها ارزیابی بهترین راه حل مقدور نیست . نحوه برنامه ریزی کارها، نحوه چینش مدارات در VLSI یا در مساله مسیریابی در شبکه برتراشه به طوری که سرعت و توان مصرفی آن بهینه شود و یا مسیریابی در شبکه ها و... جز مثال هایی هستند که به دلیل داشتن معادلات پیچیده و زیاد، امکان استفاده از روش های معلوم جهت رسیدن به راه حل بهینه وجود ندارد، لذا برای حل مشکلات مذکور الگوریتم های تکاملی که الگوریتم کلونی مورچگان نیز یکی از آنان هست مطرح شدند.
الگوریتم کلونی مورچگان یکی از موضوعات مهم هوش ازدحامی در دنیای امروز هست که از جمعیتی از مورچگان با راه حل های تصادفی شروع کرده و با تکرار، سعی در بهتر کردن مجموعه راه حل ها می نماید. این الگوریتم برای اولین بار در سال 1992 توسط دوریگو و همکارانش به عنوان یک راه حل چند عامله برای حل مسائل بهینه سازی ارائه شد .
بستر پیاده سازی های مختلفی برای اجرای کلونی مورچگان در کاربردهای مختلف از جمله نرم افزاری و سخت افزاری وجود دارد که در بستر نرم افزاری در مدل دانه درشت و بصورت دسته ای قابلیت اعتماد بالاتری دارند و دارای سرعت بیشتری به حالت دانه ریز دارد در حالت دانه ریز سربار حاصل از پیاده سازی هم زیادتر خواهد بود و دومین بستر ، بستر سخت افزاری میباشد که دارای سرعت فوق العاده زیاده در مقایسه با بستر نرم افزاری میباشد منتها دقت و انعطاف پذیری مدل سخت افزاری به مراتب کمتر از از بستر نرم افزاری آن می باشد .
اولین مدل پیاده سازی سخت افزاری کلونی مورچگان مدل بر پایه جمعیت بر روی تراشه قابل پیکربندی مجدد بود . در این مدل که مورچهها به داخل جدول فرومون پخش میشوند ، بجای اینکه در هر تکرار هر مورچه ، ماتریسn× n را بپیماید، یک جدول جمعیتی از روی جدول فرومون تشکیل میشود که بین 1 تا 8 می باشد که این جدول حاوی جمعیتی از بهترین مسیرهای پیموده شده در تکرارهای قبل میباشند و مورچه در تکرارهای بعدی از این جدول به جای استفاده از کل جدول فرومون برای انتخاب راه حل خود استفاده میکند.
متد بدین صورت است که توسط یک سوئیچ k×n که n تعداد آیتمهای مساله و k تعداد بهترین مسیرها میباشد . معیار هیوریستیک در انتخاب نود بعدی دخالت داده نشده است و به ترتیب مدل بر پایه افزاینده بر روی تراشه قابل پیکربندی مجدد و نگاشت کلونی مورچگان بر FPGA و بر متد بر پایه تکنولوژیCmos پیاده سازی گردد که در این روش های کاملا سخت افزاری انعطاف پذیری کلونی مورچگان پایین میباشد اما در کاری دیگر از ترکیب دو مدل سخت افزاری و نرم افزاری بطوری که نرمافزار به زبان c و سختافزار بر روی تراشه fpga به زبان Verilog طراحیشده است.
چهارچوب طراحیشده برای الگویتم از دو قسمت اصلی تشکیل یافته بدین ترتیب که انتخاب بهترین مسیر از میان چندین مسیر بهصورت نرمافزاری بر روی پردازنده نهفته NIOS II به زبان C پیادهسازی شده است و دیگر عملیات محاسباتی الگوریتم بهصورت سختافزاری بر روی لاجیک های تراشه قابلبرنامهریزی مجدد پیادهسازی شده است که انعطاف پذیری در کنار سرعت بالاتر نیز حفظ می گردد.
سیستم بر روی یک تراشه یک انقلاب عمده در نحوه طراحی مدارهای مجتمع میباشد که به دلیل انعطافپذیری که به طراحی میبخشد و پیچیدگی که کاهش میدهد بسیار قابلتوجه میباشد. چشمانداز توسعه یک محیط محاسباتیکاملاً فراگیر، از خانههای هوشمند، شهرهای هوشمند گرفته تا درنهایت یک سیاره هوشمند نیاز به ادامه قانون مور و بلکه فنآوریهای بیش از مور و فراتر از مور نیاز دارد.رشد نمایی مجتمع، در حال حاضر قادر به ساخت معماریهای محاسباتی هستهای است که شامل صدها هسته ناهمگن IP میباشد[1] .
در همین حال با کاهش حجم پردازندهها، عدم تعادل بین تأخیر گیتها و تأخیر سیمها بر روی چیپ ایجاد شد. به همین دلیل امروزه ارتباطات روی چیپ یکی از مهمترین عاملها برای افزایش کارایی سیستم است. یکی از راهحلهای ارائهشده درزمینه ی ارتباط روی چیپ، استفاده از تکنولوژی شبکه بر روی تراشه است، که مشکلات ارتباطات را تا حد زیادی حل می کند.
-2کارهای انجامشده
الگوریتمهای مسیریابی قطعی به دلیل سادگی جذاب هستند. برای توپولوژیهای مش، یکی از مشهورترین مسیریابها Routing - DOR - Dimension-Orderکه رایجترین آن اغلب XY مسیریابی است. این طرح مسیریابی XY یک طرح ساده است که در ابتدا بستهها را در امتداد محور X - در شبکه مش دوبعدی - هدایت می کند و هنگامیکه بستهها رسیدن به ستون جایی که مقصد در آن است، آنها سپس در امتداد محور Y روت میشوند و چون این الگوریتم هیچ انعطافپذیری و سازگاری ندارد لذا نمیتواند در مسیریابی خود معیار ازدحام و ترافیک را در نظر بگیرد.
در نظر گرفتن تراکم نیاز به یک الگوریتم است که بتواند مسیرهای جایگزین را در نظر بگیرید، درحالیکه حالتهای deadlock ,live lock که باقی هستند. تعدادی از الگوریتمهای مسیریابی تقریبا انطباقی کهمطمئناً عاری از deadlock بوده و بدون استفاده از کانالهای مجازی میتواند با محدود کردن چرخشهای خاص به دست آید.[2] بهطور خاص، حداقل باید یک چرخش برای یکی از 2 سیکل ممکن منع میباشد .
این منجر به الگوریتمهای مسیریابی شناختهشده به عنوان غرب-اول، شمال-آخرین و منفی اولین میشود. همانطور که در نام آنها اشاره شد، برخی از جفت مقصد منبع مسیرهای متعددی داشته باشند درحالیکه برخی از گزینههای تک مسیر دارند. طرح مسیر مسیریابی Odd Even - OE - بهترین توزیع سازگاری رابین جفتهای مقصد منبع با حفظ چرخشهای ممنوعه فراهم میکند .چرخش شرق به شمال و شرق به جنوب در روترهایی که در یک ستون زوج قرار دارند، ممنوع است از شمال به غرب و جنوب به غرب، در روترهایی که در ستون فرد میباشد ممنوع است .
DyaD چارچوب مسیریابی پویا است. بین حالت مسیریابی قطعی - مانند - XY و سازگار - بهطورمعمول - OE بر اساس سطح ترافیک شبکه محلی کار میکند.برای جلوگیری از وقفه deadlock از یک ترکیب XY-OE، نویسندگان پیشنهاد یک نسخه قطعی از OE ارائه دادند که OE ثابت نامیده شد. اسلات های بافر خالی در هر پورت روتر به عنوان پارامتر ترافیک استفاده میشود.آگاهی از ترافیک در الگوریتم مسیریابی نیاز به انتشار اطلاعات احتمالی از طریق شبکه دارد. این کار با استفاده از لینکهای اختصاصیافته - به مانند کار ما - یا با استفاده از بستههای شبکه انجام میشود .[3] در ساختارهای یکپارچگی سهبعدی نیاز به مسیریابهای آگاه از ترافیک شبکه در مسیرهای سهبعدی داریم.
رویکرد دیگری که در [4] پیشنهادشده است بعد را تغییر میدهد - از XY به - YX برای بستههای خاص بر اساس تراکم محلی بهدستآمده از روترهای همسایه محاسبه می شود . این رویکرد حاصل نتایج خوب در مقایسه با الگوریتم های مانند XY و OE میباشد اما آگاهی از تراکم محدود به روتر های همسایه است، در حالی که در طرح پیشنهادی ما همه روترها در فاصله دو گام آگاه از تراکم شبکه می باشند.
علاوه بر این، تراکم با استفاده از بافر خالی همسایه اندازهگیری می شود.درحالیکه رویکرد ما با استفاده از درخواستهای ترافیک ورودی و میتوان در روترهای بدون بافر نیز استفاده کرد. درنهایت، نویسندگان مصرف انرژی را در نظر نگرفتهاند ، اما تنها تراکم ازدحام را فقط مدنظر قراردادند . ازآنجاییکه بافرها باعث مصرف انرژی قابلتوجهی هستند، مسیریابی بدون بافر به عنوان یک جایگزین پیشنهاد شد. بر اساس اینکه پورت خروجی به بسته انحرافی اختصاص دادهشده بود بر اساس الگوریتمهای مسیریابی با بستههای دیگر جایگزین میشود. [5]
مجموعهای از الگوریتمهای مسیریابی ساده و کاربردی که برای تقرباًی هر توپولوژی NoC مورداستفاده قرار میگیرند، در مقابل الگوریتمهای بافر پایه ارزیابی میشوند. با این حال، مسیریابی بدون بافر به خاطر مرتبسازی اولویت دادهها جهت جلوگیری از بین رفتن عمر دادهها از تأخیر طولانیتر یا فرکانس کار پایین رنج میبرد .[6] از سوی دیگر، بدون هیچ صف ورودی یا خروجی ، بنبست در شبکههای بدون بافر نگرانکننده نیست.
ارتقاء با جایگزینی منطقی مرتبسازی با استفاده از یک شبکه جایگزینی ساختهشده است که بهطور قابلتوجهی بهبود عملکرد شبکه را از بابت هزینه بسیار کارا کرده است . کنترل منطقی فازی [11] FLC زمینهای است که در آن نظریه مجموعه [12] و استنتاج فازی برای تولید قوانین کنترل استفاده می شود. قابلیت کیفی گرفتن صفات کنترل سیستم بر اساس پدیدههای قابلمشاهده یکی از ویژگیهای اصلی کنترل فازی است و در ادبیات تحقیقاتی مختلف و محصولات تجاری نشان دادهشده است.
