دانشگاه شیراز

دانشکده‌ی مهندسی برق و کامپیوتر

پایان‌نامه کارشناسی ارشد در رشته­­

مهندسی کامپیوتر (نرم‌افزار)

عنوان:

بررسی الگوریتم های تخصیص مجدد در گریدهای محاسباتی و ارائه یک الگوریتم کارا

استاد راهنما:

دکتر غلامحسین دستغیبی فرد

برای رعایت حریم خصوصی نام نگارنده درج نمی شود

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

1- مقدمه ………………………………………………………………………………………………………………. 1

1-1 مقدمه…………………………………………………………………………………………………………… 1

1-2 ضرورت اجرا…………………………………………………………………………………………………. 2

1-3 هدف از اجرای پایان ­نامه…………………………………………………………………………………. 3

1-4 مراحل انجام پایان ­نامه…………………………………………………………………………………… 4      

1-5 ساختار پایان­ نامه……………………………………………………………………………………………. 4

2- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته…………………………………………………… 5

2-1 مقدمه………………………………………………………………………………………………………. 5

2-2 ساختار متمرکز……………………………………………………………………………………………… 7

2-3 ساختار غیر متمرکز و یا توزیعی…………………………………………………………………. 8

2-4 فرایند زمانبندی گرید و اجزای آن …………………………………………………………………. 10

2-5 انواع زمانبند ………………………………………………………………………………………….. 11

2-6 انواع کارها ……………………………………………………………………………………………… 12

2-7 نحوه­ی زمانبندی ……………………………………………………………………………………… 14

2-8 وظایف فرازمانبند ……………………………………………………………………………………. 14

2-8-1 نگاشت کار …………………………………………………………………………………………… 15

2-9 گذری بر تحقیقات پیشین …………………………………………………………………………. 17

2-9-1 مفاهیم اولیه …………………………………………………………………………………….. 17

2-9-2 الگوریتم ETF ………………………………………………………………………………………..

2-9-3 الگوریتم Myopic …………………………………………………………………………………

2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای …………………………………. 19

2-9-5 الگوریتم HLEFT ………………………………………………………………………………

2-9-6 الگوریتم hybrid ……………………………………………………………………………….

2-9-7 الگوریتم GRASP …………………………………………………………………………..

2-9-8 الگوریتم CPOP ……………………………………………………………………………..

2-9-9 الگوریتم PETS …………………………………………………………………………..

2-9-10 الگوریتم HLEFT با نگاه به جلو ……………………………………………………….. 23

2-9-11 الگوریتم FTBAR ………………………………………………………………………..

2-9-12 الگوریتم TSB ……………………………………………………………………………..

2-10 جمع بندی ……………………………………………………………………………………… 24

3- الگوریتم­های پیشنهادی ………………………………………………………………………. 25

3-1 مقدمه ……………………………………………………………………………………………… 25

3-2 الگوریتم Asuffrage …………………………………………………………………………

3-3 الگوریتم MaxSuffrage ……………………………………………………………………

3-4 الگوریتم DHLEFT…………………………………………………………………………..

4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ………………….. 34

4-1 مقدمه ……………………………………………………………………………………….. 34

4-2 محک ارزیابی براون………………………………………………………………. 34

4-3 ارزیابی الگوریتم Asuffrage…………………………………………………………..

4-4 ارزیابی الگوریتم MaxSuffrage…………………………………………………..

4-5 ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار…………………………. 40

4-6 ارزیابی الگوریتم DHLEFT…………………………………………………………

4-7 نتیجه گیری و پیشنهادات برای آینده ……………………………………………. 49

5- منابع …………………………………………………………………………………….. 50

چکیده:

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

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

1-1- مقدمه

اصطلاح “گرید” در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1]. ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستم­های کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامه­های کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزه­ای به نام محاسبات گرید شده است [1].

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

یکی از عملیات اصلی تضمین کننده­ی کارایی در شبکه­های تورین محاسباتی، تخصیص منابع به کارها می­باشد. عملیات تخصیص منابع باید مکانیسم­هایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای حتمی کارها، افزایش بهره­وری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با توجه به توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامه­های کاربردی و محدودیت­های اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete می باشد[3].

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 589