بخشی از مقاله
*** اين فايل شامل تعدادي فرمول مي باشد و در سايت قابل نمايش نيست ***
الگوریتم زمانبندی مبتنی بر min-min و max-min در محیط گرید محاسباتی
چکیده - در سال های اخیر به دلیل نیاز شدید به انجام محاسبات سنگین به گرید محاسباتی توجه فراوانی شده است.گریدمحاسباتی، یک محیط وسیع با منابع ناهمگون تحت مدیریتهای مختلف، که زمانبندی در آن با چالشهای زیادی مواجه است، می باشد . در این مقاله الگوریتمی بر ای تخصیص کارهای مستقل گرید، مبتنی بر دو الگوریتم مشهور min-min و max-min ارایه شده است. الگوریتم پیشنهادی از فواید دو الگوریتم بهره گرفته و سعی در بهبود طول زمانبندی آن دارد . با توجه به زمان کامل شدن کارها، یکی از دو الگوریتم پایه را برای اجرا انتخاب می ن ماید. معیار انتخاب الگوریتم، میانگین زمان اجرا در نظر گرفته شده است . الگوریتم پیشنهادی سعی دارد از min-min برای اجرای کارهای کوچک قبل از کارهای بزرگ و از max-min برای اجرای کارهای بزرگ با کمترین تاخیر و ایجاد تعادل بار بیشتر، استفاده کند . درحقیقت هدف از پیشنهاد این الگوریتم، ایجاد تعادل بار بیشتر واجرای موازی کارها و کاهش تاخیر کارهای کوچک و بزرگ می باشد.
کلید واژه- تعادل بار، زمانبندی ، زمان کامل شدن، کارهای مستقل.
- 1 مقدمه
گرید محاسباتی یک ساختار نرم افزاری و سخت افزاری [1] است، که محیطی برای اشتراک گذ اشتن منابع ناهمگون برای حل مسایل علمی و تجاری فراهم می آورد . گرید محاسباتی ، اغلب در کارهای علمی و محاسباتی کاربرد دارد. با توجه به اینکه گرید یک محیط پویا با منابع ناهمگون در یک گستره جغرافیایی وسیع تحت مدیریت سازمانهای مختلف می باشد ، و [2] با وجود طیف وسیع کاربران گرید با نیازمندیهای متفاوت، ارائه الگوریتم های زمانبندی همه منظوره ممکن نیست . در نتیجه محققان مجبور به برتری برخی نیازهای با اهمیت خود، در شرایط متفاوت می شوند. برخی از مهم ترین معیارهای زمانبندی طول زمانبندی، تعادل بار و بهره وری منابع می باشد. از این رو الگوریتم های زمانبندی به گروههای مختلف تقسیم بندی شده اند.
از سویی دیگر زمان بندی به مفهوم تخصیص کارها به گروه منتخبی از منابع که امکان توزیع در حوزه های مختلفی را دارند، می باشد . به گونه ای که باعث تحقق اهداف کاربران گردد . کاربران کارهای خود را به گرید ارسال می کنند و الگوریتم های زمانبندی گرید با اختصاص منابع مناسب به کارها، پاسخ را به کاربران ارسال می کنند و تمام این مسایل از دید کاربران شفاف می باشد، که یکی از مزایای مهم گرید به شمار می آید .
الگوریتم های زمانبندی زیادی برای کاهش زمان اجرای کارها در محیطهای توزیع شده با اهداف گوناگون وجود دارد . الگوریتمهای مربوط به کارهای مستقل و الگوریتمهای کارهای وابسته [3,4]
دو دسته عمده الگوریتم ها می باشند، که هر گروه شامل الگوریتم های زیادی هستند . از جمله الگوریتهایی که برای کارهای مستقل ارایه شده است min-min و max-min است. این دو الگوریتم، با اختصاص کارها به منابعی که زودترین زمان کامل شدن را برای آنها فراهم می کنند و براساس دو معیار متفاوت برای انتخاب کارها، آنها را زمانبندی می کنند. الگوریتم max-min، اولویت اجرا را به کارهای بزرگ می دهد . ابتدا کارهای بزرگ را زمانبندی می کند و سپس کارهای کوچک را به منابع ارسال می نماید . این الگوریتم با اجرای کارهای بزرگتر سبب ایجاد موازی سازی بیشتر کارها می گردد که زمان پاسخ کمتری را منجر خواهد شد . اگر چه زمانی که تعداد کارهای کوچک بیشتر از کارهای بزرگ باشد ، باعث کاهش توان عملیاتی سیستم می گردد.
الگوریتم min-min، با اختصاص کارهای کوچک قبل از کارهای بزرگ سعی در رفع مشکل و افزایش توان عملیاتی را دارد. زمانی که تعداد کارهای کوچک بیشتر است، این الگوریتم کارایی بهتری را نسبت به max-min فراهم می آورد . اگر چه، این الگوریتم با اختصاص کارهای کوچک به منابع با قدرت محاسباتی بالا و تاخیر در اجرای کارهای بزرگ سبب افزایش طول زمانبندی می شود.
2
برای رفع مشکل، این دو الگوریتم می توانند با تشخیص اینکه تعداد کارهای کوچک بیشتر است یا تعداد کارهای بزرگ، در مواقع مناسب اجرا شده ، تا کارایی قابل قبولی را ارایه دهند . در مواقع دیگر نیز با اجرای پی در پی این دو الگوریتم می توانیم تاخیر کارهای کوچک و بزرگ را حداقل سازیم.
با بررسی دو الگوریتم مشهور min-min و max-min و یافتن مزایا و معایب آنها ، سعی در ایجاد بهبود زمانبندی کارها در لگوریتم پیشنهادی شده است.
در ادامه مقاله، به تحقیقات اخیر در این رابطه و آشنایی با الگوریتم هایی در این زمینه پرداخته شده است . در بخش سوم، ارایه الگوریتم پیشنهادی و پایه ریاضی آن قرارداده شده و بخش چهارم تحلیل پیچیدگی الگوریتم و بخش پنجم نتیجه گیری و کارهای آینده، گنجانده شده است .
-2کارهای انجام شده
الگوریتمهای فراوانی برای زمانبندی کارها در محیط گرید وجود دارد که این الگوریتمها در جهت بهبود زمانبندی کارها معرفی شده اند.
یکی از مشهورترین این الگوریتم ها [5,6] min-min می باشد. که کارها را براساس زمان کامل شدنشا ن در لیستی به صورت صعودی مرتب می کند و سپس کار با کوچکترین زمان را به منبعی که این زمان را برایش فراهم نموده است ، اختصاص می دهد و سبب افزایش طول زمانبندی، به دلیل تاخیر کارهای بزرگ می گردد.
الگوریتم [5] max- min شبیه الگوریتم min-min است ، با این تفاوت که کارهای بزرگ را ابتدا به منابع اختصاص می دهد و باعث می شود کارهای کوچک مدت زمان زیادی به تاخیر بیفتند. اگر چه، زمانی که کارهای بزرگ داشته باشیم این الگوریتم نگاشت و تعادل بار و زمان بهتری را فراهم می سازد. الگوریتم Qos guided min-min [5]، کارهایی را که نیاز به پهنای باند بیشتری دارند ، ابتدا زمان بندی می کند . کیفیت سرویس مورد نیاز را فراهم می سازد. اگر پهنای باندکارها یکسان باشد، مشابه min-min عمل می کند و اگر پهنای باند کارها متفاوت باشد، از min-min بهتر عمل می کند.
[7] QoS priority grouping scheduling، به طول زمانبندی و نرخ پذیرش کارها توجه می کند . در مقایسه با الگوریتم های min-min و Qos guided min-min زمان کامل شدن و نرخ پذیرش بهتری حاصل می شود.
الگوریتم [8] Selective ، بر مبنای دو الگوریتم min-min و می باشد. براساس انحراف معیار زمان کارها یکی از آن دو را انتخاب می کند . این الگوریتم از فواید دو الگوریتم مبنا بهره مند است، اما در برخی موارد باعث کاهش تعادل بار و در نتیجه کاهش بهره وری منابع می گردد.
الگوریتم [9] RASA ، بر اساس دو الگوریتم min-min و-max min می باشد. الگوریتم، برای اختصاص کارها به منبع مناسب، از دو الگوریتم پایه به صورت متناوب استفاده می کند . اگر تعداد منابع فرد باشد ابتدا با الگوریتم min-min آغاز می شود . این الگوریتم برای اجرای کارهای کوچک و بزرگ، تاخیر قابل قبولی را دارد که کمتر از دو الگوریتم پایه است. هر چند که، از فواید دو الگوریتم پایه استفاده نمی کند.
الگوریتم [10] LBMM ابتدا Min -min را اجرا می کند و سپس منبعی را که بار زیادی دارد انتخاب می کند و دوباره کارهای آنها را به منابع با بار کم تخصیص می دهد . منابع که بار زیادی دارند را از طریق makespan بالا در زمانبندی با الگوریتم Min -min تشخیص می دهد . با این روش منابعی که بار کمی دارند و یا بیکار هستند دوباره زمانبندی می شوند.
-3 الگوریتم پیشنهادی
با توجه به قابلیتهای الگوریتمهای قبلی ، سعی شده الگوریتم پیشنهادی دارای خصوصیات مفید آنها باشد و اشکالاتشان را نیز مرتفع ساخته باشد، بدون آنکه پیچیدگی زمانی آن تغییر یابد .
در شرایطی که تعداد کارهای بزرگ بیشتر از کارهای کوچک باشد، الگوریتم max-min با توجه به اینکه ابتدا کار بزرگتر را به منبع مناسب تخصیص می دهد، باعث موازی سازی بیشتر در کارها می گردد و سبب می شود طول زمانبندی کاهش یابد . در شرایطی که تعداد کارهای کوچک بیشتر از کارهای بزرگ باشد، الگوریتم min- min با تخصیص کارهای کوچک قبل از کارهای بزرگ، منجر به توان عملیاتی بالاتر و کاهش تاخیر اجرای کارهای کوچکتر می گردد، در نتیجه کارایی بهتری را ارایه می کند. در شرایطی که کاری در لیست نباشد که جهش قابل ملاحظه ای داشته باشد، برای بوجود آمدن کمترین تاخیر در اجرای کارها، از اجرای تناوبی کارهای کوچک و بزرگ بوسیله اجرای تناوبی الگوریتم های min-min و max-min استفاده شده است.
در نتیجه، برای یافتن راهکاری که در تشخیص تعداد کارها موثر واقع شود، از مفاهیم ریاضی بهره گرفته شده است .
1-3 اساس ریاضی: میانگین حسابی یکی از شاخصهای مرکزی است که به تمام داده ها وابسته می باشد و از فرمول زیر بدست می آید:
مجموع فاصله داده ها از میانگین، برابر صفر می باشد . یعنی میانگین همواره در مکانی قرار دارد که مجموع فواصل داده های بزرگتر از میانگین، برابر قرینه مجموع فواصل داده های کوچکتر از میانگین خواهد بود . بنابراین، باتغییر داده ها (بزرگتر یا کوچکتر شدن داده ها ) مکان میانگین نیز به گونه ای تغییر می کند تا مجموع فاصله داده ها از میانگین برابر صفر شود. به طور مثال، در لیست مرتبی با تعداد داده مشخص، اگر داده ای به انتهای آن اضافه شود که فاصله آن از داده قبلی زیاد باشد (داده بزرگی به لیست اضافه گردد )، میانگین به سمت انتهای لیست می رود، که وجود داده بزرگ را نشان می دهد . اگر داده کوچکی به ابتدای لیست اضافه شود که فاصله آن با داده بعدی کم باشد (داده کوچکی به لیست اضافه شود )، میانگین به سمت ابتدای لیست می آید و این نشان می دهد که در ابتدای لیست داده کوچکی قرار دارد . با توجه به این خصوصیت میانگین، می توان تشخیص داد که تعداد کارهای بزرگ در لیست بیش تر از تعداد کارهای کوچک موجود در آن می باشد و بالعکس.
علاوه بر این، به معیار دیگری نیازمندیم تا حرکت میانگین به سمت ابتدا یا انتهای لیست را نشان دهد و برای تعیین مکان میانگین، دقیق باشد . زیرا شرایطی پیش می آید که میانگین بسیار کم از میان داده ها منحرف می شود در صورتی که در لیست داده بزرگ یا کوچکی ممکن است وجود داشته باشد. برای این منظور از میانه استفاده شده است . میانه یکی ازشاخص های مرکزی است، که همواره وسط داده ها را نشان می دهد . یعنی میانه تحت هر شرایط و با تغییر داده ها، به گونه ای جابه جا می شود، که در مرکز داده ها قرار گیرد.
برای لیست صعودی مرتب شده، به صورت زیر بدست می آید : اگر n= 2k باشد
اگر n = 2k- 1 باشد
از میانه، به عنوان شاخصی برای مقایسه با میانگین بهره گرفته شده است. که با توجه به خصوصیت میانه، می توان تشخیص داد آیا میانگین متم ایل به سمت راست یا چپ لیست می باشد . علاوه بر این، به راحتی و بدون انجام محاسبات فراوان بدست می آید. در نتیجه، می تواند معیار مناسبی جهت مقایسه با میانگین در لیست باشد.
2-3 شرح الگوریتم : ابتدا کارها در لیستی به صورت صعودی مرتب شده و میانگین و میانه بر طبق فرمولهای فوق، برای آنها محاسبه می گردد . برای تعیین محل میانگین، میانگین با میانه مقایسه شده و نشان می دهد که تعداد کارهای بزرگ بیشتر است یا تعداد کارهای کوچک بیشتر خواهد بود . پس سه حالت ممکن است پیش بیاید :
(1 اگر میانگین بزرگتر از میانه باشد : آنگاه تعداد کارهای بزرگ کمتر از تعداد کارهای کوچک می باشد و در این صورت از الگوریتم max-min برای تخصیص کاره ا به منبع مناسب استفاده می گردد. در این حالت، کار انتهای لیست برداشته شده
و به منبع مناسب اختصاص داده می شود.
(2 اگر میانگین کوچکتر از میانه باشد : آنگاه تعداد کارهای
کوچک کمتر از تعداد کارهای بزرگ است، که در این حالت از الگوریتم min-min استفاده می گردد. در این صورت، کار ابتدای لیست برداشته شده و به منبعی که این زمان را تامین می کند ، اختصاص می یابد.
(3 اگر میانگین با میانه برابر باشد : آنگاه داده ها به صورت نر مال توزیع شده اند و نیمی از کارها از میانگین کمتر و نیمی از آنها از میانگین بیشتر خواهند بود . پس فواصل داده ها از یکدیگر، به میزان زیادی جهش نداشته است . در این صورت الگوریتم های min-min و max-min به صورت تناوبی بکار گرفته می شود، تا تاخیر کارهای کوچک و بز رگ را تا حد امکان کاهش دهد و سبب ایجاد توازن بار بیشتر گردد .
با اجرای کارهای کوچک و بزرگ به صورت تناوبی، بین اجرای کارهای کوچک و بزرگ تعادلی ایجاد می شود و باعث بهبود طول زمانبندی می گردد.
این کار آنقدر ادامه می یابد تا تمام کارها زمانبندی گردد.
