نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی شبکه بر تراشه ناهمگن با هدف کاهش توان مصرفی با استفاده از الگوریتم ژنتیک
یکی از رشته های زیر مجموعه فنی مهندسی که علاقمندان بسیاری در کشور ما دارد رشته کامپیوتر و فناوری اطلاعات هستش که اتفاقا سایت دیجی لود در حال تکمیل سری جدیدی از پایان نامه های ارشد این رشته تحصیلی برای کاربران گرانقدر خود میباشد. دیجی لود در ادامه پایان نامه ” نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی شبکه بر تراشه ناهمگن با هدف کاهش توان مصرفی با استفاده از الگوریتم ژنتیک ” با فرمت Word (قابل ویرایش) در 127 صفحه را معرفی مینماید.
چکیده پایان نامه نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی شبکه بر تراشه ناهمگن با هدف کاهش توان مصرفی با استفاده از الگوریتم ژنتیک :
امروزه با پیشرفت فنآوری نیمه هادیها، تعداد مولفه های پردازشی در یک سیستم روی تراشه (SOC) افزایش یافته است. معماری ارتباطی در این قبیل سیستمها مبتنی بر گذرگاه میباشد. از این رو، با افزایش تعداد مولفه های پردازشی و با توجه به عدم کارایی و توسعه پذیری گذرگاه، مفهوم شبکه روی تراشه یا NOC به عنوان یک طرح ارتباطی درون تراشهای کارآمد و مقیاس پذیر، جهت غلبه بر مشکلات گذرگاه ها مطرح شده است. یکی از چالشهای مهم در تحقیقات مربوط به NOCها، مسئله نگاشت وظایف یک برنامه کاربردی بر روی هسته های پردازشی متصل به مسیریابهای شبکه است که این هسته ها میتوانند به صورت همگن یا ناهمگن باشند. از طرف دیگر، یکی از پرکاربردترین برنامه های کاربردی، برنامه های کاربردی تعبیه شده با نیازمندی های زمانی بیدرنگ میباشند. در بسیاری از کارهای انجام شده، به مسئله نگاشت بر روی هسته های پردازشی همگن پرداخته شده است و سعی در ارائه راه حل کارآمد کرده اند. اما تقریبا در اکثر طرحهای پیشنهاد شده، ویژگی ناهمگن بودن هسته ها علیرغم آنکه به واقعیت نزدیکتر است، نادیده گرفته شده است. همچنین ویژگی بی درنگ بودن کاربردها، مورد توجه عمده کارهای پژوهشی انجام گرفته، نیز نبوده است. یکی از چالشهای دیگر در شبکه روی تراشه، میزان توان مصرفی در NOC میباشد.
در این پایان نامه، به مسئله نگاشت وظایف یک برنامه کاربردی بیدرنگ سخت بر روی هسته های پردازشی NOC با فرض ناهمگن بودن، پرداخته شده است به طوریکه علاوه بر اینکه محدودیتهای زمانی وظایف رعایت شود، اتلاف توان در شبکه روی تراشه نیز کمینه گردد. با توجه به این که حل بهینه مسئله نگاشت یک مسئله NP-hard است، در طرح پیشنهادی از یک الگوریتم ژنتیک چند هدفه استفاده میشود. برای همگرایی سریعتر الگوریتم، معتبر بودن هر راه حل بدست آماده اعتبارسنجی میگردد تا هزینه اجرای الگوریتم ژنتیک کاهش یابد. اگر چه طرح پیشنهادی برای شبکه های روی تراشه ناهمگن ارائه شده است اما مقایسه نتایج آن با طرحهای روی تراشه های همگن نشان دهندهی سربار ناچیز طرح پیشنهادی است.
کلمات کليدی: 1- شبکه روی تراشه 2-نگاشت 3- برنامه کاربردی بیدرنگ سخت 4-الگوریتم ژنتیک چندهدفه
فهرست مطالب
چکيده. 1
فصل اول: مقدمه 2
1-1 مقدمه. 2
1-2 معرفی شبکه روی تراشه. 4
1-3 مسئله نگاشت در شبکه روی تراشه. 7
1-4 مفهوم برنامه کاربردی بیدرنگ سخت ….. 9
1-5 مسئله توان در شبکه بر روی تراشه. 11
1-6 هدف پایان‌نامه. 11
1-7 ساختار ادامه پایان‌نامه. 12
فصل دوم: معماری شبکه روی تراشه
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
راهنمای خرید و دانلود فایل
برای پرداخت، میتوانید از کلیه کارتهای عضو شتاب استفاده نمائید.
بعد از پرداخت آنلاین لینک دانلود فعال و نمایش داده میشود ، همچنین یک نسخه از فایل همان لحظه به ایمیل شما ارسال میگردد.
در صورت بروز هر مشکلی،میتوانید از طریق تماس با ما پیغام بگذارید و یا در تلگرام با ما در تماس باشید، تا شکایت شما مورد بررسی قرار گیرد.
برای دانلود فایل روی دکمه خرید و دانلود کلیک نمایید.
ديدگاه ها