پایان نامه رشته کامپیوتر با عنوان پیاده سازی الگوریتم FLB با فرمت WORD

فهرست مطالب

 عنوان                                              صفحه       

 فصل اول  :  مقدمه   

1-1مفهوم گرید..................................................2   

  1-2طبقه بندی گرید............................................. 4                         

 3-1 ارزیابی گرید............................................... 4                 

1-4کاربردگرید...................................................5                     

1-5 تعریف زمانبندی گرید........................................6  

1-6 مروری بر تحقیقات گذشته......................................7    

1-7 مفهوم اصطلاحات به کار برده شده..............................8

1-8 نمای کلی پایان نامه.........................................9

فصل دوم:زمانبندی کارها در سیستم های توزیع شده

2-1 زمانبندی کلاستر و ویژگیهای آن .............................. 10 

2-2 زمانبندی گرید و ویژگیهای آن................................13   

 3-2  رده بندی الگوریتم های زمانبندی گرید....................... 16 

  2-3-1   زمانبندی محلی/سراسری................................. 16            

  2-3-2  زمانبندی ایستا/پویا...................................16    

  2-3-3  زمانبندی بهینه/نزدیک به بهینه...........................21

  2-3-4  زمانبندی توزیع شده/مرکزی..............................22

  2-3-5  زمانبندی همکار و مستقل...............................22

2-3-6  زمانبندی زمان کامپایل /اجرا........................ 23

 2-4-1  رده بندی الگوریتم های زمانبندی از دیدگاهی دیگری..... 23

  2-4-2  اهداف زمانبندی.........................................23  

  2-4-3   زمانبندی وفقی.......................................24

  2-4-4 رده بندی برنامه های کاربردی...........................25

   2-4-4-1  کارهای وابسته.....................................25

   2-4-4-2  گراف کار..........................................26

 2-4-5   وابستگی کارهای تشکیل دهنده برنامه کاربردی...........       26   

2-4-6  زمانبندی تحت قیود کیفیت سرویس..........................26   

2-4-7  راهکارهای مقابله با پویایی گرید.......................28

 2-5  الگوریتم های زمانبندی کارهای مستقل......................32

2 -5-1 الگوریتم   MET   ...........................................32

      2-5-2  الگوریتم  MCT..............................................32

      2-5-3 الگوریتم   Min-min...............................................33

  2-5-4  الگوریتم Max-Min ................................................33

2      -5-5 الگوریتم Xsuffrage  ..............................................34                                 

2   -5-6-  الگوریتم GA . ...........................................35      

2-5-7- الگوریتم        SA. ...........................................37 

فصل سوم:الگوریتم های زمانبندی گراف برنامه

3-1 مشکلات زمانبندی گراف برنامه.................................39

3-2 تکنیک­های مهم زمان­بندی گراف برنامه در سیستم­های توزیع شده.....40   

3-2-1-  روش ابتکاری بر پایه لیست ................................ 40

  3-2-2- روش ابتکاری بر پایه تکثیر................................40

  3-2-3- روش ابتکاری کلاسترینگ......................................41

 3-3- دسته بندی الگوریتم­های زمان­بندی گراف برنامه در سیستم­های توزیع شده.....................................................44

 3-4- پارامترها و مفاهیم مورد استفاده در الگوریتم­های زمان­بندی گراف   برنامه.........................................................46

 3-5- الگوریتم­های زمان­بندی گراف برنامه با فرضیات محدودکننده......50

  3-5-1- الگوریتمی با زمان چند جمله­ای برای گراف های درختی - الگوریتم HU ....................................................50

  3-5-2- الگوریتمی برای زمان­بندی گراف برنامه  با  ساختار دلخواه در سیستمی با دو پردازنده..........................................51 

  3-5-3- الگوریتمی برای زمان­بندی گراف بازه­ای مرتب شده............52

 3-6- الگوریتم­های زمان­بندی گراف برنامه در محیطهای  همگن ..........54

  3-6-1- الگوریتم Sarkar................................................54

   3-6-2- الگوریتمHLFET................................................55

   3-6-3- الگوریتم ETF................................................55

   3-6-4- الگوریتم ISH ..............................................55

   3-6-5- الگوریتم FLB................................................56

   3-6-6- الگوریتم DSC................................................56

   3-6-7- الگوریتم CASS-II..............................................58

   3-6-8- الگوریتم DCP................................................59

   3-6-9- الگوریتم MCP................................................60

   3-6-10- الگوریتم MD...............................................61

   3-6-11- الگوریتم TDS...............................................61

 3-7- الگوریتم­های زمان­بندی گراف برنامه در محیطهای ناهمگن...............63    

  3-7-1- الگوریتم HEFT................................................63

  3-7-2- الگوریتم CPOP..................................................63

  3-7-3- الگوریتم LMT.................................................64

  3-7-4- الگوریتمTANH .................................................65  

 فصل چهارم :الگوریتم FLB

1-4           ویژگیهای الگوریتم........................................66  

    4-2 اصطلاحات به کار برده شده.................................66

    4-3 الگوریتم................................................67  

    4-4 پیچیدگی الگوریتم........................................75       

    4-5 کارایی الگوریتم.........................................77 .

فصل پنجم: شبیه سازی گرید

    5-1 ابزار شبیه سازی...................................79

        5-1-1- optosim..................................................79

        5-1-2 SimGrid ..................................................80

        5-1-3- Gridsim  ..................................................80

 کارهای انجام شده...............................................83          پیشنهادات............................................................83 

 مراجع     .............................................................85   

فهرست اشکال

   عنوان                                          صفحه

    شکل 1-2 ساختار کلاستر  ......................................11

    شکل 2-2 ساختار زمانبند گرید ...............................14

    شکل 2-3-2 رده بندی الگوریتم های ایستا.......................19

    شکل 2-4 رده بندی برنامه های کاربردی.........................26

    شکل 2-5-6کلاس بندی برنامه های کاربردی .......................37

    شکل 3-2-3 گراف نمونه با هزینه محاسباتی و ارتباطی .............43

    شکل 3-3 دسته بندی الگوریتم های گراف برنامه..................45

    شکل 3-4 گراف کارها .........................................50

    شکل 3-5-3 گراف بازه ای مرتب شده با هزینه محاسباتی یکسان .....53

   شکل 3-5-3 مقایسه الگوریتم های زمانبندی گراف برنامه در محیطهای

   همگن ........................................................54

    شکل     4-1 گراف کار...........................................76

    شکل  5-2 ساختار   Gridsim  .....................................81