پایان نامه پیاده سازی الگوریتم FLB

چکیده

پیاده سازی الگوریتم FLB

گرید محاسباتی  مجموعه ای از منابع نا همگن و پویا که بوسیله یک شبکه به یکدیگر متصل می شوندو کاربران زیادی در مکان های مختلف آنها را به اشتراک می گذارند.اغلب برنامه های کاربردی بوسیله گراف جهت دار بدون سیکل خلاصه می شوندکه رئوس آن کارها و یالهای آن ارتباطات بین کارها را نشان می دهد. که در آن کارها وابسته هستند و بر اساس اولویت باید اجرا شوند به این معنی که در گراف تا والد یک کار انجام نشود فرزند یا فرزندان نباید انجام شوند.

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

در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن  وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای  مستقل و وابسته می پردازیم و روشهای زمانبندی  گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیم.سپس الگوریتمFLB راتشریح کردوشبیه ازهای گرید را بررسی می کنیم. 

واژه های کلیدی : گراف جهت دار بدون سیکل ? کارهای وابسته?  زمانبندی ?گرید ?تکثیر.

 مقدمه

 قبل از ابداع کامپیوترهای شخصی،  عملا سیستم های توزیع شده ای  وجود نداشته است . در آن دوران ، استفاده از کامپیوتر،  شامل نشستن پشت یک ترمینال و برقراری ارتباط با یک سیستم بزرگ  بود. با اینکه ترمینال ها در  چندین ساختمان و یا حتی محل فیزیکی قرار می گرفتند ،  ولی عملا  یک کامپیوتر مرکزی وجود داشت که مسئولیت  انجام تمامی پردازش ها و ذخیره سازی  داده ها را برعهده می گرفت .

Mainfram  معایب 

• ·  هزینه سیستم های Mainfarme  . یکی از اولین دلایل مهم ، هزینه های بالای سیستم هایMainframe است . این مسئله از دو زاویه متفاوت قابل بررسی است : هزینه بالای سرمایه گذاری اولیه که بسیاری  از سازمان ها و موسسات توان مالی آن را ندارند و دوم اینکه در این مدل ، دارای صرفا" یک نقطه  آسیب پذیر با ریسک بالا می باشیم .
• ·  مالکیت اختصاصی داده ها. یکی از فاکتورهای مهم دیگر،  سیاست های مربوط به مالکیت داده ها است . سازمان ها و موسسات که  دارای داده های اختصاصی خود می باشند،  علاقه مند به واگذاری مسئولیت مدیریت داده های مربوطه ،  به سایر مکان های فیزیکی نمی باشند .
• ·    امنیت . یکی دیگر از فاکتورهای مهم در این زمینه موضوع امنیت است . برای یک سازمان ،  اولا" دستیابی به اغلب داده های آن می بایست بسادگی محقق گردد و ثانیا"  داده ها ی حساس موجود در  سازمان می بایست از بعد امنیتی،  ایمن نگهداری گردند . تامین دو خواسته فوق ( رویکردهای رقابتی  و رویکردهای امنیتی ) با جدا سازی فیزیکی داده از یکدیگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستیابی و ایمن در ذخیره سازی ، ضرورت وجود برنامه های توزیع شده را بخوبی نمایان می سازد )   

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

 روش ابتکاری بر پایه لیست

در این روش به هر کار اولویتی داده می­شود و کارها به ترتیب اولویت در لیست قرارمی­گیرند. انتخاب کار برای پردازش به ترتیب اولویت انجام می­گیرد و کار با اولویت بالاتر زودتر به منبع واگذار می­شود. تفاوت اصلی الگوریتم­های این دسته، در چگونگی  تعریف اولویت و تعریف آماده بودن کار، برای واگذاری است. زمانی که گره­ها و لبه­ها را مرتب کردیم، هنگام واگذاری کارها به منابع با دو مسئله روبرو هستیم: چگونه کارها را به شکل موازی اجرا کنیم که ترتیب تقدمی آنها حفظ شود و چگونه هزینه زمانی مسیر بحرانی را تاحد امکان کوچک نماییم.[36] 

روش ابتکاری بر پایه تکثیر

یکی از روش­های کم کردن زمان گسترش، تکثیر کارها در منابع مختلف است. ایده اصلی این الگوریتم­ها بهره­وری از زمان بیکاری برای تکثیر کارهای ماقبل است. این مسئله باعث اجتناب از انتقال نتایج از کار قبلی به کار بعدی است و به همین دلیل هزینه ارتباطی را کاهش می­دهد. بنابراین با تکیه بر این استراتژی می­توان مشکل Max-Min را حل کرد. الگوریتم­های مختلف این روش، بر اساس نحوه گزینش  کار برای تکثیر، از هم متمایز می­شوند. این دسته الگوریتم­ها در ابتدا برای تعداد معینی پردازنده یکسان (مانند سیستمهای چند پردازنده با حافظه توزیع شده) به کار رفت. البته این الگوریتم­ها دارای پیچیدگی بالاتری نسبت به الگوریتم­های ابتکاری لیست هستند.

روش ابتکاری کلاسترینگ

در سیستم­های موازی و توزیع شده، کلاسترینگ روش مناسبی برای کاهش تاخیر ارتباطی  گراف به حساب می­آید.  در این روش با قراردادن  کارهایی که ارتباط زیادی باهم دارند در یک کلاستر و واگذاری آن به یک منبع، تاخیر ارتباطی کاهش می­یابد. به طورکلی الگوریتم­های کلاسترینگ دارای دو مرحله می­باشند: فاز کلاسترینگ که گراف اصلی کارها را بخش بخش می­کند و فاز بعد از کلاسترینگ که کلاسترهای تعریف شده در مرحله قبل را اصلاح نموده و نگاشت نهایی کاربه منبع را ایجاد می­نماید.

 فهرست

 عنوان                                              صفحه 

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

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