دانلود پروژه: بررسی الگوریتم های تخصیص مجدد در گریدهای محاسباتی و ارائه یک الگوریتم کارا

 

فهرست مطالب

عنوان                                                                                                                صفحه

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