دانشکده‌ی مهندسی برق و کام
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 19
2-9-3 الگوریتم Myopic 19
2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای 19
2-9-5 الگوریتم HLEFT 20
2-9-6 الگوریتم hybrid 20
2-9-7 الگوریتم GRASP 21
2-9-8 الگوریتم CPOP 21
2-9-9 الگوریتم PETS 22
2-9-10 الگوریتم HLEFT با نگاه به جلو 23
2-9-11 الگوریتم FTBAR 23
2-9-12 الگوریتم TSB 24
2-10 جمع بندی 24
3- الگوریتمهای پیشنهادی 25
3-1 مقدمه 25
3-2 الگوریتم Asuffrage 27
3-3 الگوریتم MaxSuffrage 28
3-4 الگوریتم DHLEFT 30
4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی 34
4-1 مقدمه 34
4-2 محک ارزیابی براون 34
4-3 ارزیابی الگوریتم Asuffrage 36
4-4 ارزیابی الگوریتم MaxSuffrage 38
4-5 ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار 40
4-6 ارزیابی الگوریتم DHLEFT 43
4-7 نتیجه گیری و پیشنهادات برای آینده 49
5- منابع 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
فصل اول
1- مقدمه
1-1 مقدمه
اصطلاح “گرید” در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1]. ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستمهای کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامههای کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزهای به نام محاسبات گرید شده است [1].
از اتصال منابع محاسباتی مانند رایانههای شخصی، ایستگاههای کاری، خوشهها، سرویس دهندهها، ابررایانهها و …، توزیع شده در مناطق مختلف جغرافیایی شبکههای تورین محاسباتی (گرید) پدید آمده است که به عنوان یک سکوی محاسبات برای حل مسائل مقیاس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار میگیرد[2].
یکی از عملیات اصلی تضمین کنندهی کارایی در شبکههای تورین محاسباتی، تخصیص منابع به کارها میباشد. عملیات تخصیص منابع باید مکانیسمهایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای حتمی کارها، افزایش بهرهوری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با توجه به توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامههای کاربردی و محدودیتهای اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete می باشد[3].
در زمانبندی وظایف مستقل، هدف افزایش عملکرد کل سیستم و در زمانبندی وظایف با وابستگی، هدف کاهش زمان اجرا کارها، بدون نقض محدودیت اولویت آنها میباشد. با کم کردن زمان اجرا کارها، باعث افزایش بهرهوری از منابع شده، در نتیجه بهبود در عملکرد کل سیستم را خواهیم داشت.
در دهه گذشته زمانبندی کارها (وظایف با وابستگی و مستقل) درون محیط گرید توجه بسیاری از محققین را به خود جلب کرده است. به دلیل پویایی محیط گرید، عملیات زمانبندی باید مرتبا با بررسی کردن حالت جاری سیستم، اقدام به بروزرسانی زمانبند خود نماید. عملیات بروزرسانی با رخداد رویدادی در گرید به دلیل تخمین نادقیق زمان اجرایی، اضافه یا حذف شدن منابع، رخ می دهد. در واقع هدف اصلی از اعمال زمانبندی مجدد افزایش بهره وری از منابع، اجرای قطعی و کاهش زمان اتمام کارها می باشد به این صورت که در ابتدا براساس وضعیت جاری منابع و کارها زمانبندی صورت می پذیرد و در صورت رخداد رویدادهای فوق زمانبندی مجدد براساس منابع موجود و وضعیت کارهای باقی مانده صورت می پذیرد.
1-2 ضرورت اجرا
پژوهشهای زیادی بر روی رابطهی بین تخمینهایی که توسط کاربر به سیستم مدیریت منبع میدهد و زمان واقعی اجرای کارها صورت گرفته است و نشان داده شده که تخمینهایی که توسط کاربر فراهم میشوند در اغلب موارد از دقت کافی برخوردار نیستند. دلیل این موضوع را میتوان چنین دانست که در سیستمهای مدیریت منابع محلی، هنگامی که زمان اجرای تخمین زده شده کار به پایان برسد، کار خاتمه مییابد (فسخ میشود)، بنابراین کاربران اصولا زمان اجرای کار را بیش از حد واقعی تخمین می زنند تا از اتمام کامل کار مطمئن باشند. در پژوهشهای مختلفی تأثیر تخمینهای کاربر بر روی کارائی سیستم ارزیابی شده است و نتایج حاکی از آن است که تخمینهای غیرصحیح کاربر باعث کاهش کارائی سیستم میشود. علاوه بر این در مقاله [4] که در سال 2009 ارائه شد، نویسندگان نشان دادند که سیستمهای مدیریت منابع محلی توانایی کنار آمدن و کنترل حجم زیادی از واگذاریها را ندارند. در مقاله]5[ که در سال 2009 ارائه شد تاثیر تغییر پذیری مجموعه کاریها بر روی سیستم مدیریت منابع محلی مورد بررسی قرار گرفت و نتایج نشان داد که این تغییر پذیری باعث تصمیمات زمانبندی بدتر می شود. زمانبندی مجدد سه هدف اساسی را دنبال میکند: افزایش کارایی زمانبند، کاهش زمان اجرایی و ارائه تحمل خطا.
زمانبندی در محیط گرید بدلیل پویایی از دو مرحله تشکیل میشود در مرحله اول زمانبند براساس حالت جاری منابع، و زمان اجرایی تخمینی یک نگاشت از کارها روی منابع را بوجود میآورد. در مرحله دوم با رخداد یک رویداد، زمانبند، زمانبندی مجددی را براساس کارها، منابع و وابستگی های موجود بین کارها، صورت میدهد و نگاشت جدیدی را تولید می کند.
1-3 هدف از اجرای پایان نامه
با توجه به اینکه منابع گرید غیر اختصاصی بوده و تخمینهای نادقیق ارائه شده توسط کاربران در عملکرد گرید تاثیر بسزایی دارد زیرا کارهایی که بین آنها وابستگی داده وجود دارد (داده تولید شده توسط این کار، نیاز کار دیگری جهت شروع میباشد) و اگر در اینجا نتوانیم اجرای قطعی کار را تضمین کنیم (بدلیل خرابی منبع) اجرای کارهای پیشرو نیز امکان پذیر نمیباشد همچنین این تخمینهای نادقیق نیز باعث کاهش کارایی گرید میگردد به همین دلیل نیاز به نظارت بر وضعیت منابع و کارها و اعمال نگاشت جدید (زمانبندی مجدد) با رخداد رویدادی در گرید (تغییری در وضعیت منابع و یا زمان اجرایی کار) میباشد.
اهداف زمانبند و زمانبند مجدد گرید افزایش بهرهوری از منابع، کاهش زمان اتمام آخرین کار، افزایش کارایی، قطعیت در اجرای کارها و ایجاد توازن بار میباشد در این پایان نامه نیز سعی در ارائه یک الگوریتم زمانبند مناسب با توجه به همین اهداف داریم.
1-4 مراحل انجام پایان نامه
برای انجام پایان نامه در ابتدا مفاهیم گرید و مکانیزم زمانبندی و زمانبندی مجدد (تخصیص مجدد) موجود در محیط گرید بررسی شدند و بعد از ارزیابی روشهای موجود، روشی که بهتر بوده است انتخاب و بهبود داده شده است.
1-5 ساختار پایان نامه
در فصل دوم مفاهیم اولیه زمانبندی و گذری بر تحقیقات پیشین را مورد بررسی قرار داده و در فصل سوم الگوریتمهای پیشنهادی در ارائه شده است و در فصل چهارم نتایج حاصل از ارزیابی و مقایسه الگوریتم پیشنهادی آورده شده است.
فصل دوم
مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته
2-1 مقدمه
در این فصل ابتدا مفاهیم و محدودیتهایی که در گرید وجود دارد را شرح میدهیم. سپس زمانبندی و انواع آن را بررسی میکنیم. در آخر مروری بر کارهای گذشته داریم.
شبکههای تورین محاسباتی (گرید)، يك فن آوري جديد است كه با استفاده از زيرساختهاي ارتباطي و شبكههاي كامپيوتري و نيز با اتصال منابع محاسباتي ناهمگون در فواصل جغرافیایی مختلف، امكان دسترسي به انواع مختلف منابع را از راه دور ميدهد[6]. امروزه ميتوان با استفاده از این فن آوري، برنامههاي كاربردي بسيار پيچيده و بزرگ را كه به توان پردازشي بسيار بالا و به حجم عظيمي از دادههاي ورودي نياز دارند در شبکههای گرید اجرا كرد.
شبکههای محاسباتی گرید از لحاظ کاربرد، دارای تقسیم بندیهای متفاوتی میباشند و عبارتند از: گرید اطلاعاتی، گرید محاسباتی و . . . که در هر کدام هدف و نحوهی اختصاص منابع به کاربران متفاوت میباشد.
یکی از چالش های اصلی در گرید های محاسباتی نگاشت کارهای درخواستی کاربر به
منابع با توجه به سیاستهای زمانبندی میباشد. زمانبندي، عمل واگذاري برنامههاي كاربردي به منابع محاسباتي به نحوي كه نيازمنديهاي برنامههاي كاربردي مانند: تعداد پردازنده، زمان اجرا و … تامين گردد.
مسئله زمانبندی جزء مسائلNp-complete می باشد[3] و بیشتر الگوریتمهای ارائه شده اکتشافی میباشد.
يك زمانبند گريد پیوسته كارهاي ورودي جديد را دريافت ميكند، منابع موجود در دسترس را بررسی ميكند و منبع مناسب را با توجه به معيارهایي انتخاب ميكند. مفاهیم و محدودیتهایی که در این راستا وجود دارند در ادامه توضیح داده میشوند.
کار : یک برنامه کاربردی است که نياز به قابليتهاي پردازشي متفاوت (مانند تعداد پردازنده، حافظه،

دسته بندی : No category

دیدگاهتان را بنویسید