توضیحات

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 مقاله پیاده سازی الگوریتم FLB دارای 107 صفحه می باشد و دارای تنظیمات و فهرست کامل در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله پیاده سازی الگوریتم FLB  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : توضیحات زیر بخشی از متن اصلی می باشد که بدون قالب و فرمت بندی کپی شده است

بخشی از فهرست مطالب پروژه مقاله پیاده سازی الگوریتم FLB

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

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

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

 3-1 ارزیابی گرید;;;;;;;;;;;;;;;

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

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

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

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

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

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

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

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

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

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

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

  2-3-3  زمانبندی بهینه/نزدیک به بهینه;;;;;;;;;

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

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

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

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

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

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

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

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

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

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

2-4-6  زمانبندی تحت قیود کیفیت سرویس;;;;;;;;

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

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

2 -5-1 الگوریتم   MET   ;;;;;;;;;;;;;;

      2-5-2  الگوریتم  MCT ;;;;;;;;;;;;;;;.32

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

  2-5-4  الگوریتم Max-Min ;;;;;;;;;;;;;;;;

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

2   -5-6-  الگوریتم GA . ;;;;;;;;;;;;;;

2-5-7- الگوریتم        SA. ;;;;;;;;;;;;;;

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

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

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

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

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

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

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

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

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

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

  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 ;;;;;;;;;;;;;;;.56

   3-6-5- الگوریتم FLB;;;;;;;;;;;;;;;;56

   3-6-6- الگوریتم DSC;;;;;;;;;;;;;;;;57

   3-6-7- الگوریتم CASS-II;;;;;;;;;;;;;;;.59

   3-6-8- الگوریتم DCP;;;;;;;;;;;;;;;;60

   3-6-9- الگوریتم MCP;;;;;;;;;;;;;;;;61

   3-6-10- الگوریتم MD;;;;;;;;;;;;;;;..61

   3-6-11- الگوریتم TDS.;;;;;;;;;;;;;;;.62

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

  3-7-1- الگوریتم HEFT;;;;;;;;;;;;;;;;63

  3-7-2- الگوریتم CPOP;;;;;;;;;;;;;;;;..63

  3-7-3- الگوریتم LMT;;;;;;;;;;;;;;;;

  3-7-4- الگوریتمTANH ;;;;;;;;;;;;;;;;.65 

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

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

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

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

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

    4-5 کارایی الگوریتم;;;;;;;;;;;;;

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

    5-1 ابزار شبیه سازی;;;;;;;;;;;..79

        5-1-1- optosim;;;;;;;;;;;;;;;;..

        5-1-2 SimGrid ;;;;;;;;;;;;;;;;..

        5-1-3- Gridsim  ;;;;;;;;;;;;;;;;..

 کارهای انجام شده;;;;;;;;;;;;;;;..82      

   پیشنهادات;;;;;;;;;;;;;;;;;;;;

 منابع     ;;;;;;;;;;;;;;;;;;;;

بخشی از فهرست مطالب پروژه مقاله پیاده سازی الگوریتم FLB

    شکل 1-2 ساختار کلاستر  ;;;;;;;;;;;;..11

    شکل 2-2 ساختار زمانبند گرید ;;;;;;;;;;.

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

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

    شکل 2-5-6کلاس بندی برنامه های کاربردی ;;;;;;;..

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

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

    شکل 3-4 گراف کارها ;;;;;;;;;;;;;..50

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

   شکل 3-5-3 مقایسه الگوریتم های زمانبندی گراف برنامه در محیطهای   همگن ;;;;;;.

    شکل     4-1 گراف کار;;;;;;;;;;;;;;.76

    شکل  5-2 ساختار   Gridsim  ;;;;;;;;;;;;.

چکیده

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

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

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

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

 واژه های کلیدی

گراف جهت دار بدون سیکل ، کارهای وابسته، زمانبندی ،گرید، تکثیر

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

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

Mainfram  معایب

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

هزینه اجرای کار نیز به نگرانی های کاربران اضافه شد

 1 – 3 ارزیابی گرید

   سه مرحله برای ارزیابی گرید وجود دارد اول:تولید سیستم هایی که در اوایل 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- زمان­بندی کلاسترها و ویژگی­های آن

 

برای دریافت اینجا کلیک کنید

سوالات و نظرات شما

برچسب ها

سایت پروژه word, دانلود پروژه word, سایت پروژه, پروژه دات کام,
Copyright © 2014 cpro.ir
 
Clicky