دانلود پروژه پیاده سازی الگوریتم FLB
(Fast Load Balancing for Distributed-Memory Machines)
فایل ورد و قابل ویرایش
در 89 صفحه
چکیده
پیاده سازی الگوریتم FLB
گرید محاسباتی مجموعه ای از منابع نا همگن و پویا که بوسیله یک شبکه به یکدیگر متصل می شوندو کاربران زیادی در مکان های مختلف آنها را به اشتراک می گذارنداغلب برنامه های کاربردی بوسیله گراف جهت دار بدون سیکل خلاصه می شوندکه رئوس آن کارها و یالهای آن ارتباطات بین کارها را نشان می دهد که در آن کارها وابسته هستند و بر اساس اولویت باید اجرا شوند به این معنی که در گراف تا والد یک کار انجام نشود فرزند یا فرزندان نباید انجام شوند
برای اینکه تمام این اصول رعایت شود و از منابع به صورت بهینه استفاده گردد از الگوریتم های زمانبندی استفاده می کنیم
در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای مستقل و وابسته می پردازیم و روشهای زمانبندی گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیمسپس الگوریتمFLB راتشریح کردوشبیه ازهای گرید را بررسی می کنیم
واژه های کلیدی
گراف جهت دار بدون سیکل ٬ کارهای وابسته٬ زمانبندی ٬گرید ٬تکثیر
فهرست مطالب
فصل اول : مقدمه
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-min33
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- الگوریتم Sarkar54
3-6-2- الگوریتمHLFET55
3-6-3- الگوریتم ETF55
3-6-4- الگوریتم ISH 55
3-6-5- الگوریتم FLB56
3-6-6- الگوریتم DSC56
3-6-7- الگوریتم CASS-II58
3-6-8- الگوریتم DCP59
3-6-9- الگوریتم MCP60
3-6-10- الگوریتم MD61
3-6-11- الگوریتم TDS61
3-7- الگوریتم¬های زمان¬بندی گراف برنامه در محیطهای ناهمگن63
3-7-1- الگوریتم HEFT63
3-7-2- الگوریتم CPOP63
3-7-3- الگوریتم LMT64
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- optosim79
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
دانلود پروژه پیاده سازی الگوریتم FLB
