ثابت شده است که مسئله نگاشت یک مسئله NP-hard است و جواب بهینه تنها بعد از امتحان تمام حالات ممکن مشخص می شود[۷]. برای همین اگر فرض شود امتحان هر حالت ممکن ۰۱/۰ میلی ثانیه طول بکشد، یافتن جواب بهینه برای نگاشت ۱۶ وظیفه بر روی ۱۶ گره شبکه ۱۰۸×۹/۲ ثانیه معادل ۶/۶ سال به طول میانجامد. به همین دلیل، این مسئله در بسیاری از مقالات با روشهای مکاشفهای حل شده است.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در این پایان نامه به حالت دوم مسئله نگاشت یعنی به عبارتی به نگاشت وظایف یک برنامهی کاربردی بر روی هستههای پردازشی پرداخته می شود.
شکل ۱‑۳- مسئله نگاشت وظایف بر روی هستههای پردازشی شبکه[۱۰]
مفهوم برنامه های کاربردی بیدرنگ
در سیستمهای بیدرنگ[۲۳] صحت و درستی سیستم تنها وابسته به تولید نتایج درست نمی‌باشد بلکه به زمان تولید نتایج نیز بستگی دارد [۱۱]. برنامه های کاربردی بیدرنگ در این قبیل سیستمها دارای وظایف بیدرنگ میباشند که این وظایف در این قبیل سیستمها در پاسخ به یک اتفاق که ممکن است از داخل یا خارج سیستم رخ دهد، ایجاد میشوند. به طور مثال یک وظیفه ممکن است به خاطر یک رخداد[۲۴] داخلی از قبیل یک وقفه ساعت[۲۵] که هر چند میلیثانیه اتفاق میافتد و به طور دورهای دمای یک محفظه را اعلام می کند، ایجاد شود. وظیفه دیگری ممکن است به خاطر یک رخداد خارجی مانند فشار دادن یک سوئیچ توسط کاربر، ایجاد شود. هر یک از این وظایف دارای محدودیت زمانی به نام مهلت اتمام[۲۶] میباشند که بیانگر حداکثر زمان وظیفه برای اتمام اجرا و تولید نتایج‌اش میباشد[۱۲]. مهلت اتمام وظایف مختلف ممکن است متفاوت باشد. در سیستمهای بیدرنگ همه بستههای داده متعلق به یک وظیفه باید در آن مهلت اتمام مشخص شده به وظیفه مقصد تحویل داده شوند و از دست دادن زمان اتمام در این سیستمها به همان میزان که یک پکت در مسیر خراب یا دور انداخته شود، یک شکست تلقی می شود[۱۱]. ارتباطات بیدرنگ به طور معمول در سیستمهای بحرانی ایمنی مانند کنترل روبات، وسایل نقلیه الکترونیکی و… استفاده میشوند [۱۳].
برنامه های کاربردی بیدرنگ به دو دسته تقسیم میشوند[۱۱]:
برنامه های کاربردی بیدرنگ سخت[۲۷] : در این قبیل برنامه های کاربردی، اتمام زود هنگام وظایف چندان حائز اهمیت نمی باشد بلکه مسئله مهم آن است که همه وظایف برنامهی کاربردی مورد نظر در تمامی زمانها مهلت اتمامشان را رعایت کنند و از آن زمان تعیین شده تجاوز نکنند. بنابراین برنامه های کاربردی بیدرنگ سخت انعطافپذیر نیستند و تجاوز از مهلت اتمام را نمی توانند تحمل کنند. به همین دلیل لازم است که تمام ملزومات سیستم در زمان طراحی در نظر گرفته شوند و در واقع نوعی تضمین[۲۸] فراهم می شود. همچنین به دلیل همین عدم انعطافپذیری این برنامه های کاربردی، رفتارهای پویای سیستم نامطلوب است مگر اینکه آن رفتار را به عنوان یک وضعیتی از سیستم مدل کرد که بتواند در زمان طراحی تحلیل شود[۱۱]. Æthereal, Nostrum و Mangoنمونههای NOCهایی هستند که ارتباطات بیدرنگ سخت را پیادهسازی می کنند[۱۳].
برنامه های کاربردی بیدرنگ نرم[۲۹] : این برنامه های کاربردی در بسیاری از حوزه ها از قبیل سیستمهای چندرسانهای[۳۰]، محاسبات توزیع شده[۳۱] که نیازمند کارایی بالا هستند، ارائه شده اند[۱۱]. برنامه های کاربردی بیدرنگ نرم، نیز دارای محدودیتهای زمانی میباشند اما در برنامه های کاربردی مذکور، کیفیت سرویس[۳۲] دارای اهمیت بالاتری است. به عبارتی در این برنامه های کاربردی تا حدی قابل قبول است که برخی از ترافیکهای ارتباطی به درستی سرویس داده نشوند (یعنی تا حدودی محدودیتهای زمانیشان را رعایت نکنند) به شرط آنکه عملکرد[۳۳] آن در یک سطح مشخصی باقی بماند[۱۱]. به بیان دیگر، میانگین زمان پاسخ[۳۴] وظایف، معیار مهم در اندازه گیری کارایی در این دسته از برنامه های کاربردی میباشد وکمینهکردن هرچه بیشتر زمان پاسخ وظایف حائز اهمیت است. بنابراین هیچ گونه تضمین مطلقی برای رفتارهای زمانی این نوع سیستمها لازم نیست، در حالی که کارایی باید به طور میانگین در یک سطح قابل قبولی باشد. به خاطر همین انعطافپذیری این سیستمها به سیستمهای بیدرنگ نرم معروفاند[۱۱]. نمونه ای از سیستمهای بیدرنگ نرم، سیستمهای چندرسانهای هستند[۱۳].
مسئله توان در شبکه بر روی تراشه
اگرچه شبکه روی تراشه در ابتدا با هدف بهبود سرعت انتقال مطرح شد، ولی با توجه به اهمیت کنونی توان مصرفی، بررسی عوامل مصرف توان در شبکه روی تراشه و کنترل آن امری اجتناب ناپذیر است و به عبارتی توان بمصرفی یکی از مهمترین معیارهای ارزیابی شبکه روی تراشه میباشد. عوامل زیادی روی توان مصرفی شبکه روی تراشه تاثیر میگذارند، که عبارتند از : ساختار مسیریابها، روش راهگزینی[۳۵]، الگوریتم مسیریابی[۳۶]، الگوی ترافیکی[۱]. اما یکی از چالشهای اصلی در ازریابی توان در شبکه روی تراشه، بررسی توان مصرفی ناشی از ارتباطات بین هستههای پردازشی و همچنین اتلاف توان در المانهای شبکه از جمله مسیریاب میباشد. توان مصرفی شبکه، متوسط توان مصرف شده توسط شبکه (مسیریابها و اتصالات) را در طول مدت اجرا (و یا شبیهسازی) نشان میدهد. این توان شامل توان پویای ناشی از فعالیت اجزای شبکه و نیز توان ایستا ناشی از جریانات نشتی است. یک معیار مهم دیگر برای ارزیابی مصرف انرژی شبکه، متوسط انرژی فلیت (و یا بسته) است که انرژی متوسطی را نشان میدهدکه برای هدایت یک فلیت از گره مبدا به گره مقصد لازم است. اندازه گیری دقیق توان تنها با سنتز کامل توصیف سختافزاری شبکه (شامل جایابی و مسیریابی اتصالات) و توسط ابرازهای خاصی قابل انجام است[۷]. در این پایان نامه به دلیل آنکه استفاده از شبیهساز نیاز به زمان زیادی برای تحلیل هر راهحل در الگوریتم ژنتیک دارد، از مدلهای تحلیلی برای ارزیابی توان مصرفی در شبکه روی تراشه استفاده می شود که در ادامه به طور کامل توضیح داده خواهد شد.
هدف پایان‌نامه
یکی از چالشهای مهم در تحقیقات مربوط به شبکه روی تراشه، مسئله نگاشت برنامه کاربردی بر روی هستههای پردازشی متصل به مسیریابهای شبکه میباشد. برنامه های کاربردی انواع مختلفی دارند که یکی از پرکاربردترین آنها، برنامه های کاربردی تعبیه شده[۳۷] میباشند. برنامه های کاربردی تعبیه شده پیچیده که دارای ارتباطات زیادی بین مولفههای مختلف میباشند و همچنین نیازمند کارایی و توان محاسباتی بالایی هستند، مناسبتر است که از معماری شبکه روی تراشه بهره ببرند. این دسته از برنامه های کاربردی دارای نیازمندیهای زمانی بیدرنگ میباشند. به عبارتی وظایف این برنامه های کاربردی برای آنکه مهلت اتمام موردنظرشان رعایت شود، باید در تمامی موقعیتها، محاسبات و ارتباطاتشان به موقع انجام شود. با وجود این اهمیت برای سیستمهای تعبیه شده، تحقیقات کمی بر روی تامین ضمانت برای برنامه های کاربردی بیدرنگ سخت که شامل چندین مولفه ارتباطی روی NOC هستند، انجام شده است. همچنین همانگونه که ذکر شد، یکی از معیارهای مهم در ارزیابی شبکه روی تراشه، مسئله توان مصرفی در NOC میباشد. از این رو هدف از انجام این پایان نامه، پرداختن به مسئله نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC است به طوریکه علاوه بر اینکه محدودیتهای زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. به دلیل آنکه مسئله نگاشت یک مسئله NP-hard است و یافتن جواب بهینه نیازمند امتحان تمام حالات ممکن است، از این رو، روشی مبتنی بر الگوریتم تکاملی ژنتیک چندهدفه[۳۸] ارائه شده است که هم پاسخگوی اهداف مذکور باشد و هم توانایی رقابت با روشهای مشابه را از جنبه های مختلف داشته باشد.
ساختار ادامه پایان‌نامه
در فصل دوم مروری بر مفاهیم و معماری شبکه روی تراشه ارائه شده که در این فصل به بیان همبندی شبکه، روشهای راهگزینی، مسیریابی و الگوریتمهای مسیریابی، کانال مجازی و معیارهای ارزیابی در شبکه روی تراشه پرداخته شده است. در فصل سوم مروری بر ادبیات موضوع ارائه شده، که شامل مفاهیم نگاشت ایستا[۳۹] و پویا[۴۰] و بررسی کارهای مرتبط با هر یک از آنها میباشد. در فصل چهارم روش پیشنهادی برای نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هستههای پردازشی NOC بر مبنای الگوریتم ژنتیک[۴۱] ارائه شده است که شامل نحوه مدل کردن مسئله، اهداف الگوریتم، نحوه انجام آن و اجزاء تشکیل‌دهنده‌ی این روش میباشد. در فصل پنجم ضمن معرفی معیارهای ارزیابی و محک مورد استفاده، نتایج حاصل از الگوریتم پیشنهادی براساس معیارهای معرفی شده، مورد بررسی و ارزیابی قرار گرفتهاند. در آخر در فصل ششم خلاصهای از پایان نامه، نتیجه گیری کلی از کارهای انجام‌شده و پیشنهادهایی برای ادامه این کار ارائه شده است.
فصل دوم
فصل دوم: معماری شبکه روی تراشه
مقدمه
با پیشرفت روزافزون فنآوری و رشدسطح فشردهسازی، ابعاد تراشهها و حجم پردازندهها کاهش یافته است که این کاهش حجم پردازندهها، موجب عدم تعادل بین تاخیر دروازهها و تاخیر سیمها بر روی تراشه شده است. در این ارتباط، اگر چه تاخیر دروازهها با روند فنآوری کاهش مییابد اما تاخیر سیمها ثابت میماند و در حقیقت نسبت به دروازهها بیشتر می شود. برای کاهش اثر این تاخیرها، باید معماریهایی جایگزین معماریهای رایج شوند که با کاهش طول اتصالات و حذف سیمهای بلند مشکلات ناشی از این تاخیرها را در بلوکهای عملیاتی کاهش دهند. در واقع نکته اصلی جداسازی بخشهای ارتباطی از بخشهای محاسباتی و ذخیرهسازی میباشد. از این رو امروزه ارتباطات روی تراشه یکی از مهمترین عوامل برای افزایش کارایی سیستمهای روی تراشه است. یکی از راه حلهای ارائه شده در زمینه ارتباط روی تراشه، استفاده از فنآوری شبکه بر روی تراشه است، که مشکلات ارتباطات را تا حد زیادی حل می کند[۴]. شبکه بر تراشه ساختار ارتباطی با قابلیت استفاده مجدد فراهم می کند که این ویژگی برای طراحان تراشه اهمیت بسیار زیادی دارد؛ زیرا منجر به کاهش زمان مابین طراحی محصول و ارائه آن به بازار می شود. همچنین این ساختار ارتباطی که در آن ارتباط میان واحدهای مختلف از طریق بستههای مسیریابی شده توسط مسیریابها و راهگزینهای تعبیه شده در شبکه واقع بر روی تراشه برقرار می شود، نه تنها از قابلیت مقیاسپذیری و توسعه بالایی برخوردار است، بلکه با کاهش طول سیمهای بلند سراسری کشیده شده در سطح تراشه به کاهش توان مصرفی نیز منجر خواهد شد[۲]. در ادامه این فصل به بررسی اجمالی مفاهیم شبکه روی تراشه شامل معماری NOC، انواع همبندیهای شبکه، مسیریابی و الگوریتمهای مسیریابی، روشهای راهگزینی و کانال مجازی در شبکه روی تراشه پرداخته می شود.
معماری شبکه روی تراشه
معماریهای سنتی ارتباطی درون تراشهی مبتنی بر گذرگاه مشترک و اتصالات اختصاصی نقطه به نقطه به دلیل مقیاسپذیری ضعیف مساحت و کارایی، برای پیادهسازی سیستمهای پیچیده و در مقیاس بزرگ امروزی مناسب نیستند[۴]. این چالش از یک سو، و مقیاسپذیری و کارایی بالای شبکه های ارتباطی در سیستمهای چندپردازندهای[۴۲] و چند کامپیوتری[۴۳] از سوی دیگر، طراحان و پژوهشگران را بر آن داشت تا ساختار مشابهی را به عنوان جایگزین روشهای سنتی ارتباطات داخل تراشه مطرح نمایند. از این رو، ایده شبکه روی تراشه به عنوان یک راهحل امید بخش برای غلبه بر مشکلات فوق مطرح شد[۱].
معماری سیستمهای مبتنی بر شبکه روی تراشه شامل دهها و صدها هستهی همگن[۴۴] یا ناهمگن[۴۵] میباشد. در حالت همگن همه هستهها یکسان و در حالت ناهمگن هستههای پردازشی متفاوت از یکدیگر میباشند مانند ریزپردازندههای همه منظوره،پردازندهی خاص منظوره، بلوک حافظه، کنترل کننده I/O و… است که از طریق یک شبکه ارتباطی[۴۶] مبتنی بر مسیریاب[۴۷] به یکدیگر متصل شده اند. در هر گره شبکه، هسته پردازشی به یک مسیریاب متصل می شود و این مسیریاب از طریق اتصالات نقطه به نقطه در شبکه ارتباطی به سایر مسیریابها وصل می شود. ارتباط بین گرهها از طریق تولید بستههای[۴۸] داده و ارسال آنها به آدرس گره مقصد بر روی این زیرساخت ارتباطی[۴۹] انجام می شود[۱۴].
همان طور که در شکل ۲-۱ نشان داده شده است، شبکه های روی تراشه از سه قسمت اصلی تشکیل شده اند: رابط شبکه[۵۰]، مسیریابها و اتصالات[۵۱] بین مسیریابها. یک اتصال در شبکه روی تراشه شامل دو کانال فیزیکی میباشد که ارتباطی دوطرفه بین مسیریابها برقرار می کند (دو کانال یک طرفه در دو جهت مخالف). در هر گره شبکه، هسته پردازشی به یک مسیریاب متصل می شود و این مسیریاب از طریق اتصالات در یک شبکه ارتباطی به سایر مسیریابها وصل می شود. ارتباط بین گرهها از طریق تولید بستههای داده و ارسال آنها بر روی این زیرساخت ارتباطی انجام می شود[۱۴].
شکل ۲‑۱- معماری شبکه روی تراشه [۱۵]
رابط شبکه ارتباط منطقی بین هسته و مسیریاب را ایجاد می کند زیرا ممکن است هر هسته پردازشی پروتکل ارتباطی مجزا از شبکه داشته باشد بنابراین این رابط این کار را از طریق بستهبندی[۵۲] داده ها در سمت فرستنده و بازکردن بستهها[۵۳] و سپس استخراج داده های آن در سمت گیرنده برقرار می کند. به بیان دقیقتر، این رابط وظیفهی تبدیل یک پیام به چندین بسته در طرف فرستنده و ترکیب بستهها و بازسازی پیام در سمت مقابل را بر عهده دارد[۱۳]. برای این منظور، رابط شبکه وظیفهی تبدیل داده های هستهی پردازشی به بستههای قابل انتقال در شبکه های روی تراشه را بر عهده دارد. در طرف دیگر انتقال، رابط شبکه بستههای رسیده را به داده های قابل فهم برای هستهی پردازشی تبدیل مینماید. همچنین هستههای پردازشی هر کدام یک فرنکانس کاری متفاوتی دارند که برای ارتباط با یکدیگر نیاز به همزمان‌سازی[۵۴] دارند که این همزمان‌سازی توسط رابط شبکه انجام می شود[۱۴].
مسیریابها عناصر اصلی تشکیلدهنده شبکه روی تراشه میباشند که وظیفه انتقال بستهها را از هسته پردازشی مبدا به هسته پردازشی مقصد برعهده دارند. مسیریابها از میانگیرهای[۵۵] ورودی-خروجی، شبکه راهگزینی تقاطعی[۵۶] و یک کنترل کننده، تشکیل شده اند. میانگیرها را میتوان با ثباتها یا حافظه ایستا پیادهسازی کرد. معمولا هر میانگیر بخشی از یک بسته را در خود جای میدهد. در واقع لزوم استفاده از میانگیر در مسیریاب به خاطر آن است که هنگامی که در شبکه ازدحام[۵۷] رخ میدهد و بسته نمیتواند به مسیرش ادامه دهد، اطلاعات بسته در مسیریاب ذخیره شود. با توجه به شکل ۲-۲، در یک مسیریاب با p درگاه ورودی و خروجی، یک راهگزین تقاطعی به اندازه p×p ارتباط هر درگاه ورودی به هر درگاه خروجی مسیریاب را فراهم می آورد. کنترل کننده از واحدهای انتخابکننده کانال خروجی (مسیریابی)، تخصیصدهنده کانال خروجی و کانال مجازی و تخصیصدهنده اولویت تشکیل شده است و وظیفهی آن هدایت بستههای ورودی به یکی از درگاههای خروجی میباشد. به طور کاملتر میتوان اینگونه بیان کرد که عملیات محاسبهی مسیر و محاسبات واحدتخصیص کانال مجازی[۵۸] تنها برای سرآیند بستهها صورت میگیرد. در واحد محاسبه مسیر، درگاه خروجی که بسته باید به آن ارسال شود به همراه مجموعه کانالهای مجازی مجاز برای بسته، مشخص میگردند. در واحد تخصیص کانال مجازی، یکی از کانالهای مجازی که در واحد قبل مشخص شده بود، به فلیت سرآیند تخصیص داده می شود. واحد تخصیصدهنده کانال خروجی، یک نوبت زمانی برای استفاده از راهگزین تقاطعی به هر فلیت اختصاص میدهد تا فلیتها از درگاه ورودی به درگاه خروجی مناسب، بدون رخداد تصادم[۵۹] انتقال یابند. سپس بستههایی که به آنها اجازه عبور از راهگزین تقاطعی داده شده است،به کانال خروجی مناسب هدایت میشوند[۱۶].
شکل ۲‑۲- ساختار کلی مسیریاب در شبکه روی تراشه [۱۶]
همبندی شبکه
معماری شبکه بیانکننده همبندی و سازماندهی فیزیکی اتصالات داخلی شبکه است. همبندی یک شبکه با بهره گرفتن از نحوه اتصال گرههای آن که همان مسیریابها هستند، توسط پیوندها یا کانالهای ارتباطی مشخص می شود. شکل همبندی شبکه می تواند تاثیر زیادی در کارایی شبکه داشته باشد[۱۴]. انتخاب همبندی نخستین گام درطراحی شبکه است زیرا مسیریابی و سیاست کنترل جریان به شدت وابسته به الگوی ارتباطی بین مسیریابها است[۱۷]. تاکنون همبندیهای مختلفی برای شبکه روی تراشه ارائه شده است که مهمترین آنها عبارتند از: ستاره[۶۰]، توری[۶۱] ، هشت وجهی، توری مدور[۶۲]، SPIN[63] و BFT[64]. در شکل ۲-۳ بعضی از این آرایشها نمایش داده شده اند[۱۸]. Guerrier و Greinerدر[۱۸] معماری SPIN را برای ارتباطات داخلی راهگزینها بر روی تراشه پیشنهاد کرده‌اند. همانگونه که در شکل ۲-۳ ج نشان داده شده است این معماری با درختی بیان شده است که در این درخت هر گره چهار فرزند دارد و والدین در هر سطحی چهار دفعه تکرار میشوند. همچنین Kumar در [۱۸] برای NOC یک شبکه توری بر مبنای معماری اتصالات داخلی معروف به CLICHE پیشنهاد کرده است. این معماری شامل یک ساختار توری m×n از راهگزینها است که ارتباط منابع محاسباتی توسط این راهگزینها را برقرار می کند (شکل۲-۳ ب).
شکل ۲‑۳- همبندیهای مختلف شبکه بر روی تراشه، الف) توری مدور، ب) توری، ج) SPIN ، د) BFT، ه) هشت وجهی، و) توری مدور تا خورده [۱۸]
مشکل اصلی همبندی توری قطر شبکه میباشدکه تاثیر منفی در کارایی آن دارد. قطر شبکه برابر با بیشینه کوتاهترین مسیرهای ممکن بین هر دو گره در یک شبکه است[۱۹]. شبکه توری مدور در راستای کاهش تاخیر شبکه توری با حفظ سادگی توسطDally و Towlesدر[۱۸] برای معماری NOC پیشنهادشده است. همانگونه که در شکل ۲-۳ الف ملاحظه می شود در این مدل هر راهگزین ۵ درگاه[۶۵] دارد که یکی از آنها به منبع محلی متصل شده و بقیه به نزدیکترین راهگزینهای همسایه متصل شده اند و تنها تفاوت این همبندی با همبندی توری در راهگزینهای لبه شبکه میباشد که توسط کمربندهایی به راهگزینهای لبه متضاد شبکه متصل شده اند[۲۰]. به خاطر اینکه اتصالات راهگزینهای انتهایی در مدل توری مدور طولانی است و باید سیمهای بلندتری در شبکه قرار داد در نتیجه تاخیرهای اضافی در شبکه ایجاد می شود که میتوان با چند لایه کردن این مشکل را حل کرد و در نتیجه همبندی توری مدور تاخورده ایجاد می شود[۱۹].
معماری هشتوجهی که توسط Karim و همکارانش پیشنهاد شد، با توجه به شکل ۲-۳ ه، شامل ۸ گره و ۱۲ پیوند دوطرفه میباشد. هر گره یک عنصر پردازشی و یک راهگزین دارد[۱۸]. در معماری BFT، هستههای پردازشی در برگهای درخت و راهگزینها در رئوس قرار گرفتهاند. برای هر گره جفت مقدار (L,P) استفاده می شود که L، سطح گره و P موقعیت گره در آن سطح را نشان میدهد[۱۸]. ویژگی مشترک این همبندیها این است که هستههای پردازشی با کمک راهگزینهای هوشمند با یکدیگر ارتباط برقرار می کنند. در واقع راهگزینها یک بستر مقاوم را برای انتقال داده برای هستههای عملیاتی فراهم می کنند. از میان معماریهای فوق نوع توری مدور تاخورده برای پیاده سازی VLSI مناسب میباشد[۱۸]. با وجودی که شبکه های ارتباطی در معماریهای چندپردازندهای متداول به صورت چندبعدی استفاده میشوند ولی در شبکه های روی تراشه به منظور کوتاه نگه داشتن طول سیمها از همبندیهای دوبعدی استفاده می شود که در این میان همبندی توری با توجه به ساختار ساده و قابلیت پیادهسازی آسان، بیشتر مورداستفاده قرار گرفته است[۲۰].
مسیریابی و الگوریتمهای مسیریابی
مسیریابی یکی از معیارهای مهم در شبکه روی تراشه برای ارتباط بین عناصر پردازشی است. منظور از مسیریابی ارسال بستههای داده از طریق شبکه ارتباطی که توسط همبندی شبکه مشخص شده است، از یک هسته پردازشی به هستهای دیگر در شبکه میباشد. در شبکه های ارتباطی معمولا برای رسیدن از یک گره به گره دیگر، چندین مسیر مختلف وجود دارد. الگوریتمی که مسیر حرکت بسته از گره مبدا به گره مقصد را در شبکه ارتباطی مشخص می کند، الگوریتم مسیریابی نامیده می شود[۳]. در طراحی یک الگوریتم مسیریابی، معمولا ویژگیهایی مانند تطبیقپذیری[۶۶] ، عدم حضور بن بست[۶۷]، تحملپذیری خطا[۶۸] و اشکال و یافتن کوتاهترین مسیرها مورد بررسی قرار میگیرند که بسته به کاربرد، ویژگیهای مسیریابی مشخص میشوند[۱۷].
با توجه به شکل ۲-۴ دستهبندیهای متفاوتی برای الگوریتمهای مسیریابی ارائه شده است[۲۱]. در مسیریابی با آدرس یکتا[۶۹] ، بستههای داده به یک مقصد فرستاده میشوند در حالیکه در مسیریابی با چندین آدرس[۷۰] ، بستههای داده به مقصدهای مختلف فرستاده میشوند. برای ارتباطات روی تراشه، به خاطر وجود ارتباطات نقطه به نقطه بین مولفههای مختلف درون تراشه، روش مسیریابی با آدرس یکتا عملیتر به نظر می آید[۲۱]. معمولا سه معیار محل تصمیم گیری در مورد مسیر، چگونگی مشخص نمودن مسیر و میزان اهمیت طول مسیر برای تقسیم بندی این الگوریتمها به کار برده می شود. براساس محل تصمیم گیری در مورد مسیر، الگوریتمهای مسیریابی به دو دستهی مسیریابی مبدا[۷۱] و مسیریابی توزیع شده[۷۲] تقسیم میشوند. در نوع اول، مسیر در مبدا مشخص می شود و تمام اطلاعات مربوط به آن در بخش سرآیند[۷۳] بسته قرار داده می شود. در حالیکه در الگوریتمهای مسیریابی توزیع شده، در طول مسیر در مورد ادامه آن تصمیم گیری می شود. بنابراین در بخش سرآیند بسته کافی است آدرس مقصد قرار داده شود. در این روش در صورت بسته بودن مسیر امکان تعویض آن وجود دارد[۲۰]. به ترکیب مسیریابی مبدا و مسیریابی توزیعشده، مسیریابی چندمرحله‌ای[۷۴] گفته میشود. در مسیریابی متمرکزشده[۷۵] ، یک کنترل کننده مرکزی جریان داده ها را در سیستم کنترل می کند[۲۱].
بر اساس چگونگی تعیین مسیر، الگوریتمهای مسیریابی به دو دستهی تطبیقی و قطعی[۷۶] تقسیم بندی میشوند. در الگوریتمهای قطعی، تصمیم گیری فقط براساس آدرس مبدا و مقصد انجام می شود و بنابراین تمام بستههایی که دارای آدرس مبدا و مقصد یکسان هستند، ازمسیر یکسانی عبور می کنند. اما در الگوریتمهای تطبیقی علاوه بر آدرس مبدا و مقصد، ترافیک لحظهای شبکه نیز در تعیین مسیر موثر است و اگر ترافیک مسیر زیاد باشد، امکان تغییر مسیر و استفاده از مسیرهای خلوتتر وجود دارد. بنابراین بستههایی که دارای مبدا و مقصد مشترکی هستند، ممکن است از مسیرهای متفاوت با تاخیرهای مختلف برای انتقال استفاده کنند[۲۰].
الگوریتمهای قطعی معمولا پیادهسازی سادهتری دارند در حالیکه الگوریتمهای تطبیقی معمولا کارایی و تحملپذیری خطای بیشتری را فراهم می کنند. بعضی از شبکه ها از ترکیب دو نوع الگوریتم برای مسیریابی استفاده می کنند، به این ترتیب که بعضی از کانالها برای مسیریابی قطعی و بقیه برای مسیریابی تطبیقی استفاده میشوند. در نتیجه در این دسته از الگوریتمها مزایای هر دو روش به قیمت افزایش مساحت، پیچیدگی سیمکشی و احتمالا توان مصرفی، وجود خواهد داشت[۲۰].
شکل ۲‑۴- دستهبندی الگوریتمهای مسیریابی [۲۱]
براساس طول مسیر، الگوریتمهای مسیریابی به دو دستهی کمینه[۷۷] و غیر کمینه[۷۸] تقسیم میشوند. در نوع اول همیشه از کوتاهترین مسیرها استفاده می شود ولی در الگوریتمهای غیرکمینه، شرط استفاده از کوتاهترین مسیر الزامی نیست و میتوان جهت کاهش تاخیر بستهها از مسیرهای طولانیتر نیز استفاده کرد[۲۰]. در این پایان نامه به خاطر سادگی پیادهسازی از الگوریتم قطعی XY استفاده شده است. بر این اساس در ادامه این الگوریتم به طور خلاصه توضیح داده خواهد شد.
الگوریتم مسیریابی XY :
این الگوریتم از نوع الگوریتمهای قطعی میباشد. در این روش هر بسته ابتدا در جهت محور x مسیریابی می شود و آنقدر این عمل ادامه مییابد تا این که بسته به ستونی برسد که در آن ستون هسته عملیاتی مقصد قرار دارد. سپس مسیریابی در جهت محور y به همین طریق انجام میگیرد تا به هسته مقصد موردنظر برسد[۲۲]. در شکل ۲-۵ چهار حالت مختلف این الگوریتم نشان داده شده است. این الگوریتم جزء الگوریتم های کمینه است و بستهها کوتاهترین مسیر را بین مبدا و مقصد طی می کنند و برای شبکه های روی تراشه با همبندی توری و توری مدور مناسب است. در این الگوریتم آدرس هر مسیریاب با مختصات آن مشخص می شود بنابراین با فرض اینکه (Sx,Sy) ، (Dx,Dy) و (Cx,Cy) به ترتیب آدرس مسیریابهای مبدا، مقصد و مسیریاب جاری باشند، شبه کد این الگوریتم به صورت شکل ۲-۶ میباشد. با توجه به شبه کد در این الگوریتم آدرس مسیریاب فعلی (Cx,Cy) با آدرس مسیریاب مقصد(Dx,Dy) که در سرآیند بسته ذخیره شده است، مقایسه می شود. اگر آدرس مسیریاب فعلی با آدرس مسیریاب مقصد برابر باشد، بسته به درگاه محلی مسیریاب جهت تحویل به هسته پردازشی متصل به آن، فرستاده می شود. در غیر این صورت برای حرکت در راستای افقی، آدرس Dx با آدرس Cx مقایسه می شود. اگر Cx<Dx باشد، بسته به درگاه شرقی و اگر Cx>Dx باشد، بسته به درگاه غربی مسیریاب فعلی فرستاده می شود و اگر Cx=Dx باشد، به مفهوم آن است که بسته به ستون مسیریاب مقصد رسیده است و حرکت در راستای افقی پایان مییابد. در این حالت آدرسها در راستای عمودی یعنی Cy و Dy مقایسه میشوند. اگر Cy<Dy باشد، بسته به درگاه جنوبی و اگر Cy>Dy باشد، بسته به درگاه شمالی مسیریاب فعلی فرستاده می شود و اگر Cy=Dy شده باشد، به مسیریاب مقصد رسیده است[۲۳].
راهگزینی
الگوریتم مسیریابی مسیری که پیغامها باید از مبدا تا مقصد طی کنند، تعیین می‌کند در حالیکه سیاست راهگزینی مشخص می کند که هر پیغام چگونه مسیریاب را طی کند[۱۷]. به عبارتی روش راهگزینی تعیینکننده نحوه ذخیره شدن بستهها در مسیریابهای میانی و ارسال آنها به گرهی بعدی میباشد[۳]. با توجه به شکل ۲-۷ روشهای راهگزینی به طور کلی به دو دستهی راهگزینی بستهای[۷۹] و راهگزینی مداری[۸۰] تقسیم میشوند[۲۱].
شکل ۲‑۵- مسیرهای پیموده شده توسط الگوریتم XY [23]
شکل ۲‑۶- شبه کد الگوریتم مسیریابی XY [23]
در راهگزینی مداری ابتدا یک مسیر از گرهی مبدا به گرهی مقصد درشبکه رزرو می شود و سپس ارسال داده آغاز میگردد. با عبور سرآیند بسته که حاوی اطلاعات مسیریابی است از مسیریابهای بین مبدا و مقصد، در حین مسیریابی سرآیند، این مسیر برای آن جریان داده ذخیره می شود. پس از رسیدن بسته سرآیند به مقصد، یک پیغام تایید[۸۱] به مبدا فرستاده می شود تا برقراری مسیر انتقال داده را به اطلاع مبدا برساند[۳].به این ترتیب پس از برقراری مسیر، ارسال داده از مبدا به سمت مقصد شروع می شود (شکل ۲-۸). از جمله مشکلات این روش میتوان به کاهش بهرهوری منابع در شبکه (به علت عدم امکان استفادهی سایر جریانهای داده از منابع، ناشی از در انحصار قرار گرفتن منابع تا پایان عملیات انتقال داده برای یک جریان داده) و سربار زمان برپایی مدار اشاره نمود. از طرفی، این روش راهگزینی، برای پیامهای طولانی و جریانهای ارتباطی که نیاز به پهنای باند تضمین شده دارند، بسیار مناسب است[۳].
راهگزینی بستهای، سیاست غالب در شبکه های روی تراشه میباشد. در این روش با توجه به شکل ۲-۹، پیغامها به تکههایی با اندازه ثابت به نام بسته شکسته میشوند و هر بسته به صورت مستقل مسیریابی می شود. بنابراین هر بسته باید اطلاعات کنترلی و مسیریابی را برای رسیدن به گرهی مقصد به همراه داشته باشد[۲۰]. با توجه به شکل، در این روش هنگامی که یک بسته توسط گرههای میانی دریافت می شود، چون اطلاعات مسیر را دارد، منتظر دریافت سایر بستههای یک پیغام نمیماند. به همین دلیل، بستههای یک پیغام میتوانند به طور همزمان از چندین مسیر عبور کرده و به مقصد برسند[۱۸].
شکل ۲‑۷- روشهای راهگزینی [۲۱]
شکل ۲‑۸- راهگزینی مداری [۱۸]
شکل ۲‑۹- راهگزینی بستهای [۱۸]
راهگزینی بستهای همانگونه که در شکل ۲-۷ نشان داده شده است به سه دسته تقسیم می شود[۲۱]:
راهگزینی ذخیره و ارسال[۸۲]: در این روش پیامها به بخشهای مستقل کوچکتری به نام بسته تقسیم میشوند و فقط زمانی که بسته به طور کامل به کانال ورودی یک مسیریاب برسد، می تواند به کانال خروجی مدنظر فرستاده شود. در نتیجه، در این روش چون کل بسته ذخیره می شود، حافظه میانگیر زیادی مورد نیاز است. همچنین اینکار افزایش تاخیر بستهها را به دنبال دارد. از طرفی، این روش برای پیامهای کوتاه که تعداد آنها زیاد نیست، بسیار مناسب است زیرا برخلاف روش راهگزینی مداری، سربار زمان برپایی مدار وجود ندارد[۳].
راهگزینی برشی[۸۳]: در این روش کوچکترین واحد داده بسته نمی باشد، بلکه هر بسته به واحدهای کوچکتری به نام فلیت تقسیم می شود و به محض آزاد بودن درگاه خروجی برای یک بسته، فلیتهای آن بسته میتوانند فرستاده شوند، بدون اینکه نیاز باشد کل بسته به درگاه ورودی رسیده باشد. در نتیجه، تاخیر بستهها در این روش نسبت به روش ذخیره و ارسال کاهش مییابد. اگر درگاه خروجی یک بسته اشغال باشد، کل بسته در حافظه میانگیر ذخیره می شود[۳].
راهگزینی خزشی[۸۴]: این روش راهگزینی بسیار شبیه راهگزینی برشی است. با این تفاوت که در این روش راهگزینی، اندازه حافظه میانگیر مورد نیاز نسبت به روش برشی کاهش مییابد[۳]. در روش مذکور، همانطور که در شکل ۲-۱۰ مشاهده می شود، یک بسته به واحدهای کوچکتری با طول ثابت به نام فلیت تقسیم می شود. هر بسته یک فلیت سرآیند[۸۵] دارد که شامل اطلاعات مسیریابی است و ابتدا مسیریابها را طی و با توجه به اطلاعاتش مسیر را مشخص می کند سپس سایر فلیتها همان مسیر تعیین شده را میپیمایند. در این روش به دلیل اینکه بسته به واحدهای کنترلی کوچکتر شکسته می شود، به فضای میانگیر کمتری نیاز دارد و اندازه حافظه میانگیر ورودی به اندازه چندین فلیت است[۱۱]. درشبکههای ارتباطی متداول، عرض کانالهای فیزیکی به چند بیت محدود میشوند. بنابراین فلیتها معمولا به قسمت هایی شکسته میشوند که فیت نام داشته و تعداد بیتهای آنها برابر عرض کانال فیزیکی در شبکه میباشد. در شبکه های روی تراشه عرض کانالها به مراتب بیشتر است ولی عناصر حافظه، مساحت و توان مصرفی آنها به عنوان یک عامل محدود کننده باعث شکستن فلیتها به فیتها می شود[۲۰].
