پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,682 |
| تعداد مقالات | 13,775 |
| تعداد مشاهده مقاله | 32,269,375 |
| تعداد دریافت فایل اصل مقاله | 12,764,836 |
افزایش کارآیی و قابلیت اطمینان شبکه روی تراشه دوبعدی با کاهش تعداد لینکهای عبوری | ||||||||||||||||
| هوش محاسباتی در مهندسی برق | ||||||||||||||||
| مقاله 9، دوره 11، شماره 3، مهر 1399، صفحه 95-106 اصل مقاله (1.72 M) | ||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/isee.2020.117136.1231 | ||||||||||||||||
| نویسندگان | ||||||||||||||||
| سید امین علوی1؛ سید جواد سید مهدوی چابک* 2 | ||||||||||||||||
| 1دانشجوی مقطع دکتری، دانشکدۀ مهندسی برق - واحد مشهد - دانشگاه آزاد اسلامی - مشهد - ایران | ||||||||||||||||
| 2استادیار، دانشکدۀ مهندسی برق - واحد مشهد - دانشگاه آزاد اسلامی - مشهد - ایران | ||||||||||||||||
| چکیده | ||||||||||||||||
| شبکه روی تراشه، زیرسیستم ارتباطی درون یک مدار مجتمع است که ارتباط بین پردازندهها در سیستم روی تراشه را فراهم میسازد. برای رسیدن از یک گره به گره دیگر، چندین مسیر مختلف وجود دارد؛ بنابراین باید الگوریتم مسیریابی وجود داشته باشد تا بهوسیلۀ آن مسیر رسیدن به مقصد را به دست آورد. در این مقاله الگوریتمی مبتنی بر کاهش مسیر عبوری برای رسیدن یک بسته از مبدأ به مقصد ارائه شده است؛ این الگوریتم قادر است علاوه بر بالابردن قابلیت اطمینان، باعث کاهش تأخیر، توان مصرفی و افزایش کارآیی شبکه روی تراشه شود و این در شرایطی است که بیشتر شبکههای تحملپذیر خطای ارائهشده در این حوزه بهازای رسیدن به قابلیت اطمینان بالاتر، پارامترهایی ازقبیل تأخیر، توان مصرفی و پیچیدگیهای مداربندی را افزایش میدهند. روش ارائهشده با کمترین تغییرات سختافزاری و پیچیدگیمداری باعث بهبود کارآیی شبکه میشود. مسیر گذراندهشده با بسته برای رسیدن به مقصد کاهش مییابد و این کاهش مسیر یعنی عبور از تعداد لینک و مسیریاب کمتر و کاهش احتمال برخورد با لینکها و مسیریابهای معیوب و افزایش قابلیت اطمینان شبکه. همچنین عبور از تعداد لینکها و مسیریابهای کمتر موجب کمترشدن تأخیر و توان مصرفی شبکه نیز خواهد شد. | ||||||||||||||||
| کلیدواژهها | ||||||||||||||||
| شبکه روی تراشه؛ شبکه روی تراشه با کارآیی بالا؛ شبکه روی تراشه با قابلیت اطمینان بالا؛ شبکه روی تراشه تحملپذیر خطا | ||||||||||||||||
| اصل مقاله | ||||||||||||||||
|
1- مقدمه[1] ایدۀ شبکه روی تراشه با الهامگرفتن از شبکههای کامپیوتری مطرح شد [1]، [2] و [3]. ایدۀ اصلی، استفاده از تکنیکها و روشهای موجود در شبکههای کامپیوتری و چند پردازندهای در سطح تراشه است. شبکه روی تراشه امکان استفاده از راهحلهای کاملاً سنتزپذیر را فراهم میکند؛ بهگونهای که میتواند بهصورت اتوماتیک برای هر طراحی تراشه بهینه شود. قرارگرفتن تعداد هستههای بیشتر روی یک تراشه بهدلیل افزایش بسیار زیاد ترانزیستورها در آینده باعث بروز مشکلاتی در ارتباطات بین هستهها خواهد شد. برای رسیدن به زیرساخت ارتباطی مطلوب، پژوهشگران ایدۀ استفاده از شبکههای مبتنی بر بسته را ارائه دادند، مشابه آنچه در شبکههای کامپیوتری استفاده میشود [4]. این شبکهها علاوه بر اینکه دارای مقیاسپذیری نامحدودی دستکم ازنظر فیزیکیاند، دارای ویژگی استانداردبودن و فراهمکردن یک ساختار دارای قابلیت استفاده مجدد نیز هستند. این قابلیتها برای طراحان تراشه اهمیت زیادی دارند؛ زیرا زمان طراحی را کوتاهتر میکنند و محصولات را زودتر به بازار میرسانند. کوچکترشدن ظرفیت خازنهای مدار و کاهش سطوح ولتاژ منبع تغذیه و لاجیک، حساسیت گیتها، فلیپ فلاپها و واحدهای حافظه استفادهشده را در برابر انواع نویزهای محیطی، ذرات باردار و نویزهای همشنوایی افزایش داده است که به ایجاد خطاهای گذرا و دایمی منجر میشوند [5]؛ به همین دلیل، طراحی سیستمهای انتقال اطلاعات تحملپذیر در برابر اشکال که بتوانند مانع از دست رفتن و انتقال ناصحیح اطلاعات شوند، اهمیت ویژهای یافته است [6]. سیستم تحملپذیر خطا، سیستمی است که وظیفۀ خود را بهدرستی حتی با وجود خطاهای سختافزاری و اشتباهات نرمافزاری ادامه میدهد. تحمل خطا یکی از نگرانیهای عمده در عملکرد سیستمهای دیجیتال است و برای اینکه سیستم صحیح کار کند و تأثیر خرابی بر عملکرد آن کاهش یابد، باید ابتدا خطا پیشبینی، سپس مدیریت و کنترل شود. روشهای تحمل خطا برای پیشبینی خرابی و انجام یک اقدام مناسب قبل از خطا است. افزایش قابلیت اطمینان عملکرد سیستمهای دیجیتال با پیادهسازی ساختار تحملپذیر خطا، امکانپذیر است. تحملپذیری خطا در یک سیستم با افزونگی در سختافزار، نرمافزار، اطلاعات یا محاسبات به دست میآید. این قبیل افزونگی در پیکربندی ایستا، پویا یا ترکیبی پیادهسازی میشود [7]. افزونگی سختافزاری با فراهمکردن دو یا تعداد بیشتری نمونههای فیزیکی از یک مؤلفۀ سختافزاری به دست میآید. هدف مهم در طراحی سیستم تحملپذیر خطا این است که سیستم بهصورت خودکار، خود را در برابر بخشهای دچار خرابی بازیابی کند؛ بدون اینکه این امر تأثیری در عملکرد کلی سیستم داشته باشد. شبکه روی تراشه تحملپذیر خطا برای انتقال کامل و صحیح اطلاعات در سیستمهای روی شبکه ارائه شده است. در سالهای اخیر الگوریتمهای بسیاری برای مسیریابی شبکه روی تراشه ارائه شدهاند که بیشتر بر بهبود کارایی، قابلیت اطمینان، تأخیر و توان مصرفی متمرکز بودهاند. در ادامه برخی از آنها معرفی شدهاند. بسیاری از شبکههای روی تراشه تحملپذیر خطا برای رفع مشکل بنبست از حذف برخی چرخشها یا کانال مجازی استفاده میکنند که درنهایت موجب کاهش کارآیی سیستم میشود. در [8] روش حذف بنبست با حفظ کارآیی بالای شبکه بدون استفاده از کانالهای مجازی و حذف چرخشها پیشنهاد شده است. در این روش از بافر مقاوم - یک بافر FIFO که از فضای موجود در کش استفاده میکند - برای اجتناب از بنبست استفاده شده است. بافر مقاوم فقط در زمان رخداد خطا از فضای کش گره مدنظر استفاده میکند و فضای کش گرههای دیگر تحت تأثیر قرار نمیگیرند. این روش کارآیی شبکه را در مقایسه با شبکههای تحملپذیر خطا که از روش حذف چرخش و کانال مجازی استفاده میکنند، 2 تا 3 برابر بهبود میبخشد و سرآمد فضای مسیریاب و توان مصرفی را کاهش میدهد. در [9] الگوریتمی ارائه شده است که در آن شبکۀ کنترل و شبکۀ داده از یکدیگر جدا هستند. شبکۀ کنترل بهصورت مرکزی و با هستۀ شبکه مدیریت میشود؛ اما شبکۀ اطلاعات بهصورت گسترده است. این الگوریتم مسیریابی دارای مزایای زیر است: 1- هسته مرکزی دارای دید کامل به کل شبکه است و اطلاعات ترافیک و لینکهای معیوب را دارد و بهترین مسیر برای انتقال اطلاعات را در شبکه داده مشخص میکند؛ 2- محاسبات و تخصیص مسیر به بستهها، حساسیت کمتری به فاصله مبدأ و مقصد دارند؛ 3- دارای سربار سختافزاری کمتری نسبت به سایر الگوریتمها است؛ چون نیازی به سوئیچهای پیچیده، بافرها و جداول مسیریابی ندارد؛ 4- نیازی به اطلاعات اضافی مبدأ و مقصد در بستهها و فلیتها ندارد. یک معماری مسیریاب شبکه روی تراشۀ مطمئن در [10] ارائه شده است که توانایی تحمل خطاهای سخت و نرم را با استفاده از تکنیکهایی مانند افزونگی فضایی، بهرهگیری از چرخههای باطل و بایپس منابع معیوب دارد. با استفاده از زمان میانگین به شکست و معیارهای عامل حفاظت سیلیکون، به حداقل 5/1 برابر قابیلت اطمینان بیشتر از معماریهای موجود مسیریابهای مقاوم در برابر نقص دست مییابد. این روش یک معیار جدید به نام ضریب بهبود خطای نرم معرفی میکند و نشان میدهد تحمل خطای نرم در مقایسه با مسیریاب مبنای حفاظتنشده، 3 برابر بهبود یافته است. این بهبود قابلیت اطمینان، با ایجاد سربار مساحت و توان بهترتیب برابر با 34% و 31% انجام میشود و همچنین در حضور خطاها، تأخیر 10% افزایش مییابد. در [11] یک همبندی جدید به نام شبکۀ بازگشتی متصل صلیبی سلسلهمراتبی (HCCR) و یک الگوریتم مسیریابی کوتاهترین مسیر برای HCCR معرفی شده است. برای همۀ استراتژیهای سوئیچینگ، قطر شبکه را کوچکتر و اتصالات شبکه (در بافر و لبهها) را بهبود بخشیده و تأخیر انتشار را در ارتباط نقطهبهنقطه کاهش داده است. یک مکانیزم کدینگ با کارایی بالا به نام PS-Fibo برای کمکردن خطاهای کراستاک سیمهای شبکه روی تراشه پیشنهاد شده است [12]. مکانیزم کدینگ PS-Fibo از مزایای یک سیستم عددی جدید بهره میبرد که نهتنها تمام مسیرهای معکوس سهگانه را حذف میکند، در رنج وسیعی از عرضهای شبکه روی تراشه کاربرد دارد. در [13] یک توپولوژی به همراه الگوریتم مسیریابی اختصاصی براساس کوتاهترین مسیر به سمت مقصد به نام PentaNOC ارائه شده است که دارای قابلیت مقیاسپذیری بالا، تعداد عبورهای کمتر از لینکها، تعداد دورهای کمتر، قطر کوچکتر، تنوع بالای مسیرها و همچنین پهنای دوبخشی است. توپولوژی پیشنهادشده براساس قرارگرفتن تعدادی از بلوکهای پنجوجهی بهصورت چیدمان آبشاری با تعداد زیادی از لینکها تشکیل شده است که پنجوجهیها را در سطوح مختلف به یکدیگر ارتباط میدهند. بهعلت انتخب مسیرهای کوتاه برای رسیدن به مقصد، تأخیر بسته، کاهش و همچنین توان عملیاتی شبکه روی تراشه بهبود یافته است. در ادامه و در بخش 2، شبکه روی تراشه و ساختار آن توضیح داده شده است. در بخش 3، شبکه روی تراشۀ پیشنهادشده تشریح شده است. در بخشهای 4 و 5 بهترتیب پارامترهای الگوریتم پیشنهادشده، بررسی و نتایج شبیهسازی آن بیان شدهاند و درنهایت نتیجهگیری در بخش 6 بیان شده است. 2- شبکه روی تراشه شبکه روی تراشه، زیرسیستم ارتباطی درونمدار مجتمع است که ارتباط بین پردازندهها در سیستم روی تراشه را فراهم میسازد. ازجمله مهمترین موارد شایان توجه در طراحی یک مسیریاب شبکه روی تراشه، همبندی، الگوریتم مسیریابی و نوع سوییچینگ آناند. منظور از همبندی، چگونگی اتصال عناصر پردازشی به یکدیگر است [14]. به عبارتی یک همبندی نوعی گراف است که گرههای آن، عناصر پردازشی شبکهاند و یالهای آن اتصالات موجود مابین این عناصرند. شکل (1) نحوۀ اتصالات مسیریابها در همبندیهای توری و توری مدور را نشان داده است. ساختار منظم هر دو همبندی، پیادهسازی آنها را آسان میسازد. مشکل اصلی همبندی توری، قطر شبکه است که تأثیری منفی در لختی آن دارد. شبکۀ توری مدور در راستای کاهش تأخیر شبکۀ توری با حفظ سادگی آن مطرح شده است [15]. تنها تفاوت موجود بین شبکۀ توری و توری مدور، سوییچهای لبۀ شبکهاند که با کمربندهایی به سوییچهای لبه متضاد شبکه متصل شدهاند. به عبارت دیگر، در شبکۀ توری مدور، تمامی سوییچها دارای پنج پورت فعالاند که یکی از آنها به منبع محلی و چهار پورت دیگر آن به مسیریابهای همسایه متصل شدهاند؛ درحالیکه در همبندی توری سوییچهای لبهای از سه پورت تشکیل شدهاند.
شکل (1): همبندی توری در مقابل همبندی توری مدور نکته درخور تأمل دیگر در یک مسیریاب شبکه روی تراشه، الگوریتم مسیریابی مربوط به آن است؛ برای مثال، الگوریتم مسیریابی XY بهعلت سادگی در پیادهسازی و همچنین عاری ازبنبست بودن، در بیشتر طراحیها و آزمایشهای مربوط به شبکه روی تراشه شایان توجه قرار گرفته است [16] و [17]. درواقع بر طبق این الگوریتم، ابتدا حرکت در بعد افقی انجام میگیرد و پس از اتمام آن، حرکت در جهت عمودی شکل میپذیرد. برای استفاده از لینکهای اضافهشده در همبندی توری مدور در مقایسه با همبندی توری، تغییراتی در نحوۀ پیادهسازی الگوریتم مسیریابی XY لازم است که در ادامه توضیح داده شده است. با توجه به شکل (1)، بهرهگیری از همبندی توری مدور، علاوه بر اینکه موجب همسانشدن تمامی مسیریابهای درون شبکه از لحاظ تعداد پورتها میشود، قابلیت کاهش فاصلۀ برخی از مسیریابها را نیز دارد؛ برای نمونه، اگر دو مسیر نشان داده شده در شکل 1- الف با هم مقایسه شوند، مشخص است انتخاب مسیر شماره 2 با عبور از تعداد مسیریابهای کمتری ما را به مقصد میرساند. به این ترتیب در پیادهسازی الگوریتم مسیریابی XY علاوه بر قواعد الگوریتم، باید به لینکهای اضافهشده در همبندی توری مدور نیز توجه داشت. انجام این کار با یک مقایسۀ ساده انجامپذیر است. به این ترتیب که پیش از انتخاب پورت خروجی مدنظر، با در نظر گرفتن اختلاف بین مسیریاب فعلی و مسیریاب مقصد تصمیم میگیریم کدام مسیر را انتخاب کنیم. نکته آخری که باید دربارۀ طراحی مسیریاب در نظر گرفته شود، انتخاب سوییچینگ مدنظر برای آن است. تکنیکهای مربوط به سوییچینگ شامل تصمیمگیریهایی است که در آن زمان و نحوۀ اتصالات بین ورودیها و خروجیها در مسیریابهای میانی تعیین میشود. همچنین این تصمیمگیریها شامل مدت زمانی نیز میشود که در آن پیغامها میتوانند ازطریق مسیرهای تعیینشده منتقل شوند. سوییچینگ wormhole امروزه بهمنزلۀ یکی از رایجترین انواع در پژوهشهای مربوط به مسیریابهای شبکه روی تراشه شایان توجه قرار گرفته است [18]. در این روش برخلاف حالت سوییچینگ بستهای، لزومی ندارد ابتدا کل بسته بهصورت کامل دریافت، سپس عملیات مسیریابی برای آن انجام شود. در این روش یک مسیریاب میتواند عملیات ارسال مربوط به سرآیند و سایر بیتهای دادهای را بهمحض اتمام عملیات مسیریابی و در صورت وجود بافر خالی در پورت خروجی انتخابشده انجام دهد. به این ترتیب دیگر لزومی ندارد بستهها در بافرهای خروجی ذخیره شوند و بلافاصله درون بافرهای ورودی، گره بعدی قرار میگیرند. در این روش تنها سرآیند است که زمان تصمیمگیری برای مسیریابی و زمان تأخیر مربوط به سوییچینگ را در هر مسیریاب حس میکند. این امر بدین علت است که انتقال بهصورت پایپلاین انجام میگیرد و پس از ارسال سرآیند، فلیتهای بعدی پشت سر هم (البته در صورت نبود بنبست در مسیریابهای پیشرو) ارسال میشوند. در این روش در هر لحظه از زمان یک بسته مسدودشده درون چندین مسیریاب، بافر میشود؛ زیرا سایز بافرها معمولاً از سایز یک بسته کمتر است. تفاوت اساسی این روش با روش مشابه VCT در آن است که در اینجا، واحد کنترل جریان یک تک فلیت است؛ بنابراین بافرهایی با سایزهای کوچکتر استفاده میشوند و توان مصرفی نیز کاهش مییابد [19] و [20]. 3- شبکه روی تراشه پیشنهادشده شکل (2) یک شبکه روی تراشه وسیع با همبندی توری را نشان میدهد. مشکل اصلی همبندی توری قطر شبکه است که تأثیری منفی در لختی آن دارد و باعث بالابودن تأخیر در ارسال بستههایی میشود که فاصلۀ زیادی تا مقصد دارند و علاوه بر آن، به علت عبور بسته از لینکها و مسیریابهای زیاد، امکان دچارشدن به خطا در بسته و از بین رفتن آن بیشتر میشود؛ برای مثال، در شکل (2) بسته برای رسیدن به مقصد باید از 11 لینک عبور کند. با کاهش تعداد لینکهای عبوری بسته، امکان مواجهشدن با لینک معیوب کاهش مییابد و شبکه مطمئنتر خواهد شد. علاوه بر آن، مسیر کوتاه میشود و زمان مسیریابی در مسیریابها کاهش مییابد که موجب کاهش تأخیر و درنهایت کاهش توان مصرفی میشود.
شکل (2): همبندی توری شبکه روی تراشه 8×8 پیشنهاد ارائهشده، کاهش تعداد لینکهای عبوری در شبکههای بزرگ است؛ به نحوی که شبکۀ بزرگ به نواحی مجزایِ متشکل از شبکههای کوچکتر، تقسیم و هر کدام از نواحی دارای یک مسیریاب مرکزی شوند. با توجه به مسیر بسته، اگر مبدأ و مقصد به یکدیگر نزدیک باشند، از الگوریتم مسیریابی XY برای ارسال اطلاعات استفاده میشود؛ اما در صورتی که مقصد فاصلۀ زیادی از مبدأ داشته باشد، ابتدا بسته به مسیریاب مرکزی ناحیۀ خود ارسال میشود، سپس به مسیریاب مرکزی ناحیۀ مقصد و درنهایت به مقصد ارسال میشود.
شکل (3): تقسیم شبکه روی تراشه 18×18 به ناحیههای 9×9 شکل (3) یک شبکه روی تراشه 18×18 را نشان میدهد که به ناحیههای 9×9 تقسیم شده است. هر کدام از این نواحی از یک مسیریاب بزرگتر در مرکز خود بهره میبرند که مستقیماً به مسیریابهای مرکزی ناحیههای همسایه متصلاند. شبهکد مسیریاب مرکزی نواحی در
شکل (4): شبه کد مسیریاب مرکزی با توجه به شکل (5)، بسته در صورت استفاده از الگوریتم مسیریابی معمول XY از مسیر 1 به مقصد ارسال میشود و به عبور از 34 لینک نیاز دارد؛ در صورتی که تعداد عبور از لینکها در روش پیشنهادی که از مسیر 2 فرستاده میشود، 16 عدد کاهش مییابد و این یعنی کاهش تأخیر، توان مصرفی و افزایش اطمینانپذیری و کارآیی شبکه. با کمشدن تعداد لینکهای عبوری، کارآیی بالاتر الگوریتم پیشنهادی در شبکههای بزرگتر مشهودتر است.
شکل (5): مسیر طیشده در شبکه روی تراشه 18×18 با الگوریتم مسیریابی XY و پیشنهادی با توجه به کاربرد شبکه روی تراشه و اینکه چه ابعادی داشته باشد، اندازۀ ناحیهها تعیین میشود و با توجه به اندازۀ ناحیهها مشخص میشود مسیری که بسته باید طی بکند، کوتاه است یا بلند. اگر مسیر کوتاه باشد، مسیر با استفاده از الگوریتم XY مشخص میشود و در صورتی که مبدأ و مقصد در دو ناحیه مجزا و مسیر بلند باشد، بسته برای مسیریابی ابتدا به مسیریاب مرکزی ناحیه مبدأ، سپس به مسیریاب مرکزی ناحیۀ مقصد و درنهایت به گره مقصد ارسال میشود.
شکل (6): مسیرهای طیشده در شبکه روی تراشه 14×14 با الگوریتم مسیریابی پیشنهادی شکل (6) یک شبکه 14×14 را نشان میدهد. هر ناحیه باید شبکهای مربع با تعداد گرههای فرد باشد. این شبکه به 4 ناحیه 7×7 تقسیم شده است که در وسط هر ناحیه یک مسیریاب مرکزی وجود دارد؛ برای مثال، مسیریاب مرکزی ناحیه یک در گره (3و3) قرار دارد؛ در صورتی که بستهای بخواهد از مسیریابهای مرکزی ناحیهها استفاده کند، ابتدا باید شرط متفاوتبودن ناحیۀ مبدأ و مقصد چک شود و در صورتی که مبدأ و مقصد در دو ناحیه مجزا باشند، باید هر دو فاصله X و Y مبدأ و X و Y مقصد فاصلهای بیشتر یا مساوی عدد مشخصه متناسب با اندازۀ شبکه را داشته باشند. عدد مشخصه با توجه به اندازۀ شبکه از روش زیر محاسبه میشود:
که در آن CN عدد مشخصه و NS اندازۀ شبکه روی تراشه است. در این شبکه روی تراشه 14×14، مقدار عدد مشخصه 5 است. پس باید هر دو فاصله X و Y مبدأ و X و Y مقصد فاصلهای بیشتر یا مساوی 5 داشته باشند که در این صورت فاصلۀ مبدأ و مقصد بسته، بلند و در غیر این صورت فاصله کوتاه محسوب میشود. روند الگوریتم بهصورت فلوچات در شکل 7 نشان داده شده است.
شکل (7): فلوچارت الگوریتم پیشنهادی با توجه به شکل (6)، اگر بستهای (بسته 1) بخواهد با الگوریتم مسیریابی معمولی XY از گره (0و0) به گره (13و13) ارسال شود، باید از 26 لینک عبور کند؛ درحالیکه در صورت استفاده از الگوریتم پیشنهادی با توجه به تفاوت ناحیۀ مبدأ و مقصد، ابتدا فاصله X و Y مبدأ با X و Y مقصد محاسبه میشود که مقدار فاصله هر دوی آنها 13 و بزرگتر از 5 است؛ بنابراین از مسیریابهای مرکزی ناحیهها استفاده میشود و تعداد لینکهای عبوری به 14 عدد کاهش مییابد. کاهش تعداد لینکهای عبوری به کاهش تأخیر و توان مصرفی و افزایش اطمینانپذیری منجر میشود (تعداد کمتری مسیریاب درگیر مسیریابی میشوند). مطابق مسیر 2 در شکل (6)، اگر یک بسته بخواهد از گره (2و1) به گره (10و7) ارسال شود، ابتدا شرط مجزابودن ناحیۀ مبدأ و مقصد چک میشود، سپس فاصلۀ X و Y مبدأ با X و Y مقصد محاسبه میشود. فاصله X ها 6 و فاصلۀ Yها 8 عدد است که هر دو بزرگتر از 5 هستند؛ بنابراین مسیر بلند محسوب میشود و بسته میتواند از مسیریابهای مرکزی ناحیهها مطابق شکل (6) استفاده کند و باید از 8 لینک عبور کند؛ اما در صورت مسیریابی از روش معمول XY، بسته مجبور به عبور از 14 لینک است. مسیر 3 قصد ارسال بسته را از گره (12و4) به گره (11و8) دارد. با توجه به اینکه مبدأ و مقصد در دو ناحیه مجزا قرار گرفتهاند، شرط فاصله X و Y مبدأ با X و Y مقصد بررسی میشود که برقرار نیست و مسیر کوتاه محسوب میشود؛ بنابراین مسیریابی از الگوریتم معمول XY پیروی میکند. مسیر 4 قصد ارسال بسته را از گره (0و13) به گره (5و8) دارد. با توجه به اینکه مبدأ و مقصد در یک ناحیه قرار دارند، مسیریابی از الگوریتم معمول XY پیروی میکند.
شکل (8): حداقل اندازۀ شبکه یک ناحیه 5×5 برای شبکه روی تراشه 10×10 حداقل اندازۀ شبکۀ یک ناحیه برای تقسیمبندی یک شبکۀ بزرگ روی تراشه به نواحی دارای مسیریاب مرکزی، شبکۀ مربعی 5×5 است و در شبکۀ کوچکتر از آن، که شبکه 3×3 است، امکان استفاده از مسیریاب مرکزی وجود ندارد. شکل (8) یک شبکه 10×10 را نمایش میدهد که از نواحی 5×5 تشکیل شده است. شکل (9) مقایسهای بین تعداد لینکهای عبوری یک بسته برای رسیدن به مقصد در دو الگوریتم معمول XY و الگوریتم پیشنهادشده را نشان میدهد. همانطور که مشاهده میشود در شبکههای بزرگتر، تعداد لینکهای عبوری کاهش بیشتری دارند و این نشاندهندۀ توان عملیاتی بالاتر الگوریتم پیشنهادی در شبکههای بزرگ است.
شکل (9): مقایسه لینکهای عبوری بسته در الگوریتم مسیریابی XY و الگوریتم پیشنهادی 4- بررسی پارامترهای الگوریتم پیشنهاد شده پارامترهای مختلفی نشاندهندۀ عملکرد یک الگوریتم مسیریابی هستند؛ اما با توجه به اینکه هدف این مقاله رسیدن به شبکه روی تراشه تحملپذیر خطا با کمترین افزونگی و پیچیدگیهای اضافهشده به شبکه است، پارامترهایی ازقبیل قابلیت اطمینان، سربار مساحت، سربار توان مصرفی و تأخیر ارزیابی میشوند. 4-1- قابلیت اطمینان تحملپذیری خطا، قابلیت اطمینان الگوریتم را در مسیریابی بستهها با وجود خطای دائمی و گذرا ارزیابی میکند. خطاهای دائمی در هر شرایطی ایجاد میشوند و ممکن است بر یک یا چند ناحیه تأثیر بگذارند. این نوع خطاها بهدلیل عیبهای فیزیکی ایجاد میشوند یا هنگام استفاده از تراشه رخ میدهند. خطاهای دائمی متفاوت، اثرات متفاوتی نیز دارند. در مقابل خطاهای دائمی، خطاهای گذرا وجود دارند که تنها برای مدت زمان معین وجود دارند؛ هرچند ممکن است بهصورت مستمر آشکار و ناپدید شوند. خطاها هم در مسیریابها و هم در لینکهای شبکه رخ میدهند. الگوریتم پیشنهادی بهدلیل کاهش مسیر بستهها و همچنین عبور از لینکها و مسیریابهای کمتر، ذاتاً دارای قابلیت اطمینان بالاتری نسبت به الگوریتمهای معمول است؛ درحالیکه قابلیت تشخیص و تصحیح خطا ندارد (این الگوریتم قابلیت اضافهکردن مدارات تشخیص و تصحیح مدار در مسیرهای بلند را دارد؛ اما با توجه به اینکه هدف این روش بهبود کارآیی و قابلیت اطمینان با کمترین افزونگیها و پیچیدگیهای مداری است، به آن اضافه نشده است)؛ اما با توجه به تغییر مسیر بسته به مسیر کوتاهتر، امکان دورزدن نواحی معیوب برای بستههای با مسیر بلند وجود دارد؛ ازاینرو فقط خطاهایی اعم از دائمی و گذرا تحملپذیرند که در مسیر عبوری جدید بسته نباشند. در شبیهسازی این نقصها با معیوبکردن برخی از لینکها، بهصورت تصادفی به سیستم تزریق میشوند. 4-2- سربار مساحت در این روش، همبندی شبکه روی تراشه بهصورت توری انجام میشود؛ با این تفاوت که شبکۀ بزرگ به تعدادی زیر شبکه تقسیم میشود که هر یک از آنها یک مسیریاب مرکزی دارند که دارای تفاوتهایی با مسیریابهای معمولاند که در این شبکه به کار رفتهاند. برخلاف مسیریابهای معمول که دارای 5 پورتاند (یک پورت محلی و چهار پورت برای چهار جهت مسیریابی)، مسیریاب مرکزی دارای 9 پورت خروجی است که یک پورت برای اتصال به پردازندۀ محلی، چهار پورت برای اتصال به مسیریابهای معمول اطراف و چهار پورت برای اتصال به مسیریابهای مرکزی ناحیههای چهار طرف تعبیه شدهاند؛ بنابراین، برای بالابردن قابلیت اطمینان در شبکه روی تراشه مساحت اضافهشده به شبکه روی تراشه معمول فقط لینکهای اتصال مسیریابهای مرکزی ناحیهها به یکدیگر و مسیریابهای مرکزی ناحیهها است. این سربار مساحت در شبکههای روی تراشه با اندازۀ بزرگ، چشمپوشی میشود. 4-3- سربار توان مصرفی توان در شبکه روی تراشه با مسیریابها مصرف میشود. توان مصرفی در روش پیشنهادی همانند شبکه روی تراشه معمول است؛ با این تفاوت که مسیریابهای مرکزی ناحیهها به دلیل پیچیدگی، تعداد پورت و بافر بیشتر و همچنین ترافیک بالاتر دارای مصرف توان بالاتری نسبت به مسیریابهای سادۀ شبکه روی تراشهاند؛ اما با توجه به پایینبودن تعداد این مسیریابها در شبکههای بزرگ به نسبت مسیریابهای ساده و همچنین بیکاربودن تعداد زیادی از مسیریابهای ساده در ازای استفاده از مسیریابهای مرکزی ناحیهها، توان مصرفی کاهش پیدا خواهد کرد. 4-4- تأخیر بستهها با مسیرهای بلند برای رسیدن به مقصد از تعداد زیادی لینک و مسیریاب عبور میکنند؛ درحالیکه در الگوریتم پیشنهادی، تعداد لینک و مسیریاب عبوری برای این بستهها کاهش مییابد و موجب کاهش تأخیر رسیدن بستهها به مقصد میشود. 5- نتایج شبیهسازی شبیهسازی با شبیهساز Noxim انجام شده است که قابلیت مدیریت و تزریق اشکال به آن افزوده شد. این شبیهساز برخلاف شبیهسازهای دیگر در زمینۀ شبکه بهصورت اختصاصی برای کار روی شبکه روی تراشه طراحی شده است. شبیهساز یادشده نرمافزار متن باز است و یکی از امکانات آن، قابلیت تعریف و ایجاد الگوریتمهای مسیریابی در متن برنامه است. الگوریتم پیشنهادی، الگوریتم مسیریابی XY بهعنوان الگوریتم معمول برای شبکه روی تراشه و همچنین الگوریتمهای HCCR، Pull Off Buffer و Penta NOC با اندازه 14×14شبیهسازی شدهاند. طول فلیت 32 بیت، طول بسته 8 فلیت و اندازۀ بافر ورودی 8 فلیت در نظر گرفته شده است. در شبیهسازی، هر تکرار به مدت 11000 سیکل اجرا شده و در هر بار تکرار، یک یا چند اشکال تصادفی به شبکه تزریق شده است. 5-1- ارزیابی میانگین تأخیر بسته میانگین تأخیر یک پیغام، میانگین زمانی است که طول میکشد تا یک پیغام تولید، آمادۀ ارسال شود و به مقصد برسد. این زمان بسیار وابسته به الگوریتم مسیریابی، ترافیک شبکه و عواملی از این قبیل است. روند افزایش میانگین تأخیر بسته زمانی که نرخ تزریق بسته افزایش داده میشود، با یک منحنی نشان داده میشود. همانطور که در
شکل (10): میانگین تأخیر بسته در شبکه با اندازه 14×14 5-2- ارزیابی قابلیت اطمینان برای اندازهگیری قابلیت اطمینان، تعداد لینکهای خراب از یک تا سه بهصورت تصادفی به شبکه اعمال شدهاند. اگر همۀ بستههای تولیدشده به مقصد نرسند، شبکه اطمینانپذیر نیست. به عبارت دیگر، اگر حتی یک بسته به مقصد نرسد، شبکه اطمینانناپذیر به حساب آورده نمیشود. نتیجۀ مقایسۀ انجامشده در شکل (11)، با استفاده از 10000 تکرار تحت ترافیک تصادفی با نرخ تزریق 008/0 بسته در هر گره در هر پالس ساعت به دست آمده است. با توجه به شکل (11)، پس از الگوریتم
شکل (11): مقایسۀ قابلیت اطمینان الگوریتمهای مختلف 5-3- ارزیابی توان مصرفی جدول (1) توان مصرفی الگوریتمهای مقایسهشده را نشان میدهد. برای اندازهگیری توان مصرفی از کتابخانه STMICRO 90nm با فرکانس کاری یک گیگاهرتز و ولتاژ منبع تغذیه 2/1 ولت بهره گرفته شده است. در الگوریتم پیشنهادی با توجه به کوتاهشدن مسیر برخی بستهها و عبور از مسیریابهای کمتر، توان مصرفی کاهش یافته است و این در حالی است که تحملپذیر شدن یک شبکه روی تراشه در برابر خطا نیازمند هزینههایی ازقبیل توان مصرفی با مقدار شایان توجه است. جدول (1): مقایسۀ توان مصرفی در شبکههای روی تراشه مختلف
6- نتیجهگیری با توجه به اینکه در حال حضر اصلیترین نگرانی در زمینۀ شبکههای روی تراشه، قابلیت اطمینان بالا در عملکرد مطلوب شبکه است، یک شبکه روی تراشه با عملکرد بالا و تحملپذیر خطا پیشنهاد شد که برای رسیدن به این هدف از کاهش تعداد لینکهای عبوری یک بسته برای رسیدن به مقصد بهره میبرد. با کاهش تعداد لینکهای عبوری، تعداد مسیریابها نیز کاهش مییابد و درنهایت موجب کاهش توان مصرفی، عملکرد بهتر شبکه، کاهش احتمال برخورد با لینک و مسیریاب معیوب و کاهش تأخیر شبکه میشود. [1] تاریخ ارسال مقاله: 30/02/1398 تاریخ پذیرش مقاله: 24/10/1398 نام نویسندۀ مسئول: سید جواد سید مهدوی چابک نشانی نویسندۀ مسئول: ایران - مشهد - دانشگاه آزاد اسلامی - دانشکده مهندسی برق | ||||||||||||||||
| مراجع | ||||||||||||||||
|
[1] Tatas, K., Siozios, K., Soudris, D., Jantsch, A., Designing 2D and 3D Network-on-Chip Architectures, Springer Publishing, 2014. [2] Theocharides, T., Link, G., Vijaykrishnan, N., Irwin, M., Networks on Chip (NoC): Interconnects of Next Generation Systems on Chip, Advances in Computers, Vol. 63, pp. 35-89, 2005. [3] Cidon, I., NoC: Network or Chip?, IEEE, First International Symposium on Networks-on-Chip (NOCS'07), May 2007. [4] Gindin, R., Cidon, I., Keidar, I., NoC-Based FPGA: Architecture and Routing, IEEE, First International Symposium on Networks-on-Chip (NOCS'07), May 2007. [5] Kia, H., Ababei, C., Improving Fault Tolerance of Network-on-Chip Links via Minimal Redundancy and Reconfiguration, International Conference on Reconfigurable Computing and FPGAs, 2011. [6] Kadri, N., Koudil, M., A survey on fault-tolerant application mapping techniques for Network-on-Chip, Journal of Systems Architecture, Vol. 92, [7] Kumar, S., Leuken, R. V., A 3D network on chip for stacked-die transactional chip multiprocessors using through silicon VIAS, IEEE, 6th International Conference on Design & Technology of Integrated Systems in Nanoscale Era (DTIS), April 2011. [8] Shao t, A., Wang, D., Wang, H., Pull-Off Buffer: Borrowing Cache Space to Avoid Deadlock for Fault-Tolerant NoC Routing, IEEE 34th International Conference on Computer Design (ICCD), Scottsdale, AZ, USA, Oct. 2016. [9] Berestizshevsky, K., Even, G., Fais, Y., Ostrometzky, J., SDNoC: Software Defined Network on a Chip, Microprocessors and Microsystems, Vol. 50, pp. 138-153, 2017. [10] Poluri, P., Louri, A., Shield: A Reliable Network-on-Chip Router Architecture for Chip Multiprocessors, IEEE Transaction on parallel and distributed systems, Vol. 27, No. 10, pp. 3058-3070, OCTOBER 2016. [11] Inam, O., Al Khanjari, S., Vanderbauwhede, W., Shortest Path Routing Algorithm for Hierarchical Interconnection Network-on-Chip, Procedia Computer Science, Vol. 56, pp. 409-414, 2015. [12] Shirmohammadi, Z., Mozafari, F., Miremadi, S. G., An Efficient Numerical-Based Crosstalk Avoidance Codec Design for NoCs, Microprocessors and Microsystems, Vol. 50, [13] Boudellioua, A., Alzeidi, N., PentaNoc: A New Scalable and self-similar NoC Architecture, Procedia Computer Science, Vol. 134, pp. 358-364, 2018. [14] Attia, S., Fahmy, H., Ismail, Y., Mostafa, H., Optimizing FPGA-based hard networks-on-chip by minimizing and sharing Resources, Integration, the VLSI journal, Vol. 63, pp. 138-147, 2018. [15] Marcon, C., Webber, T., Fernandes, R., Cataldo, R., Grando, F., Poehls, L., Benso, A., Tiny - optimised 3D mesh NoC for area and latency minimisation, Electronics Letters, Vol. 50 , Issue: 3, pp. 165 – 166, 2014. [16] Wang, L., Ma, S., Li, C., Chen, W., Wang, Z., A High Performance Reliable NoC Router, 21st Asia and South Pacific Design Automation Conference (ASP-DAC), Macau, China, Jan. 2016. [17] Rambo, E. A., Seitz, C., Saidi, S., Ernst, R., Designing Networks on-Chip for High Assurance Real-Time Systems, in Pacific Rim International Symposium on Dependable Computing (PRDC), Christchurch, New Zealand, 2017. [18] Charif, A., Coelho, A., Ebrahimi, M., Bagherzadeh, N., Eddi, N., First-Last: A Cost-Effective Adaptive Routing Solution for TSV-Based Three-Dimensional Networks-on-Chip, IEEE Transactions on Computers, Vol. 67 , Issue: 10, pp. 1430 – 1444, 2018 [19] Liu, L., Ma, R., Zhu, Z., An encapsulated packet-selection routing for network on chip, Microelectronics Journal, Vol. 84, pp. 96-105, 2019. [20] Venkataramana, N.L., Kumar, R., Design and analysis of application specific network on chip for reliable custom topology, Computer Networks, Available online 5 April 2019, In Press, Accepted Manuscript. | ||||||||||||||||
|
آمار تعداد مشاهده مقاله: 1,317 تعداد دریافت فایل اصل مقاله: 521 |
||||||||||||||||