فهرست مطالب

عنوان صفحه

فهرست مطالب هشت

چکيده 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-الگوریتم ژنتیک چندهدفه