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

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

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

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

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

فهرست مطالب:

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].

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

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

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

پژوهش­های زیادی بر روی ارتباط­ی بین تخمین­هایی که توسط کاربر به سیستم مدیریت منبع می­دهد و زمان واقعی اجرای کارها صورت گرفته می باشد و نشان داده شده که تخمین­هایی که توسط کاربر فراهم می­شوند در اغلب موردها از دقت کافی برخوردار نیستند. دلیل این موضوع را می­توان چنین دانست که در سیستم­های مدیریت منابع محلی، هنگامی که زمان اجرای تخمین زده شده کار به پایان برسد، کار خاتمه می­یابد (فسخ می­گردد)، پس کاربران اصولا زمان اجرای کار را بیش از حد واقعی تخمین می زنند تا از اتمام کامل کار مطمئن باشند. در پژوهش­های مختلفی تأثیر تخمین­های کاربر بر روی کارائی سیستم ارزیابی شده می باشد و نتایج حاکی از آن می باشد که تخمین­های غیرصحیح کاربر باعث کاهش کارائی سیستم می­گردد. به علاوه در مقاله [4] که در سال 2009 ارائه گردید، نویسندگان نشان دادند که سیستم­های مدیریت منابع محلی توانایی کنار آمدن و کنترل حجم زیادی از واگذاریها را ندارند. در مقاله]5[ که در سال 2009 ارائه گردید تاثیر تغییر پذیری مجموعه کاری­ها بر روی سیستم مدیریت منابع محلی مورد مطالعه قرار گرفت و نتایج نشان داد که این تغییر پذیری باعث تصمیمات زمانبندی بدتر می گردد. زمانبندی مجدد سه هدف اساسی را دنبال می­کند: افزایش کارایی زمانبند، کاهش زمان اجرایی و ارائه تحمل خطا. دانلود متن کامل در سایت sabzfile.com

این مطلب رو هم توصیه می کنم بخونین:   دانلود پایان نامه ارشدرشته کامپیوتر:ردیابی اشیا متحرک در شبکه های حسگری بی سیم

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

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

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

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

***ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود می باشد***

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

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

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 77

قیمت : 14700 تومان

 

***

—-

پشتیبانی سایت :       

****         serderehi@gmail.com