مقاله —d1232

جدول 4-12 میانگین نتایج درصد بهرهوری از منابع الگوریتم DHLEFT48
فهرست شکلها
عنوان صفحه
شکل‏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.144
شکل 4-2 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.345
شکل 4-3 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.545
شکل 4-4 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.746
شکل 4-5 نتایج درصد بهرهوری از منابع الگوریتم DHLEFT با Fat=0.146
شکل 4-6 نتایج درصد بهرهوری از منابع الگوریتم DHLEFT با Fat=0.347
شکل 4-7 نتایج درصد بهرهوری از منابع الگوریتم DHLEFT با Fat=0.547
شکل 4-8 نتایج درصد بهرهوری از منابع الگوریتم DHLEFT با Fat=0.748

فصل اول
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] و بیشتر الگوریتمهای ارائه شده اکتشافی میباشد.
یک زمانبند گرید پیوسته کارهای ورودی جدید را دریافت میکند، منابع موجود در دسترس را بررسی میکند و منبع مناسب را با توجه به معیارهایی انتخاب میکند. مفاهیم و محدودیتهایی که در این راستا وجود دارند در ادامه توضیح داده میشوند.
کار : یک برنامه کاربردی است که نیاز به قابلیتهای پردازشی متفاوت (مانند تعداد پردازنده، حافظه، زمان لازم و ....) و محدودیتهای متفاوت داشته باشد. که معمولاً با توضیحات بخصوص کار نشان داده میشود.
منبع : منبع یک مولفه محاسباتی است (یک ابزار یا یک سرویس محاسباتی) که کارها در آن زمانبندی، تخصیص و پردازش میشوند. منابع ویژگیهای بخصوص مانند حافظه، نرم افزار و غیره دارند. پارامترهای مختلفی در مورد منابع مطرح میشود مانند سرعت پردازش و بارکاری که در طی زمان تغییر میکند. علاوه بر آن از آنجایی که منابع میتوانند به محیط های مدیریتی مختلف تعلق داشته باشند، سیاستهای مختلفی روی آنها برای دسترسی و استفاده اعمال میگردند.
دلال منبع : یک برنامه نرم افزاری است که از میانافزارها و سرویسها استفاده میکند تا مدیریت منابع، زمانبندی کارها و کنترل را انجام دهد. دلال منبع بین تولید کننده و مصرف کننده قرار میگیرد[7].
سیستم مدیریت منابع : یک برنامه نرم افزاری است که مجموعهای از منابع را مدیریت می‌کند به طوری که کارایی سیستم را بهینه کند[8].
تعریف زمانبندی : نگاشتی از کارها به منابع می باشد. یک مساله ی زمانبندی با
مجموعهای از منابع، مجموعهای از کارها، ملاکی برای بهینه بودن، مشخصات محیط و محدودیتهای دیگر تعریف میشود.
سطوح مختلفی برای زمانبندها وجود دارند که عبارتند از زمانبند گرید، زمانبند خوشه و زمانبند محلی. در ادامه توضیح مختصری در مورد آنها آورده شده است.
زمانبندی گرید : یک زمانبند پیشرفته است که با توجه به پویا بودن محیط گرید، هدف آن نگاشت کار به منابع در محیط گرید با اهداف خاص میباشد.
زمانبندی در گرید را میتوان بر مبنای معیارهای مختلفی نظیر کارآیی یا مقیاس پذیری در ساختارهای مختلفی سازماندهی کرد. براساس یک تقسیمبندی کلی سه مدل زمانبندی متمرکز، سلسه مراتبی و توزیع شده وجود دارد[9]:
2-2 ساختار متمرکز

شکل STYLEREF 1 \s ‏21 معماری زمانبندی متمرکز [10]
در مدل متمرکز (شکل 2-1) تمام ماشین های موازی توسط یک زمانبند مرکزی زمانبندی می شوند. اطلاعات وضعیت سیستم های موجود باید توسط زمانبند جمع آوری شود. این مدل با افزایش اندازه گرید محاسباتی مقیاس پذیر نیست و ممکن است منشا تنگنا در بعضی از موارد شود (اگر خطاهای شبکه باعث جدایی زمانبند از منابع شود، دسترسی و عملکرد سیستم تحت تاثیر قرار می گیرد) از مزایای این روش زمانبندی کارایی زیاد آن است، زیرا زمانبند مرکزی تمام اطلاعات منابع موجود را دارد.
در این سناریو کارها به زمانبند مرکزی ارسال میشوند و کارهایی که نمیتوانند به سرعت انجام شوند، بعد از واگذاری در صف کار مرکزی ذخیره میشوند.
این نمونه زمانبندی برای زیر ساختهای گرید سازمانی مناسب میباشد. گرید سازمانی امکان به اشتراک گذاری منابع گوناگون را به منظور بهبود همکاری داخلی و دستیابی به بازدهی بهتر از سرمایه های فناوری اطلاعات، مهیا میسازد. در نتیجه با استفاده از فناوری گرید بهره برداری از منابع موجود در یک شرکت بهتر میشود و سربار اداری کاهش مییابد.

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

شکل STYLEREF 1 \s ‏22 معماری زمانبندی سلسله مراتبی [10]

(الف) (ب)
شکل STYLEREF 1 \s ‏23 معماری زمانبندی غیرمتمرکز[10].
نمونه ای از محیط های محاسباتی ناهمگن محیط گرید میباشد. در این فصل فرایند زمانبندی و انواع سطوح زمانبندی در گرید شرح داده می شود.
2-4 فرایند زمانبندی گرید و اجزای آن
فرایند زمانبندی از سه بخش تشکیل شده است: کشف و پالایش کردن منابع، انتخاب منبع و زمانبندی بر اساس هدف های خاص و واگذاری کار[11]. REF _Ref331595962 \h \* MERGEFORMAT شکل ‏24 مدلی از سیستم های زمانبندی گرید را نشان می دهد.

شکل STYLEREF 1 \s ‏24 معماری زمانبندی گرید [11]همان طور که در شکل 2-4 دیده می شود اجزای اصلی از طریق دو نوع جریان داده با یکدیگر در ارتباط هستند: جریان اطلاعات منبع یا برنامه کاربردی و جریان فرمان زمانبندی کار. در این نوع معماری دو سطح زمانبندی دیده می شود: زمانبند گرید (فرازمانبند) و مدیریت منابع محلی.
به طور کلی، یک زمانبند گرید کار (ها) و مشخصات آن را از کاربران دریافت کرده، منابع مناسب برای اجرای کار را بر اساس اطلاعات به دست آمده از ماژول سرویس اطلاعات گرید (GIS) انتخاب و کار را بر اساس تابع هدف مورد نظر و کارایی پیش بینی شده منبع، به منبع انتخابی نگاشت می کند. اطلاعات مربوط به منابع در دسترس به ویژه در محیط های ناهمگن و پویا به منظور زمانبندی مناسب برای زمانبند گرید بسیار مهم هستند. وظیفه GIS جمع آوری و پیش بینی اطلاعات وضعیت منابع، از جمله ظرفیت های پردازنده ها، اندازه حافظه، پهنای باند، نرم افزار های در دسترس، و بار گره در یک دوره مشخص، می باشد. سیستم کشف و نظارت Globus [12] نمونه ای از GIS می باشد. نگاشت کار به منبع مورد نظر بر اساس معیارهای متفاوتی از جمله زمان تکمیل کار، هزینه اجرای کار، بهره وری بهینه از منابع و ... صورت می گیرد که تابع هدف را مشخص می کند.
2-5 انواع زمانبند
تقسیم بندی زمانبندها به شرح زیر است ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app="EN" db-id="9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp">6</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys--s</secondary-title></titles><periodical><full-title>Future generation computer sys--s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[13]:
زمانبند گرید: یکی از اجزای نرمافزاری است که مسئولیت محاسبهی یک نگاشت از کارها به منابع گرید تحت ملاکهای مختلف و تنظیمات محیط گرید را دارد. سطوح مختلفی در درون زمانبند گرید در مقایسههای مختلف ادبیات محاسبات گرید در نظر گرفته شده است که شامل ابرزمانبند، فرازمانبند، زمانبند محلی و زمانبند کسب و کار میباشد. به عنوان یک جزء اصلی از گرید، زمانبند گرید با اجزاء دیگر گرید، از قبیل سیستم اطلاعات گرید، سیستم مدیریت منبع محلی و سیستم مدیریت شبکه در تعامل است. همچنین باید این نکته را در نظر گرفت که در محیط گرید، انواع زمانبندها باید در کنار یکدیگر همزیستی داشته باشند. حتی ممکن است که آنها دارای هدفهای مختلفی باشند، اما باید برای اجرای کارها با یکدیگر در تعامل باشند.
ابرزمانبند: این نوع از زمانبند مربوط روش متمرکز در زمانبندی است که در آن، زمانبندهای محلی برای رزرو و انتساب کار به منابع استفاده میشوند. زمانبندهای محلی پردازش صف کار را مدیریت میکنند. ابر زمانبند بیشتر برای مدیریت رزرو، مذاکره و توافقات سطح سرویس استفاده میشود. همچنین کارها به طور کامل در منابع منحصر به فرد به اتمام میرسند.
فرازمانبند: این زمانبند در مواقعی که یک کار تک، به بیشتر از یک منبع در سیستم های مختلف انتساب داده میشود، استفاده می شود. به عنوان حالتی از ابرزمانبند، فرازمانبند از زمانبندهای محلی برای سیستمهای خاصی استفاده میکند. بنابراین، فرازمانبند، زمانبندهای محلی را برای محاسبهی زمانبندی کلی هماهنگ میکند. اعمال توازن بار در میان سیستمهای مختلف هدف اصلی این زمانبند میباشد.
زمانبند محلی: این زمانبند برای انتساب کارها به یک منبع استفاده میشود و به عنوان یک زمانبند "نزدیک به منبع" شناخته میشود.
زمانبند کسب وکار: این زمانبند در کسب و کارهای بزرگ که در آن منابع محاسباتی در حوزههای مختلفی توزیع شدهاند، استفاده میشود. همچنین از زمانبندهای محلی مختلف که به حوزهی یکسانی تعلق دارند استفاده میکند.
2-6 انواع کارها
کارهای ارجاعی به محیط گرید به دو دسته تقسیم میشود ADDIN EN.CITE <EndNote><Cite><Author>Xhafa</Author><Year>2010</Year><RecNum>6</RecNum><DisplayText>[8]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app="EN" db-id="9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp">6</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Xhafa, Fatos</author><author>Abraham, Ajith</author></authors></contributors><titles><title>Computational models and heuristic methods for Grid scheduling problems</title><secondary-title>Future generation computer sys--s</secondary-title></titles><periodical><full-title>Future generation computer sys--s</full-title></periodical><pages>608-621</pages><volume>26</volume><number>4</number><dates><year>2010</year></dates><isbn>0167-739X</isbn><urls></urls></record></Cite></EndNote>[13[:
کارهای مستقل: مابین این نوع کارها وابستگی داده ای و همچنین تقدم اولویت وجود ندارد. و اجرای هر کار مجزا از بقیه کارها می باشد.
کارهای جریان کاری: مابین این نوع کارها وابستگی داده ای وجود دارد به عبارتی شروع اجرا کار وابسته به اتمام یک یا بیشتر کارهای پیشنیاز میباشد این نوع کارها را توسط گرافهای جهتدار بدون دور نمایش داده می شود که یال های وارد شده به هر گره نشان دهنده تعداد کارهای پیشنیاز می باشد و تا زمانی که کلیه کارهای پیشنیاز اجرا نشده است آن کار قادر به اجرا نمی باشد. شکل 2-5 نمونهای از جریان کارها می باشد. این هماهنگی در

شکل 2-5 جریان کار

ترتیب اجرا کارها و با توجه به خطاهای قابل رخداد در محیط گرید اعمال زمانبندی مجدد الزامی می باشد چرا که در صورت اضافه شده منابع و عدم بهره وری از آن ها، باعث ایجاد تاخیر در اجرا کارهای پیشنیاز می شود و در نتیجه کارایی زمانبند کاهش می یابد ADDIN EN.CITE <EndNote><Cite><Author>Yu</Author><Year>2005</Year><RecNum>9</RecNum><DisplayText>[11, 12]</DisplayText><record><rec-number>9</rec-number><foreign-keys><key app="EN" db-id="9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp">9</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Yu, Jia</author><author>Buyya, Rajkumar</author></authors></contributors><titles><title>A taxonomy of workflow management sys--s for grid computing</title><secondary-title>Journal of Grid Computing</secondary-title></titles><periodical><full-title>Journal of Grid Computing</full-title></periodical><pages>171-200</pages><volume>3</volume><number>3-4</number><dates><year>2005</year></dates><isbn>1570-7873</isbn><urls></urls></record></Cite><Cite><Author>Cao</Author><Year>2003</Year><RecNum>8</RecNum><record><rec-number>8</rec-number><foreign-keys><key app="EN" db-id="9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp">8</key></foreign-keys><ref-type name="Conference Paper">47</ref-type><contributors><authors><author>Cao, Junwei</author><author>Jarvis, Stephen A</author><author>Saini, Subhash</author><author>Nudd, Graham R</author></authors></contributors><titles><title>Gridflow: Workflow management for grid computing</title><secondary-title>3rd IEEE/ACM International Symposium on Cluster Computing and the Grid</secondary-title></titles><pages>198-205</pages><dates><year>2003</year></dates><pub-location>Tokyo, Japan</pub-location><publisher>IEEE</publisher><isbn>0769519199</isbn><urls></urls></record></Cite></EndNote>[14, 15]. گذشته از کارائی، در یک جریان کار، مقاومت در برابر خطا نیز باید در نظر گرفته شود. مطمئنا اگر یک جریان کار گرید برای یک دورهی زمانی زیاد اجرا شود، احتمال خطا در فرایند را افزایش میدهد. در نتیجه باعث خطا در کل جریان کار می شود. بنابراین در چنین مواردی باید حتما از زمانبندی مجدد جهت رفع خطا و همچنین قطعیت در اجرا کارها استفاده گردد.
2-7 نحوهی زمانبندی (ایستا و پویا)
ایستا: در این حالت اطلاعات کامل منابع و کارها، هنگامی که زمانبندی انجام میشود در دسترس است (کارها به صورت دستهای میباشند). یکی از مزایای زمانبندی ایستا برنامهی ساده آن از دید زمانبندها میباشد. در زمان شروع تمام منابع و کارها جهت پردازش در دسترس میباشند. زمان مورد انتظار پردازش برای هر کار روی هر منبع، در ماتریس ETC قرار دارد. ماتریس ETC یک ماتریس n*m میباشد که n تعداد کارها و m تعداد ماشینها میباشد. شکل 2-6 یک نمونه از ماتریس ETC را نشان میدهد.
کار اول کار دوم کار سوم کار چهارم
منبع اول 10 5 2 7
منبع دوم 6 3 5 4
منبع سوم 9 4 8 6
شکل STYLEREF 1 \s ‏26 نمونه ماتریس ETCپویا: در زمانبندی پویا تخصیص کارها به صورت برخط انجام میشود و در همان لحظه کار برای اجرا به یک منبع فرستاده میشود. این زمانبندی معمولا زمانی استفاده میشود که تخمین هزینه ی کارها سخت است و یا کارها به صورت برخط فرستاده میشوند ADDIN EN.CITE <EndNote><Cite><Author>ZHANG</Author><Year>2009</Year><RecNum>10</RecNum><DisplayText>[13]</DisplayText><record><rec-number>10</rec-number><foreign-keys><key app="EN" db-id="9dwzd2xdkd5ve9esetpp5axiw2f0pprwsfzp">10</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>ZHANG, Hai-bin</author><author>TANG, Lin-sha</author><author>LIU, Li-xiang</author></authors></contributors><titles><title>Survey of grid scheduling</title><secondary-title>Computer Engineering and Design</secondary-title></titles><periodical><full-title>Computer Engineering and Design</full-title></periodical><pages>026</pages><volume>9</volume><dates><year>2009</year></dates><urls></urls></record></Cite></EndNote>[16[.
2-8 وظایف فرازمانبندفرا زمانبندها در سطح گرید دو نقش اساسی ایفا می کنند: نگاشت (انتساب) کارها به گره های محاسباتی و انتقال کار به منظور بهبود توازن بار بین گره های محاسباتی و کاهش زمان تکمیل کارها.
2-8-1 نگاشت کاردر محیط گرید درخواست اجرای کار کاربران همراه با پارامترهای لازم به فرازمانبند ارسال می شود. فرازمانبند بر اساس تابع هدف الگوریتمی را برای مشخص کردن ماشین مناسب اجرا می کند و گره مناسب را انتخاب می کند. در چنین مواردی اگر اطلاعاتی از گره محاسباتی موجود نباشد از الگوریتم تصادفی (انتخاب ماشین به صورت تصادفی) و چرخشی (ماشین ها یکی پس از دیگری انتخاب می شوند) می توان استفاده کرد، و در صورتی که نظارت بر ماشین های موجود امکان پذیر باشد می توان از الگوریتم های حریصانه بر خط و برون خط استفاده کرد که در این حالت معمولا ماشینی انتخاب می شود که در کمترین زمان، کار را به پایان می رساند. در زیر نمونه ای از الگوریتم های برخط و برون خط آورده شده است.
الگوریتم بر خط
حداقل زمان اجرا : در این مکانیزم کار به ترتیب ورود به ماشینی ارسال می شود که کمترین زمان اجرا را برای کار ایجاد کند. این روش ممکن است باعث طولانی شدن برخی از صف ها و عدم توازن بار در ماشین ها شود.
حداقل زمان اتمام: در این مکانیزم کار به ترتیب ورود به ماشینی ارسال می شود که کمترین زمان تکمیل را برای آن ایجاد کند. در این روش ممکن است ماشینی انتخاب شود که بهترین زمان اجرا را نداشته باشد.
الگوریتم برون خط
کمترین کمترین: این الگوریتم با مجموعه U از کارهای نگاشت نشده شروع می شود. سپس، برای هر کاری عضو مجموعه U مجموعه ای از کمترین زمان تکمیل آن کار بر روی تمام ماشین ها را محاسبه می کند.
M = {min0≤j<µ (ct(ti, mj)), for each ti€U, }
که µ برابر است با تعداد ماشین ها، ti برابر است با کارi ام و mj برابر است با ماشین j ام می باشد و ct(ti, mj) برابر است با زمان اتمام کار iام بر روی ماشین jام می باشد.
در مرحله بعد، کاری که کمترین زمان تکمیل در مجموعه M را دارد، انتخاب شده و به ماشین مورد نظر نگاشت می شود. در پایان کار نگاشت شده از مجموعه U حذف می شود و فرایند گفته شده تا زمانی که تمام کارها نگاشت شود (U خالی شود) ادامه می یابد.بیشترین کمترین: این الگوریتم بسیار شبیه به مکانیزم کمترین کمترین می باشد. الگوریتم بیشترین کمترین هم با مجموعه U حاوی کارهای نگاشت نشده شروع می شود. سپس، برای هر کاری عضو مجموعه U مجموعه ای از کمترین زمان تکمیل آن کار بر روی تمام ماشین ها محاسبه می شود. در مرحله بعد، کاری که بیشترین زمان تکمیل در مجموعه M را دارد، انتخاب شده و به ماشین مورد نظر نگاشت می شود. در پایان کار نگاشت شده از مجموعه U حذف می شود و فرایند گفته شده تا زمانی که تمام کارها نگاشت شود (U خالی شود) ادامه می یابد.
مثالی را فرض کنید که مجموعه U دارای تعداد زیادی کار با زمان اجرای کوچک باشد و یک کار با زمان اجرای بزرگ داشته باشد. با نگاشت کار با زمان اجرا طولانی تر به بهترین ماشین در ابتدای کار، باعث می شود این کار همزمان با کارهای با زمان اجرای کوتاه اجرا شود. در چنین مواردی عملکرد الگوریتم بیشترین کمترین بهتر از کمترین کمترین می باشد زیرا در الگوریتم کمترین کمترین ابتدا کارهای با زمان اجرای کوتاه زمانبندی می شوند.
حق رای: عملکرد این الگوریتم مثل الگوریتم کمترین کمترین میباشد با این تفاوت که علاوه بر کمترین زمان اتمام دومین کمترین زمان اتمام هم برای هر کار محاسبه میشود و اختلاف این دو زمان برای هر کار روی منابع مختلف محاسبه میشود. کاری که دارای بیشترین اختلاف باشد برای زمانبندی انتخاب و به منبعی که کمترین زمان اتمام را داشته اختصاص داده می شود.
علاوه بر این الگوریتم های فوق الگوریتم های اکتشافی و فرا اکتشافی مانند الگوریتم Duplex ،SA، GA، GSA، Tabu search و ... نیز در این زمینه استفاده می شود.
2-9 گذری بر تحقیقات پیشیندر این قسمت شرح کوتاهی از مفاهیم اولیه جریان کارها و همچنین به بررسی چند الگوریتم حریصانه که برای حل مسئله زمانبندی جریان کارها ارائه شده است میپردازیم.
2-9-1 مفاهیم اولیه
فرض کنید نشان دهنده یک مجموعه m تایی از منابع و نشان دهنده یک مجموعه n تایی از کارها که بین آن ها وابستگی وجود دارد می باشد. جهت نمایش وابستگی بین کارها از گراف های جهت دار بدون دور استفاده می کنیم. گره های گراف نشان دهنده کارها و یال های گراف نشان دهنده وابستگی بین کارها (محدودیت اولویت) میباشد. مقادیر هر یال هزینه انتقال داده مورد نیاز این کار می باشد (در صورتی که منبع اجرا کننده مشترک نباشند). بطور مثال فرض کنید از گره 1 به گره 3 یک یال ارتباطی وجود دارد؛ به عبارتی کار 3 وابسته به کار 1 است. حال اگر کار 3 و کار 1 روی دو منبع مختلف زمانبندی شود باید 12 واحد زمانی (هزینه درج شده بر روی یال کار 1 به 3) برای انتقال خروجی کار 1 صرف کنیم. شکل (2-7 و 2-8) نمونه ای از یک جریان کاری و زمان اجرا را نشان می دهد را نشان می دهد.
در جریان کارها گراف با یک گره شروع و به یک گره خاتمه مییابد. برای نمایش یک جریان کار از دو ماتریس ETC و DTTS استفاده می شود. ماتریسETC یک ماتریس n*m است که n تعداد کارها و m تعداد منابع را مشخص میکنند. ETC (i,j) نشان دهنده زمان مورد انتظار پردازش کار i روی ماشین j میباشد. ماتریس DTTS وابستگی دادهای و زمان انتقال داده، بین کارها را نمایش می دهد. که یک ماتریس n*n است. DTTS (i,j) نشان دهنده زمان انتقال داده از کار i به کارj است که اگر این مقدار صفر باشد نشاندهنده عدم وابستگی کار j به i میباشد.
Resource Job
r3 r2 r1 9 16 14 n1
18 19 13 n2
19 13 11 n3
17 8 13 n4
10 13 12 n5
9 16 13 n6
11 15 7 n7
14 11 5 n8
20 12 18 n9
16 7 21 n10
شکل 2-8 جدول زمان اجرایی تخمینی

شکل 2-7 گراف جهت دار بدون دور (DAG)

زمان اتمام کار i، طبق فرمول (1) محاسبه میشود.
(1)
نشان دهنده میزان حجم کار منبع j (زمان آزادی منبع)، قبل از شروع پردازش کار i می باشد (زمانی که کار i بایستی روی منبع j منتظر بماند تا شروع به اجرا کند)؛ نشان دهنده زمانی می باشد که کار i از این زمان به بعد می تواند اجرای خود را شروع نماید. (زمانیکه کار i کلیه داده های مورد نیاز خود را در اختیار دارد. این داده ها توسط کارهائی تولید می شوند که کار i به آنها وابسته است). بطور مثال اگر کار 3 و کار 1 بر روی منبع j زمانبندی شوند و کار 3 نیاز به داده تولید شده توسط کار 1 داشته باشد، برابر با زمان اتمام کار 1است؛ در غیر این صورت زمان انتقال داده از کار 1 به کار 3 نیز، باید به زمان اتمام کار1 اضافه گردد. کلیه کارهایی که آمادگی اجرا دارند (کلیه کارهای پیش نیازشان زمانبندی شده است) درون صف آماده اجرا قرار می گیرند الگوریتم های ارائه شده جهت جریان کارها از بین کارهای موجود در صف، یکی را براساس تابع هدف خود انتخاب و زمانبندی می نماید بعد از زمانبندی کار منتخبی، کلیه فرزندان کار منتخبی به صف کارهای آماده اجرا اضافه می گردند و همین روند ادامه می یابد تا زمانی که دیگر کاری درون صف آماده اجرا وجود نداشته باشد.
2-9-2 الگوریتم ETF ]17[:
این الگوریتم از بین کارهای موجود در صف آماده، کاری را انتخاب می کند که دارای کمترین زمان شروع جهت اجرا باشد در حقیقت این الگوریتم بدنبال مشغول نگهداشتن منابع می باشد و با این کار توازن بار را ایجاد می نماید. این الگوریتم دارای سرعت اجرایی مناسبی می باشد. و از معایب این الگوریتم می توان نادیده گرفتن زمان اتمام آخرین کار، کارایی و سرعت را نام برد.
2-9-3 الگوریتم Myopic ]18[ :
کارها را با ترتیبی که وارد صف کارهای آماده می گردند با همان ترتیب به آنها منابع اختصاص داده می شود انتخاب منبع برای کار مورد نظر بر این اساس است که منبعی که بتواند آن کار را زودتر از مابقی منابع به اتمام برساند در واقع این الگوریتم بصورت FIFO از صف انتخاب می کند این الگوریتم بسیار ساده میباشد ولی زمان اتمام آخرین کار خیلی مطلوب نمیباشد.
2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای و ... ]20-19[:
تمام الگوریتم های ارائه شده جهت کارهای مستقل بر روی کارهای وابستگی دار قابل اعمال می باشد با این تفاوت که این الگوریتم ها از بین کارهای موجود در صف آماده براساس سیاست های خود انتخاب و مطابق با تابع هدف خود به منبع منتخبی ارسال می نماید.
2-9-5 الگوریتم HLEFT ]21[:
این الگوریتم در ابتدا برای تمام کارها یک رتبه محاسبه می نماید و بعد از بین کارهای آماده اجرا کار با بالاترین رتبه را انتخاب و به منبعی که زودترین زمان اتمام را داشته باشد تخصیص می دهد نحوه رتبه دهی این الگوریتم بر این اساس است که در ابتدا رتبه گره پایانی برابر با میانگین زمان اجرایی این گره بروی تمام منابع می باشد و برای مابقی کارها این رتبه برابر با میانگین زمان اجرایی به اضافه بالاترین رتبه فرزند همراه با یال اتصال به آن فرزند می باشد در فصل بعد این الگوریتم بطور مفصل توضیح داده شده است و این الگوریتم بعنوان الگوریتم پایه جهت ارزیابی الگوریتم های جدید می باشد. نسخه جدید همین الگوریتم نیز در سال 2007 ]22[ ارائه شده است در نسخه جدید محیط گرید را بصورت پویا در نظر گرفته و در صورت رخداد رویدادی در منابع گرید با استفاده از زمانبندی مجدد اقدام به بروزسانی نگاشت قبلی خود می نماید. از مزایای این الگوریتم سرعت اجرایی مناسب می باشد و از معایب آن می توان نادیده گرفتن تعداد فرزندان در محاسبه رتبه و درنتیجه تولید زمان اتمام آخرین کار نامطلوب و کارایی و سرعت پایین می باشد.
2-9-6 الگوریتم hybrid ]23[:
این الگوریتم در ابتدا با استفاده از الگوریتم HLEFT به تمام کارها رتبه می دهد و بعد کارها را گروه بندی می نماید. روش گروه بندی این الگوریتم طی 4 مرحله صورت می گیرد.
مرتب سازی لیست کارها به صورت نزولی
ایجاد گروه جدید
انتخاب کار با بالاترین رتبه و قرار دادن آن در گروه تولید شده در صورت عدم وابستگی با سایر کارهای موجود در گروه و حذف کار از لیست
تکرار مرحله 3 در صورت عدم وابستگی در غیر اینصورت رفتن به مرحله 2.
در حقیقت با این کار در هر گروه کارهایی قرار دارد که مابین آنها وابستگی وجود ندارد و این کارها می توانند موازی با هم اجرا شوند بعد از اینکه تمام کارها گروه بندی شدند از گروه اول که دارای کارهایی با بالاترین رتبه می باشد شروع به اختصاص منابع می پردازد کارهای موجود در هر گروه را بصورت نزولی مرتب می نماید و کار با بالاترین رتبه در گروه را به منبعی اختصاص می دهد که دارای کمترین زمان اتمام برای این کار باشد و همین روال ادامه می یابد تا تمام کارها زمانبندی گردند. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای توازن بار بهتری می باشد.
2-9-7 الگوریتم GRASP ]24-25[:
این الگوریتم مرتبا با ساخت یک نگاشت تصادفی از کارهای موجود در صف آماده بر روی منابع موجود و با اعمال جستجوی محلی بر روی این نگاشت سعی در بهبود زمان اتمام کلی جریان کار دارد. در هر مرحله بهترین نگاشت صورت گرفته (نگاشتی که کمترین زمان اتمام جریان کار را دارد) را نگهداری می شود و این تولید نگاشت تصادفی را آنقدر تکرار می کند تا جایی که بهبودی در زمان اتمام کلی ایجاد نگردد. در این الگوریتم بدلیل تولید نگاشت تصادفی بدون توجه به رتبه کارها باعث تولید زمان اتمام آخرین کار بالا و همچنین کارایی و سرعت پایین می باشد زیرا تولید نگاشت نامطلوب میزان بهبود حاصل از جستجوی محلی را نیز کاهش می دهد.
2-9-8 الگوریتم CPOP ]26[:
این الگوریتم مطابق با الگوریتم HLEFT به تمام کارها یک رتبه تخصیص می دهد. رتبه تخصیص داده شده به هر کار از مجموع رتبه تولید شده توسط الگوریتمHLEFT و عقب گردد الگوریتمHLEFT می باشد. عقب گردد الگوریتم HLEFT در واقع بجای انتخاب بزرگترین از بین فرزندان، بزرگترین را از بین والدین گره انتخاب می کند. این الگوریتم می خواهد در واقع به گره هایی که در مسیر بحرانی قرار گرفته اند زودتر منابع تخصیص دهد و با این کار زمان اتمام کلی جریان کار را کاهش دهد. در این الگوریتم از بین کارهای موجود در صف آماده کاری که دارای بالاترین رتبه باشد را انتخاب و به منبع با کمترین زمان اتمام ارسال می نماید. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای زمان اتمام آخرین کار بهتری می باشد.
2-9-9 الگوریتم PETS ]27[:
این الگوریتم دارای 7 مرحله می باشد.
گره شروع در گروه اول
تولید گروه جدید
قرار داده کلیه فرزندان گروه قبل در گروه جدید
رفتن به مرحله دوم درصورت وجود گره بدون گروه
تولید رتبه برای هر کار براساس فرمول (2)
(2) رتبه = میانگین زمان اجرایی + بالاترین رتبه میان والدین + مجموع هزینه انتقال داده به فرزندان
مرتب سازی کارهای موجود در هر گروه بصورت نزولی براساس رتبه
نگاشت کلیه کارها به ترتیب از گروه اول براساس رتبه تا گروه آخر به منبعی که کمترین زمان اتمام را داشته باشد
در واقع با اعمال گروه بندی سعی در موازی سازی اجرای کارهایی که بین آنها وابستگی وجود ندارد می باشد این الگوریتم در اکثر مواقع دارای توازن بار می باشد و از معایب آن می توان عدم توجه به مسیر بحرانی نام برد که باعث تولید زمان اتمام اخرین کار، کارایی و سرعت نامطلوب می شود.
2-9-10 الگوریتم HLEFT با نگاه به جلو ]28[:
این الگوریتم از نحوه رتبه دهی الگوریتم HLEFT استفاده کرده است. در هر مرحله، منبعی را انتخاب می کند که برای فرزندان آن کار، کمترین زمان اتمام را تولید نماید. در واقع یکبار بصورت صوری کار مورد نظر و فرزندانش را بروی تک تک منابع زمانبندی می نماید و منبعی که کمترین زمان اتمام را برای کلیه فرزندان به همراه داشت انتخاب، و آن کار را بر روی منبع منتخبی ارسال می نماید. این الگوریتم دارای نتایج خوبی می باشد در همین مقاله نسخه دیگری نیز ارائه شده است که کار با بالاترین رتبه را انتخاب، و به منبعی تخصیص می دهد که علاوه بر فرزندان خود، برای بالاترین رتبه بعدی و فرزندان او نیز مناسب باشد. زمان اجرایی این نسخه نسبت به نسخه اول خود بیشتر می باشد اما نتایج بهتری را ایجاد می نماید. در این الگوریتم بدلیل نگاه به جلو دارای زمان اتمام آخرین کار، کارایی و سرعت مناسب می باشد.
2-9-11 الگوریتم FTBAR ]29[:
این الگوریتم در هر مرحله از بین کارهایی که در صف آماده قرار گرفته است کاری را انتخاب میکند که دارای بالاترین رتبه باشد. والدین کارهای موجود در صف آماده در زمانی که اجرایشان تمام می شود، داده تولید شده خود را باید برای فرزندان خود ارسال نمایند و این هزینه ارسال به زمان اتمام خود اضافه می گردد در این الگوریتم این هزینه اتمام بعلاوه هزینه انتقال داده تولیدی را در نظر می گیرد و از والدین خود بالاترین هزینه در دسترس قرار گرفتن داده تولیدی را با رتبه حاصل توسط الگوریتم HLEFT جمع می کند و کاری که دارای بالاترین رتبه باشد را، از بین کارهای موجود در صف آماده انتخاب و به منبعی که دارای کمترین زمان اتمام باشد ارسال می نماید. در این الگوریتم بدلیل در نظر نگرفتن تعداد فرزندان در رتبه دارای زمان اتمام آخرین کار، کارایی و سرعت مناسبی نمی باشد. اما نسبت به مابقی الگوریتم ها دارای نتایج بهتری می باشد.
2-9-12 الگوریتم TSB ]30[ :
در این الگوریتم از دو صف استفاده کرده است یک صف برای کارهایی که آمادگی اجرا را دارند و در آن ترتیب جهت اجرا و انتخاب منابع مشخص شده است (RTQ) و صف دیگری که در آن فرزندان کارهای موجود در صف RTQ قرار گرفته است این صف بنام NRTQ می باشد در ابتدای کار صف RTQ خالی و گره شروع در صف NRTQ قرار می گیرد تا زمانی که صف NRTQ خالی نشده است الگوریتم ادامه دارد در هر مرحله گره سر صف NRTQ برداشته می شود و اگر قادر به اجرا باشد (والدین گره تماما در صف RTQ قرار داشته باشد) این گره از صف NRTQ حذف و به آخر صف RTQ اضافه می گردد و تمام فرزندان این گره به آخر صف NRTQ اضافه می گردند این مراحل تا جایی که تمام گرهها در صف RTQ قرار بگیرند ادامه می یابد بعد از این مرحله از ابتدای صف RTQ کارها را به منبعی اختصاص می دهیم که دارای کمترین زمان اتمام باشد و این کار ادامه می یابد تا تمام کارها به منابع نگاشت گردند. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای زمان اتمام آخرین کار بهینه تر می باشد.
2-10 جمع بندی
با توجه به مطالبی که در این فصل مورد بررسی قرار گرفت الگوریتم های HLEFT و HLEFT با نگاه به جلو به ترتیب جهت تولید رتبه کار و انتخاب منبع مناسب که در سالهای 2007 و 2010 ارائه شده است ایده گرفته شده است.
فصل سوم

الگوریتمهای پیشنهادی
3-1 مقدمه
در این فصل الگوریتمهای پیشنهادی برای حل مسئله زمانبندی و زمانبندی مجدد را بیان میکنیم. برای حل مسئله زمانبندی 3 راهکار را پیشنهاد میدهیم که 2 مورد مربوط به زمانبندی کارهای مستقل و محیط ایستا و 1 مورد مربوط به جریان کارها و محیط پویا گرید همراه با زمانبندی مجدد میباشند. در ادامه به بررسی جزئیان این روشها میپردازیم.
در الگوریتمهای پیشنهادی، کاهش زمان اتمام آخرین کار و اجرای قطعی کارها و توازن بار از مهمترین معیارهای در نظر گرفته شده است. محیط در نظر گرفته شده با مسائلی از جمله نادقیق بودن زمان تخمینی کار و پویایی منابع روبرو می باشد.
سه روش برای رسیدن به این اهداف پیشنهاد شده است که در ادامه به طور مفصل شرح داده می شوند. در الگوریتم Asuffrage و MaxSuffrage منابع اختصاصی و زمان اجرای تخمینی دقیق در نظر گرفته شده است. و در الگوریتم DHLEFT منابع پویا و نادقیق بودن زمان اجرایی تخمینی در نظر گرفته شده است.
فرض کنید T ={ t1, t2,…, tn} نشان دهنده یک مجموعه n تایی از کارهای مستقل از یکدیگر و M ={ m1, m2,…, mm} نشان دهنده یک مجموعه m تایی از منابع در محیط گرید محاسباتی میباشد.
زمان اتمام کار i، طبق فرمول (3) محاسبه می شود
(3)
ETC (i,j) نشاندهنده زمان مورد انتظار پردازش کار i روی ماشین j میباشد. نشاندهنده میزان حجم کار منبع j ، قبل از شروع پردازش کار i میباشد (زمانی که کار i بایستی روی منبع j منتظر بماند تا شروع به اجرا کند).
جهت ارزیابی کیفیت الگوریتمهای زمانبند معیارهای متفاوتی موجود است که متداول ترین معیارها عبارتند از :
زمان اتمام آخرین کار: محبوب ترین معیار بهینهسازی به حداقل رساندن زمان اتمام آخرین کار میباشد. زمان اتمام آخرین کار طبق فرمول (4) محاسبه میشود.
(4)
نرخ طول زمانبندی(SLR) : برای زمان هایی که جریان کاری بسیار بزرگ است بهتر است زمان اتمام آخرین کار نرمال شود این مقدار طبق فرمول (5) محاسبه می شود.
(5) SLR =Makespan/CPL
CPL نشان دهنده مسیر بحرانی از مبدا به گره مقصد می باشد.
سرعت: این معیار میزان بهبود اجرای ترتیبی جریان داده بر روی اجرای موازی و توزیع شده آن می باشد که طبق فرمول 6 محاسبه می شود.
(6) SpeedUp=Sequential Time/Makespan
Sequential Time نشان دهنده اجرای تمام کارها بروی یک منبع می باشد.
کارایی: این معیار میزان سرعت اجرایی برنامه براساس اجرای موازی را مورد بررسی قرار می دهد هرچه این میزان به 1 نزدیک تر باشد دلیل بر کارایی بالاتر زمانبندی دارد. کارایی یک زمانبند براساس فرمول 7 محاسبه می شود.
(7) Efficiency=(Sequential Time/M)/Makespan
M تعداد منابع موجود می باشد.
بهرهوری منابع (سودمندی منابع): این معیار توازن بار سیستم گرید را نشان میدهد. بهره وری منابع طبق فرمول (8) محاسبه میشود.
(8)
نشان دهنده میزان حجم کار منبع j میباشد.
3-2 الگوریتم Asuffrage
در الگوریتم حق رای هزینه هر کار را براساس اختلاف مابین اولین و دومین کمترین زمان اتمام محاسبه میشود و کار با بالاترین هزینه انتخاب میگردد؛ در واقع الگوریتم حق رای فقط یک مرحله بعد را در انتخاب کار در نظر میگیرد و ضرری را که به واسطه انتخاب نشدن بهترین منبع برای کار متحمل میشویم را معیار ارزیابی قرارداده و با توجه به این فاکتور کارها را به منابع واگذار میکند.
در الگوریتم پیشنهادی (Asuffrage) سعیمی کنیم افق دید خود را گسترش داده و به جای ملاک قراردادن یک مرحله بعد، تعدادی از مراحل را در تصمیم گیری دخیل کنیم. در هر دور به جای زمان اتمام دومین کمترین زمان اتمام، میانگین زمان اتمام را برای کار i روی منابع موجود بدست میآوریم (فرمول (10)) تا بتوانیم بازه تغییرات زمان اتمام را در تصمیمگیری دخالت دهیم. جهت اولویتدهی به کارهایی که سریعتر به مرز میانگین تغییرات خود نزدیک می شوند، تعداد منابعی که زمان اتمامشان کمتر از میانگین زمان اتمام برای کار i میباشد را شمارش مینمائیم (فرمول (12)) و عدد بدست آمده را در اختلاف میانگین زمان اتمام (فرمول (10)) و کمترین زمان اتمام (فرمول (11)) ضرب میکنیم (فرمول (9)) تا اولویت کارهایی که زودتر به مرز میانگین تغییرات میرسند بیشتر شود.
(9)
(10)
(11)
(12)

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *