دانلود متن کامل پایان نامه با فرمت ورد

پایان نامه مقطع کارشناسی ارشد رشته کامپیوتر

دانشگاه شیراز

دانشکده‌ی مهندسی برق و کامپیوتر

پایان‌نامه كارشناسی ارشد در رشته­­

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

عنوان:

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

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

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

برای رعایت حریم خصوصی نام نگارنده درج نمی شود

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

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 ……………………………………………………………………………………..

4-4 الگوریتم­ MaxSuffrage ………………………………………………………………………………..

4-5 الگوریتم توازن نسخه یک …………………………………………………………………………….. 38

4-6 الگوریتم توازن نسخه دو ………………………………………………………………………………. 40

4-7 الگوریتم ژنتیک و توازن بار ………………………………………………………………………….. 41

4-8 جمع­بندی ……………………………………………………………………………………………………… 46

5- نتایج حاصل از ارزیابی………………………………………………………………………………. 47

5-1 مقدمه ……………………………………………………………………………………………………………. 47

5-2 محک ارزیابی براون ……………………………………………………………………………………… 47

5-3 ارزیابی الگوریتم Asuffrage …………………………………………………………………………

5-4 ارزیابی الگوریتم MaxSuffrage ……………………………………………………………………

5-5 ارزیابی الگوریتم توازن نسخه یک …………………………………………………………………. 53

5-6 ازریابی الگوریتم توازن نسخه دو …………………………………………………………………… 54

5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار……………………………………………………. 55

5-8 پیشنهادات برای آینده …………………………………………………………………………………. 57

6- منابع ……………………………………………………………………………………………………… 58

چکیده:

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

1- مقدمه

1-1- مقدمه

کامپیوترهای امروزی مانند مغز انسان معمولا از بخش کوچکی از توانایی‌های خود استفاده می‌کنند و اغلب به‌ صورت غیرفعالند و منتظر اطلاعات ورودی می‌مانند. تصور کنید که اگر از منابع سخت‌افزاری این همه کامپیوتر غیرفعال استفاده شود و همه در یک کامپیوتر جمع شوند، چه دستگاه پرقدرتی خواهیم داشت. شبکه­های محاسباتی (گرید)[1] زمینه‌ای را فراهم آورده است که بتوان از منابع (کامپیوتری) سیستم‌های دیگر نیز استفاده نماییم. اغلب مسائل پیچیده علمی، مهندسی و تجارت احتیاج به میزان زیادی از منابع برای اجرا دارند، بهترین راه حل برای اینگونه مسائل استفاده از گرید می­باشد[1].

هدف شبکه­های محاسباتی (گرید) به اشتراک گذاشتن منابع کامپیوتری در نقاط مختلف جغرافیایی با مدیریت­های مختلف بین کاربران است. کاربران درخواست­های خود را پیوسته برای محیط گرید ارسال می­کنند و بخش مدیریت منابع[2] این کارها را به گره های محاسباتی[3] موجود در شبکه اختصاص می­دهد. به چگونگی تخصیص این درخواست­ها روی گره­های محاسباتی مختلف زمانبندی[4] می­گویند.

اعمال سیاست­های مختلف برای عملیات زمانبندی نتایج متفاوتی را خواهد داشت که این سیاست با توجه به اهداف مشخص شده برای گرید اتخاذ می­شوند. عملیات زمانبندی در سیاست­های مختلف از فاکتورهای متفاوتی برای تخصیص کارها روی منابع مختلف استفاده می­کند. امکان دارد یک فاکتور نقش تعیین کننده­ای در یکی از سیاست­ها داشته باشد ولی در سیاست دیگر اصلا به آن توجه نشود، از اینرو هدف هر الگوریتم بهینه کردن سیاست مورد نظر خود است.

 1-2 هدف از اجرای پایان نامه

با توجه به تاثیر بالای عملیات زمانبندی در عملکرد بهینه گرید و مزایایی که برای گرید در قسمت قبل ذکر شد، ارائه یک روش کارا در زمانبندی می تواند تاثیر زیادی در حل مسائل بزرگ در شاخه های مختلف داشته باشد.

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

1-3 مراحل انجام پایان نامه

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

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

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

2- ادبیات موضوعی

1-2- مقدمه

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

الگوريتم ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترين‏ها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينه‏كننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو، انتخاب ويژگي، درك تصوير و يادگيري ماشيني است[3-8]. در الگوريتم‏ ژنتيك[1]، نحوه تكامل ژنتيكي موجودات زنده شبيه‏سازي مي‏شود.

اگرچه كارهايي توسط يك زيست­شناس به نام Fraser در زمينه مدل­سازي تكامل در سيستم‌هاي بيولوژيك در دهه 60 ميلادي صورت گرفت ولي الگوريتم ژنتيك براي كاربردهاي مهندسي و به صورت امروزي آن، نخستين بار توسط جان هلند[9] متخصص علوم كامپيوتر دانشگاه ميشيگان در سال 1975 پيشنهاد گرديد. كار وي آغاز تمامي كوشش­ها براي كاربرد الگوريتم ژنتيك در مهندسي است. پس از آن كارهاي Dejong [10]در سال 1975 در زمينه بررسي و مقايسه چندين روش الگوريتم ژنتيك پايه‌هاي نظري بحث را فراهم آورد. اين الگوريتم با الهام از طبيعت بر پايه اصل تكاملي «پايداري بهترين‌ها»[2] استوار است. الگوريتم ژنتيك اگرچه پس از الگوريتم استراتژي تكاملي پيشنهاد گرديد ولي مشهورترين روش از بين الگوريتم‌هاي تكاملي است. در يك الگوريتم ژنتيك يك جمعيت از افراد طبق مطلوبيت آنها در محيط بقا مي­يابند. افرادي با قابليت­هاي برتر، شانس ازدواج وتوليد مثل بيشتري را خواهند يافت. بنابراين بعد از چند نسل فرزنداني با كارايي بهتر بوجود مي‌آيند. در الگوريتم ژنتيك هر فرد از جمعيت بصورت يك كروموزوم معرفي مي‌شود. كروموزوم­ها در طول چندين نسل كامل­تر مي‌شوند. در هر نسل كروموزوم­ها ارزيابي مي‌شوند و متناسب با ارزش خود امكان بقا و تكثير مي‌يابند. توليد نسل در بحث الگوريتم ژنتيك با عملگرهاي آمیزش3 و جهش4 صورت مي‏گيرد. والدين برتر بر اساس يك تابع برازندگي انتخاب مي‌شوند.

در هر مرحله از اجراي الگوريتم ژنتيك، يك دسته از نقاط فضاي جستجو مورد پردازش‏هاي تصادفي قرار مي‏گيرند. به اين صورت كه به هر نقطه دنباله‏اي از كاراكترها نسبت داده مي‏شود و بر روي اين دنباله‏ها، عملگرهاي ژنتيكي اعمال مي‏شوند. سپس دنباله‏هاي بدست آمده رمزگشایی مي‏گردد تا نقاط جديدي در فضاي جستجو بدست آيد. در آخر براساس اين كه تابع هدف در هر يك از نقاط چه مقدار باشد، احتمال شركت نمودن آنها در مرحله بعد تعيين مي‏گردد[11-14].

الگوريتم‏ ژنتيك را مي‏توان يك روش بهينه‏سازي تصادفي جهت‏دار دانست كه به تدريج به سمت نقطه بهينه حركت مي‏كند. در مورد ويژگي‌هاي الگوريتم ژنتيك در مقايسه با ديگر روش‌هاي بهينه سازي مي‌توان گفت كه الگوريتمي است كه بدون داشتن هيچ گونه اطلاعي از مسئله و هيچ گونه محدوديتي بر نوع متغيرهاي آن براي هر گونه مسئله اي قابل اعمال است و داراي كارآيي اثبات شده‌اي در يافتن بهينه كلي[3] مي‌باشد. توانايي اين روش در حل مسائل پيچيده بهينه‌سازي است كه روش‌هاي كلاسيك يا قابل اعمال نيستند و يا دريافتن بهينه كلي قابل اطمينان نيستند[15].

[1] Genetic Algorithm

[2] Survival of the fittest

3 Cross Over

4 Mutation

[3] Global Optimum

[1]Grid Computing

[2]Resource Management

[3]Nodes Computation

[4]Scheduling

***ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است***

متن کامل را می توانید دانلود نمائید

چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

تعداد صفحه : 77

قیمت : 14700 تومان

 

***

—-

:       

****         serderehi@gmail.com

جستجو در سایت : کلمه کلیدی خود را وارد نمایید :