نگاشت وظایف یک برنامه کاربردی بی‌درنگ سخت بر روی شبکه بر تراشه ناهمگن با هدف کاهش توان مصرفی

جزئیات و دریافت

این پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد.

فهرست مطالب

عنوان    صفحه
فهرست مطالب    هشت
چکيده    1
فصل اول: مقدمه    2
1-1    مقدمه    2
1-2    معرفی شبکه روی تراشه    4
1-3    مسئله نگاشت در شبکه روی تراشه    7
1-4    مفهوم برنامه های کاربردی بیدرنگ    9
1-5    مسئله توان در شبکه بر روی تراشه    11
1-6    هدف پایان‌نامه    11
1-7    ساختار ادامه پایان‌نامه    12
فصل دوم: معماری شبکه روی تراشه    13
2-1    مقدمه    13
2-2    معماری شبکه روی تراشه    14
2-3    هم‌بندی شبکه    17
2-4    مسیریابی و الگوریتم‌های مسیریابی    19
2-5    راه‌گزینی    22
2-6    کانال مجازی    27
2-7    نتیجه‌گیری    28
فصل سوم: مروری بر مفاهیم نگاشت و کارهای انجام شده    29
3-1    مقدمه    29
3-2    روش‌های نگاشت ایستا    29
3-2-1    نگاشت دقیق    31
3-2-2    نگاشت مبتنی بر جستجو    32
3-3    روش‌های نگاشت پویا    45
3-4    نتیجه‌گیری    47
فصل چهارم: روش پیشنهادی    48
4-1    مقدمه    48
4-2    معرفی طرح کلی روش پیشنهادی    49
4-3    اجزای طرح پیشنهادی    52
4-3-1    مدل کاربرد    52
4-3-2    مدل معماری شبکه بر تراشه    55
 
4-3-3    مدل تحلیلی بررسی قابلیت زمانبندی    57
4-3-4    مدل تحلیلی توان    62
4-3-5    الگوریتم ژنتیک چند هدفه NSGA-II    63
4-4    نتیجه‌گیری    74
فصل پنجم: ارزیابی نتایج    76
5-1    مقدمه    76
5-2    معیارهای ارزیابی    76
5-3    معرفی محک مورد استفاده    79
5-4    محیط شبیه‌سازی    83
5-5    ارزیابی نتایج    84
5-6    نتیجه‌گیری    99
فصل ششم: جمع‌بندی و ارائه‌ی پیشنهادات    100
6-1    مقدمه    100
6-2    مرور مطالب    101
6-3    کارهای آینده    103
6-4    نتیجهگیری    104
 مراجع    105

 
فهرست شکل¬ها

 
عنوان    صفحه
شکل ‏1 1 نمایی کلی از سیستم بر تراشه با دو ساختار ارتباطی (1) گذرگاه (2) نقطه به نقطه    4
شکل ‏1 2 مسئله نگاشت هسته‌های پردازشی به گره‌های شبکه روی تراشه    8
شکل ‏1 3 مسئله نگاشت وظایف بر روی هسته‌های پردازشی شبکه    9
شکل ‏2 1 معماری شبکه روی تراشه    15
شکل ‏2 2 ساختار کلی مسیریاب در شبکه روی تراشه    17
شکل ‏2 3 همبندی‌های مختلف شبکه بر روی تراشه، 1) توری مدور، 2) توری، 3) SPIN، 4) BFT، 5) هشت وجهی، 6) توری مدور تا خورده    18
شکل ‏2 4 دسته‌بندی الگوریتم‌های مسیریابی    21
شکل ‏2 5 مسیرهای پیموده شده توسط الگوریتمXY    23
شکل ‏2 6 شبه کد الگوریتم مسیریابیXY    23
شکل ‏2 7 روش‌های راه‌گزینی    24
شکل ‏2 8 راه‌گزینی مداری    24
شکل ‏2 9 راه‌گزینی بسته‌ای    25
شکل ‏2 10 اجزای یک پیغام در راه‌گزینی خزشی    26
شکل ‏2 11 مسدود شدن یک بسته در شبکه و ایجاد بن‌بست    27
شکل ‏2 12 روش‌های راه‌گزینی ذخیره و ارسال (a) و خزشی (b)    27
شکل ‏2 13 تسهیم کردن کانال خروجی و رفع بن‌بست توسط کانال مجازی    28
شکل ‏3 1 طبقه‌بندی روش‌های نگاشت    30
شکل ‏3 2 جریان طراحی الگوریتم در [40]    35
شکل ‏3 3 ساختار ذره در الگوریتم PSO    39
شکل ‏3 4 نگاشت کاربرد روی NOC به صورت مارپیچ    41
شکل ‏3 5 مثال ادغام دوجمله‌ای (N=16)    42
شکل ‏3 6 مفهوم انتخاب مسیر لوزی شکل    44
شکل ‏3 7 مسیر زیگزاک برای نگاشت هسته    44
شکل ‏3 8 روش نگاشت پویای سلسله مراتبی    46
شکل ‏4 1 نمونه‌ای از شبکه روی تراشه ناهمگن    51
شکل ‏4 2 درگاه خروجی مسیریاب در داوری براساس اولویت    57
شکل ‏4 3 مثال تداخل مستقیم و غیرمستقیم جریان‌های ترافیکی    60
شکل ‏4 4 نحوه عملکرد الگوریتم NSGA-II    65
شکل ‏4 5 سطوح نامغلوب در الگوریتم NSGA-II    66
شکل ‏4 6 محاسبه‌ی فاصله ازدحام    66
شکل ‏4 7 مراحل الگوریتم ژنتیک NSGA-II    67
شکل ‏4 8 ساختار کروموزوم    68
شکل ‏4 9 ساختار کلی الگوریتم ژنتیک    70
شکل ‏4 10 انتخاب مسابقه‌ای دودویی    71
شکل ‏4 11 روش تقاطع تک نقطه‌ای    72
شکل ‏5 1 مدل کاربرد وسیله‌ی نقلیه‌ی خودمختار    80
شکل ‏5 2 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 بدون استفاده از توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4    89
شکل ‏5 3 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 برای کاربرد وسیله‌ی نقلیه خودمختار در روش [50]    90
شکل ‏5 4 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 با به کار بردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4    91
شکل ‏5 5 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 بدون استفاده از توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 5×5    93
شکل ‏5 6 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 با به کاربردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 5×5    94
شکل ‏5 7 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 بدون استفاده از توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 3×3     95
شکل ‏5 8 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 با به کاربردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 3×3     95
شکل ‏5 9 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 با به کار بردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4 با دو برابر کردن وظایف    96
شکل ‏5 10 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 بدون استفاده از توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4 با دو برابر کردن وظایف    97
 
 
شکل ‏5 11 همگرایی جواب‌ها با نرخ تقاطع 8/0 و نرخ جهش 01/0 با به کار بردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4    97
شکل ‏5 12 همگرایی جواب‌ها با نرخ تقاطع 5/0 ، نرخ جهش 01/0 و انتخاب مسابقه‌ای با اندازه‌ی 3 با به کار بردن توابع امکان‌پذیری و میزان بهره‌وری در شبکه بر تراشه 4×4    98
شکل ‏5 13 همگرایی جواب‌ها با نرخ تقاطع 5/0 و نرخ جهش 01/0 با فرض همگن بودن شبکه بر تراشه    98

 
فهرست جدول¬ها

 
عنوان    صفحه
جدول ‏5 1 وظایف تشکیل دهنده‌ی کاربرد    81
جدول ‏5 2 جریان‌های ترافیکی بین وظایف کاربرد    82
جدول ‏5 3 مشخصات وظایف کاربرد    85
جدول ‏5 4 بدترین زمان اجرا و توان مصرفی هر یک از وظایف بر روی هسته‌های پردازشی    86
جدول ‏5 5 معیارهای استفاده شده در الگوریتم ژنتیک چندهدفه‌ی NSGA-II    88
جدول ‏5 6 مقادیر توابع هدف در جبهه‌ی نامغلوب نهایی    92
جدول ‏5 7 خلاصه‌ای از نتایج ارائه شده بر روی شبکه‌های با ابعاد مختلف با نرخ جهش 01/0 و نرخ تقاطع  5/0    99
جدول ‏5 8 خلاصه‌ای از نتایج الگوریتم پیشنهادی در برخی حالات خاص در شبکه بر تراشه 4×4    99
                                                                                                                                                

چکيده
امروزه با پیشرفت فن¬آوری نیمه¬هادی¬ها، تعداد مولفه¬های پردازشی در یک سیستم روی تراشه (SOC) افزایش یافته است. معماری ارتباطی در این قبیل سیستم¬ها مبتنی بر گذرگاه می¬باشد. از این رو، با افزایش تعداد مولفه¬های پردازشی و با توجه به عدم کارایی و توسعه¬پذیری گذرگاه¬، مفهوم شبکه روی تراشه یا NOC به عنوان یک طرح ارتباطی درون تراشه-ای کارآمد و مقیاس¬پذیر، جهت غلبه بر مشکلات گذرگاه¬ها مطرح شده است. یکی از چالش¬های مهم در تحقیقات مربوط به NOCها، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هسته¬های پردازشی متصل به مسیریاب¬های شبکه است که این هسته¬ها می¬توانند به صورت همگن یا ناهمگن باشند. از طرف دیگر، یکی از پرکاربردترین برنامه¬های کاربردی، برنامه¬های کاربردی تعبیه شده با نیازمندی¬های زمانی بی¬درنگ می¬باشند. در بسیاری از کارهای انجام شده، به مسئله نگاشت بر روی هسته¬های پردازشی همگن پرداخته شده است و سعی در ارائه راه حل کارآمد کرده¬اند. اما تقریبا در اکثر طرح¬های پیشنهاد شده، ویژگی ناهمگن بودن هسته¬ها علی¬رغم آن¬که به واقعیت نزدیک¬تر است، نادیده گرفته شده است. هم¬چنین ویژگی بی¬درنگ بودن کاربردها، مورد توجه عمده کارهای پژوهشی انجام گرفته، نیز نبوده است. یکی از چالش¬های دیگر در شبکه روی تراشه، میزان  توان مصرفی در NOC می¬باشد. در این پایان¬نامه، به مسئله نگاشت وظایف یک برنامه کاربردی بی¬درنگ سخت بر روی هسته¬های پردازشی NOC با فرض ناهمگن بودن، پرداخته شده است به¬طوری¬که علاوه بر این¬که محدودیت¬های زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. با توجه به این که حل بهینه مسئله نگاشت یک مسئله NP-hard است، در طرح پیشنهادی از یک الگوریتم ژنتیک چند هدفه استفاده می-شود. برای همگرایی سریع¬تر الگوریتم، معتبر بودن هر راه حل بدست آماده اعتبارسنجی می¬گردد تا هزینه اجرای الگوریتم ژنتیک کاهش یابد. اگر چه طرح پیشنهادی برای شبکه¬های روی تراشه ناهمگن ارائه شده است اما مقایسه نتایج آن با طرح¬های روی تراشه¬های همگن نشان دهنده¬ی سربار ناچیز طرح پیشنهادی است.

کلمات کليدی: 1- شبکه روی تراشه  2-نگاشت  3-برنامه کاربردی بی‌درنگ سخت 4-الگوریتم ژنتیک چندهدفه
1-    فصل اول
فصل اول: مقدمه
1-1    مقدمه
با توسعه فن‌آوری نیمه هادی¬ها امکان تجمیع تعداد زیادی المان پردازشی  و حافظه¬ای مختلف شامل پردازنده¬های سیگنال ، سخت¬افزارهای خاص منظوره ، مدارهای منطقی برنامه¬پذیر ، پردازنده¬های همه منظوره  و انواع حافظه و مدارات جانبی در داخل یک تراشه فراهم شده است که این مفهوم به سیستم روی تراشه  شناخته شده است[1]. در این قبیل سیستم¬ها ارتباطات بین مولفه¬های گوناگون که یک چالش مهم محسوب می‌شود،  همان‌طور که در شکل 1-1 نشان داده شده است به صورت نقطه به نقطه  یا از طریق گذرگاه¬ها  برقرار می‌شود[2]. در اتصالات نقطه به نقطه بين هر دو هسته¬ي پردازشيِ نيازمند به ارتباط، يك اتصال اختصاصي ايجاد مي-شود. از آن¬جا كه اين روش تنها از سيم¬ها (و بدون استفاده از سخت-افزار اضافه) براي انتقال داده¬ها استفاده مي¬كند، بهترين كارايي و توان مصرفي را براي برقراري ارتباط بين تعداد كم هسته¬ها ارائه مي-كند. اما اين روش داراي مشكلات زيادي از جمله عدم مقياس¬پذيري ، پيچيدگي زياد طراحي و مسيريابي اتصالات در سطح مدار و هزينه¬ي پياده-سازي بالا است. ايرادهاي فوق باعث مي¬شود كه استفاده از اتصالات نقطه به نقطه فقط در سيستم¬هاي كوچك مقرون به صرفه باشد. با بزرگ شدن اندازه¬ي سيستم، استفاده از اتصالات نقطه به نقطه به علت زياد شدن سيم¬هاي مورد نياز و مشكلات طراحي، امكان¬پذير نيست[2]. روش ديگر، يعني معماري ارتباطي مبتني بر گذرگاه، هسته¬هاي پردازشي را با استفاده از يك كانال مشترك به يكديگر ارتباط مي¬دهد. در مقايسه با اتصالات نقطه به نقطه، گذرگاه مشترك پيچيدگي طراحي سطح مدار كم¬تري دارد و چون از كانال¬هاي كم¬تري استفاده می¬کند، هزينه¬ي پياده¬سازي آن نيز پايين¬تر مي¬باشد. اما گذرگاه مشترك دارای  مشكل اساسي عدم مقياس¬پذيري توان و كارآيی می‌باشد. با زياد شدن تعداد دستگاه¬هاي متصل به گذرگاه، طول آن و نيز مدارات ارسال و دريافت داده¬ي متصل به آن افزايش يافته و باعث ايجاد يك بار خازني زياد مي¬گردند. تمام اين بار خازني در جريان يك انتقال داده شارژ و دشارژ می¬شود. اين امر، تأخير و توان مصرفي گذرگاه مشترك را به طرز چشم¬گيري افزايش مي¬دهد. افزون بر اين، تمام عناصر متصل به گذرگاه از يك مسير واحد استفاده مي¬نمايند و لذا در هر لحظه فقط دو گره با هم ارتباط دارند و ساير گره-ها بايد منتظر آزاد شدن كانال بمانند. اين امر موجب كاهش شديد كارآيي سيستم به ويژه هنگامي¬كه عناصر متقاضي ارتباط زياد باشند، می‌شود [4]. با توجه به اين مشكلات، روش گذرگاه نمي¬تواند پاسخگوي نيازهاي ارتباطي تراشه¬هاي آينده باشد. بنابراین نیاز به یک ساختار ارتباطی برای تجمیع تعداد زیادی هسته¬های پردازشی در کنار یکدیگر می¬باشد به طوری که این ساختار ارتباطی مقیاس-پذیر بوده و کارایی بالا داشته باشد[4].
با افزایش قدرت پردازشی تراشه¬ها پیچیدگی و قابلیت برنامه¬های کاربردی نیز افزایش یافته است و این افزایش پیچیدگی سخت¬افزار و نرم¬افزار در سیستم¬های روی تراشه و پردازنده¬های چند هسته¬ای، به نوبه¬ی خود افزایش حجم و پیچیدگی ترافیک ارتباطی داخل تراشه را موجب می¬شود. از سوی دیگر، کاهش اندازه¬ی مشخصه¬ی  ترانزیستورها مشکلات و چالش¬های دیگری را در سطح مدار به ویژه برای ساختارهای ارتباطی درون تراشه، به همراه دارد. مواجهه با این پیچیدگی ارتباطات و هم¬چنین مسائل موجود در فن‌آوری¬های جدید VLSI نیاز به بازنگری روش¬های سنتی ارتباطی درون تراشه را ایجاد کرد و شبکه روی تراشه به عنوان یک طرح ارتباطی درون تراشه¬ای نوین برای رفع و کاهش این مشکلات مورد توجه قرار گرفت[5].
شبکه¬های ارتباطی روی تراشه که Network-on-Chip (NoC) نامیده می¬شوند یک راه¬حل ممکن برای ارتباطات روی تراشه‌ی پلتفرم¬های SOC جهت غلبه بر محدودیت¬های گذرگاه¬ها می¬باشند. شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکه¬ای از مسیریاب‌ها با هم در ارتباط می¬باشند. در این‌جا به جای استفاده از سیم¬های اختصاصی  از شبکه برای ارتباط بین مولفه¬ها استفاده می¬شود که موجب تاخیر کمتر، اتلاف توان کمتر و به طور کلی کارایی بالاتری می¬شود[5]. شبکه روی تراشه مزایای زیادی از جمله پودمانی بودن   و مقیاس¬پذیری را دارا می¬باشد [2]. هم¬چنین NOC مباحث مربوط به محاسبات و ارتباطات را به طور مجزا انجام می¬دهد[1].
چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده می¬باشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت می¬باشند، کیفیت سرویس مورد نظر را فراهم آورد.
1-2    معرفی شبکه روی تراشه
کاهش ترانزیستورها به کمتر از 50 نانومتر، منجر به افزایش تعداد ترانزیستورها به بیش از چندین میلیارد در یک تراشه می¬گردد. بنابراین باید روش¬های جدیدی برای مدیریت حجم انبوهی از ترانزیستورها بر روی یک تراشه اعمال شود[5]. سیستم بر تراشه و شبکه بر تراشه دو روش پیاده¬سازی برای این مشکلات هستند. سیستم بر تراشه شامل تعداد زیادی هسته¬های عملیاتی با قابلیت به¬کارگیری مجدد می¬باشد و برای ارتباط این هسته¬ها نیاز به معماری¬های ارتباطی مقیاس¬پذیر و با قابلیت گسترش و کارایی بالا می¬باشد. سیستم‌های روی سیلیکون متفاوت از سایر سیستم‌ها، باید به¬گونه¬ای صحیح طراحی شوند که نیازی به تغییر یا تعمیر در آن¬ها نباشد، زیرا این کار برای آن¬ها عملا غیرممکن می¬باشد. سیستم روی تراشه نیاز به شیوه¬های طراحی دارد که با دیگر انواع طراحی در سیستم¬های با مقیاس بزرگ عمومیت دارد[1]. نگاه به روش¬های طراحی اتصالات روی تراشه و مقایسه¬ی این اتصالات با اتصالات گسترده روی شبکه¬ی اینترنت می-تواند مفید باشد. شبکه¬ی اینترنت قادر به کنترل پیچیدگی سیستم و ایجاد سرویس مطمئن، با وجود مشکلات و خطاهای محلی است. به همین دلیل، فن‌آوری شبکه قادر است که کیفیت سرویس را، حتی با وجود تفاوت در گره¬های اینترنتی و پیوند¬ها، برای ما تضمین کند. واضح است که فن‌آوری شبکه ابزار مناسبی برای بهبود فن‌آوری طراحی سیستم در مدارهای بسیار مجتمع است. از طرف دیگر، تلاش بر این است که به کمک خصوصیات شبکه، به ارتباط قابل اطمینان و پر سرعت بر روی تراشه دست یافت. بعضی بر این باورند که شبکه بر روی تراشه به این معناست که پروتکل¬های شبکه مانند TCP/IP بر روی برد سیلیکونی آورده شود. چنین کاری به خاطر تاخیر بالا و پیچیدگی آن امکان پذیر نیست[6]. ارتباطات بر روی تراشه باید پر سرعت باشد. به همین دلیل روش¬های ایجاد شبکه بر روی تراشه باید ساده و موثر باشند و معیارهایی از قبیل پهنای باند، تاخیر، مصرف توان باید بهینه شوند. مدارهای بسیار مجتمع دارای لایه¬های مختلف سیم هستند که می¬توانند برای انتقال داده و اطلاعات کنترلی مورد استفاده قرار گیرند. گذرگاه¬های داده برای انتقال موازی اطلاعات استفاده می¬شوند. وجود واحدهای محاسباتی و ذخیره¬کننده بر روی تراشه، سرعت انتقال را بسیار بالا می¬برد. با این حال، استفاده از گذرگاه در سیستم¬ها، محیط را تبدیل به محیطی رقابتی می¬کند. به عبارتی معماری ارتباطی کنونی سیستم بر تراشه¬ها گذرگاه¬های مشترک و گذرگاه¬های سلسله مراتبی هستند که مقیاس¬پذیری و توسعه¬پذیری کمی دارند. بنابراین رشد تعداد هسته¬ها در تراشه باعث ایجاد گلوگاه در گذرگاه¬های ارتباطی سیستم بر تراشه می¬گردد[4]. هم¬چنین با کوچک شدن اندازه¬ی ترانزیستورها و سرعت بالای واحدهای محاسباتی، سهم تاخیر سیم-ها و ارتباط¬ها در تعیین کارآیی و توان مصرفی پررنگ¬تر شده است. اگر چه تاخیر دروازه¬ها  با روند تکنولوژی کاهش می¬یابد اما تاخیر سیم¬ها ثابت می¬ماند و در حقیقت نسبت به دروازه¬ها بیشتر می¬شود. برای کاهش اثر این تاخیرها،  باید معماری¬هایی جایگزین معماری¬های رایج شوند که با کاهش طول اتصالات و حذف سیم¬های بلند مشکلات ناشی از این تاخیرها را در بلوک¬های عملیاتی کاهش دهد. در واقع هدف اصلی جداسازی بخش¬های ارتباطی از بخش¬های محاسباتی و ذخیره¬سازی می¬باشد. این رویکرد باعث ارائه و توسعه معماری¬های جدیدی شد که تحت عنوان شبکه بر تراشه از آن¬ها یاد می¬شود[5]. شبکه بر تراشه ساختار ارتباطی با قابلیت استفاده مجدد فراهم می¬کند که این ویژگی برای طراحان تراشه اهمیت بسیار زیادی دارد؛ زیرا منجر به کاهش زمان مابین طراحی محصول و ارائه آن به بازار می¬شود. به طور خلاصه، مهمترین هدف برای استفاده از شبکه بر روی تراشه، دستیابی به کارایی بالا است[2].
 به طور خلاصه می‌توان گفت شبکه بر تراشه شامل واحدهای عملیاتی است که از طریق شبکه¬ای از مسیریاب‌ها با هم در ارتباط می¬باشند. چالش اساسی در این گونه ساختارها وجود قابلیتی در تراشه طراحی شده می¬باشد که بتواند با برقراری تعادل بین معیارهای مختلف که حائز اهمیت می¬باشند، کیفیت سرویس مورد نظر را فراهم آورد[1]