انجام پایان نامه

درخواست همکاری انجام پایان نامه  بانک مقالات رایگان انجام پایان نامه

سفارش پایان نامه

|

انجام پایان نامه ارشد

نوشته شده توسط moshaveranetehran.net   
دسته: انجام پایان نامه | مقالات
نمایش از دوشنبه, 03 خرداد 1395 07:38
بازدید: 83

با تشکر و قدر دانی از جناب آقای مهندس محبی که

اینجانب را در این پروژه راهنمایی و یاری نمودند.

تقدیم به پدر و مادر عزیزم که سرمایه های با ارزش زندگیم هستند

و همیشه مرا راهنمایی نموده اند.

چکیده

پیاده سازی الگوریتم 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-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

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


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

Mainfram  معایب

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

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

يک برنامه توزيع شده،   برنامه ای است که پتانسيل های پردازشی آن ممکن است توسط چندين کامپيوتر فيزيکی تامين  و داده های آن در چندين محل فيزيکی،  مستقر شده باشد .

یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند.

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

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

 

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

یکی از مزایای مهم سیستمهای توزیع شده سرعت بالای اجرای برنامه‌هاست چرا که یک برنامه همزمان می‌تواند از چندین کامپیوتر برای اجراء شدنش استفاده کند.[22]

  همچنین به علت توزیع شدن اطلاعات, بانکهای اطلاعاتی حجیم می‌توانند روی یکسری کامپیوترهای شبکه شده قرار بگیرند. و لازم نیست که همه اطلاعات به یک کامپیوتر مرکزی فرستاده شود(که در نتیجه این نقل و انتقالات حجیم زمان زیادی به هدر می‌رود.(

به علت تأخیر‌های انتقال در شبکه و نویزهای احتمالی در خطوط انتقالی قابلیت اعتماد اجرای یک برنامه دریک سیستم تنها,بیشتر از قابلیت اجرای آن دریک سیستم توزیع شده است .

همچنین درسیستم توزیع شده اگر یکی از کامپیوترهایی که وظیفه اصلی برنامه جاری را برعهده دارد خراب شود کل عمل سیستم مختل خواهد شد . از طرف دیگر اگر اطلاعاتی همزمان در چند کامپیوتر به صورت یکسان ذخیره گردد ویکی از کامپیوترها خراب شود, داده هارا می‌توان از کامپیوترهای دیگر بازیابی کرد از این نظر امنیت افزایش می‌یابد.

اشتراک  به منابع محاسباتی محدود نمی­شود. انواع منابع اعم از انباره­ها،نرم­افزار و بانک­های اطلاعاتی را در بر می­گیرد. در عین حال، امنیت و سیاست محلی نیز تضمین می­شود.[21]

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

 

 

 

 

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

 

  • گرید محاسباتی: شامل گره­هایی است که محاسبات کارها را انجام می­دهد. معمولا از گرید محاسباتی برای اجرای موازی برنامه­ها به منظور دست یافتن به کارایی بهتر استفاده می­شود.
  • · گرید داده: شامل گره­هایی است که امکان ذخیره و بازیابی حجم بالایی از داده­ها  را فراهم می­کند. در چنین سیستمی، هم داده­ها و هم کاربران توزیع شده اند. این سیستم با مشکلاتی  از قبیل حجم بالای داده که ممکن است افراز شده باشد، تکرار در چندین سایت و ناسازگاری داده­ها روبروست.
  • · گرید خدماتی: شامل گره­هایی است که تقاضاها را به کمک سرویسهای از قبل موجود، پاسخ می­دهند. زمانی که تقاضایی به چنین گره­ای ارسال می­شود، ابتدا تقاضا معنا می­شود تا مشخص شود که تقاضا کننده،  خواستار انجام چه سرویسی است  و نهایتا نتیجه به متقاضی برگشت داده می­شود.

هرچند مرز مشخصی بین این سه دسته وجود ندارد، اما بحث ما معطوف به گریدهای محاسباتی است.

  انگيزه گريد محاسباتي، مجتمع كردن منابع توزيع شده ناهمگون جهت حل مسائل پيچيده علمي، صنعتي و تجاري است . جهت رسيدن به اين هدف يك سيستم زمانبندي كارآمد به عنوان يك بخش حياتي براي گريد لازم است . متاسفانه پويايي و ناهمگوني منابع گريد باعث پيچيدگي زمانبندي وظايف مي شوند. بعلاوه با معرفي مدل اقتصادي گريد، علاوه بر زمان اتمام كار،

هزينه اجراي كار نيز به نگراني هاي كاربران اضافه شد .

 

13 ارزیابی گرید

   سه مرحله برای ارزیابی گرید وجود دارد اول:تولید سیستم هایی که در اوایل 1990 متولد شد. دوم:تولید سیستم با تمرکز روی ابزار برای حمایت از معیار های بزرگ داده و محاسبه جریان الکتریکی . سوم: تولید سیستم هایی که برای همکاری جهانی بر تغییرات تاکیید دارد .

اولین تولید فوریتی فرا محاسبه یا محیط های گرید نام گذاری شده است. عموما واقعیت این پروژه بهبود بخشیدن به منابع محاسباتی در یک دامنه کاربردوسیع بود. پروژه ارائه شده پیشگام این تکنولوژی [3]فافنر بود.

نسل دوم  گرید در  نتیجه یک فوریت از یک زیر ساخت که قادر به بهم پیوند دادن بیشتر مرکزهای سوپر محاسباتی مشخص شده است. اکنون  با ارتقا تکنولوژیهای شبکه وسازگاری آن با استانداردهای گرید می تواند به عنوان یک زیر ساخت توزیع کننده ممکن و قابل قبول در مقیاس های بزرگ که محاسبات را می خواهند حمایت کنند. در این نوع گرید به طور معمول طبیعت نا همگون منبع ها و بهبود بخشیدن کاربرد ها با محیط همگون ویکنواخت را با مجموعه ای از واسط های استاندارد پنهان می کند.گلو باس  [20]یکی از پروژه های توزیع شده است که برای اینکه گرید را استوار کند.

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

 

    4-1 کاربردهای گرید

 

    اخیرا تلاش زیادی برای انتقال دادن برنامه های کاربردی به گرید صورت گرفته است.یک مثال پروژه EGEE است. هدف های آن بهبود بخشیدن کار محققان در دانشگاه و صنعت  با دسترسی به منبع های محاسباتی اصلی و مستقل از محل جغرافیایی آنها است.تمرکز روی تعداد زیادی از کاربران گرید است.دو کاربرد برای پیدا کردن تایید اجرا  و کارایی زیر ساختها انتخاب شده است یکی محاسبه برخوردها با پشتیبانی از انرژی فیزیکی بالا در آزمایشات فیزیک ودیگری گرید های پزشکی که چندین گروه به طور یکسان با مشکلات سیل عظیم اطلاعات و داده های مراقبت از سلامت روبه رو هستند.[14]  

نمونه : تلسکوپ جادوگر(majic)

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

آن بزرگترین تلسکوپ اشعه گاما در جهان است و چندین تلسکوپ دیگر در کشورهای اروپایی به آن در جمع آوری اطلاعات کمک می کنند.توزیع جغرافیایی منابع مدیریت آنها را مشکل می کند و این یک نمونه برای گرید محاسباتی است که می تواند کمک بزرگی بکند زیرا محققان می تواند به طور یکسان به تمام منابع دسترسی داشته باشند. تلسکوپ در شبهای اول ماه کار می کند و حدود 600 گیگا بایت اطلاعات در شب ثبت می کند داده های اضافی  تلسکوپ و اطلاعات هوا شناسی نیز ذخیره می شوند.تمام این داده ها باید دریافت و آنالیز شوند.[11]    

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

قدرت گرید بخصوص در پردازش های فشرده مثل تحقیقات علمی و نمونه های مالی و طراحی های صنعتی و نمودار پرداخت تصویر مفید تر است.

 

 

 

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

 

    زمان­بند،  مدیر منبعی میانی است  و واسطی است بین مصرف کننده­ها و منابع.

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

 

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

     طیف وسیع کاربران گرید دارای برنامه­هایی با نیازمندی­های متفاوت هستند. ممکن است برنامه­های آنان دسته­ای و یا به خط[2] باشد،  شامل کارهای  وابسته به هم و یا مستقل  باشد.  به همین دلیل، ارائه الگوریتم زمان­بندی همه منظوره که بتواند برای تمامی سناریوها مناسب باشد، امکان­پذیر نیست. از این رو ما بحث خود را به زمان­بندی کارهای وابسته، معطوف نموده ایم. هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، برنامه، به شکل گراف جهتدار بدون سیکل (DAG[3]) مدل می­شود که در آن گره­ها نشان دهنده کارها و لبه­ها نشان دهنده ترتیب گره­هاست. گاهی اوقات وزنی نیز به گره­ها و لبه­ها اضافه می­شود که به ترتیب نشان دهنده هزینه­های محاسباتی و هزینه­های ارتباطی است.  ایجاد تعادل بین به حداکثر رساندن موازی سازی و به حداقل رساندن تاخیر ارتباطی به عنوان مسئله مهمی در زمان­بندی کارها مطرح است. برای زمان­بندی گراف برنامه، الگوریتم­های ابتکاری[4] متعددی مطرح شده است. برای زمان­بندی گراف برنامه، الگوریتم­های ابتکاری[5] متعددی مطرح شده است. این الگوریتم­ها را می­توان به سه دسته کلی تقسیم کرد. الگوریتم­های بر پایه  لیست[6]، الگوریتم­های بر پایه تکرار[7] و الگوریتمهای  کلاسترینگ[8]. ­

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

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

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

1- 7 مفهوم اصطلاحات بکاربرده شده در این پایان نامه

ü application: مجموعه­ای از کارهای  وابسته و یا مستقل  است که به حل مسئله معینی منتهی می­شود. در این تحقیق  از واژه فارسی "برنامه" به جای واژه " application " استفاده شده  است. در این تحقیق واژه job نیز معادل واژه application تلقی شده است.

ü   task : واحد کار application گرید به شمار می­آید که می­توان آن را برای اجرا فقط به یک منبع محاسباتی فرستاد . در این تحقیق  از واژه فارسی "کار" به جای واژه " task " استفاده شده  است.

 

ü   scheduling: به فرایند کشف منبع، انتخاب منبع و ارسال کار به منبع گفته می­شود . در این تحقیق "زمان­بندی" ترجمه شده است.

 

DAG: برنامه حاوی چندین کار موازی، به شکل گراف جهتدار بدون سیکل "DAG" مدل می­شود. از این  واژه با عنوان گراف برنامه و یا به اختصار گراف  یاد شده است.

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

در فصل اول (فصل جاری)، مفاهیم و تعاریف پایه بیان شده است. مفهوم گرید و مسئله زمان­بندی تبیین شده، روش­های موجود زمان­بندی گراف برنامه به طوراجمال بیان شده است.

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

در فصل سوم، موضوع  زمان­بندی گراف برنامه در سیستم­های توزیع شده، مورد بحث و بررسی قرار گرفته، پارامترها و عناصر تاثیرگذار بر الگوریتم­ها بیان شده است.

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

 

 

 

 

 

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

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

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

نهادی مرکزی کنترل همه گره­های محاسباتی را بر عهده دارد.  نمونه ای از پیاده سازی کلاستر می­تواند بدین صورت باشد: گره­هایی که سیستم عامل لینوکس دارند و نرم افزار Beowulf که امکان موازی­سازی را فراهم می­کند . شکل زیر ساختار کلاستر را نشان می دهد.

 

 

 

 

 

 

 

 

 

 

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

کلاسترها به صورت رئیس/مرئوس[9] سازماندهی می­شوند.[6] گره رئیس، مسئولیت قبول کارها،
زمان­بندی آنها، ارسال آنها  به گره مرئوس را برای اجرا بر عهده دارد. گره مرئوس، کامپیوتر مستقلی است که پردازنده، حافظه و سیستم عامل خودش را دارد و مسئول اجرای کار و برگشت دادن نتیجه به کاربران است.  گره­های مرئوس معمولا با شبکه ای با سرعت بالا، تاخیرکم و عرض باند زیاد  که امکان ارتباط بین پردازنده ای را فراهم می­کند، به هم متصل هستند. ارتباط بین پردازنده ای  با مکانیسم ارسال پیام[10] مانند PVM یا MPI  انجام می­شود.

کلاستر، هم برای اجرای کارهای ترتیبی و هم کارهای موازی، وسیله مناسبی است. برنامه نویس بر اساس مکانیسمهای ارسال پیام،  نحوه توازی برنامه­ها را مشخص می­کند. اجرای موازی نیازمند کتابخانه زمان اجرایی[11] است که از PVM و MPI حمایت کند. سیستم زمان­بند کلاستر ساختار رئیس/مرئوس دارد. گره رئیس، کارها را از سرویس گیرنده­ها[12] دریافت نموده و در صف قرار می­دهد. گره رئیس اطلاعات مربوط به کارهای پذیرفته شده را در اختیار دارد. گره رئیس کارهای منتظر در صف را برای اجرا به گره­های مرئوس می­فرستد. یعنی نقش زمان­بند را نیز بازی می­کند. همه گره­های کلاستر همسان هستند،  یعنی پردازنده، اندازه حافظه و عرض باند شبکه یکسانی دارند. تعداد گره­های مرئوس نیز معمولا ثابت است. همه گره­ها نیز به محاسبه کلاستر اختصاص دارند. شبکه ارتباطی، خصوصی و سرعت بالاست یعنی امکان ارتباط بین هر زوج از گره­ها در اغلب مواقع تضمین شده است.  گره رئیس که نقش زمان­بند را نیز بازی می­کند، با مجموعه ثابتی از گره­های مرئوس در ارتباط است.

 زمان­بند در هنگام تصمیم گیری فقط به در دسترس بودن گره­ها توجه دارد. گره مرئوسی که اجرای کاری را به پایان می­رساند، در دسترس بودن خود را به زمان­بند گزارش می­دهد.  یعنی در هر زمان، زمان­بند اطلاعات وضعیت همه گره­ها را در اختیار دارد. روش کار بدین صورت است که هر برنامه،  درخواست­های منبع خود را در یک فایل اسکریپت ثبت می­نماید و زمان­بند این فایل را تفسیر می­کند. ممکن است برنامه ای  شامل چندین کار کوچکتر شود که انتظار می رود هرکدام در گره مرئوس  مجزایی اجرا شوند. برنامه هنگام تقاضای منبع، تعداد گره­های درخواستی و زمان اجرای انتظاری را مشخص می­کند.  ممکن است زمان­بند ابتدا صف کارها را مرتب نماید.متداول­ترین الگوریتم­های مرتب سازی در کلاسترها عبارت است از: ابتدا اولین کار[13] ،  ابتدا کار با کوچکترین تقاضا[14]، ابتدا کوتاهترین کار[15] و backfill .

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

خصوصیات  زمان­بند کلاستر از خصوصیات محیطهای محاسباتی  کلاستر ناشی می­شود. این خصوصیات عبارتند از:

  • ·     همسانی منابع و برنامه­ها

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

 

  • ·     منابع تخصیص داده شده[17]

اغلب کلاسترها در یک دامنه مدیریتی قرار دارند و گره­های محاسباتی و شبکه ارتباطی هردو به محاسبات کلاستر اختصاص دارند. به همین دلیل رفتار گره­های محاسباتی و ظرفیت ارتباط قابل پیش بینی است.

  • ·     ساختار زمان­بندی مرکزی

در کلاستر، نهادی مرکزی وظیفه زمان­بندی را بر عهده دارد. زمان­بند بر روی همه گره­های محاسباتی و اطلاعات کارها،  کنترل کامل دارد. 

  • ·     شبکه ارتباط داخلی سریع

محل گره­های محاسباتی اهمیتی ندارد، چون شبکه ارتباط داخلی خصوصی و سریع بوده و عرض باند کافی را فراهم می­کند.

 

  • ·     هدف کارایی یکنواخت

کل کلاستر یک هدف کارایی را دنبال می­کند و زمان­بند برای رسیدن به این هدف تلاش
می­کند. به همین دلیل طراحی زمان­بند برای چنین سیستمی،  ساده است.

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

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

  • ·     ناهمگونی منابع:

گرید محاسباتی از دو نوع منبع تشکیل شده است: منابع محاسباتی و ارتباطی(شبکه). در هردوی آنها ناهمگونی به چشم می­خورد. شبکه­ها در عرض باند و پروتکل­های ارتباطی متفاوتند. منابع محاسباتی دارای سخت افزار متفاوت(مجموعه دستورات، معماری، تعداد  پردازنده­ها، اندازه حافظه فیزیکی، سرعت پردازنده)  و نرم افزار متفاوت (سیستم عامل، سیستم فایل، نرم افزار مدیریت کلاستر) می­باشند. این ناهمگونی­ها یعنی تفاوت در پردازش کارها.  سیستم زمان­بند باید از این توان­های محاسباتی متفاوت به شکل بهینه استفاده نماید.

  • خودمختاربودن دامنه ها:

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

  • ·     منابع تخصیص نیافته:

     به دلیل وجود منابع تخصیص نیافته، رقابت زیادی  بر سر استفاده از منابع وجود دارد. یعنی ممکن است که  منبعی به طور همزمان به چند گرید متصل باشد و کاربران محلی و سایر گریدها بطور همزمان در آن منبع شریک باشند. یکی از نتایج رقابت این است که رفتار و  کارایی  در خلال زمان تغییر  می­کند. به عنوان مثال در شبکه­های گسترده که از مجموعه پروتکل اینترنت[19]  استفاده می­کنند، خصوصیات شبکه مانند تاخیر و عرض باند در خلال زمان تغییر می­کند. در چنین محیطی، طراحی مدل کارایی دقیق کار بسیار مشکلی است. با سنجش کسری از منابع در دسترس به شکل پویا می­توان رقابت را تشخیص داد. سیستم مدیریت منبع با ضمانت کیفیت سرویس و رزرو منبع، پیش بینی کارایی منبع را ساده­تر می­کند.[9]

  • ·     تنوع برنامه ها:

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

  • ·     رفتار پویا:

       در محیطهای محاسباتی موازی سنتی مانند کلاستر، استخر منبعی با منابع ثابت  وجود دارد. اما در گرید هم در شبکه و هم در منابع محاسباتی پویایی وجود دارد. اولا شبکه­ای که کاربران زیادی به آن متصل اند، نمی­تواند عرض باند تضمین شده را فراهم کند در ثانی در دسترس بودن منابع و توانایی آنها نیز حالتی پویا دارد یعنی ممکن است منابع جدیدی به شبکه افزوده شود و یا به دلیل مشکلات شبکه منابعی از دسترس خارج شوند. به دلیل وجود رقابت بین اعضای شریک در یک منبع، توانایی منابع در حین زمان نیز تغییر می­کند. زمان­بند باید بتواند با چنین رفتار پویایی سازگار شده،  بعد از اتصال منبع جدیدی به طور خودکار آن را تشخیص داده و در تصمیم گیری­های آتی آن را به شمار آورد و هنگامی که به دلایل نامعلومی، منبعی از دسترس خارج می­شود با اعمال مکانیزم­هایی مانند نقطه وارسی[20] و یا زمان­بندی مجدد[21] قابلیت اطمینان سیستم گرید را تضمین کند.شکل زیر ساختار زمانبند گرید را نشان می دهد.

 

                شکل 2-2 ساختار زمانبند گرید [28]

 

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

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

    زمان­بندی محلی، نحوه تخصیص و اجرای کارها در یک پردازنده را  تعیین می­کند  ولی سیاست زمان­بندی سراسری از اطلاعات سیستم بهره می­برد تا کارها را بین چندین پردازنده به گونه­ای تقسیم کند که کارایی سیستم بهینه شود. مشخص است که زمان­بندی گرید در دسته زمان­بندی سراسری  قرار دارد.[8]

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

در زمان­بندی ایستا فرض می­شود که اطلاعات مربوط به همه منابع گرید، همچنین اطلاعات مربوط به کارهای یک برنامه کاربردی در هنگام زمان­بندی در دسترس است. در زمان­بندی پویا، ایده اصلی این است که تخصیص کارها، در حین اجرای برنامه کاربردی انجام شود.این شیوه هنگامی مفید است که تعیین زمان اجرا غیر ممکن باشد، سمت انشعاب و تعداد تکرارهای حلقه نامشخص باشد و کارها زمان حقیقی[22] باشند. زمان­بندی گرید می­تواند به هر دو شکل ایستا و پویا انجام گیرد.

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

 

 

 

 

 

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

 

 

                                                                      

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

 

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

اگر به منبعی تعداد زیادی کار واگذار شود، سیاست متوازن­سازی مشخص می­کند  که آیا لازم است که تعدادی از کارها به منابع دیگر فرستاده شود یا نه و در صورت لزوم ، کدام کارها باید منتقل شوند. توازن بار پویا به چهار روش مختلف انجام می­شود. روش FIFO­ی غیر مقید[23]،  روش مقید به توازن، روش مقید به هزینه  و  روش ترکیبی[24]  که در ذیل به توضیح آنها خواهیم پرداخت.

 

- روش FIFOی غیر مقید

    در این روش ، کار وارده، به منبعی که در حال حاضر کوتاهترین طول صف و یا کمترین زمان انتظار در صف را دارد، واگذار می­شود.  به این روش، توازن بار مصلحت­بین[25] نیز گفته می­شود. 

 

- روش مقید به توازن

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

این شیوه مزایای زیادی دارد. بارهای اولیه سریعا بین منابع توزیع شده و اجرای آنها آغاز می­شود، پروسه متوازن­سازی مجدد، توزیع شده و قابل توسعه[26] است. تاخیر ارتباطی آن کم است  چون انتقال کارها فقط بین منابع نزدیک به هم انجام می­گیرد. چن و همکارانش با بهره­گیری از این روش، الگوریتم زمان­بندی برای گرید ارائه داده اند.

 

- روش مقید به هزینه

  این روش بهبود یافته روش مقید به توازن است. یعنی هنگام متوازن­سازی مجدد به هزینه ارتباط کارها نیز توجه دارد. یعنی به جای تعویض کارها به شکل دوره­ای،کارها را قبل از انتقال بررسی می­کند. اگر هزینه ارتباطی مربوط به انتقال کار از کاهش زمان اجرای آن بزرگتر باشد، کار منتقل نخواهد شد. این روش  هنگامی که هزینه ارتباط بین منابع نا­همگون باشد و هزینه ارتباط در اجرای برنامه کاربردی، دغدغه اصلی باشد، از روش قبلی کارآمدتر است. کوروسکی و همکارانش سیاست زمان­بندی خود را بر این اساس پایه نهادند[25].

- روش ترکیبی

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

در بعضی از الگوریتم­های زمان­بندی پویا مانند  ، منابع رزرو می­شوند. به ویژه در گرید برای رسیدن به درجه­ای از قطعیت کارایی منابع، این تکنیک عمومیت دارد.

 2-3-3-بهینه / نزدیک به بهینه

در حالتی که همه اطلاعات مربوط به منابع و کارها شناخته شده باشند، تخصیص بهینه بر اساس معیارهایی مانند "به حداقل رساندن زمان گسترش[27]" یا "حداکثر نمودن  بهره­وری منابع[28] " صورت می­گیرد. اما به علت طبیعت NP-complete الگوریتم­های زمان­بندی، داشتن فرضیات معقول مشکل بوده و معمولا اثبات بهینگی چنین الگوریتم­هایی سخت است. به همین دلیل تحقیقات فعلی به دنبال راه حل­های نزدیک به بهینه است. الگوریتم­های نزدیک به بهینه به دو دسته تقریبی و ابتکاری تقسیم می­شوند. الگوریتم­های تقریبی مدل­های محاسباتی رسمی[29] را بکار می­برند اما کل فضای جواب را جستجو نمی­کنند بلکه هنگامی که راه حلی به اندازه­ی کافی خوب پیدا شود، جستجو متوقف می­شود.  زمانی که متریک مناسبی برای ارزیابی جواب وجود داشته باشد، این روش زمان صرف شده برای یافتن زمان­بندی [30] را کاهش می­دهد.

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

  • در دسترس بودن تابعی برای ارزیابی جواب
  • زمان مورد نیاز برای ارزیابی جواب
  • توانایی  قضاوت در مورد مقدار جواب بهینه بر اساس بعضی متریکها
  • در دسترس بودن مکانیسمی برای محدود کردن فضای جواب

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

2-3-4- توزیع شده/ مرکزی

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

2-3-5- همکار/مستقل

نکته قابل توجه دیگر در الگوریتم­های زمان­بندی توزیع شده این است که آیا گره­های درگیر زمان­بندی به شکل همکار، کار می­کنند یا به شکل مستقل؟ درحالت مستقل، هر زمان­بند[6]  به صورت خودمختار و بر اساس اهداف بهینه خود و بدون توجه به تاثیر تصمیمش بر روی بقیه سیستم، تصمیم­گیری می­کند. مثال این نوع زمان­بندها، زمان­بند سطح برنامه کاربردی  است. در حالت همکار، هر زمان­بند کارهای بخش مربوط به خود را زمان­بندی می­کند  اما همه زمان­بندها به سمت یک هدف مشترک سیستمی پیش می­روند و هدف مشترک، بالا بردن کارایی کل سیستم است نه کارایی محلی و نه کارایی برنامه  خاصی.

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

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

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

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

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

مصرف­کنندگان منابع (کاربران گرید) و فراهم­کنندگان منابع، اهداف متفاوتی را دنبال می­کنند. کاربران به دنبال کارایی بیشتر برنامه کاربردی خود هستند و هزینه کمتر در حالی که فراهم­کنندگان منبع به دنبال بهره­وری بیشتر از منابع خود هستند و منفعت بیشتر.

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

الگوریتم­های زمان­بندی با هدف منبع گرا، تلاش دارند که کارایی منابع را بهبود بخشند یعنی  توان عملیاتی[32](تعداد برنامه­های پردازش شده یک منبع در یک پریود خاص) را بالا برند و بهره­وری(درصد مشغول بودن یک منبع) را بهبود بخشند. بهره­وری پایین به معنای بیکار بودن منبع و تلف شدن توان  آن است. در یک منبع دارای  چند پردازنده، بهره­وری پردازنده ها، متفاوت است و برای بهبود توان عملیاتی بایستی بار پردازنده­ها را متوازن ساخت. کندر سیستمی است که  هدف  زمان­بندی آن افزایش توان عملیاتی است.

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

 

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

در زمان­بندی وفقی، الگوریتم­ها و پارامترهای تصمیم­گیری به طور پویا بر اساس وضعیت قبلی، فعلی و آتی منبع تغییر می­کنند. در گرید محاسباتی، مسئله وفق­پذیری از  سه دیدگاه مطرح است: وفق­پذیری با ناهمگونی منابع،  وفق­پذیری با پویایی کارایی منابع و وفق­پذیری با تنوع برنامه­های کاربردی.

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

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

برنامه های کاربردی

 

 گراف کار      کارهای وابسته

 

 گراف جهتدار بدون سیکل   بدون گراف جهتدار بدون سیکل

          

               گراف کار تکرار شونده     گراف فعال کار

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

 

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

کارها به تعداد زیادی کار وابسته دو طرفه  تقسیم می شوند این به این معنی است که آنها در هر سفارش می توانند انجام شوند.کارهایی مانند رییس و مرئوس   [6]از این نوعند.در ذیل نمونه ای از این الگوریتم ها آورده شده است.

 

 

 

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

به دو قسمت گراف جهتدار بدون  سیکل وغیر گراف جهتدار بدون سیکل تقسیم می شود.

گراف جهتدار بدون سیکل             

کارها در این مجموعه می توانند بوسیله گراف جهت دار بدون سیکل مختصر می شود.در رئوس کارها قرار می گیرند و لبه ها داده هایی که بین کارها جابه جا می شوند را نشان می دهد.هدف در زمانبندی الگوریتم هایی که کارها را به پردازنده ها واگذار می کنند این است که نتیجه زمانبندی را مینیمم می کنند.الگوریتم های زمانبندی گراف جهتدار بدون سیکل بررسی مشترک را در الگوریتم هایی مثل اختیار گراف کار امکان پذیر می کند.  [8]

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

 

بدون گراف جهتدار بدون سیکل  

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

 

 

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

   وابستگی کارها به معنای وجود ترتیب تقدمی بین آنهاست. یعنی تا اتمام اجرای همه­ والدین کار، نمی­توان اجرای آن را آغاز کرد. وابستگی و یا استقلال کارها تاثیری اساسی بر الگوریتم­های زمان­بندی دارد.

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

هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، از مدل ویژه­ای به نام
 گراف­برنامه استفاده می­شود. از زمانی که فراساختار گرید رشد کرده و قدرتمند شده است، گراف­برنامه­ها نیز پیچیده و پیچیده تر شده است. بحث زمان­بندی گراف برنامه به طور مشروح در فصل سوم مطرح شده است.

2-4-6- زمان­بندی تحت قيود كيفيت سرويس

    در محيط­هاي توزيع شده ، ناهمگون با منابع تخصيص نيافته، كيفيت سرويس دغدغه اصلی بسياری از برنامه­های كاربردی است. تلقی کاربران مختلف از كيفيت سرويس متفاوت است مانند نيازمندی به سرعت خاصی از پردازنده، اندازه حافظه، عرض باند شبكه،  نسخه نرم­افزار و يا مهلت.  كيفيت سرويس هدف نهايی يك بر نامه كاربردی نيست اما مجموعه­ای از شرايط است كه برای اجرای موفقيت­آميز يك برنامه كاربردی لازم است.  دو روش برای مقابله با ناهمگونی و تغييرپذيری مطرح است. 1- روش تضمين­كننده سرويس: این روش بر گفتگو[33] و گفتگوی مجدد بر سر قرارداد كيفيت سرويس استوار است. اين فراساختار مديريت كيفيت سرويس فرض می­كند، كه فراهم­کنندگان سرويس فرم گارانتی سرويس ارائه  می­دهند. 2- روش بهترين تلاش: در این روش، فرض می­شود كه امكان تضمين كيفيت ندارد اما فراهم­كننده سرويس حداكثر تلاش خود را برای ارائه سرويس بهتر انجام می­دهد. البته دغدغه تحقيقات جاری، اعمال كيفيت سرويس در سطح مديريت منابع است نه در سطح  زمان­بندی  کار.  يكبار كه كيفيت سرويس توسط منابع تضمين شود يا كاربر با كيفيت موجود خود را وفق دهد، باقی پروسه زمان­بندی در كانال متعارف خود می­افتد.  با آگاهی از اين محدوديت، هی تلاش كرد تا براي اولين بار كيفيت سرويس را درسطح   زمان­بندی کارهای گريد، بررسی كند.  اطلاعات مربوط به کیفیت سرویس را در الگوريتم   زمان­بندي Min-min جا سازی كرد تا تطبيق بهتري بين سطوح متفاوت تقاضا / پاسخ  کیفیت سرویس  به وجود آورد. کارها  فقط به منابعی كه مقيد به رعایت کیفیت سرویس  هستند،  وا گذار مي شود  و کارهای نیازمند کیفیت سرویس بهتر،  قبل از کارهای  با نياز پايين­تر نگاشت  مي شوند.  ترتيب کارهايی كه نيازمندی   يكسانی دارند را الگوريتم Min-min  مشخص  می­كند.  در اين زمينه فقط يك بعد كيفيت سرويس، يعنی عرض باند شبكه در نظر گرفته شده  و کارها مستقل فرض شده اند.  دامنه تحقيقات در اين زمينه هنوز باز است.

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

يكی از مشكلات اصلی زمان­بندی کارها در محيط گريد، طبيعت پويای منابع گريد است.  علت تغييرات پويای منابع برمی­گردد به خود مختاری سايت­ها و رقابت بر سر استفاده اشتراكی از منابع.

سيستم­های فعلی زمان­بندی  گريد برای  وفق دادن خود با اين تغييرات از سه تكنيك بهره
مي­گيرند.  زمان­بندی بر اساس اطلاعات به روز [34] حاصل از سرويس­های اطلاعاتی گريد (يعنی استفاده از الگوريتم­های پويا برای متوازن سازی بار)،  پيش­بينی كارايی،  زمان­بندی مجدد پويا در زمان اجرا.

 

الف- زمان­بندی بر اساس اطلاعات  سرويس اطلاعاتي گريد([35]GIS)

GIS بخشی  نرم افزاری،  منفرد و يا توزيع شده است که اطلاعات بسياری در خصوص مردم، نرم­افزار،  سرويس­ها و سخت­افزار را نگهداری می­کند.  اين بخش با گريد محاسباتی همكاری داشته و به هنگام نياز اين اطلاعات را در اختيار گرید  قرار می­دهد.  مهمترين وظيفه سرویس اطلاعاتی در زمان­بندی   گريد کشف و هدايت[36] منبع به شكل پويا ست.

كشف منبع ، منابع جديد قابل دسترسی و محل آنها را به زمان­بند اعلام می­كند و هدايت منبع اطلاعات مهم و به روز در خصوص منابع  و وضعيت محل مجموعه داده ها را در اختيار زمان­بند قرار می­دهد. سرويس­های اطلاعاتی، زمينه تحقيق جديدی است. از سرویس­های اطلاعاتی موجود، می­توان به  MDS , [37]NWS[38] اشاره کرد.

ب- زمان­بندی بر اساس  پيش بينی كارايی

   در سيستم­های پويا، پيش بينی امر مهمی برای تصميم­گيری است. مثل پیش­بینی وضع هوا، پيش­بينی وضعيت بازار بورس.  در بحث زمان­بندی، تقريبا تمامی الگوريتم­های ايستا بر پيش­بيني تخمين كارآيی تكيه دارند.  معمولا به دست آوردن اطلاعات ايستا،  مانند فركانس  پردازنده، اندازه حافظه، عرض باند شبكه،  فايل سيستم­ها، كار ساده­ای است.  اما بدست آوردن اطلاعات زمان اجرا مانند بار پردازنده،  حافظه دردسترس، عرض باند در دسترس شبكه، بسيار مشكل است.

هنگامی كه تصمیمی در خصوص  زمان­بندی  اتخاذ ميشود،  پيش­بينی دقيق پارامترهای منابع در حين اجرا، برای رسيدن به اهداف نهايی، بسيار مهم  است.  تاکفوسا و همکارانش الگوريتم زمان­بندی  مهلتی برای سيستمی  با ساختار رئيس/مرئوس در گريد [6]ارائه كردند. زمان پردازش سرويس پيش­بينی شده ، به كمك پارامتری كه نشان­دهنده اطمينان زمان­بند به دقت پيش­بينی است، محاسبه می­شود. اگر پيش­بينی كارایی  نادرست باشد، بهره­وری منبع افت می­نمايد و يا سرويس به دليل انقضای مهلت،  انجام نمی­شود. اسچوف و همکارانش از پارامتری به نام "شانس[39]"برای بيان رفتار متغير منابع استفاده كردند كه می­توان اين پارامتر را از طريق NWS بدست آورد و فرض كردند كه اين مقادير را بتوان با توزیع  نرمال نشان داد.  بر اساس اين فرض، استراتژی زمان­بندی  متوازن  در زمانی [40] براي برنامه­هاي كاربردی  داده موازی[41] تعريف نمودند.  ميزان داده­های توزيع شده روی هر منبع بر اساس ميزان انحراف استاندارد از زمان كامل­سازی پيش بينی شده محاسبه می­شود. 

ممکن است پيش­بيني بر اساس ركوردهاي تاريخي[42] صورت گیرد و یا بر اساس مدل­سازی بار کاری. در روش پیش­بینی بر اساس رکوردهای تاریخی، براساس داده­هاي ثبت شده در خصوص در دسترس بودن منابع قبلي، ركوردهاي كارايي برنامه  و در نظر گرفتن پارامترهای پويا، می­توان به كمك تكنيك­هایی  ساده و يا پيچيده،  پيش بينی­های لازم را انجام داد.  ینگ و همکارانش  شيوه­اي سه سطحي براي پيش­بيني ارائه كردند.  سطح اول، ساده­ترین سطح و یک گام رو به جلو است. در این سطح فقط به تغییرات بار پردازنده توجه شده وبالاترین مقدار[43] ثبت شده، حد آستانه تلقی می­شود. اگر کارایی در نقطه زمانی فعلی حالت افزایشی داشته باشد، پیش­بینی می­شود که در نقاط زمانی بعدی نیز افزایشی است، مگر آنکه حد آستانه بالایی فرا برسد و برعکس. با استفاده از پیش­بینی تک نقطه­ای و با ترکیب کارایی در چندین نقطه در بازه قبلی می­توان کارایی در بازه­ای از زمان را نیز محاسبه کرد(مثلا با به دست آوردن میانگین آنها) و از روش پیش­بینی یک گام به جلو[44] برای ترکیب مقادیر استفاده کرد. واریانس کارایی در هر بازه را نیز می­توان به شیوه­ای مشابه بدست آورد. یعنی با استفاده از داده­های تاریخی در مجموعه­ای از نقاط، انحراف از کارایی هر بازه را بدست آورد و از روش زمان­بندی یک گام به جلو، برای استاندارد نمودن انحراف از بازه­های قبلی سود جست. ماشین با واریانس بازه­ای پایین­تر قابل اعتمادتر بوده و زمان­بند، کارهای کمتری را به منابع با واریانس بالاتر ارجاع می­دهد.

در روش پيش­بيني بر اساس مدل نمودن بار کاری، ایده اصلی این روش این است که اگر بتوان ورود برنامه کاربردی را مدل کرد، می­توان کارایی را درست­تر پیش بینی نمود. به عنوان مثال، هی فرض کرد که بارکاری تابعی خطی از زمان باشد. گنگ  مدلی برای  کارایی زمان­بند برای کارهای موازی  بر روی منابع ناهمگون تخصیص نیافته، ارائه کرد که کارهای محلی صاحب منبع می­توانستند در هنگام نیاز منبع را از  کارهای راه دور پس بگیرند. او فرض کرد که نرخ ورود کارهای محلی از توزیع پوآسون پیروی می­کند و تابع احتمال زمان کامل شدن کارهای راه دور را  نیز بر اساس  همین فرض مطرح کرد. 

ج- زمان­بندی مجدد

هنگامی که سرویس پیش­بینی منبع در اختیار نباشد یا نتواند پیش­گویی دقیقی انجام دهد، تنها چاره " زمان­بندی مجدد" است. یعنی تصحیح زمان­بندی قبلی بر اساس وضعیت جدید منابع. مهاجرت کار پیش شرط زمان­بندی مجدد به حساب می­آید و خوشبختانه امروزه فراساختار گرید  از مهاجرت کار حمایت می­کند. در GrADS، ایده­ی قرارداد کارایی مطرح شد، این قرارداد، توافقی است بین کاربر و فراهم­کننده منبع. این ایده سبب می­شود که هنگام مهیا شدن منابعی با توانایی­های معین و پارامترهای معین، برنامه کاربردی به سطح تحمل معینی از کارایی برسد. هنگامی که نقض قراردادی رخ دهد، زمان­­بند مجدد فعال شود. زمان­بند مجدد با توجه به حسگرهای داده، تخمین باقی مانده کار و هزینه انتقال به منبع جدید، تعیین می­کند که آیا زمان­بندی مجدد، مقرون به صرفه هست یا نه. اگر مقرون به صرفه باشد،  زمان­بند،  زمان­بندی جدیدی را ایجاد کرده و با فعال­کننده[45] زمان­بند مجدد بر روی هر پردازنده تماس بر قرار می­کند.  فعال­کننده­ها از مکانیزم­های مختلفی برای زمان­بندی استفاده می­کنند. مثلا مکانیزم توقف و شروع مجدد[46](RSR) و مکانیزم تعویض پردازنده[47] (RPS )

 

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

2-5-1- الگوریتم  MET [48]:

این الگوریتم [4]، کار را به منبعی که  بهترین زمان اجرای پیش­بینی شده برای آن کار را دارد، واگذار  می­نماید و توجهی ندارد که آیا این منبع در حال حاضر دردسترس است یا نه. انگیزه این الگوریتم این است که هر کاری را به بهترین ماشین واگذار نماید. این الگوریتم ممکن است باعث نامتوازنی شدید بار شود و  برای محیطهای محاسباتی ناهمگون مناسب نیست چون ویژگی منابع و کارها را ثابت فرض می­کند.  یعنی ماشینی که می­تواند کاری را سریعتر اجرا کند، خواهد توانست سایر کارها را نیز سریعتر اجرا کند!

 

 

2-5-2- الگوریتم  MCT [49] :

این الگوریتم [4]، کار را به ترتیبی اختیاری به منبع که کوچکترین زمان کامل کردن آن کار را دارد، واگذار می­کند. این امر باعث می­شود که بعضی از کارها به ماشینی واگذار شوند که کوچکترین زمان اجرا را برای آنها ندارد. ایده این الگوریتم ترکیب مزایای توازن بار فرصت طلب  (OLB ) و MET است و پرهیز از شرایطی  که MET و OLB ضعیف عمل  می­کنند.

 

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

 این  الگوریتم [7]، با مجموعه U یعنی مجموعه همه کارهای نگاشت نشده، آغاز به کار می­کند.  سپس مجموعه می­نیمم زمان­های کامل شدن، یعنی

      (2- 1)                                                

ایجاد می­شود. پس از آن، کاری که کوچکترین زمان کامل شدن را دارد، از مجموعه M انتخاب شده و به منبع نظیر سپرده می­شود. نهایتا کار دیگری از مجموعه U انتخاب شده و مراحل فوق برای آن تکرار می­شود. این روند ادامه می­یابد تا همه اعضای مجموعه U نگاشت شوند. [22]این روش نیز همانند روش MCT بر اساس به حداقل رساندن زمان کامل شدن، عمل می­کند ولی در روش Min-min همه کارهای نگاشت نشده در حین تصمیم گیری برای نگاشت در نظر گرفته می­شوند در حالی که درMCT  در هر زمان فقط یک کار در نظر گرفته می­شود.

 

2-5-4- الگوریتم  Max-min:

این الگوریتم [6]، مشابه روش Min-Min است، با این تفاوت که پس از ساخت مجموعه M،  کاری که بزرگترین زمان کامل شدن را دارد، انتخاب می­شود. به طور شهودی Max-min سعی دارد که مشکلات مربوط به اجرای کارهای با زمان اجرای طولانی را حداقل نماید. به عنوان مثال فرض کنید که  برنامه­ای دارای تعداد زیادی کار با زمان اجرای کم و یک کار با زمان اجرای طولانی باشد. اگر ابتدا کار طولانی را به بهترین ماشین نگاشت نمود، این امکان فراهم می­شود که کار طولانی بتواند با کارهای کوتاه به طور همروند اجرا شود. در این حالت نگاشت Max-min از نگاشت Min-min بهتر عمل می­کند. [21]اما اگر ابتدا همه کارهای کوتاه اجرا شوند و بعد کار طولانی، ماشین­های زیادی در سایت بیکار خواهند ماند. در حالات مشابه این مثال، الگوریتم Max-min نگاشت بهتر و توازن بار بهتر و زمان گسترش بهتری  خواهد داشت.

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

 

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

 الگوریتم ابتکاری دیگر برای زمان­بندی کارهای مستقل، Suffrage   نام دارد. منطق پشت این الگوریتم این است که اگر کاری که به میزبان معینی واگذار می­شود، نتواند به آن سایت برود، می­رنجد[51]!  میزان رضایت[52] هر کار به این صورت تعیین می­شود:اختلاف بین بهترینMCT   و دومین بهترین MCT. کاربا میزان رضایت بالاتر، مقدم خواهد بود. الگوریتم های Suffrage زمانی که کار، داده ورودی و خروجی دارد و منابع کلاستر شده اند، با مشکل مواجه می­شوند. در این حالت منطقا باید کار به منبعی که تا حد امکان به منبع داده نزدیک است واگذار شود تا زمان گسترش کاهش یابد. اما اگر منابع کلاستر شده باشند و گره­ها در یک کلاستر کارایی مشابهی داشته باشند، در این صورت بهترینMCT   و دومین بهترین MCT بسیار به هم نزدیک خواهند شد و میزان رضایت به صفر میل خواهد نمود و کار، اولویت پایین تری خواهد داشت و ممکن است کارهای دیگری به این گره واگذار شود و کار موردنظر از منبع داده بیرون بیفتد. برای حل این مشکل کاسانوا الگوریتم Suffrage را بهبود بخشید و Xsuffrage نامید. بدین صورت که برای هر کار میزان رضایتی در سطح کلاستر مطرح نمود.

 

2-5-6- الگوریتم[53]GA :

این روش،[18] تکنیک جستجویی برای  فضاهای بزرگ است. الگوریتم GA دارای نسخه­های زیادی است. در این جا، به  بیان یکی از این نسخه­ها می­پردازیم.  

فرض کنید کل تعداد نگاشت­های ممکن یک کار، 200 حالت باشد. 200 کروموزوم در نظر گرفته  می­شود.  هر کروموزوم، برداری است t*1 که موقعیت i (t   0< i<)  نشان دهنده  کار  ti و عنصر موقعیت i منبعی است که کار به آن نگاشت می­شود. جمعیت اولیه کروموزوم­ها با دو روش ایجاد  می­شود:

الف) انتخاب200  کروموزوم تصادفی  ازتوزیع یکنواخت .

ب) انتخاب جواب تکنیک Min-Min  به عنوان اولین کروموزوم و 199 جواب تصادفی.

الگوریتم GA، دقیقا 8 بار اجرا می­شود. یعنی با جمعیت اولیه هرکدام از دو روش بالا، چهار بار اجرا  می­شود و بهترین این  هشت نگاشت، به عنوان جواب نهایی انتخاب می­شود. هر کروموزوم دارای مشخصه­ای است با نام "میزان سازگاری[54]" . میزان سازگاری  هر  کروموزوم، زمان گسترش محاسبه شده از تطابق کارها با منابع آن  کروموزوم می­باشد. میزان سازگاری کمتر، نشانه نگاشت بهتر است. بعد از مرحله انتخاب، الگوریتم وارد حلقه اصلی خود(حلقه  while)  می­شود. انتخاب کروموزوم، بر اساس قانون چرخ رولت انجام می­شود، یعنی کروموزومی که میزان سازگاری کمتری داشته باشد، احتمال انتخاب شدنش بیشتر است. احتمالا این روش بعضی کروموزوم­ها را تکثیر[55] و برخی را حذف می­نماید. کروموزوم­هایی که به نگاشت­های بهترمنتهی می­شوند،  شانس بالاتری برای تکثیر در نسل بعد دارند. نخبه سالاری [56]خاصیتی است که تضمین می­کند که بهترین جواب­ها، در جمعیت باقی بماند. سپس  عمل تقاطع[57] انجام می­شود، یعنی یک جفت کروموزوم به تصادف انتخاب شده، نقطه­ای تصادفی بر روی کروموزوم اول انتخاب شده و از آن نقطه تا انتهای کروموزوم، مقادیر دو کروموزوم باهم تعویض  می­شود. 60% احتمال دارد که بر روی یک کروموزوم عمل تقاطع انجام شود.

بعد از عمل تقاطع، جهش(موتاسیون)[4] صورت می­گیرد. یعنی ابتدا کروموزومی به تصادف انتخاب شده، یکی از کارهای آن به تصادف برگزیده شده و به منبعی تصادفی نسبت داده می­شود.40% احتمال دارد که بر روی یک کروموزوم عمل جهش صورت گیرد. مقادیر تصادفی عملیات تقاطع و جهش از توزیعی یکنواخت انتخاب  می­شوند. نهایتا کروموزومهای این جمعیت اصلاح شده و مجددا ارزیابی می­شوند. تا این مرحله، یک تکرار الگوریتم GA، کامل می­شود.

شرط توقف GA، یکی از این سه شرط است.

-          کلا 1000 تکرار انجام شده باشد.

-          در 150 تکرار تغییری در کروموزوم نخبه صورت نگرفته باشد.

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

   مراحل این الگوریتم را می­توان بدین صورت خلاصه کرد:

 

 

 

 

 

Initial population;

Evaluation;

While(stopping criteria not met){

Selection;

Crossover;

Mutation;

Evaluation; }

Output best solution;

شکل  2-5-6 مراحل الگوریتم GA

2-5-7- الگوریتم SA [58]:

 SA، [18]تکنیک جستجویی است که از روند فیزیکی گداختن جامدات الهام گرفته شده است.  در روند گداختن جامدات  به دنبال به دست آوردن دمایی هستیم  که جامد با کمترین انرژی به حالت کریستالی  در آید.

در ابتدا دما افزایش داده می­شود تا حدی که فلز، ذوب شود. اگر دما به آهستگی کاهش یابد، ذره­های فلز مذاب به شکل محلی  مرتب شده و وضعیت پایداری پیدا می­کنند. تئوری SA بیان می­کند که اگر بتوان دما را تا حد امکان آهسته  پایین آورد، جامد به درجه حرارت تعادل خواهد رسید که وضعیتی بهینه است. در قیاس، تعادل گرمایی با نگاشت بهینه  کار به ماشین  (هدف بهینه­سازی)، دما با زمان کامل سازی نگاشت (تابع هزینه) و تغییر دما با تغییر پروسه نگاشت، قابل مقایسه است.

در ذیل به بیان نمونه­ای از الگوریتم SA می­پردازیم. دمای اولیه سیستم همان زمان گسترش نگاشت اولیه است. روند SA اولیه بدین شرح است.  نگاشت اولیه با استفاده از توزیع یکنواخت تصادفی، تولید  می­شود. نگاشت به روشی مشابه آنچه در عمل جهش در الگوریتم GA  شرح داده شد، جهش می­یابد و زمان­گسترش ارزیابی شده و در خصوص قبول یا رد آن تصمیم­گیری می­شود. اگر زمان گسترش جدید بهتر باشد، نگاشت جدید جایگزین نگاشت قدیمی­تر می­شود. اگر زمان گسترش جدید، بدتر(طولانی تر) باشد، عدد تصادفی zÎ[0,1) انتخاب شده و با y مقایسه می­شود.

      (2-2)                             

 

اگرz>y ، نگاشت جدید (نگاشت ضعیفتر) پذیرفته می­شود. در غیر این صورت نگاشت قدیمی­تر حفظ می­شود. برای جواب­های با زمان­گسترش یکسان(یا هنگامی که دمای سیستم خیلی زیاد باشد) yà0.5 و جواب ضعیفتر با احتمال 50% قبول می­شود. جواب­های با زمان­گسترش بسیار متفاوت(یا زمانی که دما خیلی کم باشد) yà1 و جواب ضعیف­تر معمولا رد می­شود. بعد از هر جهش، دمای سیستم به 90% دمای فعلی کاهش می­یابد. (به این درصد، سرعت کاهش دما[59] گفته می­شود.)   تا این مرحله، یکبار تکرار این الگوریتم به پایان می­رسد.  این الگوریتم، زمانی متوقف خواهد شد که هیچ تغییری در زمان گسترش در 150  تکرار رخ ندهد و یا دمای سیستم به سمت صفر میل کند.

 

 

 

 

 

 

 

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

هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، برنامه به شکل گراف جهتدار بدون سیکل (DAG) مدل می­شود که در آن گره­ها نشان دهنده کارها و لبه­ها نشان دهنده ترتیب بین گره­هاست. گاهی اوقات وزنی نیز به گره ها و لبه ها اضافه می­شود که به ترتیب نشان دهنده هزینه­های محاسباتی و هزینه­های ارتباطی است.

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

 

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

مشکل اصلی به دو دسته تقسیم می شود 1)زمانبندی کارهای خود مختار 2) زمانبندی کارهای چند گانه. گروه اول: کارهای مستقل روی پردازنده هایی از یک سیستم توزیع شده محاسباتی با چندین سیستم با عملکرد بهینه زمانبندی می شوند. گروه دوم :نیاز دارد به تخصیص کارهای چند گانه با رعایت اولویت واینکه زمان اتمام برنامه را روی سیستم های توزیع شده موازی می نیمم کند. این مشکلات می تواند بوسیله روشهای ایستا و پویا حل شود. [15]

 

 

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

 

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

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

 

 

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

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

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

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

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

 شکل3-2-3 (الف) یک گراف  و هزینه­های محاسباتی و ارتباطی آن را نشان می­دهد:
در شکل 3-2-3 (ب)  سه کلاستر خطی را مشاهده  می­کنید یعنی {n1,n2,n7} , {n3,n4,n6} , {n5}  و در شکل 3-2-3 (ج) سه کلاستر غیر خطی{n1,n2}  {n3,n4,n5,n6} , {n7}

 

 

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

ب) نمونه ای از کلاسترینگ خطی  ج)نمونه ای از کلاسترینگ غیرخطی

 

  مسئله به دست آوردن کلاسترینگ بهینه، مسئله ای NP_complete است و راه حل­های ابتکاری دارد.  فاز بعد از کلاسترینگ شامل ادغام کلاسترها، تعیین پردازنده­ها و تعیین ترتیب کارها در پردازنده­های محلی است.  برای ادغام کلاسترها، سه استراتژی وجود دارد: توازن بار(LB[60])، به حداقل رساندن ترافیک ارتباطی(CTM [61])، روش تصادفی RND) [62])

  • توازن بار(LB): زمان اجرای کارهای یک کلاستر، بار کاری آن کلاستر محسوب می­شود. در گام ادغام کلاستری مانند C1 انتخاب می­شود که کمترین بار کاری را دارد. از بین کلاسترهایی که با C1 لبه ارتباطی دارند، کلاستر C2­ای که کمترین بار کاری را دارد انتخاب می­شود. کلاستر C1 و C2 باهم ادغام می­شوند.
  • به حداقل رساندن ترافیک ارتباطی(CTM): ترافیک ارتباطی زوج  کلاستر ( C1,C2 ) بصورت مجموع زمان­های ارتباطی لبه­های از C1 به C2 و از C2  به C1 تعریف می­شود. در هر گام ادغام، جفت کلاسترهایی که بیشترین ترافیک را دارند، باهم ادغام می­شوند.
  • تصادفی RND)): در هر گام اصلاح،  زوجی تصادفی از کلاسترها را باهم ادغام می­کند.

برای تخصیص پردازنده، ابتکار ساده­ای به کار گرفته می­شود تا نگاشت یک به یکی بین کلاسترها و پردازنده ها صورت گیرد. ابتدا  کلاستری که بیشترین  ترافیک ارتباطی با سایر  کلاسترها را دارد به پردازنده­ای واگذار می­شود. سپس  کلاستر واگذار نشده­ای که بیشترین ترافیک را با یک  کلاستر واگذار شده دارد انتخاب شده و به نزدیکترین پردازنده­ای که  شریک ارتباطی­اش است ، واگذار می­شود. الگوریتم تکرار می­شود تا همه کلاسترها به پردازنده­ها واگذار شوند.

بر اساس ايده اصلي كلاسترينگ، نيازي نيست كه ابتكارات كلاستر، در فاز كلاسترينگ به تفاوت منابع توجه کنند. اما در فازهاي بعدي يعني ادغام كلاسترها، فاز تخصيص منبع ،  ناهمگونی منابع قطعا بر كارايي نهايي تاثير ميگذارد.

الگوريتم های ابتكاری كلاسترمناسبی تا كنون براي محيط گريد مطرح نشده است، محيطي كه دارای  ارتباطات گران مي باشد و كارايي منابعش در خلال زمان تغيير مي كند. ارزش ديگر ابتكارات کلاستر براي زمان­بندي  گريد،  طبيعت چند بخشي آن است كه اين انعطاف را به زمان­بند گريد مي دهد كه براي شكل­دهي و سازماندهي منابع تحت امرش، از استرات‍ژی­های متفاوتی  استفاده کند.

 

 

 

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

احمد و همکارانش الگوریتم­های زمان­بندی گراف برنامه را به صورت شکل

 3-2 دسته بندی
کرده­اند[41] [29] :

 

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

زمان­بندی برنامه­های موازی در محیطهای چندپردارنده­ای به دو دسته اصلی تقسیم می­شود.
 زمان­بندی کارهای مستقل و زمان­بندی کارهای وابسته. کارهای مستقل رابطه تقدمی نداشته و می­توانند به طور همزمان اجرا شوند. اثبات شده که زمان­بندی اینگونه کارها در محیطهای چندپردازنده­ای، مسئله ای Np_complete است. در تحقیقات اولیه در خصوص زمان­بندی گراف برنامه، فرضیات ساده کننده­ای در نظر گرفته شده است. مثلا نوع گراف به ساختار [16]خاصی محدود شده( مثلا ساختار درختی) یا هزینه ارتباط و یا هزینه محاسبات یکنواخت فرض شده و یا اصلا هزینه ارتباط در نظر گرفته نشده است. و با توجه به این فرضیات محدود کننده، الگوریتم­هایی با پیچیدگی چندجمله­ای ارائه شده است.

الگوریتم­هایی که به هزینه ارتباطی محیط نیز توجه دارند، به دو دسته تقسیم می­شوند. دسته­ای که از رهیافت تکثیرکار استفاده می­کنند یعنی الگوریتم­های TDB [63]و دسته­ای که از این رهیافت استفاده  نمی­کنند.  هدف  الگوریتم­های TDB کاهش سربار محاسباتی و افزایش تحمل خطاست. استراتژی­های متفاوتی برای انتخاب کار جهت تکثیر وجود دارد، بعضی الگوریتم­ها  فقط کار ماقبل بلافصل را تکثیر می­کنند و بعضی همه اجداد ماقبل را. [37]

از نظر مدل­سازی محیط پردازش، برخی الگوریتم­ها، تعداد پردازنده­ها را محدود فرض کرده­اند که به این دسته از الگوریتمها BNP [64] گفته می­شود و برخی تعداد پردازنده­ها را نامحدود فرض کرده­اند که به آن دسته از الگوریتم­ها UNC [65] گفته می­شود. در هر دو دسته فرض شده که شبکه ارتباطی کامل است یعنی بین هر زوج پردازنده، مسیری موجود است و توجهی به پویایی لینکها و استراتژی­های مسیریابی نشده است. الگوریتم­های کمی وجود دارند که مدل­های کلی­تری برای سیستم فرض کرده­اند مثلا توپولوژی شبکه را اختیاری فرض کرده­اند و یا به پویایی لینک­ها توجه نموده­اند که به این دسته از الگوریتم­ها APN [66] گفته می­شود.[29]

قبل از ارائه الگوریتم­های زمان­بندی گراف برنامه، به معرفی چند پارامتر و اصطلاح مطرح در الگوریتم­های زمان­بندی می­پردازیم.

 

 

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

  • · [67]blevel,[68] tlevel:  در بیشتر الگوریتم­های زمان­بندی گراف برنامه از این دو صفت، برای تعیین اولویت استفاده می­شود.  tlevel گره ni، وزن طولانی ترین مسیر از گره  مبدا تا گره  ni است (شامل خود ni). طول مسیر ازجمع  وزن همه گره­ها و لبه­ها  به دست  می­آید(زمان اجرای ni را شامل نمی­شود).  tlevel هر گره  نشان­دهنده نزدیکترین زمان شروع ممکن برای  آن گره است که آن را با ASAP[69] نیز نشان  می­دهند. بعضی الگوریتم­ها وزن لبه­ها را به حساب  نمی­آورند. در چنین حالتی به این صفت tlevel ایستا و یا SL  گفته می­شود. در زیر، روال محاسبه tlevel  آورده شده است. این روال، دارای پیچیدگی زمانی O(v+e)  می­باشد. ( v تعداد رئوس گراف و e تعداد لبه هاست.)

 

1 Create TList , a  list  o f  nodes  in  topological  order .

2 for each node n o f TList do 

3              max = 0

4              for each parent p of  n  do

5                              if ( tlevel (p) + tp + cp,n ) > max then

6                              max = tlevel (p) +tp + c p,n

7              end if

8 end for

9 tlevel(n)=max

10 end for

 

 

blevel گره ni  وزن طولانی ترین مسیر از ni  تا گره خروجی است ( زمان اجرای ni را نیز شامل می­شود). در ادامه، روال محاسبه blevel  آورده شده است. که پیچیدگی زمانی آن  O(v+e) می­باشد.

 

1 Create RTList , a list o f  nodes in reversed  topological order .

2 for each  node n of RTList do

3              max = 0

4              for each child  c of  n  do

5                              i f (c n,c + blev e l ( c ) ) > max  then

6                              max = c n,c + blevel ( c )

7                              end if

8              end for

9              b l e v e l (n) = tn + max

10 end for

 

به طور کلی، زمان­بندی بر اساس ترتیب نزولی blevel ، به زودتر زمان­بندی شدن گره­های روی مسیر بحرانی منجر  می­شود در حالی که زمان­بندی به ترتیب صعودی tlevel ، به زمان­بندی گره­ها به ترتیب توپولوژی آنها منتهی می­شود.

  • مسیر بحرانی ( CP [70]) :  CP،  طولانی­ترین مسیر گراف است.  ممکن است در یک گراف بیش از یک مسیر بحرانی وجود داشته باشد. حد بالای blevel و tlevel به میزان CP محدود می­شود.
  • [71]ALAP: این پارامتر مشخص­کننده دیرترین زمان شروع ممکن برای یک گره است به بیان دیگر نشان می­دهد که شروع یک گره چقدر می­تواند تاخیر داشته باشد بدون آنکه بر طول کلی زمان­بندی تاثیر بگذارد.  ALAPهر گره از تفاضل CP گراف و blevel آن گره بدست می­آید.
  • · :  به تفاوت بین ALAP و ASAP یک گره،  Mobility آن گره گفته می­شود. در بعضی از الگوریتم­ها از این پارامتر بعنوان اولویت گره استفاده می­شود. گاهی از این پارامتر برای زمان­بندی کارهای یک منبع استفاده می­شود. یعنی اجرای کارهای قبلا زمان­بندی شده را به تاخیر می­اندازند تا بتوان یک کار جدید، در شکاف[72] زمانی فراهم آمده،  جاسازی کرد(کاری که قید ترتیب را نقض نکند).
  • [73]DS:  به مسیربحرانی گراف  زمان­بندی شده،  DS و به وزن آن زمان موازی[74] می­گویند. با کمک فرمول (3-1) می­توان زمان موازی  گراف زمان­بندی شده را محاسبه کرد.

      (3-1)

  • · کارآزاد[75]: کاری، آزاد محسوب می­شود که ماقبلی نداشته باشد یا اینکه همه ماقبل­های آن قبلا بررسی شده و به منبعی نگاشت شده باشند.
  • · کارجزئی آزاد[76] :  کاری، جزئی آزاد  محسوب می­شود که بعضی از  ماقبل­های آن قبلا بررسی شده و به منبعی نگاشت شده باشند.
  • · کار آماده: کار آماده، کاری است که می­تواند فورا اجرا شود چون داده­های مورد نیازش در منبعی که به آن نگاشت شده مهیا است. هر کار آماده، کارآزاد نیز محسوب می­شود ولی هر کار آزاد، کار آماده نیست.

در شکل3-3 مقادیر پارامترهای مشروحه را برای یک گراف  نمونه ملاحظه می­نمایید. 

 

       
 

الف)

 
   

ب)

 
 

 

 

شکل  3-4-  الف) گراف کارها    
 ب) مقادیر پارامترهای SL , tlevel , blevel , ALSAP  گره های گراف

 

 

 

 

 

 

 

 

 

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

 

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

پیچیدگی این الگوریتم خطی است.  فرضیات محدود کننده­ای در نظر گرفته شده است. ساختار گراف، درختی[77] فرض شده، هزینه محاسباتی منابع یکسان و هزینه ارتباطی صفر و تعداد منابع محدود و معادل p، در نظر گرفته شده است. در واقع در چنین گرافی، هر راس از سایر رئوس قابل دسترس می­باشد. به هر گره ni   برچسب αi  زده می­شود بدین صورت که : xi +1  = α      و     xi  طول مسیر از ni   تا گره  خروجی گراف می­باشد.چون هزینه ارتباطی وجود نداشته و هزینه محاسبات یکسان فرض شده، xi همان تعداد لبه های مسیر خواهدشد. مراحل این الگوریتم را می­توان بدین صورت خلاصه کرد:

- اولین p گره با بالاترین مقدار برچسب، به پردازنده­ها واگذار می­شود. یعنی در آغاز الگوریتم حداقل همه گره­های ورودی گراف، زمان­بندی می­شوند.

- p تا کار زمان­بندی شده از گراف حذف شده و همه گره­های فاقد گره ماقبل، گره ورودی تلقی می­شود.

-  گام­های 1 و 2 تا زمان­بندی شدن تمامی گره­های گراف  تکرار می­شود.

Hu بهینگی الگوریتم خود تحت شرایط ذکر شده را اثبات کرده است.

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

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

  1. گره­ی خروجی انتخاب شده و به آن برچسبی با مقدار 1 اختصاص داده می­شود.
  2. در گام jام برچسبهای  1,2,….j-1    تخصیص می­یابد. فرض کنید، S مجموعه گره­های تخصیص نیافته­ای باشد که هیچ گره مابعد بلافصل آن بدون برچسب نباشد. برچسب j باید به عنصری از S واگذار شود . برای هر گره x متعلق به مجموعه S فرض کنید که   گره­های مابعد بلافصل x باشند. فرض کنید l(x) توالی کاهشی از اعداد صحیح باشد که توسط مجموعه برچسب­های y مشخص می­شود. اگر  آنگاه برجسب j به x زده می­شود.
  3. بعد از کامل شدن پروسه برچسب گذاری، لیست کارها به ترتیب نزولی مرتب شده و کارها به ترتیب به منبعی که زودترین زمان شروع را برایش امکان پذیر سازد، واگذار می­شود.

 

کافمن و گراهام به کمک مثال­هایی  نشان دادند که زمانی که تعداد پردازنده­ها افزایش یابد یا هنگامی که هزینه محاسباتی کارها متفاوت باشد، پروسه برچسب­گذاری و پروسه زمان­بندی هر دو دارای پیچیدگیO(v2)   خواهند بود.

 

3-5-3- الگوریتمی برای زمان­بندی گراف بازه­ای مرتب شده[78]:

 پاپادیمترو و یاناکاکیس الگوریتمی بهینه با  زمان خطی  برای زمان­بندی گراف  بازه­ای مرتب شده، برای مالتی پروسسورها ارائه نموده اند. در یک گراف  بازه­ای مرتب شده، دو گره رابطه تقدمی دارند اگر و فقط اگر بتوان آن گره­ها را به بازه غیر همپوشانی از خط حقیقی نگاشت نمود. با توجه به این ویژگی می­توان از تعداد گره­های مابعد یک گره به عنوان اولویت آن سود جست. شکل 3-4 مثالی ازچنین گرافی است.  پیچیدگی زمانی این الگوریتم، O(v+e) است.[13] اگر از شرط یکسان بودن  هزینه محاسبات صرف نظر شود، مسئله تبدیل به مسئله ای Np_complete می­شود.[12]

 

 

 

 

 

 

 

 

 

 

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

   ب) زمان­بندی بهینه تولید شده توسط الگوریتم پاپادیمترو و یاناکاکیس

 

 

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

 

الگوریتم

نوع الگوریتم

اولویت

پیچیدگی زمانی

فرضیات

Sarkar

Clustring

Weight of edges

O(e(v+e))

BNP

HLFET

Static  list scheduling

Static blevel

O(v2)

BNP

ETF

Static  list scheduling

ASAP

O( v2p)

BNP

ISH

Static  list scheduling

 blevel

O( v2)

BNP

FLB

Static  list scheduling

ASAP

 

BNP

DSC

Dynamic list scheduling

blevel+tlevel

O((e+v)log v)

UNC

CASS-II

Clustering

blevel+tlevel

 

UNC

DCP

Dynamic list scheduling

Mobility

O( v3)

UNC

MCP

Dynamic list scheduling

ALAP

O( v2log v)

UNC

MD

Dynamic list scheduling

Relative Mobility

O( v3)

UNC

TDS

Duplication-based

Static blevel

O(v+e)

BNP

 

 

 

 

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

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

 این الگوریتم ، در زمره الگوریتم­های کلاسترینگ به شمار می­آید. در ابتدا، الگوریتم  لبه­های گراف را به ترتیب نزولی وزنشان مرتب می­کند. بعد در هر گام کلاسترینگ، لبه­ها به ترتیب ملاقات شده و اگر باعث افزایش زمان موازی نشوند، مقدار آنها به صفر تغییر داده می­شود. در هر گام کلاسترینگ، زمان موازی با پیمایش توپولوژیکی گراف زمان­بندی شده، محاسبه می­شود. چون e تا پیمایش خواهیم داشت، پیچیدگی زمانی این الگوریتم  O(e(v+e)) خواهد بود (که بر پیچیدگی  O(elog e) برای مرتب­سازی لبه­ها غلبه می­کند). در این الگوریتم تعداد پردازنده­ها محدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

 

 

 3-6-2- الگوریتم HLFET[79]:

این الگوریتم [36]، از دسته الگوریتم­های زمان­بندی به کمک لیست می­باشد. ابتدا مقدار blevel ایستای گره­ها محاسبه می­شود. سپس گره­ها به ترتیب نزولی مقدار blevel ایستایشان، مرتب  شده و لیست گره­های آماده را پدید  می­آورند. نهایتا گره­های لیست آماده به ترتیب به پردازنده­ای که نزدیکترین زمان شروع را برایشان میسر سازد، واگذار می­شوند.

 در این الگوریتم تعداد پردازنده ها محدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

 

3-6-3- الگوریتم ETF[80] :

 ایده اصلی این الگوریتم  [23]، این است که تا حد امکان پردازنده را مشغول نگه دارد. در هر گام زمان­بندی، اولویت کارهای آماده نگاشت نشده، محاسبه می­شود. اولویت کار، یعنی نزدیکترین زمان شروع ممکن برای آن کار که با نگاشت آزمایشی آن کار بر روی همه منابع تعیین می­شود.  سپس کار با کوچکترین اولویت انتخاب شده و به پردازنده مرتبط با این اولویت، واگذار می­شود. پیچیدگی زمانی این الگوریتم O(v2p) است. این الگوریتم توجهی به مسیر بحرانی گراف ندارد و تضمین نمی­کند که کارهای مهمتر را زودتر زمان­بندی کند. [5]

در این الگوریتم تعداد پردازنده­ها محدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

 

 

3-6-4- الگوریتم ISH[81] :

این الگوریتم [36]، سعی دارد تا حد امکان، شکاف­های زمانی بیکار پردازنده­ها را پر کند. در ابتدا مقدار blevel گره­ها به شکل ایستا محاسبه می­شود و از این پارامتر به عنوان  اولویت گره­ها استفاده  می­شود. یعنی گره با مقدار blevel بیشتر، اولویت بالاتری خواهد داشت. سپس گره آماده­ی با بالاترین اولویت انتخاب شده و به پردازنده­ای که نزدیکترین زمان شروع را برایش میسر سازد، واگذار می­شود (یعنی در صف FIFO آن پردازنده قرار می­گیرد). اگر زمان­بندی گره­ای سبب ایجاد شکاف زمانی بیکار در پردازنده­ای شود، الگوریتم سعی می­کند که گره هایی را در شکاف بیکار پدید آمده، جاسازی کند. سپس گره آماده دیگری از صف انتخاب شده و مراحل فوق تکرارمی­شود. پیچیدگی زمانی این الگوریتم O(v2) است . در این الگوریتم تعداد پردازنده­ها محدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

3-6-5- الگوریتم FLB[82] :

 این الگوریتم [2]، توسعه یافته الگوریتم ETF است و از معیار انتخاب کار مشابهی استفاده
می­کند. با این تفاوت که کار با روشی با   O(log p)))  انتخاب می­شود، در حالی که در الگوریتم ETF انتخاب با (O(wp صورت می­گرفت که w عرض درخت و p  تعداد پردازنده هاست. (عرض درخت: حد اکثر تعداد کارهای مستقل گراف). در حین روند زمان­بندی ممکن است حالتی پیش بیاید که اجرای چندین کار آماده را بتوان در یک "نزدیکترین زمان" آغاز کرد. الگوریتمهای ETF و FLB معیارهای متفاوتی برای مقابله با این حالت دارند. در این الگوریتم تعداد پردازنده­ها محدود تصور شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

3-6-6- الگوریتم : [83]DSC

 الگوریتم Sarkar، بزرگترین لبه ارتباطی گراف را صفر می­کرد. ممکن است این لبه اصلا جزو DS نباشد.  از طرفی می دانیم که DS تعیین کننده "زمان موازی " است، در نتیجه صفر کردن چنین لبه­ای به کاهش زمان موازی، منجر نخواهد شد. ایده اصلی این الگوریتم [ 15]، صفر کردن لبه­هایی است که باعث کاهش DS می­شوند. در گام مقداردهی اولیه، هر گره، یک کلاستر فرض می­شود. سپس کلاسترهای مناسب انتخاب شده و باهم ادغام می­شوند تا هزینه ارتباط آنها "صفر" گردد.  بدین ترتیب لبه متصل کننده دو کلاستر هم مقدار صفر خواهد گرفت. در گام مقداردهی اولیه، blevel همه گره­ها و مقدار tlevel گره­های آزاد محاسبه  شده و دو لیست ساخته می­شود. لیست کارهای آزاد (FL)  و لیست کارهای آزاد جزئی (PFL). اولویت در لیست (FL) بدین صورت تعریف می­شود:

                                           

      (3-2)                                              

 

و کارها به ترتیب نزولی اولویتشان در لیست (FL) قرار می­گیرند در نتیجه گره روی DS، گره با بالاترین اولویت خواهد بود. tlevel گره­های آزاد نسبی بدین شکل تعریف می­شود:

 

      (3-3)

که EG مجموعه گره­های آزمایش شده است و اولویت گره­های موجود در لیست کارهای آزاد جزئی بدین صورت تعریف می­شود:

      (3-4)                         

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

  1. مقداردهی اولیه

- همه گره­های آزاد ورودی را در لیست (FL) قرار بده.

- blevel همه گره­ها را حساب کن.

- برای همه گره­های آزاد قرار بده: tlevel = 0

  1.  ny = head(PFL) و nx = head(FL)
  2. اگر  PRIO(nx) >=  pPRIO(ny)   آنگاه  minimize tlevel(nx) و الا ، تحت شرایط DSRW [84] پروسه
      minimize  tlevel(nx)   را صدا بزن.
  3. اولویت مابعدهای nx را بروز رسانی کن.
  4. تا بررسی همه گره­ها، مراحل فوق را تکرار کن.

ü پروسه minimization: به منظور کاهش tlevel(nx)، پروسه مینیمم­سازی، چندین لبه وارده کار آزاد nxرا صفر می­کند. اگر صفر کردن لبه باعث کاهش tlevel نشود، گره در کلاستر خود باقی مانده و ادغامی صورت نمی­گیرد. هزینه پروسه مینیمم­سازی O(mlog m) است که m تعداد گره­های ماقبل nxاست.

ü تضمین کاهش طول DS (DSRW ): این شرط زمانی مطرح می­شود که DS از هیچ کار آزادی عبور نکند و یک DS وجود دارد که از گره آزاد جزئی ny می­گذرد. در این حالت صفر کردن لبه­های وارده غیر DS از گره­های آزاد، می­تواند در کاهش tlevel(ny) در گام­های بعدی موثر باشد. بنابراین DSRW بیان می­کند که صفر کردن لبه­های یک گره آزاد بر کاهش آتی tlevel(ny) تاثیر نخواهد داشت، اگر با صفر کردن لبه DS وارده از ny قابل کاهش باشد.   اگر np  گره ماقبل آزمایش شده ny باشد و صفر کردنp,ye به کاهش ptlevel(ny) بیانجامد، آنگاه از شرط  DSRW استفاده می­شود تا به گره­های دیگر اجازه نگاشت به منبع در دست np داده نشود تا ny آزاد شود.

 پیچیدگی این الگوریتم از مرتبه O((e+v)log v)  می­باشد. در این الگوریتم تعداد پردازنده­ها نامحدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

3-6-7- الگوریتم CASS-II[85]

این الگوریتم [24]، با الگوریتم DSC قابل مقایسه است، با این تفاوت که ساخت کلاسترها از پایین به بالا است یعنی  این الگوریتم  با گره­های خروجی،  شروع به کار می­کند. این الگوریتم دارای دو گام است. در گام اول، مقدار tlevel همه گره­ها محاسبه می­شود.  در گام دوم یعنی گام کلاسترینگ، ابتدا مقدار blevel گره­ها محاسبه  می­شود. سپس گره­های خروجی nx در یک کلاستر قرار می­گیرند و مقدار blevel آنها بدین صورت تنظیم می­شود:

            (3-5)                                                                     

و مراحل زیر تکرار می­شود:

-  گره ny که همه گره­های مابعد بلافصل آن کلاستربندی شده باشند، انتخاب می­شود. (گره جاری)

- چون همه مابعدهای ny کلاستربندی شده اند و blevel آنها قبلا محاسبه شده است، مقدار blevel(ny)  به راحتی محاسبه می­شود. گره­های جاری به ترتیب کاهشی میزان tlevel + blevel در پروسه کلاستربندی، شرکت می­کنند. برای گره جاری ny مفروض، فرض کنید که nx مابعد غالب آن باشد(یعنی مابعدی که تعیین کننده میزان blevel(ny) است). و فرض کنید Cx، کلاستر حاوی nx باشد. ny در صورتی به کلاستر Cx ملحق می­شود که این الحاق باعث افزایش blevel(ny) و blevel(Cx) نشود. (ماکزیمم  blevel متعلق Cx است.) در غیر اینصورت ny در کلاستر جدیدی جای می­گیرد. در این الگوریتم تعداد پردازنده ها نامحدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

3-6-8- الگوریتم DCP[86]:

این الگوریتم  [36]، از پارامتر mobility استفاده می­کند. به  تفاوت ALAP (دیرترین زمان شروع ممکن) و ASAP(زودترین زمان شروع ممکن)، mobility گفته می­شود. پارامتر mobility را می­توان به شکل زیر نیز تعریف کرد:

      (فرمول 3-6) 

گره­های با mobility کوچکتر زودتر انتخاب می­شوند. کوچکرین مقدار mobility صفر است و گره­های با mobility صفر  روی مسیر بحرانی قرار دارند. این الگوریتم  از نوعی استراتژی رو به جلو[87] برای یافتن کلاستر مناسب گره، بهره می­گیرد. [36]

مراحل این الگوریتم را می­توان به شرح زیر خلاصه کرد:

  1. مقدار ASAP و ALAP همه گره­ها را محاسبه کن.
  2. گره nx با کوچکترین مقدار mobility را انتخاب کن. فرض کن nc فرزند زمان­بندی نشده nx باشد که بیشترین ارتباط را با آن دارد.
  3. از میان پردازنده هایی که والدین nx یا فرزندان آن را در اختیار دارد، پردازنده­ای را انتخاب کن که کمترین مقدار  ASAP(nx)+ ASAP(nc) را ایجاد می­کند. هنگام بررسی یک پردازنده، ابتدا سعی کن شکاف زمانی بیکاری پیدا کنی. اگر امکان پذیر نبود سعی کن با بیرون کشیدن تعدادی گره پایینی قبلا زمان­بندی شده، شکاف زمانی بیکار تولید کنی.  (با توجه به mobility به گونه­ای که طول زمان­بندی افزایش نیابد.) در صورت شکست، پردازنده جدیدی انتخاب کن.
  4. nx را در p زمان­بندی کن.
  5. ALAP و ASAP همه گره­ها را به روز کن.
  6. مراحل 2 الی 5 را تا زمان­بندی همه گره­ها تکرار کن.

 

3-6-9- الگوریتم MCP [88]:

این الگوریتم [14]، از ALAP (دیرترین زمان شروع ممکن) به عنوان اولویت گره­ها استفاده می­کند. ابتدا  ALAP همه گره­ها محاسبه می­شود. سپس لیست گره­ها به ترتیب صعودی ALAP مرتب می­شود. گره­ها به ترتیب به پردازنده­ای که کوچکترین زمان شروع ممکن را برایشان میسر سازد، واگذار می­شوند. پیچیدگی این الگوریتم O(v2logv)  می­باشد. در این الگوریتم تعداد پردازنده­ها نا محدود در نظر گرفته شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

3-6-10- الگوریتم MD[89] :

 این الگوریتم [13]، از معیاری به نام mobility نسبی به عنوان اولویت گره­ها استفاده می­کند. این معیار بدین صورت تعریف می­شود:       

       (3-7)             


که  زمان اجرای کار nx است.  اگر گره­ای بر روی مسیر بحرانی گراف جزئی زمان­بندی شده قرار داشته باشد، مجموع blevel و tlevel آن معادل طول مسیربحرانی جاری بوده و در نتیجه mobility آن صفر خواهد شد. این الگوریتم بدین شکل کار می­کند که در هر گام، گره با کوچکترین اولویت به اولین پردازنده­ای که شکاف زمان به اندازه کافی بزرگ دارد، واگذار شده و در آن شکاف زمانی جاسازی می­شود. این الگوریتم تلاشی برای به حداقل رساندن زمان شروع گره ها نمی­کند و این مسئله ممکن است  به افزایش طول زمان­بندی منتهی شود. پیچیدگی این الگوریتم  O(v3) می­باشد . در این الگوریتم، تعداد پردازنده­ها نامحدود فرض  شده و فرض شده که بین همه منابع ارتباطی دو بدو وجود دارد.

 

3-6-11- الگوریتم TDS [90]:

در این الگوریتم [36]، برای هر گره گراف،  نزدیکترین زمان شروع(est  )، نزدیکترین زمان کامل شدن (ect) دیرترین زمان شروع ممکن  (last)، دیرترین زمان کامل شدن (lact) و جد مطلوب[91] محاسبه می­شود.  last دیر ترین زمانی است که می­توان اجرای کار را  آغاز نمود و الا کارهای بعد آن با تاخیر مواجه خواهند شد. اجداد مطلوب گره i، گره­های ماقبلی هستند که اگر i  به همان پردازنده­هایی واگذار شود که آنها آنجا در حال اجرا هستند،  est(i) حداقل  خواهد شد. از میزان level گره (یعنی طول مسیر از آن گره تا گره  خروج، با صرف نظر از هزینه ارتباطی مسیر)  به عنوان اولویت برای تعیین ترتیب پردازش  استفاده می­شود. برای محاسبه مقدار level، کل گراف  پیمایش می­شود که پیچیدگی این مرحله از مرتبه O(e+v)   است. بر اساس این مقدار و به شکل تکراری کلاسترهایی تولید  می­شود.  گام کلاسترسازی مانند جستجوی اول عمق از گره واگذار نشده­ای که کوچکترین مقدار level را دارد تا یک  گره  ورودی انجام می­شود. هنگامی که یک گره ورودی  می­رسد،  کلاستری  تولید می­شود. همه کارهای یک کلاستر به یک منبع واگذار خواهند شد. در این گام مقادیر lact و last تعیین می­کنند که آیا نیازی به تکثیر هست یا نه. به عنوان مثال اگر j، جد مطلوب i باشد و (last(i)-lact(j))< c i,j    باشد که c i,j  هزینه ارتباطی بین i و j است، i  به همان پردازنده j واگذار می­شود و اگر j به پردازنده دیگری واگذار شود، در پردازنده i نیز تکثیر خواهد شد. در گام کلاسترینگ، گراف   را از گره  خروج  مشابه جستجوی اول عمق پیمایش می­کنیم که پیچیدگی این مرحله  همان پیچیدگی جستجوی اول عمق یعنی O(v+e)  خواهد بود. پس پیچیدگی کلی O(v+e)   خواهد بود. در گراف   متراکم ، تعداد لبه­ها متناسب با O(v2) خواهد شد وبدترین پیچیدگی الگوریتم تکثیر خواهد بود. توجه کنید که در گام کلاسترینگ، تعداد منابع در دسترس کمتر از تعداد مورد نیاز فرض می­شود .

 

 

 

 

 

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

 

3-7-1- الگوریتم [92]HEFT:

این الگوریتم [36]، برای تعداد معینی پردازنده ناهمگون، طراحی شده است و شامل دو مرحله است. در مرحله اول، blevel همه گره­های گراف محاسبه می­شود.  blevel  هر گره نشان دهنده اولویت زمان­بندی آن گره نیز  می­باشد. درحله دوم، مرحله انتخاب منبع است. در این مرحله کارها به ترتیب اولویت بررسی شده و  به پردازنده­ای که کوتاهترین زمان اتمام را برایشان فراهم کند، واگذار می­شوند. این الگوریتم از نوعی سیاست جایگذاری بهره می­گیرد و سعی دارد که  کار را در نزدیکترین شکاف زمانی بیکار بین دو کار قبلا زمان­بندی شده جا سازی کند. پیچیدگی زمانی این الگوریتم ، O(e*p)  است که e  تعداد لبه­هاست و p  تعداد منابع می­باشد. اگر گراف برنامه متراکم باشد، پیچیدگی زمانی این الگوریتم، O(v2*p) خواهد بود.  HEFT یکی از متداول­ترین الگوریتم­های لیست برای پردازنده­های ناهمگون است و هدف کارایی آن  کاهش زمان گسترش کل گراف برنامه است.

 

 

3-7-2- الگوریتم [93]CPOP :

 این الگوریتم [1]، نیز شامل دو مرحله است. در مرحله نخست اولویت کارها مشخص می­شود. یعنی blevel و tlevel کلیه کارهای گراف، محاسبه شده و مجموع blevel و tlevel آن به عنوان اولویت کار منظور می­شود. ابتدا کار ورودی انتخاب شده و به عنوان کار متعلق به مسیر بحرانی علامت می­خورد. سپس گره مابعد بلافصلی که بالاترین اولویت را دارد انتخاب شده و به عنوان کار متعلق به مسیر بحرانی علامت می­خورد و این روند تا رسیدن به گره خروجی تکرار می­شود. در مرحله دوم، کارها به ترتیب اولویت انتخاب شده و اگر روی مسیر بحرانی قرار داشته باشند، در پردازنده مخصوصی زمان­بندی می­شوند. این پردازنده، ماشینی است که هزینه محاسبه جمع شونده  کارهای مسیر بحرانی را به حداقل می­رساند. و اگر کار، روی مسیر بحرانی قرار نداشته باشد، به پردازنده­ای که نزدیکترین زمان اتمام را برایش میسر سازد، واگذار  می­شود. پیچیدگی زمانی این الگوریتم در حالتی که گراف برنامه متراکم است، O(v2*p) خواهد بود.

 

 

3-7-3- الگوریتم [94]LMT :

این الگوریتم ، در دو مرحله اجرا می­شود. در مرحله اول، کارهایی  که می­توانند به شکل موازی اجرا شوند، به روش تجزیه سطحی گروه­بندی می­شوند.  در مرحله دوم  به شیوه حریصانه هر کار به سریعترین منبع در دسترس واگذار می­شود. کارهای سطح بالاتر، اولویت بیشتری نسبت به کارهای سطح پایین تر خواهند داشت و در یک سطح، کاری که بالاترین میانگین هزینه اجرا را داشته باشد، اولویت بالاتری خواهد داشت. اگر تعداد کارهای موجود در یک سطح از تعداد پردازنده­های در­دسترس بیشتر باشد، کارهای ریز باهم ادغام شده و کارهای درشت­تری می­سازند تا تعداد کارها،  معادل تعداد پردازنده­ها شود. سپس کارها بر اساس میانگین زمان اجرا، مرتب شده و به ترتیب از کوچک به بزرگ بررسی شده و به پردازنده­ای که مجموع هزینه اجرا و هزینه ارتباط کمتری داشته باشد، واگذار می­شود.  پیچیدگی زمانی این الگوریتم برای گراف متراکم O(v2*p2) است.

 

 

3-7-4- الگوریتمTANH  [95]:

 این الگوریتم [10]، نمونه ای  از الگوریتم­های تکثیر کاراست. در این الگوریتم برای هر کار،  پارامتری به نام پردازنده مطلوب[96]  تعریف می­شود که پردازنده­ای است که می­تواند زودتر کار را کامل کند. سایر پارامترهای کار، بر اساس پارامتر پردازنده  مطلوب محاسبه می­شود. در گام کلاسترینگ، اولین کار کلاستر به اولین پردازنده مطلوبش واگذار می­شود و اگر اولین پردازنده مطلوب  قبلا تخصیص شده باشد، به دومین و الا آخر. اگر تعداد پردازنده­ها از تعداد کلاسترهای تولید شده، کمتر باشد، از الگوریتم کاهشی ویژه ای برای ادغام کلاسترها استفاده  می­شود. در مقایسه با نسخه مربوط به منابع همگون،  این نسخه پیچیدگی بالاتری دارد یعنی از مرتبه O(v2 *p)  است و این منطقی به نظر می­رسد چون زمان اجرای یک کار بر روی منابع مختلف، متفاوت است.

 

 

 

 

 

 

 

 

 

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

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

این الگوریتم از الگوریتم هایی است که در زمان کامپایل و بر اساس لیست کار می کند. واز انواع الگوریتمهای اکتشافی برای کارهای وابسته در محیطهای همگن و یک مرحله ای است .اگر چه برنامه های وسیع برای سیستم های بزرگ در زمان کامپایل پیچیدگی زیادی دارد  اما این الگوریتم از الگوریتم های سریع است.[23]

در هر بار تکرار کار آمادهای که زمان شروع کمتری دارد را انتخاب می کند.هدف اصلی آن بهره وری بیشتر و مشغول نگه داشتن پردازنده میباشد.

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

پهنای گراف : بیشترین تعداد کارهایی که بواسطه یک مسیر پیوسته نیستند.

کار ورودی: کاری که هیچ یال ورودی نداشته باشد.

کار خروجی : کاری که هیچ یال خروجی نداشته باشد.

کار آماده : کاری که اجرای تمام والدینش تمام شده است .

پایان اجرا : اجرای یک کار زمانی تمام می شود که تمام پیام ها در از والدینش رسیده باشد.

زمانبندی : کارtرا به یک پردازنده proc(t) اختصاص می دهد و یک زمان شروع ST(t) و زمان اتمام FT(t)  را می دهد

زمان اتمام آخرین کار زمان بندی شده

   پردازنده توانا: پردازنده ای است که آخرین پیغام ازآن رسیده باشد . آخرین

پیغام زمانی می رسد که کار آماده t تعریف شده باشد

  پیام موثر: پیغامی که توسط اجداد t که زمانبندی شده اند می رسد زمان ارتباط را 0 در نظر می گیرد

   

تخمین زمان شروع:یک کار با پردازنده p آماده زمان بندی می شود

EST(t,p) = max{EMT(t,p),PRT(t)}

کار آماده نوع EP :زمان رسیدن آخرین پیام بزرگتر از زمان آماده کردن پردازنده توانا

LMT(t)≥prt (EP(t))

پردازنده فعال: کار های نوع EP که آنها پردازنده های توانا دارند و در غیر این صورت غیر فعال .

زمان تکمیل موازی :

Tpar = max PRT(p)

طول مسیر مجموع زمانهای اجرا و هزینه ارتباط کارها و وابسته های لبه برای مسیر .

برای گره ورودی خواهیم داشت :

                     

 

4-3الگوریتم FLB

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

 کار آماده ای که می تواند زود تر شروع شود با پردازنده ای که زمان شروع آن کار حاصل شده زمان بندی می شود.[42]

در الگوریتم ETF در هر بار زمان بندی زمان کار با تمام پردازنده ها سنجیده می شود و بررسی تمام پردازنده ها پیچیدگی زمانی اگوریتم را بالا می برد اما در الگوریتم FLB فقط دو نمونه پردازنده نیاز است که بررسی شود. به دست آوردن زمان شروع کمتر برای یک کار آماده معین روی زمان بند جزئی، کار معین باید زمانبندی شود الف)برای پردازنده ای که آخرین پیام رسیده از آن آمده است ب)پردازنده ای که در زمان معین زود تر بیکار شده است . اگر چه پردازنده ای که آخرین پیام از آن رسیده قبل از این که پیامش به پردازنده دیگر برسد بیکار شده پس زمان شروع یک کار بوسیله زمانبندی کار روی آن پردازنده می تواند بهبود پیدا کند ( به دلیل این که زمان ارسال پیام 0 می شود ) اگر آن پر دازنده در زمان رسیدن پیام مشغول باشد سپس کار تا زمان رسیدن آخرین پیام نمی توان زود تر شروع شود. در نتیجه کار ها روی پردازنده هایی که زود تر بیکار شده زود تر شروع خواهند شد .

دو نوع کار وجود  دارد الف) کار EP کار ی است که روی پردازنده فعال زود تر شروع می شود . ب) کار غیر EP کاری است که روی پردازنده ای که زود تر بیکار می شود شروع شود .

فقط دو جفت پردازنده – کار وجود دارد که می تواند کمترین زمان شروع برای یک کار را بدست بیاورد. الف)نوع EP کار t با کمترین تخمین زمان شروع EST(t,EP(t)) روی پردازنده های فعال ب)نوع غیر EP  کار t’ با کمترین زمان آخرین پیام رسیده LMT(t’) روی پردازنده هایی که زود تر بیکار می شوند اولین نمونه کمترین زمان شروع زود تر از نوع کار های EP و دومین نمونه کمترین زمان شروع زود تر از کار های غیر EP  است . اگر چه در این دو نمونه زمان شروع زودتر یکسانی بدست آمد کار نوع غیر EP  ترجیح داده می شود زیرا ارتباطات بوسیله ارسال پیام از کار های اجدادش با ارتباطات قبلی اشتراک داشته اند .

برای هر پردازنده معین که فعال است دوانبار لیست مرتب شده کار نوع EP وجود دارد . کار ها در ابتدای لیست  (EMT_EP_task_1)  به طور کمینه بوسیله زمان رسیدن پیام های موثر و کارا روی پردازنده های فعالشان ذخیره شده اند EMT(t,EP(t)) .

کار ها در لیست دوم(LMT_EP_task_1) به صورت کمینه بوسیله زمان رسیدن آخرین پیغامشان ذخیره شده اند . کار های نوع غیر EP در یک لیست (nonEP_task_1) به صورت کمینه بوسیله زمان رسیدن آخرین پیغامشان ذخیره شده اند.برای سه لیست کار به وسیله انتخاب کار با مسیز طولانی تر با هر کار خروجی گره ها شکسته می شود .

یک لیست از پردازنده های فعال (active_proc_1) به صورت افزایشی توسط حداقل EST(t) از وظايف نوع EP که توسط آنها امکان پذیرند مرتب شده اند. حداقلEST(t) از وظايف نوع EP برای یک پردازنده در O(1) با محاسبه بیشترین مقدار بین EMT اولین وظیفه در لیست (EMT_EP_task_1) پردازنده و PRT پردازنده بدست می آید. دومین لیست که برای ذخیره همه پردازنده ها است. لیست پردازنده های سراسری (all-proc-1) است که به صورت افزایشی با PRT آنها مرتب می شود.

 

 

 

 

 

 

 

 

 

 

الگوریتم FLB به صورت زیر می باشد :

 

 در شروع مجموعه وظایف آماده شامل وظایف ورودی است. هیچ کدام از آنها شرایط نوع EP را ندارند. پس آنها در لیست وظیفه نوع non-EP ذخیره می شوند.به علاوه چون وظیفه نوع EP وجود ندارد پردازنده فعالی نیز وجود ندارد و لیست پردازنده های فعال خالی است. همه پردازنده ها زمان آمادگی صفر را دارند، بنابراین همه آنها اولویت یکسانی در لیست پردازنده های سراسری دارند. حلقه زمانبندی آنقدر تکرار می شود تا همه وظایف زمانبندی شوند.در هر تکرار، یک وظیفه با استفاده از تابع ScheduleTask() زمانبندی می شود. بعد از هر زمانبندی یک وظیفه بر روی یک پردازنده، لیست وظایف آن پردازنده و لیست پردازندها و مجموعه وظایف آماده باید به روز شوند و با توجه به شرایط جدیدی که در آخرین زمانبندی ایجاد می شود مراحل دنبال می شود.

 

این تابع دو جفت کار-پردازنده برای زمانبندی انتخاب می کند.

اولین زوج شامل وظیفه نوع EP با حداقل زمان EMT و پردازنده توانا سازش است. زوج دوم وظیفه non-EP با کمترین LMT و پردازنده ای است که زودتر بیکار می شود.  زوجی که حداقل زمان شروع را حاصل کند انتخاب شده و وظیفه انتخاب شده به پردازنده انتخاب شده زمانبندی می شود. زمانبندی یک وظیفه شامل نسبت دادن آن به پردازنده متناظر ، زمان شروع و زمان پایان می شود. تابع Dequeue برای خارج کردن اولین عنصر لیست استفاده می شود.  برای انتقال عناصر ذخیره شده لیست مورد استفاده قرار می گیرد.

 

بعد از زمانبندی یک وظیفه به یک پردازنده، زمان آمادگی پردازنده تغییر می کند. در نتیجه برخی از وظایف نوع EP که تونا ساز توسط آن پردازنده بودند ممکن است شرایط EP بودن را از دست دهند. UpdateTaskLists وظایفی که به علت افزایش یافتن زمان آمادگی پردازنده شرایط EP را از دست می دهند، به لیست وظایف نوع non-EP انتقال می دهند. وظایف بر اساس LMT شان بررسی می شوند. در نهایت اگر وظیفه نوع EP برای آن پردازنده وجود نداشته باشد ، پردازنده از لیست پردازنده های فعال خارج می شود.

 

تابع UpdateProcLists لیست پردازنده های فعال را بروز رسانی می کند. اگر وظیفه ای از نوع EP برای پردازنده وجود نداشته باشد، از لیست لیست پردازنده های فعال باید خارج شود. اگر هنوز وظیفه ای از نوع EP برای پردازنده وجود داشته باشد، اولویت پردازنده باید محاسبه شده و بر اساس اولویت بدست آمده لیست پردازنده های فعال بروز شود.بنابر این اولویت پردازنده ها ولیست پردازنده های فعال باید به روز شود س لیست پردازنده های عمومی نیز بید به روز شود زیرا پردازنده جاری تغییر کرده ودر آن زمان بیکار شده است.

 

تابع UpdateReadyTasks وظایفی را که از طریق زمانبندی وظیفه جاری آماده می شوند را به لیست وظایف آماده وابسته به نوع EP یا non-EP اضافه می کند. به علاوه اگر وظیفه از نوع EP باشد پردازنده تواناسازش فعال شده و به لیست پردازنده های فعال اضافه می شود. در صورتی که پردازنده در لیست پردازنده های فعال باشد و اولویتش تغییر کند، لیست پردازنده های فعال باید بروز شود.

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

برای محاسبه اولویت وظایف، همه وظایف و ارتباطات باید یکبار ارائه شوند. پس پیچیدگی زمانی محاسبه اولویت وظایف O(E + V) می شود.

زمانبندی یک وظیفه شامل مقایسه بین دو عمل زمانبندی وظیفه است که بر اساس زمانهای شروع تخمین زده شده برای آنها است. محاسبه زمانهای شروع تخمینی که پیچیدگی زمانی آن O(1) است که شامل محاسبه ماکزیمم زمان ورود پیام موثر روی آن پردازنده و زمان آمادگی پردازنده است. این عمل در هنگام تصمیم گیری برای هر زمانبندی وظیفه انجام می شود و از آنجایی که V وظیفه وجود دارد پیچیدگی زمانی زمانبندی وظایف برابر O(V) می شود.

اعمال لیستهای وظیفه، افزودن و حذف کردن وظایف از لیستهای مرتب شده است. هر وظیفه حداکثر یکبار به لیست وظایف نوع EP اضافه و حذف می شود و حداکثر یکبار به وظایف نوع non-EP اضافه و حذف می شود. از آنجای که حداکثر W وظیفه آماده در هر لحظه می تواند وجود داشته باشد یک عمل لیست پیچیدگی زمانی O(log W) دارد. در هنگامی که V وظیفه وجود دارد پیچیدگی زمانی نگهداری لیست O(V log W) می شود.

در هر تکرار زمانبندی، لیست پردازنده های سراسری تغییر می کند، زیرا زمان آمادگی پردازنده برای پردازنده مقصد تغییر می کند. در نتیجه، یک عمل پیچیدگی زمانی O(log P) ایجاد کرده که پیچیدگی زمانی نگهداری لیست پردازنده های سراسری O(V log P) است.

بعد از هر زمانبندی، یک وظیفه می تواند وضعیت فعال یا غیر فعال بودن یک پردازنده یا اولویتش را در لیست پردازنده های فعال تغییر دهد که پیچیدگی کل مورد نیاز برای نگهداری لیست پردازنده های فعال O(V logP) می شود.

هزینه یافتن وظایف آماده، از آنجایی که همه وظایف و یالها باید پیمایش شود دارای پیچیدگی O(E+V) است.

در نتیجه پیچیدگی زمانی کل الگوریتم FLB ، O(V(log(W)+log(P))+E) می شود.

بررسی یک مثال :

 

     شکل 4-1گراف کار                                               اجرای الگوریتم       

اثر اجرای الگوریتم در جدول نشان داده شده است. دو ستون اول در جدول، لیست وظایف نوع EP تواناساز توسط p0 و p1 را مشخص می کند. در این ستونها وظایف بر اساس EMT و در صورت برابری EMT شان بر اساس پارامترهای LMT و EMT و Blevel مرتب می شوند. سومین ستون در جدول، وظایف نوع non-EP را بر اساس LMT به صورت مرتب لیست می کند. آخرین ستون جدول، زمانبندی را در هر تکرار نشان می دهد که شامل زمان شروع و زمان پایان وظیفه می باشد.

در ابتدا تنها یک وظیفه آماده به نام t0 وجود دارد. از آنجایی که پردازنده تواناسازی وجود ندارد t0از نوع non-EP است. وظیفه به پردازنده p0 به صورت تصادفی نسبت داده می شود زیرا بار کاری همه پردازنده ها صفر است.

بعد از زمانبندی t0 سه وظیفه t1 و t2 و t3آماده زمانبندی می شوند. در این حالت دیگر وظیفه ای از نوع non-EP وجود نخواهد داشت و هر دو وظیفه از نوع EP می باشند. در این مرحله تنها پردازنده ای که از نوع فعال محسوب می شود پردازنده p0 است که وظیفه t0 به آن زمانبندی شده است. از آنجایی که پارامتر EMT هر دو برابر است از پارامتر دوم Blevel بالاتر برای اولویت دهی آنها استفاده می شود. وظیفه t3 که دارای اولویت بالاتری است برای زمانبندی انتخاب شده و به پردازنده تواناسازش که p0 است نسبت داده می شود.

بعد از زمانبندی t3، از آنجاییکه  بزرگتر از  می شود این وظیفه از لیست پردازنده تواناساز p0 خارج شده و به لیست وظایف non-EP اضافه می شود.کار آماده t2هنوز شرایط EP را دارد.دو زوج پردازنده- کار p0- t2 و p1-t1 برای تکرار زمانبندی بعدی مقایسه می شوند.

p1-t1انتخاب می شود به دلیل  کمتر از  است. مراحل دیگر نیز به همین ترتیب طی شده تا تمامی وظایف زمانبندی شوند.

 

 4-5 کارایی

  Mcp ,ETFزمانبندی اجرای خوبی را دارند.که تفاوت آنها در اجرای مسائلریز شده است که تصمیم زمانبندی را حساس تر می کنند. برای مسائل ریز شده زمانبند  mcp ٬ 23% بهتر و زمانبند     5%   ETF       بهتر عمل می کند.        DSC-LLBروش چند مر حله ای است که در صورتی که کمترین پیچیدگی را فراهم کند  روش قابل قبولی است و اجرای زمانبندی آن در مقایسه با MCP,ETF   خیلی بدتر نیست و عموما طول زمانبندی آن 20% بیشتر از طول زمانبندی  ,ETF mcp  نیست اگر چه در بعضی نمونه ها می تواند تفاوت بیشتری وجود داشته باشد. همچنین مواردی وجود دارد که اجرایDSC-LLB    در مقایسه با یک الگوریتم زمانبندی لیست بهتر عمل می کند.

FCP   هر دو ویژگی هزینه پایین و اجرای خوب را داردو اجرای قابل مقایسه ای با  MCP را فراهم می کند  زیرا آن در شرایط زمانبندی یکسان به عنوان MCP است اما از یک روش موثر تر استفاده می کند.

مقایسه با ETF اگر چه تفاوت FCP,ETF بیشتر قابل توجه است تا تفاوت بین FCP,MCP .

FLB  نسبت به DSC_LLB اجرای بهتری را فراهم می کند و FLB دو مزیت هزینه کم و اجرای خوب را دارد.علی رغم اینکه معیار انتخاب کار یکسانی را ETF,FLB دارند FLB  بهتر عمل می کند به علت اینکه در شکستن گره ها معیار کار متفاوتی را دارند.ETF از اولویت کاری محاسبه شده به صورت ایستا استفاده می کندو FLB از زمان رسیدن پیام برای اولویت کارها استفاده می کند و اگر یکسان باشد از blevel استفاده می کند.اگر کارهای زیادی بازمان شروع یکسان وجود داشته باشد  بیشترین اولویت انتخاب می شود همانطور که اگر اولویت کارها متفاوت باشند ETF,FLB ممکن است یک جفت کار- پردازنده مختلف را برای زمانبندی شدن انتخاب کنند.

FLB اجرای بهتری را دارد چون نقشه اولویت آن پویاست و بنابراین دقت وصحت آن نیز بیشتر است .در جاهایی که اتصالات  کارها بیشتر باشد کارایی FLB در مقایسه با MCP پایین تر است و دلیل آن است که FLB مانندETF به ارتباطات بعدی توجه ندارد  و FLB کارایی بهتری را نسبت به DSC_LLB  دارد. 

 

 

 

     

 

 

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

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

 اساس سیستم های توزیع شده روی مجموعه ای از روشها و ابزارهاست.در یک سیستم توزیع شد وسیع پارامتر های زیادی باید بررسی شوند.تعامل بین منابع پیچیده است وهمین تلاش برای ایجاد مدل های تحلیلی را نشدنی می سازد.این کار به ساختن ابزار سطح بالا نیاز دارد.شبیه سازها جزء این ابزار هستند.آنها برای آنالیز سیستم های ویژه و نتیجه آنها مورد توجه هستند.شبیه سازها برای مشاهده خصوصیات کلی و جزئی یک سیستم توزیع شده با دقت بالا مفید هستند  . خصوصیت برتر آنها این است که مستقل از بستر هستند و با استفاده از آنها می توانیم یک مدل را از یک سیستم واقعی بسازیم.سپس ما قادر خواهیم بود با آن نتیجه هایی با دقت بالا را تولید کنیم.شبیه سازها تلاش می کنند رفتار گرید های پویا را روی روشهای زمانبندی مختلف  شبیه سازی کنند[38] [37]

شبیه سازان گرید  نگرانی کاربران را در مورد مسائل خارجی که ممکن است به محیط گرید تاثیر بگذارند مرتفع می سازند.[26]

محیط گرید با بکار گرفتن چندین شبیه ساز گرید هم می تواند شبیه سازی شود.

 

   optosim5-1-1-  

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

اساس طراحی آن روی گرید داده است و سعی می کند کمبود شبیه ساز برای گرید داده را جبران کند.شبیه ساز باعث می شود که توپولوژی شبکه را بوسیله برشمردن لینکها ی بین منابع و پهنای باند در دسترس آنها شبیه سازی کنیم.برای بررسی پایداری[27] و رفتار الگوریتم های بر اساس تکرار مناسب است.

SimGrid  2-1-5

با ابن شبیه ساز این امکان وجود دارد که یک توپولوژی دلخواه را برای شبکه های اتصال داخلی شبیه سازی کنیم که با گرید سیم ممکن نیست.به عبارت دیگر با این شبیه ساز می توان یک مدل پلت فرم با دست ساخته شود و این کار برای میزبانهای کمی انجام می شود.اما برای موارد واقعی تر غیر ممکن است.بعلاوه ویژگی های مرسوم برای شبیه سازی زمانی که زمانبندی با یک پرداش انجام می شود را ندارد.[31] [32][33]

     

       Gridsim5-1-3   

یک ابزار شبیه سازی مجزا روی است.این شبیه ساز بوسیله دانشکده علوم کامپیوتر دانشگاه ادین بورگ استرالیا نوشته شده است. مرکز توجه آن روی گرید اقتصادی است که شامل زمانبندی تولیدات و مشتریهایی است که منابع شان را به اشتراک می گذارند.سعی می کند در یک زمان اجرای قابل قبول برنامه ها را در اختیار کاربران قرار دهدکارهابرای زمانبند مستقل تلقی می شوند.بیشتر برای مطالعه زمان-هزینه مجموعه کارها روی گرید نا همگن با ضرب العجل اجرای کار و بودجه محدود استفاده می شود.[34]             

 

 

 

 

 

 طراحی شده با یک چهار چوب توسعه پذیر چند لایه که در شکل زیر نشان داده شده است.که می توان لایه های جدید را به آن اضافه کردوآن را کامل نمود.[17]

 

  شکل 5-2- ساختار           GridSim

 

این ساختار برای پیشرفت و بهبود گرید سیم و کاربرد آن است که در شکل 5-2 نشان داده شده است.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

کارهای انجام شده

برای پیاده سازی الگوریتم flb از زبان جاوا باIDE   netbean  استفاده شده است. به دلیل اینکه این الگوریتم از الگوریتم های زمانبندی گرید در کارهای وابسته می باشد برای پیاده سازی آن ابتدا باید DAG با زبان جاوا پیاده سازی می شد به دلیل اینکه در  Gridsim  دستوراتی  برای پیاده سازی DAG وجود نداشت برای این کار از نسخه دوم پکیج Ptolemy  استفاده شده است. این پکیج  متعلق به دانشگاه برکلی در کالیفرنیا است که از کلاس های مختلفی تشکیل شده که یکی از آنها کلاس Graph می باشد. این کلاس این امکان را به کاربر می دهد تا با استفاده از توابعی  مانند

 addnode, addedge …       DAG را پیاده سازی کند.

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

برای این کار باید با این شبیه ساز User,Gridresource,Gridlet  ساخت .  و سپس باید دستورات مربوط به ارسال کارها به     Gridsim را نوشت و سپس در مرحله بعد می بایست Gridsim  را  آغاز کرد تا کار شبیه سازی محیط گرید را انجام داده و نتیجه را به ما نشان دهد.

نتایج و پیشنهادات

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

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

با توجه به مشکلات موجود در این الگوریتم  می توان در آینده الگوریتم هایی برای بهبود آنها ارا ئه کرد که به مسیر بحرانی و به موازنه بار روی منابع گرید توجه بیشتری داشته باشد.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Refrense

[1]    A. Darte. Two heuristics for task scheduling, laboratoire lip-imag, ecole normale

          superieure de lyon, 69364. 1991.

 

[2]   A. Radulescu and A. J. C. van Gemund. Flb: Fast load balancing for

          distributed-memory machines. In Proc. Int’l Conf. on Parallel Processing, 1999.

 

   [3]   A. R˘adulescu and A. J. C. van Gemund. On the complexity

      of list scheduling algorithms for distributed-memory

      systems. In Proc. ICS, pages 68–75, June 1999.

 

 

[4]   Amstrong, R., Hensgen, D., and Kidd, T. (1998). The relative performance of various

         mapping algorithms is independent of sizable variances in run-time predictions.

        IEEE Heterogeneous Computing Workshop(HCW’98), pages 79–87.

 

[5]    Aubin Jarry, Henri Casanova, and Francine Berman. Dagsim: A simulator for

         dag scheduling algorithms. Technical Report RR2000-46, LIP, 2000.

 

[6]    Beaumont, O., Legrand, A., Marchal, L., and Robert, Y. (2005). Independent and

          divisible tasks scheduling on heterogeneous star-shaped platforms with limited

         memory. Proceedings of the Conference on Parallel,Distributed and Network-

        Based Processing(Euromicro-PDP’05), pages 179–186.

 

[7]  Braun, T., Siegel, H., Beck, N., and Freund, R. (2001). A comparision of eleven static

         heuristics formapping a class of independent tasks onto heterogeneous distributed

         computing systems. Journal of Parallel and Distributed Computing, 61:810–837.

 

 

[8]    Casavant, T. and Kuhl, J. (1988). A taxonomy of scheduling in general-purpose

         distributed computing systems. IEEE Transactions on Software Engineering,

         14(2):141–153.

 

[9]  C.A. Glass, C.N. Potts, and P. Shade. Unrelated parallel machine scheduling

        using local search. Mathematical and Computer Modelling, 20(2):41–52, July

        1994.

 

[10 ]  D.K. Friesen. Tighter bounds for lpt scheduling on uniform processors. SIAM

          Journal on Computing, 16(3):554–560, June 1987.

 

[11]   Eckart Lorenz and the MAGIC collaboration. Status of the 17m diameter magic

        telescope. New Astronomy Reviews, 48(5-6):339–344, April 2004.

 

 

[12]      E.G. Coffman. Computer and Job-Shop Scheduling Theory. Wiley, 1976.

 

[13]     E.G. Coffman and R.L. Graham. Optimal scheduling for two-processor systems.

          Acta Informatica, 1:200–213, 1972.

 

[14]    EGEE Project. http://public.eu-egee.org/.

 

[15]   F. Berman, R.Wolski, H. Casanova,W. Cirne, H. Dail, M. Faerman, S. Figueira,

         J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, S. Spring, A. Su, and

        D. Zagorodnov. Adaptive computing on the grid using apples. IEEE Trans. on

        Parallel and Distributed Systems (TPDS), 14(4):369–382, 2003.

 

 

 

[16]   F.D. Berman, R. Wolski, S. Figueira, J. Schopf, and G. Shao. Applicationlevel

        scheduling on distributed heterogeneous networks. In ACM Press, editor,

       Proceedings of the 1996 ACM/IEEE conference on Supercomputing,, 1996.

 

[17] GridSim (2002). The gridsim project homepage. http://www.gridbus.org/gridsim/.

 

[18]     H. El-Rewini and T.G. Lewis. Scheduling parallel program tasks onto arbitrary

            target machines. Journal of Parallel and Distributed Computing, 9:138–153,

          1990.

 

[19]      Ibarra, O. and Kim, C. (1977). Heuristic algorithms for scheduling independent tasks

           on non-identical processors. Journal of the ACM, 24(2):280–289.

 

[20] I. Foster and C. Kesselman. Globus: A metacomputing infrastructure toolkit.

Intl. J. Supercomputer Application, 11(2):115–128, 1997.

 

 

[21]    I. Foster and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure.

          Morgan Kaufmann, San Francisco, CA, 1998.

 

[22]    I. Foster, J. Geisler, W. Nickless, W. Smith, and S. Tuecke. Software infrastructure

          for the i-way high performance distributed computing experiment. In

          Proc. 5th IEEE Symposium on High Performance Distributed Computing, pages

        562–571, 1997.

 

[23]   J. J. Hwang, Y. C. Chow, F. D. Anger, and C. Y. Lee. Scheduling precedence

         graphs in systems with interprocessor communication times. SIAM Journal on

          Computing, 18(2):244–257, April 1989.

 

[24]   Jing-Chiou Liou and Michael A. Palis. An efficient task clustering heuristic for

         scheduling dags on multiprocessors. In Symposium of Parallel and Distributed

       Processing, 1996.

 

[25]   Manzur Murshed Gippsland, Rajkumar Buyya , “Using the GridSim ToolKit for

         Enabling Grid Computing Education.

 

[26]    M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the

         Theory of NP-Completeness. W.H. Freeman and Company, 1979.

 

[27]      M. Maheswaran and H. J. Siegel. A dynamic matching and scheduling algorithm

          for heterogeneous computing system. In the 7th Heterogeneous Computing

        Workshop(HCW ’98), pages 57–69. IEEE Computer Society Press, March 1998.

 

[28]    N. Tonellotto, Information Science and Technologies Institute Italian National

         Research Council Italy, R. Yahyapour Institute for Robotics Research University of

        Dortmund Germany, “A Proposal for a Generic Grid Scheduling Architecture”.

 

[29]   O. Ibarra and C. Kim. Heuristic algorithms for scheduling independent tasks

         on nonidentical processors. Journal of the ACM, 77(2):280–289, April 1977.

 

[30]   Pam, M. (1988). Software pipelining:an effective scheduling technique for vliw machines.

         In Proceedings of the SIGPLAN’88, pages 318–328.

 

[31 ]   P.C. Fishburn. Interval Orders and Interval Graphs. John Wiley & Sons, 1985.

 

[32]    R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl.

         Math., 17:416–429, 1969.

 

[33]   R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan. Optimization

          and approximation in deterministic sequencing and scheduling: A survey.

        Annals of Discrete Mathematics, (5):287–326, 1979.

 

[34]    S. J. Kim and J. C. Browne. A general approach to mapping of parallel computation

          upon multiprocessor architectures. Proc. Int’l. Conf. on Parallel Processing,

         pages 1–8, 1998.

 

[35]   R. Sethi. Scheduling graphs on two processors. SIAM Journal of Computing,

           5(1):73–82, March 1976.

 

 

[36]     T. Adam, K.M. Chandy, and J.R. Dickson. A comparison of list schedules for

         parallel processing systems. CACM, 17(12):685–690, 1974.

 

 

[37]    T.C. Hu. Parallel sequencing and assembly line problems. Oper. Research,

        19(6):841–848, November 1961

 

[38]   T. Yang and A. Gerasoulis. Dsc: Scheduling parallel tasks on an unbounded

            number of processors. IEEE Transactions on Parallel and Distributed Systems,

          5(9):951–967, September 1994.

 

[39]   W.H. Kohler and K. Steiglitz. Characterization and theoretical comparison of

           branch-and-bound algorithms for permutation problems. Journal of the ACM,

          21(1):140–156, January 1974

 

[40]   Yu-Kwong Kwok and Ishfaq Ahmad. Static scheduling algorithms for allocating

          directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–

         471, 1999.

 

[41]    Eclipse Project, http://www.eclipse.org/eclipse/

 

[42]    FAFNER. http://www.npac.syr.edu/factoring.html.

 

 

 



[1] Global Grid Forum

[2] On Line                                                                                                                                                                                                                                                                                   

[3] Directed Acyclic Graph

[4] Heuristic

[5] Heuristic

[6] List  scheduling

[7] Duplication based

[8] Clustering

[9] Master/Slave

[10] Message Passing

[11] Run Time

[12] Client

[13] First Come First Serve

[14] Minimal Request Job First

[15] Shortest Job First

[16] Throughput

[17] Dedicated

[18] Domain

[19] IP

[20] Check Pointing

[21] Rescheduling

[22] Real Time

[23] Unconstrained FIFO

[24] Hybrid

[25] Opportunistic Load Balancing 

[26] Scalable

[27] Make Span

[28] Utilization

[29] Formal

[30] Schedule

[31] Sender-initiated

[32] Throughput

[33] Negotiating

[34] Just In Time

[35] Grid Information System

[36]Monitoring

[37] Network weather System

[38]  Meta computing  Discovery System

[39] Stochastic

[40] Time-Balancing

[41] Data-Parallel

[42] Historical

[43] Peak

[44] Look   Ahead

[45] Actuator

[46] Rescheduling by Stop and Restart

[47] Rescheduling by  processor swapping

[48] Minimum Execution Time

[49] Minimum Completion Time

[50] Excepted Completion Time

[51] Suffer

[52] Suffrage

[53] Genetic Algorithm

[54] Fitness

[55] Duplicate

[56] Elitism

[57] Cross over

[58] Simulated Annealing

[59] Cooling Rate

[60] Load Balancing

[61] Communication Traffic Minimization

[62] RaNDom

[63] Task Duplication Based

[64] Bounded Number of Processors

[65] Unbounded Number of Clusters

[66] Arbitrary Processor  Network

[67] Bottom level

[68]Top level

[69] As Soon As Possible

[70] Critical Path

[71] As Late As Possible

[72] Slot

[73] Domain sequence

[74] Parallel Time

[75] Free Task

[76] Partial Free Task

[77] Intree

[78] interval ordered

[79] Highest Level First with Estimated Times

[80] Earliest Time First

[81] Insertion Scheduling Heuristic

[82] Fast Load Balancing

[83] Dominant Sequence Clustering

[84] Domain Sequence Length Reduction Warranty

[85] Clustering And Scheduling System II

[86] Dynamic Critical Path

[87] Look Ahead

[88] Modified Critical Path

[89] Mobility  Directed

[90] Task Duplication-based Scheduling

[91] Favorite Predecessor

[92] Heterogeneous Earliest Finish Time

[93] Critical  Path On a Processor

[94] Levelized Min Time

[95] Task Duplication-based scheduling Algorithm for Network

[96] Favorite Processor      

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

دانلود فایل اول

دانلود فایل دوم

سفارش پایان نامه

نقشه