پایان نامه ارشد:ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار |
(در فایل دانلودی نام نویسنده موجود است)
تکه هایی از متن پایان نامه به عنوان نمونه :
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
فهرست مطالب
عنوان صفحه
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
شکل 4-1 الگوریتم توازن نسخه دوم ……………………………………………………………………………………. 41
1- مقدمه
1-1 مقدمه
کامپیوترهای امروزی مانند مغز انسان معمولا از بخش کوچکی از تواناییهای خود استفاده میکنند و اغلب به صورت غیرفعالند و منتظر اطلاعات ورودی میمانند. تصور کنید که اگر از منابع سختافزاری این همه کامپیوتر غیرفعال استفاده شود و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکههای محاسباتی (گرید)[1] زمینهای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستمهای دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید میباشد[1].
هدف شبکههای محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریتهای مختلف بین کاربران است. کاربران درخواستهای خود را پیوسته برای محیط گرید ارسال میکنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص میدهد. به چگونگی تخصیص این درخواستها روی گرههای محاسباتی مختلف زمانبندی[4] میگویند.
اعمال سیاستهای مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ میشوند. عملیات زمانبندی در سیاستهای مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده میکند. امکان دارد یک فاکتور نقش تعیین کنندهای در یکی از سیاستها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است.
1-2 هدف از اجرای پایان نامه
با توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.
در گریدهای محاسباتی هدف بالا بردن درصد استفاده از منابع در کنار کاهش زمان اتمام آخرین کار میباشد. در این طرح تحقیق همین اهداف را دنبال میکنیم و سعی داریم نگاشتی از کارها را ارائه دهیم که هم باعث بالا رفتن بهرهوری از منابع شود و هم کمترین زمان را برای اتمام آخرین کار داشته باشد.
1-3 مراحل انجام پایان نامه
فرم در حال بارگذاری ...
[سه شنبه 1398-07-23] [ 07:08:00 ب.ظ ]
|