زمانبندی وظيفه‌ها در سيستم‌های بیدرنگ نهفته چندهستهای با هدف بهبود انرژی مصرفی و کارايی
یکی از رشته های زیر مجموعه فنی مهندسی که علاقمندان بسیاری در کشور ما دارد رشته کامپیوتر و فناوری اطلاعات هستش که اتفاقا سایت دیجی لود در حال تکمیل سری جدیدی از پایان نامه های ارشد این رشته تحصیلی برای کاربران گرانقدر خود میباشد. دیجی لود در ادامه پایان نامه ” زمانبندی وظيفه‌ها در سيستم‌های بیدرنگ نهفته چندهستهای با هدف بهبود انرژی مصرفی و کارايی ” با فرمت Word (قابل ویرایش) در 120 صفحه را معرفی مینماید.
چکیده پایان نامه زمانبندی وظيفه‌ها در سيستم‌های بیدرنگ نهفته چندهستهای با هدف بهبود انرژی مصرفی و کارايی :
امروزه با پیشرفتهای چشمگیر در صنعت الکترونیک و نیاز روزافزون به تکنولوژیهای کنترلی، کاربرد و اهمیت سیستمهای تعبیه‌شده نیز بیشتر شده است تا جاییکه سیستمهای تعبیه‌شده از مهمترین زمینه های پژوهشی در سالهای اخیر محسوب میشوند. در اکثر مواقع، عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند، از اینرو عموماً اکثر سیستمهای تعبیه‌شده، بیدرنگ میباشند. تجهیزات نظامی و صنعتی، تلفن همراه و کاربردهای تجاری همچون دستگاه های خودپرداز و سیستمهای هوشمند، نمونه‌هایی از سیستمهای تعبیه‌شده بیدرنگ میباشند. علاوه بر بیدرنگ بودن، مصرف انرژی مناسب نیز یکی دیگر از مشخصه های اصلی سیستمهای تعبیه‌شده میباشد که یک مسئله اساسی پیش روی طراحان سیستمهای دیجیتال محسوب میشود. یکی از مسائل مهم در سیستمهای چند هسته ای زمانبندی وظیفه ها و اجرای آنها توسط هسته های موجود است. برخلاف سیستمهای تک هسته ای که مسئله زمانبندی فقط در مورد زمان میباشد، در سیستمهای چند هسته ای این مسئله یک مسئله دو بعدی است و علاوه بر زمان ، مکان و فضای اجرای هسته ها را هم شامل میشود، یعنی تصمیمگیری میشود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است.
در این پایان نامه ما بروی چهار مشکل اصلی در سيستم‌های بیدرنگ تمرکز میکنیم: مصرف انرژی ، بهره‌وری سیستم، کارایی سیستم، زمان پاسخ سیستم. یکی از مهم ترین مسائلی که روی تمامی این چهار مشکل تاثیر مستقیم دارد نحوه توزیع بار بین منابع موجود است که در اینجا منظور از منابع، هسته های یک پردازنده چند هسته ای میباشد. یک توزیع ناکارامد بار روی هسته ها باعث مصرف انرژی بیشتر و پایین آمدن بهره وری و کارایی کل سیستم میشود. بیشتر روشهایی که تاکنون ارائه شده‌اند، بدون توجه به نوع وظیفه، آنها را بین پردازنده ها توزیع میکنند و بیشتر به تمرکز روی روشهای تنظیم فرکانس و ولتاژ هر هسته بسنده میکنند. الگوریتم پیشنهادی ما در این پروژه، یک الگوریتم سه سطحی میباشد که در سطح اول یک روش جدید برای تفکیک وظایف تناوبی از وظایف غیرتناوبی متناسب با تعداد هسته های موجود ارائه میشود. سطح دوم از دو قسمت تشکیل میشود. در قسمت اول یک الگوریتم جدید برای توزیع وظایف تناوبی بین هسته های مربوط به آن ها که در سطح اول الگوریتم مشخص شده، ارائه میشود و در قسمت دوم الگوریتم توزیع وظایف غیرتناوبی بین هسته های مشخص شده برای آنها ، مطرح میشود. در سطح سوم الگوریتم جدیدی برای تنظیم فرکانس و ولتاژ سررسید محور بیان میکنیم. نتایج شبیه سازی نشان میدهد که الگوریتم پیشنهادی ما در مقایسه با الگوریتم‌های موجود، در حین اینکه باعث کاهش مصرف انرژی کل سیستم میشود، بهره وری و کارایی سیستم و همچنین زمان پاسخ وظایف غیر تناوبی را بهبود بخشیده است و با توجه به تامین سررسیدهای زمانی بیشتر برای وظایف تناوبی وکاهش زمان پاسخ وظایف غیرتناوبی با حفظ میزان کارایی و پایین بودن نسبی مرتبه زمانی اجرای الگوریتم، کیفیت سیستم افزایش پیدا خواهد کرد.
کلمات کلیدی : زمانبندی، وظایف بیدرنگ، پردازنده‌های چند هسته‌ای ، سیستمهای تعبیه‌شده
ساختار پايان نامه
در فصل اول به صورت مختصر به اهمیت، دغدغه‌ها و کاربردهای مختلف سیستمهای تعبیه‌شده و مشخصه‌های کاربردی آن پرداخته میشود و پس از آن به سراغ توصیف مسئله رفته واهمیت آن را بیان میکنیم. در پایان نیز خلاصه‌ای از ساختار بخش‌ها و فصل‌های مختلف پایان‌نامه را شرح می‌دهیم.
در فصل دوم، مفاهیم و تعاریف اولیه که برای درک مسئله اهمیت دارد را به تفصیل شرح داده و بررسی میکنیم. ابتدا سیستمهای تعبیه‌شده را تعریف کرده و مهمترین خواص این سیستم‌ها را به طور کامل شرح می‌دهیم. سپس به بیان اهمیت مصرف انرژی در سیستمهای تعبیه‌شده می‌پردازیم و بیان خواهیم کرد که چطور یک توزیع مناسب وظایف بین هسته‌های یک پردازنده چندهستهای، می‌تواند باعث کاهش انرژی مصرفی در سیستم مخصوصا سیستم‌هایی که دارای محدودیت منبع تامین‌کننده انرژی هستند، شود. سپس سیستمهای بیدرنگ را توضیح داده و انواع سیستمهای بیدرنگ از نظر محدودیت زمانی را بیان میکنیم. سپس تابع سودمندی در یک سیستم بیدرنگ را با توجه به نوع ماهیت وظایف بیان کرده و رسم میکنیم. سپس به تعریف یک وظیفه پرداخته و حالت‌های مختلفی که یک وظیفه می‌تواند در طول حیاتش در سیستم تجربه کند را با رسم شکل بیان میکنیم. پس از آن وظیفه بیدرنگ و مشخصه‌های مهم آن را بیان میکنیم و انواع وظایف بیدرنگ را بر اساس فرکانس آزاد شدنشان شرح می‌دهیم. سپس به تعریف سررسید یک وظیفه پرداخته و انواع آن را بر اساس وابستگی آن به زمان آزاد شدن و همچنین وابستگی آن به دوره تناوب وظیفه شرح می‌دهیم. پس از تعریف هسته پردازنده در یک سیستم چندهستهای و منابع در یک سیستم تعبیه‌شده، به بررسی مفاهیم زمانبندی و اصطلاحات مختلف در زمانبندی یک سیستم می‌پردازیم و در نهایت سیستمهای چندهستهای را تعریف کرده و ویژگی‌ها و عملکرد آنها را شرح می‌دهیم.
در فصل سوم ابتدا به طبقه‌بندی انواع روشهای زمانبندی تک‌هسته‌ای می‌پردازیم و سپس چندتا از الگوریتم‌های معروف زمانبندی تک هسته‌ای را شرح می‌دهیم. سپس انواع معماری سیستمهای چندهستهای را تشریح میکنیم و پس از آن به توصیف طبقه‌بندی انواع روشهای زمانبندی چندهستهای و مزایا و معایب هرکدام خواهیم پرداخت. سپس روشهای زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان میکنیم و در نهایت به شرح کامل الگوریتم‌های زمانبندی چندهستهای ارائه شده در مقاله‌های مرتبط گذشته می‌پردازیم و مزایا و معایب آنها را تحلیل میکنیم.
در فصل چهارم الگوریتمی برای توزیع و زمانبندی وظایف در یک سیستم چندهستهای پیشنهاد خواهد شد. این الگوریتم شامل سه سطح است، سطح اول تفکیک وظایف و هسته‌های متناسب با آنها، سطح دوم الگوریتمی برای توزیع واختصاص وظایف بین هسته‌ها و سطح سوم، یک الگوریتم انرژی- سررسید محور، برای تنظیم فرکانس هسته‌ها متناسب با سررسید و زمان اجرای وظایف میباشد. در این فصل ابتدا جایگاه الگوریتم پیشنهادی خود را در بین طبقه‌بندی انواع الگوریتم‌های زمانبندی چندهستهای مشخص میکنیم و سپس ساختار کلی زمانبندی پیشنهادی خود را با رسم شکل دقیق آن بیان میکنیم. سپس به بیان کلیات الگوریتم پیشنهادی خود پرداخته و مدل وظیفه و تمامی مشخصه‌های آن در الگوریتم خود را تشریح میکنیم. سپس مدل سیستم پیشنهادی خود را بیان میکنیم و بعداز آن به شرح کامل همراه با جزئیات الگوریتم پیشنهادی خود می‌پردازیم.
در فصل پنجم نحوه شبیه سازی، محیط آن و شرایط سیستم شرح داده خواهد شد و نتایج آزمایش و مقایسه با دیگر روش‌ها بیان خواهد شد. ابتدا به بیان تنظیمات اولیه شبیه‌سازی خواهیم پرداخت و سپس محیط شبیه‌سازی و زبان برنامه نویسی مورد استفاده برای شبیه‌سازی را بیان خواهیم کرد. سپس به ارزیابی مصرف انرژی، میزان نقض سررسید، متوسط زمان پاسخ وظایف غیرتناوبی و متوسط زمان انتظار آنها در الگوریتم پیشنهادی در مقایسه با دیگر الگوریتم‌ها با نشان دادن نمودار خواهیم پرداخت.
در فصل ششم به بیان نتیجه‌گیری نهایی این پژوهش پرداخته خواهد شد و پیشنهاداتی برای کارهای آینده ارائه میشود.
فهرست مطالب |
چکيده. 1
فصل اول :مقدمه
1-1 پيشگفتار. 2
1-2 توصيف مسئله. 3
1-3 ساختار پايان نامه. 4
فصل دوم :مفاهيم اوليه
2-1 سيستم های تعبيه‌شده. 6
2-1-1 مصرف انرژی در سيستم‌های تعبيه‌شده. 8
2-2 سيستم‌های بیدرنگ ….. 9
2-2-1 انواع سيستم های بیدرنگ از نظر محدوديت زمانی.. 11
2-2-2 تابع بهره‌وری در سيستم‌های بیدرنگ….. 12
2-3 وظيفه. 13
2-3-1 مدل وظيفه بیدرنگ….. 14
2-3-2 دسته‌بندی وظايف بیدرنگ….. 15
2-4 سررسيد.. 16
2-5 هسته پردازنده. 18
2-6 منابع. 18
2-7 مفاهيم زمانبندی.. 19
2-7-1 تعاريف مربوط به مبحث زمانبندی.. 20
2-8 سيستم های چندهستهای.. 21
2-9 نتيجه‌گيری.. 22
فصل سوم : مرور منابع و کارهای انجام‌شده
3-1 طبقه بندی روشهای زمانبندی.. 23
3-2 الگوريتم‌های زمانبندی بیدرنگ تک پردازنده. 26
3-3 طبقه‌بندی معماری سيستم‌های چندهستهای.. 29
3-4 زمانبندی بیدرنگ چندهستهای .. 30
3-4-1 معايب روشهای زمانبندی عمومی و جزبندی.. 32
3-5 زمانبندی چند هسته‌ای مبتنی بر DVFS.. 34
3-6 بررسی کارهای گذشته. 37
3-6-1 الگوريتم توزيع بار غير تعادلی LU-McEP.. 37
3-6-2 الگوريتم زمانبندی غيرتعادلی جزبندی با RBound.. 42
3-6-3 الگوريتم زمانبندی چند سطحی PDAMS 47
3-6-4 الگوريتم زمانبندی پيشنهادی در مرجع ]37[. 59
3-7 نتيجه‌گيری.. 65
فصل چهارم : الگوريتم پيشنهادی
4-1 جايگاه الگوريتم پيشنهادی.. 66
4-2 کليات الگوريتم پيشنهادی.. 68
4-3 مدل وظيفه الگوريتم پيشنهادی.. 68
4-4 مدل سيستم الگوريتم پيشنهادی.. 69
4-5 شرح کامل الگوريتم پيشنهادی.. 71
4-5-1 بخش اول الگوريتم پيشنهادی (تفکيک وظايف و هسته‌ها). 71
4-5-2 بخش دوم الگوريتم پيشنهادی (توزيع وظايف بين هسته‌ها). 72
4-5-3 الگوريتم پيشنهادی تنظيم فرکانس سررسيد محور (بخش سوم الگوريتم پيشنهادی). 83
4-6 نتيجه‌گيری.. 88
فصل پنجم :شبيه‌سازی و ارزيابی الگوريتم پيشنهادی
5-1 تنظيمات اوليه شبيه‌سازی.. 89
5-2 محيط شبيه‌سازی.. 91
5-3 ارزيابی انرژی مصرفی.. 92
| نه |
5-4 ارزيابی کارايی.. 97
5-4-1 ارزيابی نرخ نقض سررسيد.. 97
5-4-2 ارزيابی متوسط زمان پاسخ وظايف غيرتناوبی.. 99
5-4-3 ارزيابی متوسط زمان انتظار وظايف غيرتناوبی.. 101
5-5 نتيجه‌گيری.. 102
فصل ششم : نتيجه‌گيری و پيشنهادات
6-1 نتيجه‌گيری.. 103
6-2 پيشنهادات… 104
مراجع. 105
واژگان اختصاری.. 108
| ده |
فهرست شکلها
شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بیدرنگ 13
شکل 2-2- نمودار گذار حالت یک وظیفه. 14
شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه. 17
شکل 3-1 تفسیم‌بندی انواع روشهای زمانبندی.. 26
شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF.. 27
شکل 3-3 بررسی اجمالی معماری پردازنده AMP و SMP.. 30
شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده 32
شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست… 33
شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهستهای.. 34
شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون DVFS ب) با DVFS.. 36
شکل 3-8 شبه کد الگوریتم تخصیص وظایف…. 40
شکل 3-9 الگوریتم ScaleTaskSet 43
شکل 3-10 شبه کد الگوریتم RBound-FF.. 45
شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35] 46
شکل 3-12 مدل سیستم مرجع [36] 50
شکل 3-13 شبه کد الگوریتم ED3VFS 54
شکل 3-14 مثالی از بارگذاری غیرتعادلی.. 55
شکل3-15 مثالی از توزیع وظایف بیدرنگ…. 56
شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB.. 59
شکل 3-17 شبه‌کد الگوریتم جزبندی با WFD… 61
شکل 3-18 شبه کد زمانبند پیشنهادی در [37] 62
شکل 3-19 شبه‌کد سیاست اجرای EDF.. 62
شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF.. 63
شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در [37] 63
شکل 3-22 نمودار زمانی مثال مربوطه در [37] 65
شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی.. 67
شکل 4-2 مدل سیستم پیشنهادی.. 70
شکل 4-3 شبه‌کد الگوریتم توزیع وظایف تناوبی.. 76
شکل 4-6 شبه‌کد الگوریتم پیشنهادی توزیع وظایف غیرتناوبی.. 80
شکل 4-7 فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی.. 81
| یازده |
شکل 4-8 نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی.. 84
شکل 5-1 مقایسه انرژی مصرفی حالت‌های مختلف نسبت تفکیک هسته‌ها برای وظایف تناوبی و غیرتناوبی.. 93
شکل 5-2 انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف…. 94
شکل 5-3 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS.. 95
شکل 5-4 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS در 6 مجموعه وظیفه مختلف…. 96
شکل 5-5 مقایسه نرخ نقض سررسید وظایف در همه حالت‌های ممکن الگوریتم پیشنهادی.. 97
شکل 5-6 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS.. 98
شکل 5-7 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی ما با الگوریتم‌های LU-McEP و PDAMS را در تمام حالت‌ها 99
شکل 5-8 مقایسه زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و PDAMS.. 100
شکل 5-9 مقایسه متوسط زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و PDAMSدر همه حالت‌ها 101
شکل 5-10 مقایسه متوسط زمان انتظار وظایف غیرتناوبی الگوریتم پیشنهادی ما نسبت به الگوریتم‌های LU-McEP و PDAMS.. 102
فهرست جدولها
جدول 2-1 خلاصه‌ای از مشخصه‌های یک سیستم تعبیه‌شده بیدرنگ…. 10
جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در [37] 64
جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در [37] 64
جدول 4-1 فرکانسها و توان متناظر هر سطح فرکانسی.. 85
جدول 4-2 مثال عددی از الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی.. 86
جدول 5-1 مشخصات پردازنده چندهستهای PowerPC 405PL شرکت IBM… 89
راهنمای خرید و دانلود فایل
برای پرداخت، میتوانید از کلیه کارتهای عضو شتاب استفاده نمائید.
بعد از پرداخت آنلاین لینک دانلود فعال و نمایش داده میشود ، همچنین یک نسخه از فایل همان لحظه به ایمیل شما ارسال میگردد.
در صورت بروز هر مشکلی،میتوانید از طریق تماس با ما پیغام بگذارید و یا در تلگرام با ما در تماس باشید، تا شکایت شما مورد بررسی قرار گیرد.
برای دانلود فایل روی دکمه خرید و دانلود کلیک نمایید.
ديدگاه ها