بخشی از مقاله
ارائه یک الگوریتم مسیریابی تحمل پذیراِشکال با قا بلیت بازپیکربندی در شبکه روی تراشه
خلاصه
شبکه روی تراشه به عنوان زیر ساخت مناسب جهت ارتباط بین واحدهای پردازشی در یک تراشه معرفی شده است. از طرفی کوچک شدن ادامهدار ابعاد ترانزیستورها و افزایش چگالی آنها روی تراشه، احتمال رخداد اِشکالهای متعددی در هنگام ساخت و حین کار سیستم را افزایش داده است. از اینرو مواجهه با اِشکال یکی از چالش های مهم در طراحی سیستم روی تراشه درفنّاوری زیر میکروناست. بر همین اساس در این مقاله یک الگوریتم مسیریابی تحمل پذیر اِشکال شبکه روی تراشه با قابلیت باز پیکربندی ارائه شده است. نتایج شبیهسازی بیانگر آن است که الگوریتم پیشنهادی با سربار مساحتی معقول، عملکرد مناسبی از منظر میانگین تعداد گام ارسال، راندمان و مصرف انرژی دارد
.1 مقدمه
پیشرفتهای که سالانه در تکنولوژی مدارات مجتمع سیلیکونی جهت ساخت قطعات در مقیاس کوچکتر رخ میدهد طراحان را قادر به مجتمع سازی یک سیستم پیچیده با تعداد زیادی واحد عملیاتی به نام هسته نموده است. انتظار میرود که با هر نسل تکنولوژی سیلیکون، تعداد زیادی از این هستهها روی یک تراشه جای گیرد1]و .[2 طبق پیش بینی نقشه راه برای نیمه هادیها ITRS در سال 2020، در پردازندههای آینده تعداد هستههای پردازشی می تواند بالغ به هزار عدد برسد.[3] در مراکز صنعتی و تحقیقاتی افق ترسیمی برای پردازندههای آینده وجود صدها و حتی هزاران هسته روی یک تراشه می باشد .[3] از تلاشهای اولیه که در این راستا انجام شده می توان شرکت اینتل را نام برد که یک پردازنده 80 هسته ای در تکنولوژی 65 نانومتری برای اهداف تحقیقاتی ارائه کرده است.[4]
با افزایش تعداد هسته های پردازشی و پیچیدهتر شدن سیستم بر تراشه، استفاده از گذرگاهها مشترک جهت ارتباط بین هسته ها با مشکل مواجه شد در این راستا ایده شبکه بر تراشه مطرح شد که در آن هستهها بر اساس یک زیرساخت ارتباطی شامل مسیریابها از طریق لینکهای ارتباطی که شبکه میان ارتباطی نامیده میشوند، به یکدیگر متصل میگردند.[5] شبکه بر تراشه به عنوان شبکهای میان ارتباطی در سطح تراشه، بهرهوری و کارایی بالاتری از سیستم را به ارمغان میآورد.فنّاوری شبکه روی تراشه مزایایی از قبیل کارآیی بالا، ساخت یافته بودن، قابلیت استفاده مجدد و مقیاس پذیری دارد.[6] اما روند کوچک شدنفنّاوری پیامدهایی از جمله کاهش سطوح ولتاژ منبع تغذیه و منطق و کوچکتر شدن ظرفیت خازنهای مدار و را به همراه دارد. این پیامدها حساسیت ترانزیستور، لینکهای ارتباطی را در برابر انواع نویزهای محیطی که میتوانند منجر به ایجاداِشکالهای گذرا و دائمی شوند را افزایش داده است[7]با. افزایش اِشکالات، طراحی سیستمهای تحملپذیراِشکال که بتوانند مانع از آثار مخرب آنها شوند اهمیت ویژه ای دارد. به منظور تحمل پذیری اِشکال روشهای مختلفی ارائه شده است که در یک تقسیم بندی کلی میتوان آنها را به دو دسته کلی ساختارهای تحمل پذیر اِشکال و الگوریتمهای مسیریابی تحمل پذیر اِشکال تقسیم کرد.[8] در این مقاله تمرکز بر الگوریتمهای مسیریابی تحمل پذیر اِشکال جهت مدیریت اِشکالات دائمی است.
الگوریتمهای مسیریابی تحملپذیراِشکال بیشتر برای مقاوم کردن شبکه ارتباطی در برابر اشکالهای دایمی ارائه شده اند. در [8] مروری بر الگوریتمهای مسیریابی تحمل پذیر اشکال شده است به عنوان مثال در این مرجع بیان شده است که با استفاده از یک سری ارتباطات تصادفی مشابه با پروتکلهای تصادفی گاسیپ هنگام وقوع اشکال دایمی یا گذرا، در نهایت بسته درست را به مقصد میرساند مشکل اصلی این روش این است که تنها برای ترافیک کم مفید میباشد و در ترافیک متوسط یا زیاد این روش باعث تولید ترافیک زیاد میباشد. علاوه بر این اشاره ای به استفاده از الگوریتمهای فلادینگ و رندوم واک روشی جهتتحِمل پذیریاِ شکالهای دائمی ارائه شده است7]و .[8 در ا ین مراجع یک الگوریتم مسیریابی بر پایه مسیریابی منبع بررسی شده است. این الگوریتم از دو مرحله کشف مسیر و نگهداری مسیر تشکیل شده است. بدین روش گرهها مسیرهای میان یک منبع و تمام مقصدهای موجود در شبکه بر روی تراشه را کشف و سپس همزمان با استفاده از آنها، نگهداری از آنها را نیز برعهده میگیرند. [8] یک ساختار برای مسیریاب شبکه بر روی تراشه و الگوریتم مسیریابی مربوط به آن برای مقابله با اشکالهای دایمی در لینکها بررسی شده که مانند قبلی از دو مرحله تشکیل شده است. در مرحله اول، شبکه برای یافتن مسیری میان هر جفت منبع-مقصد مورد بررسی قرار میگیرد. این عمل پس از هر شروع مجدد یا طی پیکربندی مجدد سیستم بعد از هر عیب یابی، انجام میشود. در مرحله دوم مسیرهای پیدا شده و ذخیره شده، برای ارتباطات دادهای در وضعیت عادی سیستم مورد استفاده قرار میگیرند. بهرحال همچنان نیاز به طراحی الگوریتمهای مسیریابی به ویژه با سربار تحمیلی مساحتی و توان مصرفی کم است تا در کاربردهای مختلف حق انتخاب برای طراح سیستم روی تراشه فراهم شود.
.2 رویکرد پیشنهادی:
در این معماری، الگوی اِشکال بلاکی محدب از مرجع [9] با اعمال تغییراتی در نظر گرفتهشده است. در این الگو، اِشکال گره و پیوند لحاظ شده است. اگر یک گره خراب شود کلیه پیوندهای متصل به آن نیز اِشکالدار در نظر گرفته میشود. اگر کانال فیزیکی در هر جهت خراب شود، کل پیوند دوجهته خراب در نظر گرفته میشود. تمرکز اصلی این پژوهش بر اِشکال دائمی گره است. در این الگو ، هر گره از وضعیت گرههای همسایه مطلع هستند و با ارسال و دریافت بستههای خاص ناحیه اِشکال را مشخص میکنند. تغییرات پیشنهادی ما در این الگو به این صورت است که شبکه را مطابق شکل 1 به پنج منطقه مجازی تقسیم میشود. یکی از آنها منطقه مرکزی به نام Center-Zone که مرزهای شبکه را در برنمیگیرد. چهار منطقه دیگر مربوط به لبههای تراشه میشود که با توجه به مرز مربوطهشان نامهای Right-Zone، Left-Zone ، Up-Zone و Down-Zone دارند. با این تقسیمبندی هر ناحیه اِشکال به یکی از این مناطق تعلق میگیرد. با توجه به الگوی اِشکال،
هر مسیریاب یک ثبات وضعیت با مقدار اولیه صفر دارد که مفهوم آن وضعیت نرمال گره مربوطه است. گرههای اطراف یک ناحیه اِشکال معین، در ثبات وضعیت خود علاوه بر منطقهناحیه اِشکال، موقعیت جغرافیایی خود را نسبت به ناحیه اِشکال (یعنی شمال، جنوب، شرق و...) ذخیره میکنند. در این مقاله، فرض است شناسایی اِشکالات به صورت استاتیکی است یعنی با وقوع اِشکال دائمی سیستم ری سِت میشود و یک برنامه سیستمی اجرا میشود تا مؤلفههای اِشکالدار و نواحی اِشکال مشخص گردد.
شکل:1 تقسیم بندی مجازی شبکه به 5 منطقه
همانطور که گفته شد با توجه به محدودیتهای مساحتی روی تراشه ، واحد مسیریابی باید ساده و کم هزینه باشد در همین راستا، یک الگوریتم مسیریابی تطبیقی و تحملپذیر اِشکال بر اساس الگوریتم مسیریابی کمینه غرب در اول ارائه شده است. الگوریتم مسیریابی کمینه غرب در اول یک نمونه از پروتکلهای تصمیمگیرنده در مبدأ است که مزایایی مانند سرعت بالا و هزینه طراحی کم دارد.[10] در این الگوریتم اگر مقصد در غرب باشد به صورت قطعی مانند الگوریتم XY عمل میکند و در غیر این صورت به صورت تطبیقی عمل میکند با این شرط که در ادامه مسیریابی حرکتی به سمت غرب ندارد. درواقع با این عمل چرخشهای NW و SW (شمال به غرب و جنوب به غرب) ممنوع میشود تا از وقوع بنبست جلوگیری شود. اما بههرحال این الگوریتم دارای تطبیقپذیری جزئی است[10]مثلاً.اگر ناحیه اِشکال در سمت راست گره Right-Zone باشد، الگوریتم هنگام حرکت بستهها به سمت غرب درست کار میکند اما اگر ناحیه اِشکال در دیگر مناطق شبکه (شکل (1 تشکیل شوند، حرکت به سمت غرب با چالش روبرو میشود. بنابراین این الگوریتم اصلاحاتی نیاز دارد تا مسیرهای شکسته شده را بازیابی کنداصلاحات. بر اساس موقعیت ناحیه اِشکال در مناطق تعریف شده انجام میگیرد که به موجب آن مسیرهای شکسته شده با مسیرهای قطعی جدیدی جایگزین میشود. درواقع گرههای اطراف ناحیه اِشکال بر اساس ثباتهای وضعیتشان بستهها را به درگاه مناسب هدایت میکنند. برای مثال اگر ناحیه اِشکال در منطقه Center-Zone قرار داشته باشد و بستهها قابل هدایت به سمت غرب نباشد، الگوریتم بستهها را به صورت قطعی به سمت جنوب ارسال میکند. برای نواحی اِشکال در دیگر مناطق نیز سناریو مشابه منطقه Center-Zone میتوان در نظر گرفت. در این مناطق موقع نیاز به حرکت
به سمت غرب که مسیر شکسته شده، بستهها با توجه به مقصد نهایی شان به سمت شمال یا جنوب هدایت میشوند. بهر حال با تغییر قوانین پایه الگوریتم کمینه غرب در اول منجر به چرخشهای غیر مجاز این الگوریتم میشود که این امکان وقوع بنبست را به وجود میآورد[5]حضور. ناحیه اِشکال در منطقه Center-Zone و اعمال سیاست جدید مسیریابی باعث استفاده از چرخش غیر مجاز S-Wدر اطراف ناحیه اِشکال میشود. مطابق گراف وابستگی کانال این سناریو میتواند باعث بروز بنبست در شبکه میشود. برای جلوگیری از بنبست یک راهحل مبتنی بر چرخش پیشنهادشده است که در آن بهجای چرخش S-W ، چرخش E-Sدر اطراف ناحیه اِشکال غیر مجاز شود. از اینرو مسیرهای دیگر نیز مطابق قوانین چرخش جدید اصلاح میشود. بستههای که نیاز به چرخش E-S دارند به سمت غرب هدایت میشوند، البته این قوانین باعث میشود
که طول بعضی از مسیرها در مقایسه با الگوریتم پایه بیشتر شودباید. توجه داشت که تغییر قوانین برای نواحی اِشکال در دیگر مناطق منجر به بنبست نمیشود چونکه یک لبه تراشه در ناحیه اِشکال درگیر است و از انتظار چرخشی جلوگیری میکند. مسئله دیگری که باید توجه داشت نزدیکی دو ناحیه اِشکال به یکدیگر است. با اعمال سیاستهای جدید رفتار نرمال الگوریتم مسیریابی کمینه غرب در اول برای گرههای مجاور به گرههای اطراف ناحیه اِشکال نیز ممکن است تغییر کند که امکان وقوع بنبست را به وجود میآورد. جهت اطمینان از جلوگیری این اتفاق فاصله بین دو ناحیه اِشکال باید بیش از دو گام باشد که گرهای اطراف برهم اثر نگذارند. اگر فاصله دو ناحیه اِشکال کمتر بود این دو ناحیه با هم ترکیب میشوند یعنی تعدادی از گرههای سالم جزء ناحیه اِشکال در نظر گرفته میشود که بهنوعی قربانی میشوند.
