پیاده سازی الگوریتم Fast Load Balancing – FLB

پیاده سازی الگوریتم Fast Load Balancing – FLB

 فهرست مطالبعنوان                                             صفحه      فصل اول : مقدمه   1-1مفهوم گرید…………………………………………..21-2طبقه بندی گرید……………………………………… 4                      3-1 ارزیابی گرید……………………………………….. 4               1-4کاربردگرید……………………………………………5                 1-5 تعریف زمانبندی گرید………………………………….6   1-6 مروری بر تحقیقات گذشته………………………………..7   1-7 مفهوم اصطلاحات به کار برده شده…………………………81-8 نمای کلی پایان نامه…………………………………..9فصل دوم:زمانبندی کارها در سیستم های توزیع شده2-1 زمانبندی کلاستر و ویژگیهای آن ………………………… 102-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 الگوریتم های زمانبندی کارهای مستقل………………….322 -5-1 الگوریتم  MET  …………………………………….32     2-5-2 الگوریتمMCT……………………………………….32    2-5-3 الگوریتم   Min-min………………………………………..332-5-4 الگوریتم Max-Min …………………………………………332     -5-5 الگوریتم Xsuffrage……………………………………….34                             2   -5-6-الگوریتم GA . …………………………………….35     2-5-7- الگوریتم        SA. …………………………………….37فصل سوم:الگوریتم های زمانبندی گراف برنامه3-1 مشکلات زمانبندی گراف برنامه……………………………393-2 تکنیک­های مهم زمان­بندی گراف برنامه در سیستم­های توزیع شده…..40  3-2-1- روش ابتکاری بر پایه لیست ………………………….. 40 3-2-2- روش ابتکاری بر پایه تکثیر…………………………..40 3-2-3- روش ابتکاری کلاسترینگ………………………………..41 3-3- دسته بندی الگوریتم­های زمان­بندی گراف برنامه در سیستم­های توزیع شده……………………………………………..44
3-4- پارامترها و مفاهیم مورد استفاده در الگوریتم­های زمان­بندی گراف
 برنامه…………………………………………………46 3-5- الگوریتم­های زمان­بندی گراف برنامه با فرضیات محدودکننده……503-5-1- الگوریتمی با زمان چند جمله­ای برای گراف های درختی – الگوریتم HU …………………………………………….50
3-5-2- الگوریتمی برای زمان­بندی گراف برنامه با ساختار دلخواه در سیستمی
با دو پردازنده……………………………………51 3-5-3- الگوریتمی برای زمان­بندی گراف بازه­ای مرتب شده…………52 3-6- الگوریتم­های زمان­بندی گراف برنامه در محیطهای همگن ……….543-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…………………………………………633-7-2- الگوریتم CPOP…………………………………………..633-7-3- الگوریتم LMT………………………………………….643-7-4- الگوریتمTANH ………………………………………….65فصل چهارم :الگوریتم FLB1-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 ……………………………….