دانلود پایان نامه

دانشگاه صنعتی اصفهان

دانشکده برق و کامپیوتر

پایان‌نامه کارشناسی ارشد مهندسی کامپیوتر

گرایش معماری

عنوان:

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

استاد راهنما:

دکتر علی فانیان

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

فهرست مطالب:
چکیده. 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-1   مقدمه
با توسعه فن‌آوری نیمه هادی­ها امکان تجمیع تعداد زیادی المان پردازشی[1] و حافظه­ای مختلف شامل پردازنده­های سیگنال[2]، سخت­افزارهای خاص منظوره[3]، مدارهای منطقی برنامه­پذیر[4]، پردازنده­های همه منظوره[5] و انواع حافظه و مدارات جانبی در داخل یک تراشه فراهم شده است که این مفهوم به سیستم روی تراشه[6] شناخته شده است[1]. در این قبیل سیستم­ها ارتباطات بین مولفه­های گوناگون که یک چالش مهم محسوب می‌شود،  همان‌طور که در شکل 1-1 نشان داده شده است به صورت نقطه به نقطه[7] یا از طریق گذرگاه­ها[8] برقرار می‌شود[2]. در اتصالات نقطه به نقطه بین هر دو هسته­ی پردازشیِ نیازمند به ارتباط، یک اتصال اختصاصی ایجاد می­شود. از آن­جا که این روش تنها از سیم­ها (و بدون استفاده از سخت­افزار اضافه) برای انتقال داده­ها استفاده می­کند، بهترین کارایی و توان مصرفی را برای برقراری ارتباط بین تعداد کم هسته­ها ارائه می­کند. اما این روش دارای مشکلات زیادی از جمله عدم مقیاس­پذیری[9]، پیچیدگی زیاد طراحی و مسیریابی اتصالات در سطح مدار و هزینه­ی پیاده­سازی بالا است. ایرادهای فوق باعث می­شود که استفاده از اتصالات نقطه به نقطه فقط در سیستم­های کوچک مقرون به صرفه باشد. با بزرگ شدن اندازه­ی سیستم، استفاده از اتصالات نقطه به نقطه به علت زیاد شدن سیم­های مورد نیاز و مشکلات طراحی، امکان­پذیر نیست[2]. روش دیگر، یعنی معماری ارتباطی مبتنی بر گذرگاه، هسته­های پردازشی را با استفاده از یک کانال مشترک به یکدیگر ارتباط می­دهد. در مقایسه با اتصالات نقطه به نقطه، گذرگاه مشترک پیچیدگی طراحی سطح مدار کم­تری دارد و چون از کانال­های کم­تری استفاده می­کند، هزینه­ی پیاده­سازی آن نیز پایین­تر می­باشد. اما گذرگاه مشترک دارای  مشکل اساسی عدم مقیاس­پذیری توان و کارآیی می‌باشد. با زیاد شدن تعداد دستگاه­های متصل به گذرگاه، طول آن و نیز مدارات ارسال و دریافت داده­ی متصل به آن افزایش یافته و باعث ایجاد یک بار خازنی زیاد می­گردند. تمام این بار خازنی در جریان یک انتقال داده شارژ و دشارژ می­شود. این امر، تأخیر و توان مصرفی گذرگاه مشترک را به طرز چشم­گیری افزایش می­دهد. افزون بر این، تمام عناصر متصل به گذرگاه از یک مسیر واحد استفاده می­نمایند و لذا در هر لحظه فقط دو گره با هم ارتباط دارند و سایر گره­ها باید منتظر آزاد شدن کانال بمانند. این امر موجب کاهش شدید کارآیی سیستم به ویژه هنگامی­که عناصر متقاضی ارتباط زیاد باشند، می‌شود [4]. با توجه به این مشکلات، روش گذرگاه نمی­تواند پاسخگوی نیازهای ارتباطی تراشه­های آینده باشد. بنابراین نیاز به یک ساختار ارتباطی برای تجمیع تعداد زیادی هسته­های پردازشی در کنار یکدیگر می­باشد به طوری که این ساختار ارتباطی مقیاس­پذیر بوده و کارایی بالا داشته باشد[4].

برای دانلود متن کامل پایان نامه اینجا کلیک کنید