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

چکيده 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

چکيده

امروزه با پیشرفت­های چشمگیر در صنعت الکترونیک و نیاز روزافزون به تکنولوژی­های کنترلی، کاربرد و اهمیت سیستم­های تعبیه‌شده نیز بیشتر شده است تا جاییکه سیستم­های تعبیه‌شده از مهمترین زمینه­های پژوهشی در سالهای اخیر محسوب می­شوند. در اکثر مواقع، عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند، از اینرو عموماً اکثر سیستم­های تعبیه‌شده، بی­درنگ می­باشند. تجهیزات نظامی و صنعتی، تلفن همراه و کاربردهای تجاری همچون دستگاههای خودپرداز و سیستم­های هوشمند، نمونه‌هایی از سیستم­های تعبیه‌شده بی­درنگ می­باشند. علاوه بر بی­درنگ بودن، مصرف انرژی مناسب نیز یکی دیگر از مشخصه­های اصلی سیستم­های تعبیه‌شده می­باشد که یک مسئله اساسی پیش روی طراحان سیستم­های دیجیتال محسوب می­شود. یکی از مسائل مهم در سیستم­های چند هسته­ای زمانبندی وظیفه­ها و اجرای آنها توسط هسته­های موجود است. برخلاف سیستم­های تک هسته­ای که مسئله زمانبندی فقط در مورد زمان می­باشد، در سیستم­های چند هسته­ای این مسئله یک مسئله دو بعدی است و علاوه بر زمان ، مکان و فضای اجرای هسته­ها را هم شامل می­شود، یعنی تصمیم­گیری می­شود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در این پایان نامه ما بروی چهار مشکل اصلی در این نوع سیستم ها تمرکز می­کنیم: مصرف انرژی ،  بهره‌وری سیستم، کارایی سیستم، زمان پاسخ سیستم. یکی از مهم ترین مسائلی که روی تمامی این چهار مشکل تاثیر مستقیم دارد نحوه توزیع بار بین منابع موجود است که در اینجا منظور از منابع، هسته­های یک پردازنده چند هسته­ای می­باشد. یک توزیع ناکارامد بار روی هسته­ها باعث مصرف انرژی بیشتر و پایین آمدن بهره­وری و کارایی کل سیستم می­شود. بیشتر روش­هایی که تاکنون ارائه شده‌اند، بدون توجه به نوع وظیفه، آنها را بین پردازنده­ها توزیع می­کنند و بیشتر به تمرکز روی روش­های تنظیم فرکانس و ولتاژ هر هسته بسنده می­کنند. الگوریتم پیشنهادی ما در این پروژه، یک الگوریتم سه سطحی می­باشد که در سطح اول یک روش جدید برای تفکیک وظایف تناوبی از وظایف غیرتناوبی متناسب با تعداد هسته­های موجود ارائه می­شود. سطح دوم از دو قسمت تشکیل می­شود. در قسمت اول یک الگوریتم جدید برای توزیع وظایف تناوبی بین هسته­های مربوط به آن ها که در سطح اول الگوریتم مشخص شده، ارائه می­شود و در قسمت دوم الگوریتم توزیع وظایف غیرتناوبی بین هسته­های مشخص شده برای آن‌ها ، مطرح می­شود. در سطح سوم الگوریتم جدیدی برای تنظیم فرکانس و ولتاژ سررسید محور بیان می­کنیم. نتایج شبیه­سازی نشان می­دهد که الگوریتم پیشنهادی ما در مقایسه با الگوریتم‌های موجود، در حین اینکه باعث کاهش مصرف انرژی کل سیستم می­شود، بهره­وری و کارایی سیستم و همچنین زمان پاسخ وظایف غیر تناوبی را  بهبود بخشیده است و با توجه به تامین سررسیدهای زمانی بیشتر برای وظایف تناوبی وکاهش زمان پاسخ وظایف غیرتناوبی با حفظ میزان کارایی و پایین بودن نسبی مرتبه زمانی اجرای الگوریتم، کیفیت سیستم افزایش پیدا خواهد کرد.

کلمات کلیدی :  زمان‌بندی، وظایف بی‌درنگ، پردازنده‌های چند هسته‌ای ، سیستم­های تعبیه‌شده