فایل زمانبندی وظيفه‌ها در سيستم‌های بیدرنگ نهفته چندهستهای
دسته بندي :
کالاهای دیجیتال »
رشته کامپیوتر و IT (آموزش_و_پژوهش)
این پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد
فهرست مطالب...............................................................................................................................................................هشت
چکيده 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
چکيده
امروزه با پیشرفتهای چشمگیر در صنعت الکترونیک و نیاز روزافزون به تکنولوژیهای کنترلی، کاربرد و اهمیت سیستمهای تعبیه‌شده نیز بیشتر شده است تا جاییکه سیستمهای تعبیه‌شده از مهمترین زمینههای پژوهشی در سالهای اخیر محسوب میشوند. در اکثر مواقع، عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند، از اینرو عموماً اکثر سیستمهای تعبیه‌شده، بیدرنگ میباشند. تجهیزات نظامی و صنعتی، تلفن همراه و کاربردهای تجاری همچون دستگاههای خودپرداز و سیستمهای هوشمند، نمونه‌هایی از سیستمهای تعبیه‌شده بیدرنگ میباشند. علاوه بر بیدرنگ بودن، مصرف انرژی مناسب نیز یکی دیگر از مشخصههای اصلی سیستمهای تعبیه‌شده میباشد که یک مسئله اساسی پیش روی طراحان سیستمهای دیجیتال محسوب میشود. یکی از مسائل مهم در سیستمهای چند هستهای زمانبندی وظیفهها و اجرای آنها توسط هستههای موجود است. برخلاف سیستمهای تک هستهای که مسئله زمانبندی فقط در مورد زمان میباشد، در سیستمهای چند هستهای این مسئله یک مسئله دو بعدی است و علاوه بر زمان ، مکان و فضای اجرای هستهها را هم شامل میشود، یعنی تصمیمگیری میشود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در این پایان نامه ما بروی چهار مشکل اصلی در این نوع سیستم ها تمرکز میکنیم: مصرف انرژی ، بهرهوری سیستم، کارایی سیستم، زمان پاسخ سیستم. یکی از مهم ترین مسائلی که روی تمامی این چهار مشکل تاثیر مستقیم دارد نحوه توزیع بار بین منابع موجود است که در اینجا منظور از منابع، هستههای یک پردازنده چند هستهای میباشد. یک توزیع ناکارامد بار روی هستهها باعث مصرف انرژی بیشتر و پایین آمدن بهرهوری و کارایی کل سیستم میشود. بیشتر روشهایی که تاکنون ارائه شده‌اند، بدون توجه به نوع وظیفه، آنها را بین پردازندهها توزیع میکنند و بیشتر به تمرکز روی روشهای تنظیم فرکانس و ولتاژ هر هسته بسنده میکنند. الگوریتم پیشنهادی ما در این پروژه، یک الگوریتم سه سطحی میباشد که در سطح اول یک روش جدید برای تفکیک وظایف تناوبی از وظایف غیرتناوبی متناسب با تعداد هستههای موجود ارائه میشود. سطح دوم از دو قسمت تشکیل میشود. در قسمت اول یک الگوریتم جدید برای توزیع وظایف تناوبی بین هستههای مربوط به آن ها که در سطح اول الگوریتم مشخص شده، ارائه میشود و در قسمت دوم الگوریتم توزیع وظایف غیرتناوبی بین هستههای مشخص شده برای آنها ، مطرح میشود. در سطح سوم الگوریتم جدیدی برای تنظیم فرکانس و ولتاژ سررسید محور بیان میکنیم. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی ما در مقایسه با الگوریتم‌های موجود، در حین اینکه باعث کاهش مصرف انرژی کل سیستم میشود، بهرهوری و کارایی سیستم و همچنین زمان پاسخ وظایف غیر تناوبی را بهبود بخشیده است و با توجه به تامین سررسیدهای زمانی بیشتر برای وظایف تناوبی وکاهش زمان پاسخ وظایف غیرتناوبی با حفظ میزان کارایی و پایین بودن نسبی مرتبه زمانی اجرای الگوریتم، کیفیت سیستم افزایش پیدا خواهد کرد.
کلمات کلیدی : زمانبندی، وظایف بیدرنگ، پردازنده‌های چند هستهای ، سیستمهای تعبیه‌شده