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

دانلود متن کامل پایان نامه مقطع کارشناسی ارشد رشته مهندسی کامپیوتر

گرایش : نرم‌افزار

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

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

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

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

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

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

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

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

اسفند ماه 1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود(در فایل دانلودی نام نویسنده موجود است)تکه هایی از متن پایان نامه به عنوان نمونه :(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)چکیدهشبکه­های تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا می­کند. بدلیل پویایی منابع و تخمین نادقیق زمان اجرایی و ... عملیات زمانبندی باید مکانیسم هایی را برای پشتیبانی از تحمل خطا، افزایش بهره وری از منابع و کاهش زمان اتمام کارها استفاده کند، که به آن زمانبندی مجدد گویند. در این پایان نامه دو الگوریتم زمانبندی کارهای مستقل و یک الگوریتم زمانبندی جریان کارها با در نظر گرفتن پویایی محیط ارائه شده که اهداف آنها کاهش زمان اجرا، افزایش بهره­وری از منابع، ایجاد توازن بار و پشتیبانی از تحمل خطا می باشد. کلید واژه: گرید محاسباتی، زمانبندی، زمانبندی مجدد، جریان کار.  فهرست مطالب  عنوان                                                                                                                صفحه 1- مقدمه ..............................................................................................................................  11-1 مقدمه................................................................................................................................................................... 11-2 ضرورت اجرا....................................................................................................................................................... 21-3 هدف از اجرای پایان نامه ................................................................................................................................. 31-4 مراحل انجام پایان نامه ...................................................................................................................................... 41-5 ساختار پایان نامه ........................................................................................................................................ 42- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته.................................................... 52-1 مقدمه........................................................................................................................................................... 52-2 ساختار متمرکز......................................................................................................................................... 72-3 ساختار غیر متمرکز و یا توزیعی.......................................................................................................... 82-4 فرایند زمانبندی گرید و اجزای آن .................................................................................................... 102-5 انواع زمانبند ............................................................................................................................................. 112-6 انواع کارها ................................................................................................................................................. 122-7 نحوه­ی زمانبندی ..................................................................................................................................... 142-8 وظایف فرازمانبند .................................................................................................................................... 142-8-1 نگاشت کار ...................................................................................................................................... 152-9 گذری بر تحقیقات پیشین .................................................................................................................... 172-9-1 مفاهیم اولیه .................................................................................................................................. 172-9-2 الگوریتم ETF ................................................................................................................................ 192-9-3 الگوریتم Myopic ......................................................................................................................... 192-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای .................................................. 192-9-5 الگوریتم HLEFT ........................................................................................................................ 202-9-6 الگوریتم hybrid ........................................................................................................................... 202-9-7 الگوریتم GRASP ....................................................................................................................... 212-9-8 الگوریتم CPOP ........................................................................................................................... 212-9-9 الگوریتم PETS ............................................................................................................................. 222-9-10 الگوریتم HLEFT با نگاه به جلو .......................................................................................... 232-9-11 الگوریتم FTBAR .................................................................................................................... 232-9-12  الگوریتم TSB .......................................................................................................................... 242-10  جمع بندی .......................................................................................................................................... 243- الگوریتم­های پیشنهادی ............................................................................................ 253-1 مقدمه ......................................................................................................................................................... 253-2 الگوریتم Asuffrage .............................................................................................................................. 273-3 الگوریتم MaxSuffrage ....................................................................................................................... 283-4 الگوریتم DHLEFT................................................................................................................................ 304- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ....................................... 344-1 مقدمه ......................................................................................................................................................... 344-2 محک ارزیابی براون.................................................................................................................................. 344-3 ارزیابی الگوریتم  Asuffrage............................................................................................................... 364-4  ارزیابی الگوریتم  MaxSuffrage....................................................................................................... 384-5  ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار.................................................................... 404-6 ارزیابی الگوریتم DHLEFT.................................................................................................................. 434-7 نتیجه گیری و پیشنهادات برای آینده .............................................................................................. 495- منابع........................................................................................................................... 50     فهرست جدول­ها  عنوان                                                                                                                صفحه جدول 4-1 حالات ماتریس ETC...................................................................................................................... 36جدول 4-2 نتایج زمان اتمام آخرین کار الگوریتم Asuffrage................................................................. 37جدول 4-3 نتایج درصد بهره­وری از منابع الگوریتم Asuffrage.............................................................. 37جدول 4-4 نتایج زمان اتمام آخرین کار الگوریتم MaxSuffrage.......................................................... 39جدول 4-5 نتایج درصد بهره­وری از منابع الگوریتم MaxSuffrage....................................................... 39جدول 4-6 مقادیر پارامتر N............................................................................................................................... 41جدول 4-7 مقادیر پارامتر Fat............................................................................................................................ 41جدول 4-8  مقادیر پارامتر Density................................................................................................................. 41جدول 4-9  درصد خطا در تخمین زمان اجرایی......................................................................................... 42جدول 4-10  زمان رخداد رویداد...................................................................................................................... 43جدول 4-11 میانگین نتایج  زمان اتمام آخرین کار الگوریتم DHLEFT............................................ 48جدول 4-12 میانگین نتایج درصد بهره­وری از منابع الگوریتم DHLEFT........................................... 48   فهرست شکل­ها  عنوان                                                                                                                صفحه شکل‏2-1 معماری زمانبندی متمرکز ............................................................................................................... ....... 7شکل‏2-2 معماری زمانبندی سلسله مراتبی .................................................................................................. ....... 9شکل ‏2-3 معماری زمانبندی غیرمتمرکز ...................................................................................................... ....... 9شکل ‏2-4 معماری زمانبندی گرید .................................................................................................................. 10شکل ‏2-5 جریان کار ........................................................................................................................................... 13شکل ‏2-6 نمونه ماتریس ETC ......................................................................................................................... 14شکل ‏2-7 گراف جهت دار بدون دور(DAG) ............................................................................................... 18شکل ‏2-8 جدول زمان اجرایی تخمینی ......................................................................................................... 18شکل 3-1 شبه کد الگوریتم DHLEFT ........................................................................................................ 33شکل 4-1 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.1.............................................. 44شکل 4-2 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.3.............................................. 45شکل 4-3 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.5.............................................. 45شکل 4-4 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.7.............................................. 46شکل 4-5 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.1........................................... 46شکل 4-6 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.3........................................... 47شکل 4-7 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.5........................................... 47شکل 4-8 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.7........................................... 48مقدمهاصطلاح "گرید" در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1].  ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستم­های کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامه­های کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزه­ای به نام محاسبات گرید شده است [1].از اتصال منابع محاسباتی مانند رایانه­های شخصی، ایستگاه­های کاری، خوشه­ها، سرویس دهنده­ها، ابررایانه­ها و ...، توزیع شده در مناطق مختلف جغرافیایی شبکه­های تورین محاسباتی (گرید) پدید آمده است که به عنوان یک سکوی محاسبات برای حل مسائل مقیاس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار می­گیرد[2].یکی از عملیات اصلی تضمین کننده­ی کارایی در شبکه­های تورین محاسباتی، تخصیص منابع به کارها می­باشد. عملیات تخصیص منابع باید مکانیسم­هایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای حتمی کارها، افزایش بهره­وری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با توجه به توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامه­های کاربردی و محدودیت­های اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete می باشد[3].در زمانبندی وظایف مستقل، هدف افزایش عملکرد کل سیستم و در زمانبندی وظایف با وابستگی، هدف کاهش زمان اجرا کارها، بدون نقض محدودیت اولویت آن­ها می­باشد. با کم کردن زمان اجرا کارها، باعث افزایش بهره­وری از منابع شده، در نتیجه بهبود در عملکرد کل سیستم را خواهیم داشت.در دهه گذشته زمانبندی کارها (وظایف با وابستگی و مستقل) درون محیط گرید توجه بسیاری از محققین را به خود جلب کرده است. به دلیل پویایی محیط گرید، عملیات زمانبندی باید مرتبا با بررسی کردن حالت جاری سیستم، اقدام به بروزرسانی زمانبند خود نماید. عملیات بروزرسانی با رخداد رویدادی در گرید به دلیل تخمین نادقیق زمان اجرایی، اضافه یا حذف شدن منابع، رخ می دهد. در واقع هدف اصلی از اعمال زمانبندی مجدد افزایش بهره وری از منابع، اجرای قطعی و کاهش زمان اتمام کارها می باشد به این صورت که در ابتدا براساس وضعیت جاری منابع و کارها زمانبندی صورت می پذیرد و در صورت رخداد رویدادهای فوق زمانبندی مجدد براساس منابع موجود و وضعیت کارهای باقی مانده صورت می پذیرد.تعداد صفحه : 78قیمت : 14000تومان

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

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت :        09309714541 (فقط پیامک)        info@arshadha.ir

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

--  -- --

مطالب مشابه را هم ببینید

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