ثابت شده است که مسئله­ نگاشت یک مسئله­ 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]
در راه­گزینی مداری ابتدا یک مسیر از گره­ی مبدا به گره­ی مقصد درشبکه رزرو می­ شود و سپس ارسال داده آغاز می­گردد. با عبور سرآیند بسته که حاوی اطلاعات مسیریابی است از مسیریاب­های بین مبدا و مقصد، در حین مسیریابی سرآیند، این مسیر برای آن جریان داده ذخیره می­ شود. پس از رسیدن بسته سرآیند به مقصد، یک پیغام تایید[۸۱] به مبدا فرستاده می­ شود تا برقراری مسیر انتقال داده را به اطلاع مبدا برساند[۳].به این ترتیب پس از برقراری مسیر، ارسال داده از مبدا به سمت مقصد شروع می­ شود (شکل ۲-۸). از جمله مشکلات این روش می­توان به کاهش بهره­وری منابع در شبکه (به علت عدم امکان استفاده­ی سایر جریان­های داده از منابع، ناشی از در انحصار قرار گرفتن منابع تا پایان عملیات انتقال داده برای یک جریان داده) و سربار زمان برپایی مدار اشاره نمود. از طرفی، این روش راه­گزینی، برای پیام­های طولانی و جریان­های ارتباطی که نیاز به پهنای باند تضمین شده دارند، بسیار مناسب است[۳].
راه­گزینی بسته­ای، سیاست غالب در شبکه ­های روی تراشه می­باشد. در این روش با توجه به شکل ۲-۹، پیغام­ها به تکه­هایی با اندازه­ ثابت به نام بسته شکسته می­شوند و هر بسته به صورت مستقل مسیریابی می­ شود. بنابراین هر بسته باید اطلاعات کنترلی و مسیریابی را برای رسیدن به گره­ی مقصد به همراه داشته باشد[۲۰]. با توجه به شکل، در این روش هنگامی که یک بسته توسط گره­های میانی دریافت می­ شود، چون اطلاعات مسیر را دارد، منتظر دریافت سایر بسته­های یک پیغام نمی­ماند. به همین دلیل، بسته­های یک پیغام می­توانند به طور هم­زمان از چندین مسیر عبور کرده و به مقصد برسند[۱۸].
شکل ‏۲‑۷- روش­های راه­گزینی [۲۱]
شکل ‏۲‑۸- راه­گزینی مداری [۱۸]
شکل ‏۲‑۹- راه­گزینی بسته­ای [۱۸]
راه­گزینی بسته­ای همان­گونه که در شکل ۲-۷ نشان داده شده است به سه دسته تقسیم می­ شود[۲۱]:
راه­گزینی ذخیره و ارسال[۸۲]: در این روش پیام­ها به بخش­های مستقل کوچک­تری به نام بسته تقسیم می­شوند و فقط زمانی که بسته به طور کامل به کانال ورودی یک مسیریاب برسد، می ­تواند به کانال خروجی مدنظر فرستاده شود. در نتیجه، در این روش چون کل بسته ذخیره می­ شود، حافظه­ میانگیر زیادی مورد نیاز است. هم­چنین این­کار افزایش تاخیر بسته­ها را به دنبال دارد. از طرفی، این روش برای پیام­های کوتاه که تعداد آن­ها زیاد نیست، بسیار مناسب است زیرا برخلاف روش راه­گزینی مداری، سربار زمان برپایی مدار وجود ندارد[۳].
راه­گزینی برشی[۸۳]: در این روش کوچک­ترین واحد داده بسته نمی ­باشد، بلکه هر بسته به واحدهای کوچک­تری به نام فلیت تقسیم می­ شود و به محض آزاد بودن درگاه خروجی برای یک بسته، فلیت­های آن بسته می­توانند فرستاده شوند، بدون این­که نیاز باشد کل بسته به درگاه ورودی رسیده باشد. در نتیجه، تاخیر بسته­ها در این روش نسبت به روش ذخیره و ارسال کاهش می­یابد. اگر درگاه خروجی یک بسته اشغال باشد، کل بسته در حافظه میانگیر ذخیره می­ شود[۳].
راه­گزینی خزشی[۸۴]: این روش راه­گزینی بسیار شبیه راه­گزینی برشی است. با این تفاوت که در این روش راه­گزینی، اندازه­ حافظه میانگیر مورد نیاز نسبت به روش برشی کاهش می­یابد[۳]. در روش مذکور، همان­طور که در شکل ۲-۱۰ مشاهده می­ شود، یک بسته به واحدهای کوچک­تری با طول ثابت به نام فلیت تقسیم می­ شود. هر بسته یک فلیت سرآیند[۸۵] دارد که شامل اطلاعات مسیریابی است و ابتدا مسیریاب­ها را طی و با توجه به اطلاعاتش مسیر را مشخص می­ کند سپس سایر فلیت­ها همان مسیر تعیین شده را می­پیمایند. در این روش به دلیل این­که بسته به واحدهای کنترلی کوچک­تر شکسته می­ شود، به فضای میان­گیر کم­تری نیاز دارد و اندازه حافظه میان­گیر ورودی به اندازه­ چندین فلیت است[۱۱]. درشبکه­های ­ارتباطی متداول، عرض کانال­های فیزیکی به چند بیت محدود می­شوند. بنابراین فلیت­ها معمولا به قسمت­ هایی شکسته می­شوند که فیت نام داشته و تعداد بیت­های آن­ها برابر عرض کانال فیزیکی در شبکه می­باشد. در شبکه ­های روی تراشه عرض کانال­ها به مراتب بیشتر است ولی عناصر حافظه، مساحت و توان مصرفی آن­ها به عنوان یک عامل محدود کننده باعث شکستن فلیت­ها به فیت­ها می­ شود[۲۰].

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...