بخشی از مقاله
چکیده –
با گسترش کاربردهای چندپردازندهای در سیستمهای امروزی و نیاز به ارتباط تعداد زیادی عناصر پردازشی و حافظهها بر روی یک تراشه، شبکههای روی تراشه بهعنوان یک جایگزین مناسب برای روشهای مبتنی بر گذرگاه ارائه شدهاند. با در نظر گرفتن محدودیتهای ساخت این شبکه در سطح تراشه و نیز محدودیت سطح تراشه، همبندی توری و روش کنترل جریان خزشی به صورت گسترده در طراحیهای امروزی مورد استفاده قرار گرفتهاند. محدودیت میانگیر در این روش کنترل جریان و نیز افزایش ترافیک روی این شبکهها، باعث گردیده تا این شبکهها در معرض وقوع بنبست قرار گیرند. جهت رفع این مشکل روشهای اجتناب از بنبست و نیز روشهای کشف و بازیابی بنبست ارائه گردیدهاند. با توجه به اینکه روشهای اجتناب از بنبست، محدودیتهای زیادی را بر روی الگوریتمهای مسیریابی اعمال میکند، روشهای کشف و بازیابی بنبست راهکار مناسبتر و کمهزینهتری برای شبکههایی که نرخ وقوع بنبست در آنها کم است، ارائه مینماید. در این مقاله روشهای کشف بنبست ارائه شده برای شبکههایی که از همبندی توری استفاده مینمایند مورد بررسی قرار گرفتهاند.
کلید واژه- شبکههای روی تراشه، همبندی توری، کنترل جریان خزشی، بنبست
-1 مقدمه
با افزایش کاربردهای چندپردازندهای در سیستمهای امروزی و نیاز به ارتباطات بین هستههـای پردازشـی، شـبکههـای میـان ارتباطی نقش به سزایی در افزایش کارایی این سیستمها یافتهاند .[1] با در نظر گرفتن ویژگیهای همبندیهـای ارائـهشـده بـرای پیادهسازی شبکههای روی تراشه و امکان پیـادهسـازی آن هـا در سطوح فلزی مدارات VLSI، همبندی توری بهعنوان یـک گزینـه مناسب برای این سیستم ها تشـخیص داده شـده کـه بـه صـورت گسترده مورد استفاده قرار گرفته اند. برای کنترل جریـان داده هـا در این شبکه هـا ، بـا توجـه بـه محـدودیت هـای تـوان مصـرفی و مساحت اشغالی روی تراشه برای مسـیریابهـا، روش کلیـد زنـی خزشی به لحاظ حجم کـم میـزان میـانگیر موردنیـاز، بـه عنـوان اصلیترین روش کنتـرل جریـان داده مـورد اسـتفاده اسـت .[2] میزان کـم میـانگیر موجـود در ایـن روش و نیـز افـزایش میـزان ارتباطات روی تراشه سبب شده تا این سیستم هـا مسـتعد وقـوع بن بست گردند. وقوع بن بست در شبکه های میان ارتبـاطی نظیـر
شبکه های روی تراشه سبب کاهش کارایی سیستم و حتی از کـار افتادگی آن میگردد. در پیادهسازیهای الگوریتمهای مسـیریابی، حذف بن بست یک مسئله بسیار مهم میباشد. برای برون رفـت از ایــن مشــکل، دو راهکــار وجــود دارد: اجتنــاب از بــنبســت و کشف/بازیابی بن بست. راهکارهای مبتنی بر اجتنـاب از بـن بسـت محدودیت های زیادی روی کارایی الگوریتم های مسیریابی اعمـال میکنند و با توجه به نرخ کم وقوع بن بسـت، مـیتواننـد کـارایی مسیریاب ها را به شدت کاهش دهند. راهکارهای مبتنی بر کشـف و بازیابی، بدون اعمال هیچ محـدودیتی بـرای مسـیریابی، امکـان استفاده از انواع مختلف مسیریابی را فراهم میآورند و در صـورت وقوع بن بست با کشف آن ها، روش هایی را برای بازیابی از بن بست فعال میسازند.
در ایـن تحقیــق سـعی شــده تـا روشهــای متفـاوت کشــف بن بسـت در شـبکههـای تـوری کـه از روش کلیـد زنـی خزشـی استفاده مینمایند موردبررسی قرار گیرند. در ادامه سـاختار ایـن مقاله به این صورت است: در بخش 2 به معرفی کلیات شبکههای روی تراشه و اجـزای تشـکیل دهنـده آن پرداختـه مـیشـود. در
زذتل خغ1سکطغکطکسغپه
ذهه شAلع ,لاهلاکغهعطکل y,هق ذصستص
بخش 3 به بررسی شرایط وقوع بنبست و راهکارهـای جلـوگیری از آن میپردازیم. در بخـش 4 روشهـای مهـم ارائـهشـده بـرای تشخیص و بازیابی بن بست مورد بررسی قرار میگیرد و درنهایـت در بخش 5 به جمعبندی میپردازیم.
-2 شبکههای روی تراشه
در طول 40 ساله اخیر افزایش میزان سرعت پردازندهها تقرباًی مطابق با قانون مور بوده است و تقرباًی در هر دو سال شاهد دو برابر شدن قدرت پردازندهها بودهایم. در سالهای اخیر وقوع محدودیتهایی باعث گردیده تا رسیدن به این میزان پیشبینی شده توسط تکپردازندهها قابل حصول نباشد. محدودیتهایی همچون میزان چگالی توان، میزان بارآوری تراشه و تفاوت سرعت بین پردازنده و عناصر حافظه از عواملی هستند که باعث گردیده تا گرایش به سمت پردازش موازی و استفاده از سیستمهای چندپردازندهای و چندهستهای افزایش یابد .[1] در اینگونه سیستمها بهجای استفاده از یک پردازنده با سرعت و پیچیدگی بالا، از تعدادی پردازنده با سرعت و پیچیدگی کمتر بهصورت موازی استفاده میگردد. وظیفههای موجود، به بخشهای قابل موازیسازی تقسیم شده و هر بخش به یکی از این عناصر پردازشی موکول میگردد تا بهصورت موازی انجام پذیرند. با توجه به اینکه این بخشهای برنامه ممکن است به یکدیگر وابستگی داشته باشند و یا نتایج یک بخش مورد نیاز سایر بخشها باشد، این عناصر پردازشی نیاز به ارسال و دریافت داده به یکدیگر دارند. جهت برقراری این ارتباط روشهایی نظیر استفاده از یک گذرگاه مشترک، استفاده از چندین گذرگاه و یا شبکههای روی تراشه استفاده میگردند. استفاده از گذرگاه مشترک با توجه به اینکه در هر لحظه فقط در دسترس یکی از عناصر پردازشی است، کارایی کل سیستم را بهشدت کاهش میدهد و در واقع به گلوگاه سیستم تبدیل میشود. این مشکل با استفاده از همبندیهای مختلف شبکه روی تراشه نظیر توری، توری مدور، ابر مکعب، ابر توری و ... قابل رفع میباشد چرا که امکان برقراری چندین ارتباط بهصورت همزمان را فراهم میآورند .[3]
محدودیت دیگری که در ارتباطات روی تراشه وجود دارد مربوط به پیادهسازی این همبندیها روی مدارات VLSI میباشد. در این مدارات تعداد محدودی لایههای فلزی موجود است که بهعنوان ارتباطات فیزیکی قسمتهای مختلف تراشه مورد استفاده قرار میگیرند. این محدودیت سبب میگردند تا
نتوان همبندیهای پیچیده را که از لحاظ کارایی عملکرد بسیار خوبی میتوانند داشته باشند را در سطح تراشهها پیادهسازی کرد؛ بنابراین بایستی یک مصالحه بین کارایی یک همبندی و امکان پیادهسازی آن برقرار شود. همبندی توری دوبعدی به لحاظ مسطح بودن آن به خوبی قابل پیادهسازی در سطح تراشه بوده و از کارایی خوبی نیز از لحاظ امکان ایجاد ارتباطات همزمان بین عناصر پردازشی برخوردار است. از این رو در بیشتر سیستمهای روی تراشه امروزی از این نوع همبندی استفاده میشود. شکل 1 یک توری 3 در 3 را نمایش میدهد که 9 عنصر پردازشی را با استفاده از مسیریابها به یکدیگر متصل نموده است.
