HPF-G: یک محیط برنامه نویسی سطح بالا در محیط گرید

چکیده :

پدیده نوظهور گرید، به معنای به اشتراک گذاشتن منابع محاسباتی ناهمگون و داده ها بین سازمانهای مستقل که از نظر جغرافیایی پراکنده اند، امروزه بعنوان یک فناوری حیاتی برای اجرای برنامه های با کارایی بالا مطرح شده است. برنامه های کاربردی گرید معمولا نیاز به حجم عظیمی از داده های توزیع شده و یا منابع محاسباتی برای اجرای خود دارند که معمولا در یک سازمان واحد وجود ندارد. با این وجود رسیدن به کارایی بالا در این محیط، به دلیل وجود منابع ناهمگون و ماهیت پویای گرید، بسیار مشکل است و نیاز به توان بالای برنامه نویسی دارد. از آنجا که بسیاری از کاربران گرید، مهندسین و دانشمندان علوم مختلف هستند، نیاز به زبانهای سطح بالایی داریم که ناهمگونی و پویایی محیط گرید را از دید برنامه نویس پنهان کرده و به وی امکان ایجاد برنامه های با کارایی بالا، بدون درگیری با جزئیات سطح پایین گرید را بدهند. در این مقاله یک مدل برنامه نویسی موازی برروی گرید بنام HPF-G ، مبنای زبان متداول HPF که در سیستمهای موازی و توزیع شده کاربرد بسیار زیادی دارد، پیشنهاد شده است. مدل پیشنهادی با به تعویق انداختن زمان تقسیم داده ها تا زمان اجرا، به برنامه این امکان را می دهد تا با بدست آوردن اطلاعات لازم از وضعیت زمان اجرای گرید، داده ها را به نحو مناسبی تقسیم کرده و به کارایی بالاتری دست یابد. کلیه این عملیات توسط خود سیستم انجام شده و نیازی به دخالت برنامه نویس نیست.

پروژه آماده: پیاده سازی الگوریتم FLB ( فیال ورد :90 صفحه) (Fast Load Balancing for Distributed-Memory Machines)

پیاده سازی الگوریتم FLB ( فایل ورد :90 صفحه)

(Fast Load Balancing for Distributed-Memory Machines)

چکیده:

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

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

در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای مستقل و وابسته می پردازیم و روشهای زمانبندی گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیم.سپس الگوریتم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-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

پایان نامه محاسبات گریدی

پایان نامه محاسبات گریدی

تعداد صفحات:116

فرمت فایل:doc

فهرست مطالب

عنوان

صفحه

مقدمه

....................................................

12

فصل اول

مبانی گرید

....................................................

14

Grid computing 1-1 چیست ؟

....................................................

15

2-1 انواع Grid  

....................................................

17

 3-1 اهمیت Grid Computing

....................................................

18

4-1 ابزار قدرتمند Globus  

....................................................

20

5-1 نگاهی به‌اجزای Grid 

....................................................

21

Grid 6-1  از دید برنامه نویسان

....................................................

27

7-1 پیچیدگی‌ها

....................................................

30

8-1 مقدمه‌ای بر محاسبات توری 

31

9-1 مسأله گرید

....................................................

33

10-1 گرید و مفاهیم دیگر از محاسبات توزیعی

....................................................

34

11-1 فواید محاسبات توری

....................................................

37

1-11-1بهره برداری از منابع مورد استفاده

....................................................

37

2-11-1 ظرفیت پردازنده موازی 

....................................................

39

3-11-1 منابع مجازی و سازمانهای مجازی 

....................................................

40

4-11-1دستیابی به منابع اضافی

....................................................

42

5-11-1 توازن منابع

....................................................

44

6-11-1 قابلیت اطمینان

....................................................

45

7-11-1مدیریت

....................................................

47

12-1 استانداردها برای محیط‌های گرید

....................................................

48

1-12-1 استاندارد OGSI

....................................................

49

2-12-1 استاندارد گرید FTP

50

3-12-1 استاندارد WSRF

....................................................

51

4-12-1 استانداردهای مرتبط با سرویس‌های وب

....................................................

51

فصل دوم

امنیت و طراحی گرید

....................................................

52

-21 معرفی امنیت گرید (گرید Security)

....................................................

53

1-1-2  نیازهای امنیتی گرید

....................................................

53

2-1-2  چالش‌های امنیتی موجود در گرید

....................................................

54

3-1-2  دامنه‌های امنیتی گرید

54

4-1-2  اصول امنیت

....................................................

56

5-1-2  اصطلاحات مهم امنیت گرید

....................................................

58

6-1-2 مجوز اعتبارسنجی 

....................................................

61

2-2 طراحی گرید

....................................................

68

1-2-2 اهداف راه حل

....................................................

69

2-2-2 توپولوژی گرید

....................................................

73

1-2-2-2 Intra گرید

....................................................

74

2-2-2-2 Extra گرید

....................................................

76

3-2-2-2  Inter گرید

....................................................

77

3-2بررسی برخی از پروژه‌های گرید

....................................................

78

SETI @ Home 1-3-2

....................................................

78

NAREGL2-3-2

....................................................

78

3-3-2  Floding@Home

....................................................

79

Google 4-3-2

....................................................

80

BLAST 5-3-2   

....................................................

81

4-2  مقایسه ونتیجه گیری 

....................................................

82

فصل سوم

زمانبندی در گریدهای محاسباتی

....................................................

83

1-3  زمانبندی در گریدهای محاسباتی

....................................................

84

2-3  توابع  هدف

....................................................

93

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

....................................................

96

منابع 

....................................................

101