مهندسی کامپیوتر (نرم‌افزار)

ارائه یک الگوریتم زمانبندی کارا در شبکه محاسباتی گرید با هدف کاهش زمان اتمام کل و توازن بار

استاد راهنما:

دکتر غلامحسین دستغیبی فرد

دی ماه 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
دانلود متن کامل در سایت sabzfile.com
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 مراحل انجام پایان نامه

برای انجام پایان­نامه آغاز مفاهیم گرید و روش­های موجود مطالعه و مطالعه شدند و بعد از مقایسه صورت گرفته روی روش­های مختلف، الگوریتم ژنتیک برای تولید نگاشت انتخاب گردید. در کنار الگوریتم ژنتیک الگوریتمی را ارائه کردیم که به توازن بار روی منابع کمک می­کند و با بهره گیری از مزایای دو الگوریتم نام برده شده نگاشت بهینه­ای را برای کارها بدست آوردیم. برای پیاده­سازی الگوریتم­ها از زبان برنامه نویسی java شده می باشد.

 

1-4 ساختار پایان نامه

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

[1]Grid Computing

[2]Resource Management

[3]Nodes Computation

[4]Scheduling

تعداد صفحه :77

قیمت : 14700 تومان

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :        ****       serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  **** ***