چکیده

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

 

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

 

 

فهرست مطالب

 

 

عنوان                                                                                                                صفحه

 

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

 

 

 

 

 

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

 

 

عنوان                                                                                                                صفحه

 

جدول 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].