مطالعه الگوریتم های تخصیص مجدد در گریدهای محاسباتی و ارائه یک الگوریتم کارا

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

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

اسفند ماه 1392

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

(در فایل دانلودی نام نویسنده موجود می باشد)

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

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

چکیده

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

 

کلید واژه: گرید محاسباتی، زمانبندی، زمانبندی مجدد، جریان کار.

 

 

فهرست مطالب

 

 

عنوان                                                                                                                صفحه

 

1- مقدمه ………………………………………………………………………………………………………………  1

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

1-2 ضرورت اجرا……………………………………………………………………………………………………………………………………. 2

1-3 هدف از اجرای پایان­نامه………………………………………………………………………………………………………………… 3

1-4 مراحل انجام پایان­نامه…………………………………………………………………………………………………………………….. 4

1-5 ساختار پایان­نامه………………………………………………………………………………………………………………………. 4

2- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته……………………………………………. 5

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

2-2 ساختار متمرکز……………………………………………………………………………………………………………………….. 7

2-3 ساختار غیر متمرکز و یا توزیعی……………………………………………………………………………………………. 8

2-4 فرایند زمانبندی گرید و اجزای آن ………………………………………………………………………………………. 10

2-5 انواع زمانبند …………………………………………………………………………………………………………………………… 11

2-6 انواع کارها ………………………………………………………………………………………………………………………………. 12

2-7 چگونگی­ی زمانبندی ……………………………………………………………………………………………………………………. 14

2-8 وظایف فرازمانبند …………………………………………………………………………………………………………………… 14

2-8-1 نگاشت کار …………………………………………………………………………………………………………………….. 15

2-9 گذری بر تحقیقات پیشین …………………………………………………………………………………………………….. 17

2-9-1 مفاهیم اولیه …………………………………………………………………………………………………………………. 17

2-9-2 الگوریتم ETF ……………………………………………………………………………………………………………….. 19

2-9-3 الگوریتم Myopic …………………………………………………………………………………………………………. 19

2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای ………………………………………….. 19

2-9-5 الگوریتم HLEFT ………………………………………………………………………………………………………… 20

2-9-6 الگوریتم hybrid …………………………………………………………………………………………………………… 20

2-9-7 الگوریتم GRASP ……………………………………………………………………………………………………….. 21

2-9-8 الگوریتم CPOP …………………………………………………………………………………………………………… 21

2-9-9 الگوریتم PETS …………………………………………………………………………………………………………….. 22

2-9-10 الگوریتم HLEFT با نگاه به جلو ……………………………………………………………………………… 23

2-9-11 الگوریتم FTBAR …………………………………………………………………………………………………….. 23

2-9-12  الگوریتم TSB ………………………………………………………………………………………………………….. 24

2-10  جمع بندی ………………………………………………………………………………………………………………………… 24

3- الگوریتم­های پیشنهادی ……………………………………………………………………………….. 25

3-1 مقدمه ……………………………………………………………………………………………………………………………………… 25

3-2 الگوریتم Asuffrage ……………………………………………………………………………………………………………… 27

3-3 الگوریتم MaxSuffrage ……………………………………………………………………………………………………….. 28

3-4 الگوریتم DHLEFT……………………………………………………………………………………………………………….. 30

4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ………………………………… 34

4-1 مقدمه ……………………………………………………………………………………………………………………………………… 34

4-2 محک ارزیابی براون…………………………………………………………………………………………………………………. 34

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

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

4-5  ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار………………………………………………………….. 40

4-6 ارزیابی الگوریتم DHLEFT…………………………………………………………………………………………………… 43

4-7 نتیجه گیری و پیشنهادات برای آینده …………………………………………………………………………………. 49

5- منابع…………………………………………………………………………………………………………… 50

 

 

 

 
دانلود متن کامل در سایت sabzfile.com
 

فهرست جدول­ها

 

 

عنوان                                                                                                                صفحه

 

جدول 4-1 حالات ماتریس ETC………………………………………………………………………………………………………. 36

جدول 4-2 نتایج زمان اتمام آخرین کار الگوریتم Asuffrage……………………………………………………….. 37

جدول 4-3 نتایج درصد بهره­وری از منابع الگوریتم Asuffrage…………………………………………………….. 37

جدول 4-4 نتایج زمان اتمام آخرین کار الگوریتم MaxSuffrage…………………………………………………. 39

جدول 4-5 نتایج درصد بهره­وری از منابع الگوریتم MaxSuffrage………………………………………………. 39

جدول 4-6 مقادیر پارامتر N………………………………………………………………………………………………………………. 41

جدول 4-7 مقادیر پارامتر Fat……………………………………………………………………………………………………………. 41

جدول 4-8  مقادیر پارامتر Density………………………………………………………………………………………………….. 41

جدول 4-9  درصد خطا در تخمین زمان اجرایی…………………………………………………………………………….. 42

جدول 4-10  زمان رخداد رویداد………………………………………………………………………………………………………. 43

جدول 4-11 میانگین نتایج  زمان اتمام آخرین کار الگوریتم DHLEFT…………………………………….. 48

جدول 4-12 میانگین نتایج درصد بهره­وری از منابع الگوریتم DHLEFT……………………………………. 48

 

 

 

فهرست شکل­ها

 

 

عنوان                                                                                                                صفحه

 

شکل‏2-1 معماری زمانبندی متمرکز ………………………………………………………………………………………………… ……. 7

شکل‏2-2 معماری زمانبندی سلسله مراتبی …………………………………………………………………………………….. ……. 9

شکل ‏2-3 معماری زمانبندی غیرمتمرکز ………………………………………………………………………………………… ……. 9
جستجو در سایت :   


شکل ‏2-4 معماری زمانبندی گرید …………………………………………………………………………………………………… 10

شکل ‏2-5 جریان کار …………………………………………………………………………………………………………………………. 13

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

شکل ‏2-6 نمونه ماتریس ETC …………………………………………………………………………………………………………. 14

شکل ‏2-7 گراف جهت دار بدون دور(DAG) ………………………………………………………………………………….. 18

شکل ‏2-8 جدول زمان اجرایی تخمینی …………………………………………………………………………………………… 18

شکل 3-1 شبه کد الگوریتم DHLEFT ………………………………………………………………………………………….. 33

شکل 4-1 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.1………………………………………. 44

شکل 4-2 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.3………………………………………. 45

شکل 4-3 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.5………………………………………. 45

شکل 4-4 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.7………………………………………. 46

شکل 4-5 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.1……………………………………. 46

شکل 4-6 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.3……………………………………. 47

شکل 4-7 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.5……………………………………. 47

شکل 4-8 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.7……………………………………. 48

مقدمه

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

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

یکی از عملیات اصلی تضمین کننده­ی کارایی در شبکه­های تورین محاسباتی، تخصیص منابع به کارها می­باشد. عملیات تخصیص منابع بایستی مکانیسم­هایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای صد در صد کارها، افزایش بهره­وری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با در نظر داشتن توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامه­های کاربردی و محدودیت­های اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete می باشد[3].

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

در دهه گذشته زمانبندی کارها (وظایف با وابستگی و مستقل) درون محیط گرید توجه بسیاری از محققین را به خود جلب کرده می باشد. به دلیل پویایی محیط گرید، عملیات زمانبندی بایستی مرتبا با مطالعه کردن حالت جاری سیستم، اقدام به بروزرسانی زمانبند خود نماید. عملیات بروزرسانی با رخداد رویدادی در گرید به دلیل تخمین نادقیق زمان اجرایی، اضافه یا حذف شدن منابع، رخ می دهد. در واقع هدف اصلی از اعمال زمانبندی مجدد افزایش بهره وری از منابع، اجرای قطعی و کاهش زمان اتمام کارها می باشد به این شکل که در آغاز براساس وضعیت جاری منابع و کارها زمانبندی صورت می پذیرد و در صورت رخداد رویدادهای فوق زمانبندی مجدد براساس منابع موجود و وضعیت کارهای باقی مانده صورت می پذیرد.

تعداد صفحه : 78

قیمت : 14700 تومان

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

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

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

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

***  **** ***