دانشگاه شیراز
دانشکدهی مهندسی برق و کامپیوتر
پایاننامه كارشناسی ارشد در رشته ی
مهندسی کامپیوتر (نرمافزار)
ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار
استاد راهنما:
دکتر غلامحسین دستغیبی فرد
دی ماه 1392
فهرست مطالب
عنوان صفحه
1- مقدمه …………………………………………………………………………………………………… 1
1-1 مقدمه ……………………………………………………………………………………………………………. 1
1-2 هدف از اجرای پایان نامه ………………………………………………………………………………. 2
1-3 مراحل انجام پایان نامه ………………………………………………………………………………….. 2
1-4 ساختار پایان نامه …………………………………………………………………………………………… 3
2- ادبیات موضوعی ………………………………………………………………………………………. 4
2-1 مقدمه ……………………………………………………………………………………………………………. 4
2-2 ساختار الگوریتم ژنتیک ………………………………………………………………………………… 6
2-3 عملگرهای ژنتیکی …………………………………………………………………………………………. 7
2-4 روند کلی الگوریتم ژنتیک ……………………………………………………………………………… 8
2-5 شرط پایان الگوریتم ………………………………………………………………………………………. 10
2-6 برخی از کاربردهای الگوریتم ژنتیک ……………………………………………………………… 10
2-7 تعاریف ……………………………………………………………………………………………………………… 11
2-8 مزایای اجرای موازی ……………………………………………………………………………………….. 12
2-9 مراحل زمانبندی در گرید …………………………………………………………………………….. 16
2-10 انواع زمانبند ………………………………………………………………………………………………….. 17
2-11 انواع زمانبندی ……………………………………………………………………………………………… 18
2-12 نحوهی زمانبندی (ایستا و پویا) …………………………………………………………………… 19
2-13 ساختار زمانبند …………………………………………………………………………………………….. 19
2-14 انواع صفبندی کارها ……………………………………………………………………………………. 21
2-15 پیچیدگی محاسباتی زمانبندی …………………………………………………………………….22
2-16 جمع بندی ………………………………………………………………………………………………… 22
3- پیشینه پژوهشی …………………………………………………………………………………….. 23
3-1 مقدمه ……………………………………………………………………………………………………………. 23
3-2 الگوریتمهای حریصانه ………………………………………………………………………………….. 23
3-3 الگوریتمهای تکاملی …………………………………………………………………………………….. 26
3-3-1 راهکارهای مبتنی بر جستجوی محلی ………………………………………… 26
3-3-2 راهکارهای جمعیت محور ……………………………………………………………. 28
3-4 جمعبندی …………………………………………………………………………………………………… 31
4- الگوریتمهای پیشنهادی ………………………………………………………………………….. 33
4-1 مقدمه ……………………………………………………………………………………………………………. 33
4-2 فرضیات وتعاریف …………………………………………………………………………………………… 34
4-3 الگوریتم Asuffrage …………………………………………………………………………………….. 35
4-4 الگوریتم MaxSuffrage ……………………………………………………………………………….. 36
4-5 الگوریتم توازن نسخه یک …………………………………………………………………………….. 38
4-6 الگوریتم توازن نسخه دو ………………………………………………………………………………. 40
4-7 الگوریتم ژنتیک و توازن بار ………………………………………………………………………….. 41
4-8 جمعبندی ……………………………………………………………………………………………………… 46
5- نتایج حاصل از ارزیابی………………………………………………..…………………………….. 47
5-1 مقدمه ……………………………………………………………………………………………………………. 47
5-2 محک ارزیابی براون ……………………………………………………………………………………… 47
5-3 ارزیابی الگوریتم Asuffrage ………………………………………………………………………… 49
5-4 ارزیابی الگوریتم MaxSuffrage …………………………………………………………………… 51
5-5 ارزیابی الگوریتم توازن نسخه یک …………………………………………………………………. 53
5-6 ازریابی الگوریتم توازن نسخه دو …………………………………………………………………… 54
5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار……………………………………………………. 55
5-8 پیشنهادات برای آینده …………………………………………………………………………………. 57
6- منابع ……………………………………………………………………………………………………… 58
فهرست جداول
عنوان صفحه
جدول 5-1 حالات ماتریس ETC …………………………………………………………………………………………. 49
جدول 5-2 نتایج makespan الگوریتم Asuffrage ……………………………………………………………. 50
جدول 5-3 نتایج resource utilization الگوریتم Asuffrage ……………………………………….. 51
جدول 5-4 نتایج makespan الگوریتم MaxSuffrage ……………………………………………………… 52
جدول 5-5 نتایج resource utilization الگوریتم MaxSuffrage ………………………………….. 53
جدول 5-6 نتایج makespan الگوریتم توازن نسخه یک …………………………………………………….. 54
جدول 5-7 نتایج makespan الگوریتم توازن نسخه دو ……………………………………………………….. 55
جدول 5-8 نتایج makespan الگوریتم ژنتیک به همراه توازن بار ………………………………………. 56
جدول 5-9 نتایج resource utilization الگوریتم ژنتیک به همراه توازن بار ……………………… 57
فهرست شکلها
عنوان صفحه
شکل 2-1 کروموزوم قبل و بعد از اعمال عملگر جهش ……………………………………………………….. 8
شکل 2-2 نمودار گردشی الگوریتم زنتیک …………………………………………………………………………… 9
شکل 2-3 ماتریس تخمین زمان اجرا (ETC) ……………………………………………………………………… 12
شکل 2-4 مجازیسازی منابع ناهمگن توسط گرید …………………………………………………………….. 13
شکل 2-5 مهاجرت کارها برای ایجاد توازن بار ……………………………………………………………………. 14
شکل 2-6 تنظیمات تکرار گرید …………………………………………………………………………………………… 15
شکل 2-7 تنظیم سیاست تخصیص کارها به منابع توسط مدیر …………………………………………. 16
شکل 2-8 ساختار زمانبند متمرکز ……………………………………………………………………………………….. 19
شکل 2-9 ساختار زمانبند سلسله مراتبی …………………………………………………………………………….. 20
شکل 2-10 ساختار زمانبند غیر متمرکز ……………………………………………………………………………… 20