زمانبندی کارها در محیطهای ابری با استفاده از چارچوب نگاشت – کاهش و الگوریتم ژنتیک
الموضوعات : جنرال لواءسید نیما خضر 1 , نیما جعفری نویمی پور 2
1 - گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
2 - گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
الکلمات المفتاحية:
ملخص المقالة :
زمانبندی وظایف یک جزء حیاتی هر سیستم توزیعشده همچون گرید، ابر و شبکه های نظیر به نظیر می باشد که وظایف را برای اجرا به منابع مناسب ارجاع می دهد. روش های رایج در زمانبندی دارای معایبی از قبیل پیچیدگی زمانی بالا، همزمان اجرا نشدن کارهای ورودی و افزایش زمان اجرای برنامه است. الگوریتم های زمانبندی بر پایه اکتشاف جهت اولویتدهی به وظایف از سیاست های متفاوتی استفاده می کنند که باعث به وجود آمدن زمان های اجرای بالا بر روی سیستم های رایانش توزیع شده ناهمگن می شود. بنابراین، روشی مناسب است که اولویت دهی آن باعث تولید زمان اجرای کل کمینه گردد. الگوریتم ژنتیک به‌عنوان یکی از روشهای تکاملی به‌منظور بهینه کردن مسائل NP-کامل به کار گرفته می شود. در این مقاله الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای زمانبندی وظایف بر روی رایانش ابری با استفاده از صف های اولویت چندگانه ارائه‌شده است. ایده اصلی این مقاله، استفاده از چارچوب نگاشت-کاهش برای کاهش زمان اجرای کل برنامه می باشد. نتایج آزمایش‌ها بر روی مجموعه ای از گراف های جهت دار بدون دور تصادفی حاکی از آن است که روش پیشنهادی زمان اجرای کل دو روش موجود را با سرعت همگرایی بالا بهبود داده است.
زمانبندی کارها در محیطهای ابری با استفاده از چارچوب نگاشت- کاهش و الگوریتم ژنتیک
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال دهم، شمارههای 37 و 38، پاییز و زمستان 1397 |
|
*سید نیما خضر *نیما جعفری نویمیپور
*کارشناس ارشد، گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
** دانشیار، گروه مهندسی کامپیوتر، واحد تبریز، دانشگاه آزاد اسلامی، تبریز، ایران
تاریخ دریافت: 04/10/1398 تاریخ پذیرش:16/03/1399
چكيده
زمانبندی وظایف یک جزء حیاتی هر سیستم توزیعشده همچون گرید، ابر و شبکههای نظیر به نظیر میباشد که وظایف را برای اجرا به منابع مناسب ارجاع میدهد. روشهای رایج در زمانبندی دارای معایبی از قبیل پیچیدگی زمانی بالا، همزمان اجرا نشدن کارهای ورودی و افزایش زمان اجرای برنامه است. الگوریتمهای زمانبندی بر پایه اکتشاف جهت اولویتدهی به وظایف از
سیاستهای متفاوتی استفاده میکنند که باعث به وجود آمدن زمانهای اجرای بالا بر روی سیستمهای رایانش توزیعشده ناهمگن میشود. بنابراین، روشی مناسب است که اولویتدهی آن باعث تولید زمان اجرای کل کمینه گردد. الگوریتم ژنتیک به‌عنوان یکی از روشهای تکاملی به‌منظور بهینه کردن مسائل NP-کامل1 به کار گرفته میشود. در این مقاله الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای زمانبندی وظایف بر روی رایانش ابری با استفاده از صفهای اولویت چندگانه ارائه‌شده است. ایده اصلی این مقاله، استفاده از چارچوب نگاشت-کاهش برای کاهش زمان اجرای کل برنامه میباشد. نتایج آزمایش‌ها بر روی
مجموعهای از گرافهای جهتدار بدون دور تصادفی حاکی از آن است که روش پیشنهادی زمان اجرای کل دو روش موجود را با سرعت همگرایی بالا بهبود داده است.
نویسندة عهده‌دار مکاتبات: نیما جعفری نویمیپور jafari@iaut.ac.ir |
[1] . NP-Completeness
1- مقدمه
سیستمهای رایانش توزیعشده ناهمگن1 نوعی از سیستمهای رایانش توزیعشده است که وظایف را روی چندین
پردازندههای اجرا میکند [1]. زمانبندی وظایف در محیطهای ابری به مجموعهای از زیر وظایف کوچک‌تر اولویتدار، جهت پردازش تجزیه میشود [2]. این زیروظایف نشاندهنده محدودیت تقدم2 میباشند به این معنی که نتیجه دیگر وظایف قبل از اجرای زیر وظیفه فعلی نیاز است [2]. با تجزیه یک کار رایانش به زیر وظایف و اجرای آنها بر روی چندین پردازنده، زمان اتمام وظیفه میتواند کاهش پیدا کند. بنابراین هدف از این کار، زمانبندی زیروظایف بر روی تعدادی پردازنده در دسترس جهت کاهش زمان اتمام وظایف بدون نقض محدودیتهای تقدم میباشد [3]. توسعه3 الگوریتمهای زمانبندی وظایف که زیروظایف یک برنامه را به پردازندهها تخصیص میدهند، در سیستمهای ابری یک چالش میباشد. باوجود تلاشهای بسیاری که اخیراً در زمینة زمانبندی وظایف صورت گرفته است، همچنان این مسئله در محیطهای رایانش ناهمگن به‌عنوان یکی چالش مهم باقیمانده است [4]. تعدادی از چالشهای مهم زمانبندی وظایف در سیستمهای ابری در زیر آورده شده است:
· ناهمگن بودن منابع
· زمان اجرای الگوریتم4
· زمان اجرای کل5
· سرعت همگرایی6 راهحلها در روشهای تکاملی
· بهرهوری7 الگوریتم زمانبندی
با توجه به افزایش حجم داده‌ها در محیط ابری کاهش زمان اجرای الگوریتم زمانبندی همچنین به‌عنوان یک چالش مهم باقیمانده است. بنابراین الگوریتمهای گوناگونی جهت کاهش زمان اتمام وظایف با موازیسازی زیروظایف و رعایت رابطههای تقدم آنها ارائه‌شده‌اند. معمولاً رابطههای تقدم با گراف جهتدار بدون دور 8نشان داده میشوند که از رأسها که نشاندهنده کارها و یالهای جهتدار نشانگر وابستگی بین کارها میباشد. گرافهای جهتدار بدون دور برای نشان دادن برنامهها با حجم زیاد و مختلف مناسب و گویا است [5]. از طرف دیگر سیستم هادوپ، اجرا وظایف را در یک مرکز داده مشترک را فراهم می کند[18]. نگاشت-کاهش یک ابزار مؤثر در هادوپ برای پردازش دادههای بزرگ در رایانش ابری میباشد که با استفاده از پردازندهها و یا کامپیوترها به‌صورت موازی دستورات و برنامهها را اجرا مینماید [6]. این چهارچوب برنامه نویسی اجازه اجرای پردازش موازی و توزیع شده بروی مجموعه بزرگی از داده‌ها در یک محیط توزیع‌یافته را میدهد [16]. این چارچوب با رویکردها مختلفی ارائه‌شده است و در زمینه‌های مختلف کاربردهای مختلفی دارد ازجمله الگوریتم‌هایی که در دادههای بزرگ دارای پیچیدگی زمانی بالایی است که با بهبود پردازش به‌صورت موازی زمان اجرای الگوریتم را کاهش میدهد [7]. لذا این مقاله به چگونگی، زمانبندی کارهای اولویتدار بر روی گرافهای مستقیم بدون دور بزرگ به کمک الگوریتم ژنتیک و چارچوب نگاشت-کاهش می‌پردازد.
به‌صورت خلاصه اهداف مقاله به‌صورت زیر است:
· استفاده از الگوریتم ژنتیک برای زمانبندی در محیطهای ابری ناهمگن با استفاده چارچوب نگاشت-کاهش
· بهبود زمان اجرای کل برنامه
· افزایش سرعت همگرایی راهحلها و جلوگیری از همگرایی زودرس
ادامه مقاله به صورت زیر سازماندهی خواهد شد: در بخش 2 برخی از روشهاي مهم در زمانبندی کارها در محیطهای ابری مورد مطالعه و بررسی قرار خواهد گرفت. در بخش 3 ساختار کلی و روش پیشنهادی با استفاده از چارچوب نگاشت-کاهش و الگوریتم ژنتیک نشان داده خواهد شد. در بخش 4 هم به بررسی نتایج بدست آمده و مقایسه روش پیشنهادی با روشهای دیگر در زمان اجرای کل برنامه پرداخته خواهد شد. و در نهایت نتیجه گیری و پیشنهاد کارهای آتی نشان داده خواهد شد.
2-پیشینۀ تحقیق
در این بخش روشهای موجود در زمینه زمانبندی وظایف و بررسی مزایا و معایب این روشها دارد. همچنین بعد از بررسی روشهای موجود ایده اصلی روش زمانبندی پیشنهادی این مقاله شرح داده میشود. طبیعت چندهدفه در مسئله زمانبندی در ابر، حل آن مخصوصاً درزمانی که کارها زیاد و پیچیده میباشند را سخت میکند. در میان مسائل مختلف زمانبندی، زمانبندی ماشین با پردازندههای موازی یکی از مسائل بهینه‌سازی NP-سخت است. در مسئله زمانبندی پردازنده موازی، مجموعهای از n کار وجود دارد (T1, T2, …, Tn)؛ هرکدام می‌توانند بر روی m پردازنده (P1, P2, …, Pm) پردازش شوند، هر کار باید با رعایت تقدم بر روی پردازنده پردازش شود. هر پردازنده فقط میتواند یک کار را در یک‌زمان معین پردازش کند. در ادامه چندین روش برای زمانبندی کارها در محیطهای ابری بررسی خواهد شد.
پژوهشگران در مقاله [8] جهت رسیدن همزمان به دو معیار کارآیی بالا و زمانبندی سریع دو الگوریتم زمانبندی بر پایه لیست9 HEFT وCPOP ارائه دادهاند. الگوریتم HEFT در هر مرحله یک وظیفه با بیشترین ارزش رتبه رو به بالا10 را انتخاب و با استفاده از روش درج11 به پردازندهای تخصیص میدهد که زودترین زمان شروع را کاهش دهد. درحالی‌که الگوریتم CPOP برای اولویتدهی از تجمیع مقدارهای رو به بالا و رو به پائین12 به وظایف استفاده میکند. تفاوت دیگر این دو الگوریتم در قسمت انتخاب پردازنده به وظایف میباشد بهطوری که الگوریتم CPOP وظایف موجود بر روی مسیر بحرانی را بر روی پردازندهای اجرا میکند که زمان اجرای کل وظایف مسیر بحرانی را کمینه کند. در مقاله [9] یک الگوریتم زمانبندی مبتنی بر الگوریتم کلونی مورچه ارائه‌شده است. هدف این زمان‌بند کمینه کردن زمان گردش مجموعهی کارها همزمان با کمینه کردن حداکثر زمان اتمام انجام کل کارها میباشد. این روش ارائه‌شده اجازه پرداختن به کارهای چابک‌تر درحالی‌که زمان تکمیل کاهش مییابد را میدهد. همچنین نتایج ارزیابی نشان میدهد که الگوریتم کلونی مورچه بهتر از الگوریتمهای تصادفی و بهترین تلاش عمل میکند. در مقاله [10] روشی در زمینه زمانبندی کارها در ابر خبره ارائه‌شده است. این روش دارای عملکرد سریع‌تر با دقت بالاتر و نرخ شکست پایین‌تر در مقایسه با روشهای بررسی‌شده میباشد. نتایج پیاده‌سازی نشانگر بهبود حداکثر 56 درصدی، 14 درصدی و 7.5 درصدی به ترتیب بر اساس معیارهای زمان کلی اجرا، نرخ شکست و کارایی منابع انسانی در مقایسه با روشهای دیگر میباشد. در مقاله [11] یک الگوریتم زمانبندی سطوح پویا ارائه‌شده است. نتایج شبیه‌سازی‌ها اثبات کردهاند که این الگوریتم میتواند به‌صورت کارا نیازهای جریان کار رایانش ابری را ازنظر اعتماد، کاهش هزینههای زمانی و اطمینان از اجرای کارها در یک حالت امن را تأمین کند. پژوهشگران در مقاله [12] یک روش زمانبندی وظایف در سیستمهای رایانش ناهمگن با استفاده از الگوریتم ژنتیک و صفهای اولویتدار چندگانه به نام MPQGA را ارائه کردهاند.
ایده اصلی روش ارائه‌شده به‌کارگیری مزیتهای هر دو نوع الگوریتم اکتشافی و تکاملی و اجتناب از ایرادات آنها میباشد. روش ارائه‌شده الگوریتم ژنتیک را جهت تخصیص اولویت به هر وظیفه و روش اکتشافی EFT را جهت نگاشت13 وظایف به پردازندهها به کار گرفته است. همچنین روش MPQGA عملگرهای ترکیب، جهش و تابع برازندگی مناسبی را جهت زمانبندی گراف جهتدار بدون دور طراحی کرده است. نتایج شبیهسازی انجام‌شده بر روی گرافهای دنیای واقعی14 و تصادفی نشان میدهد که الگوریتم MPQGA دو روش غیرتکاملی و یک روش جستجوی تصادفی به نام 15 BGAرا بهبود بخشیده است. در این ادامه به مقایسه روشهای موجود پرداخته‌شده است. در الگوریتمHEFT وظایف با استفاده از ارزش رو بالا انتخاب میشود و دارای همگرای متوسط میباشد، در روش CPOP وظایف با استفاده از ارزش رو بالا و پایین انتخاب میشود و مانندHEFT دارای سرعت همگرایی متوسط میباشد. در الگوریتم MPQGA که بهبودیافته الگوریتم HEFT است برای بهبود زمانبندی از الگوریتم ژنتیک استفاده‌شده است. جدول 1 الگوریتمهای موجود را از جنبه روش مورداستفاده، مزایا و معایب آنها مورد مقایسه قرار میدهد.
جدول1: مقایسه روشهای بررسی‌شده برای زمانبندی کارها در محیطهای ابری
زمان اجرا | مزایا | معایب | الگوریتمهای زمانبندی |
متوسط | پیچیدگی کمتر | همگرایی کند، عدم تولید نتایج پایدار در مسائل با طیف گسترده | [8] |
بالا | پیچیدگی و هزینه ارتباطی کمتر | نتایج نامناسب در گرافهای بر پایه محاسبات | [9] |
متوسط | هزینه ارتباطی کمتر | همگرایی کند | [10] |
متوسط | هزینه ارتباطی و اجرای کمتر | مناسب برای محیطهای همگن | [11] |
متوسط | کارایی بهتر | همگرایی کند و پیچیدگی بیشتر | [12] |
در روشهای بررسی‌شده، زمان اجرای کل برنامهها بالا است. در صورتی که تعداد زیر وظایف افزایش پیدا کند زمان اجرای کل برنامه افزایش مییابد. مطالعات اخیر نشان میدهد که الگوریتمهای ژنتیک بر روی انواع مسائل طبیعی عملکرد موفقی داشتهاند. الگوریتم ژنتیک یک روش جستجوی مؤثر برای پیدا کردن یک جواب بهینه یا نزدیک به بهینه هست. با توجه به‌سرعت پایین الگوریتم ژنتیک در مسائل بزرگ، دراین مقاله برای افزایش سرعت همگرایی و دوری از همگرایی زودرس و کاهش زمان اجرای برنامه از چارچوب نگاشت-کاهش استفاده شده است.
3-روش پیشنهادی
در این بخش به روش پیشنهادی پرداخته شده است. در ابتدا تعاریف متغییرهای ﻣﺴﺌﻠﻪ بیان شده است در ادامه به معرفی کردن الگوریتم ژنتیک برای ترکیب کردن خدمات ابری پرداخته شده است. در ادامه یک الگوریتم ژنتیک موازی جدید زمانبندی وظیفه با استفاده از چارچوب نگاشت-کاهش بر روی رایانش ابری با استفاده از صفهای اولویت چندگانه ارائه‌شده است.
1-3-تعاریف اولیه
روش پیشنهادی دارای یک مجموعه از پردازندههای ناهمگن P میباشد که توسط شبکه پرسرعت به همدیگر متصل شدهاند. در این روش مسئله زمانبندی وظایف توسط گراف جهتدار بدون دور G(V,E) نمایش داده‌شده است که شکل 1 نمونه ارائه‌شده در این مقاله را نشان میدهد.
شکل 1: گراف جهتدار بدون دور با 10 زیروظیفه [5]
بهطوری که V نشاندهنده زیروظایف برنامه و E نشاندهنده لبههای گراف است که وابستگیهای بین زیروظایف را مشخص میکنند. هر زیر وظیفه در گراف فقط بر روی یک پردازنده میتواند اجرا شود. مقدارهای لبهها نشانگر مقدار هزینه ارتباطی بین دو زیر وظیفه است و میانگین هزینه محاسباتی هر زیر وظیفه در پردازندهها بر روی هر گره مقدارگذاری شده است. جدول 2 نمادهای استفاده‌شده در رابطهها و الگوریتمهای این مقاله را توضیح میدهد.
جدول 2: نمادهای استفاده‌شده در روش پیشنهادی
نماد | شرح | |||||||||||||||||||||||||||||||||||
ti | iامین زیر وظیفه در گراف | |||||||||||||||||||||||||||||||||||
pk | k امین پردازنده در سیستم | |||||||||||||||||||||||||||||||||||
E | مجموعه لبهها در گراف | |||||||||||||||||||||||||||||||||||
T | مجموعه زیروظایف در گراف | |||||||||||||||||||||||||||||||||||
P | مجموعه پردازندهها در سیستم | |||||||||||||||||||||||||||||||||||
tentry | زیر وظیفه ورودی در گراف | |||||||||||||||||||||||||||||||||||
texit | زیر وظیفه خروجی در گراف | |||||||||||||||||||||||||||||||||||
Succ(ti) | مجموعه تأخرهای زیر وظیفه ti | |||||||||||||||||||||||||||||||||||
Pred(ti) | مجموعه تقدمهای زیر وظیفه ti | |||||||||||||||||||||||||||||||||||
| میانگین هزینه محاسباتی زیر وظیفه ti | |||||||||||||||||||||||||||||||||||
| هزینه محاسباتی زیر وظیفه ti بر روی پردازنده pk | |||||||||||||||||||||||||||||||||||
| مقدار هزینه ارتباطی بین وظایف ti و | |||||||||||||||||||||||||||||||||||
| رتبه رو به بالای زیروظیفه ti | |||||||||||||||||||||||||||||||||||
| رتبه رو به پایین زیروظیفه ti | |||||||||||||||||||||||||||||||||||
Rankb+t(ti) | جمع رتبه روبه بالا و پایین زیروظیفه ti | |||||||||||||||||||||||||||||||||||
| زودترین زمان شروع زیروظیفه ti بر روی پردازنده pk | |||||||||||||||||||||||||||||||||||
| زودترین زمان پایان زیروظیفه ti بر روی پردازنده pk | |||||||||||||||||||||||||||||||||||
| زمان شروع واقعی زیروظیفه ti بر روی پردازنده pk | |||||||||||||||||||||||||||||||||||
| زمان پایان واقعی زیروظیفه ti بر روی پردازنده pk | |||||||||||||||||||||||||||||||||||
| زمان بیکار و در دسترس بودن پردازنده pk | |||||||||||||||||||||||||||||||||||
| مخفف کلمه انگلیسی جمعیت | |||||||||||||||||||||||||||||||||||
PopSize | مخفف کلمه انگلیسی اندازه جمعیت | |||||||||||||||||||||||||||||||||||
| مخفف کلمه انگلیسی اندازه کروموزوم |
Subtask (ti) | Rankb | Rankt | Rankb+t | level |
t0 | 129 | 0 | 123 | 0 |
t1 | 81 | 24 | 105 | 1 |
t2 | 78 | 23 | 101 | 1 |
t3 | 100 | 17 | 117 | 1 |
t4 | 99 | 30 | 129 | 1 |
t5 | 60 | 50 | 110 | 2 |
t6 | 67 | 52 | 119 | 2 |
t7 | 35 | 75 | 110 | 3 |
t8 | 42 | 77 | 119 | 3 |
t9 | 12 | 107 | 119 | 4 |
اندازه جمعیت اولیه الگوریتم پیشنهادی با نماد PopSize نمایش داده میشود و مقدار آن 4 برابر تعداد وظایف موجود در گراف است (n×4). اندازه جمعیت الگوریتم تا پایان یافتن الگوریتم ثابت است یعنی در طول تولید نسلهای جدید این مقدار تغییری نمیکند. در الگوریتم پیشنهادی به‌منظور داشتن تخمریزی20 خوب در مقداردهی جمعیت اولیه از سه سیاست رتبهبندی اکتشافی بنامهای رتبه رو به بالا(رابطه (1))، رتبه رو به پایین (رابطه (2)) و ترکیبی از این دو روش با رتبه سطح (رابطه (3)) برای مقداردهی سه کروموزوم اول جمعیت استفاده‌شده است [12]. در جدول 3 با استفاده از سه سیاست رتبهبندی شده است. اولویتهای کروموزومهای باقیمانده با جایگشتهای تصادفی تولید میشوند. کروموزومهای تولیدشده تصادفی به دلیل اینکه اولویت‌هایشان معتبر نیست از سمت چپ به راست به‌طوری‌که زیروظایف محدودیتهای اولویت را نقض نکنند مرتبسازی میشوند. فرآیند تولید جمعیت اولیه درالگوریتم 1 نشان داده شده است.
|
|
|
Algorithm 1. Initial population | ||||||||||||||||||||||||||||||||||||
1: Initial three of the chromosomes by using three heuristic rank policies 2: for i=3 to PopSize-1 do 3: for j=0 to ChSize-1 do 4: generate a genes j 5: move chromosome i from left to right in first valid place in the queue in order to has a valid topological order 6: end for 7: end for |
|
|
|
|
Algorithm 2. Assigning subtasks to processors function | ||||||||||||||||||||||||||||||||||||
1: Fill the priority queue with subtasks 2: while the priority queue is not empty do 3: Select the first subtask ti from the priority queue 4: for each processor pk in the processor set do 5: Compute 6: Assign subtask ti to the processor pk that minimizes 7: end for 8: Remove ti from the priority queue 9: end while 10: Return makespan= |
|
Algorithm 3. Crossover operation |
Input: Two parents from the current population. Output: Two new offsprings 1: Choose randomly a suitable crossover point i 2: Cut the father’s chromosome and the mother’s chromosome into left and right segments 3: Generate a new offspring, namely the son 4: Inherit the left segment of the father’s chromosome to the left segment of the son’s chromosome 5: Copy genes in mother’s chromosome that do not appear in the left segment of father’s chromosome to the right segment of son’s chromosome 6: Generate a new offspring, namely the daughter 7: Inherit the left segment of the mother’s chromosome to the left segment of the daughter’s chromosome 8: Copy genes in father’s chromosome that do not appear in the left segment of mother’s chromosome to the right segment of daughter’s chromosome 9: Return the two new offsprings |
در الگوریتم 4 عملگر تک نقطهای به‌صورت چارچوب نگاشت-کاهش در آمده است به صورتی که هر عمکلر ترکیب به یک نگاشت تخصیص داده می شود.
Algorithm 4. Crossover Mapper |
1: Run HDFS engine 2: Assign algorithm 5 to each mapper 3: Run the MapReduce job tracker 4: Start the calculation 5: Write the result into M blocks 6: Send the result to the shuffle phase 7: if all individuals have been processed successfully then Write best individual to global file in DFS 8: Copy and send the result to the Reducer |
الگوریتم 4: ترکیب تک نقطهای با استفاده از چارچوب نگاشت-کاهش
3-7-جهش
عملگر جهش در الگوریتم ژنتیک برای نگه داشتن تنوع جمعیت بوسیله تغییر کروموزوم بکار میرود. بعد از اعمال عملگر تركيب به منظور اجتناب از همگرايي به بهينه محلي و ايجاد تنوع و گوناگوني درجمعيت با استفاده از عملگر جهش يك تعداد از كروموزومهاي به دست آمده تغيير داده
ميشوند. همچنین دو ژن برای انجام عملیات جهش تعریف میشوند. الگوریتم 5 جزئیات عملگر جهش الگوریتم پیشنهادی را تشریح میکند.
Algorithm 5. Mutation operation |
Input: A randomly chosen chromosome. Output: A new chromosome. 1: Choose randomly a gene Ti 2: Find the first successor Tj member Succ(i) 3: Choose randomly a gene Tk in the interval [i+1, j-1] 4: if l < i for all Tl member Pred(k) then 5: Generate a new offspring by interchanging gene Ti and gene Tk 6: return the new offspring 7: else 8: Go to Step 1 9: end if |
در الگوریتم 6 عملگر جهش به‌صورت چارچوب نگاشت-کاهش درآمده است به صورتی که هر عملگر ترکیب به یک نگاشت تخصیص داده میشود.
Algorithm 6. Mutation Reduce |
1: Check the HDFS engine 2: Assign the result of algorithm 6 to each Reducer 3: Run the MapReduce job tracker 4: Start the calculation 5: Write the result into M blocks 6: Check the termination 7: if all individuals have been processed successfully then Write best individual to global file in DFS 8: Send the result to the cluster |
الگوریتم 6) جهش با استفاده از چارچوب نگاشت-کاهش
3-8-انتخاب
در الگوریتم پیشنهادی به‌منظور انتخاب بعضی از کروموزومها برای الگوریتم جستجوی محلی از روش انتخاب چرخ رولت با پذیرش اتفاقی22 استفاده‌شده است [14]. این روش دارای پیچیدگی زمانی (1)o میباشد. این الگوریتم انتخاب دارای دو مرحله اصلی است: در مرحله اول یک کروموزوم به‌طور تصادفی از میان جمعیت انتخاب میشود که این انتخاب با احتمال (n/1) صورت میگیرد. در مرحله بعدی مقدار برازندگی کروموزوم ارزیابی‌شده و اگر کروموزوم انتخاب‌شده یکی از نخبههای جمعیت باشد برای جستجوی محلی انتخاب میشود در غیر این صورت کروموزوم انتخاب‌شده پذیرفته نمیشود و تابع انتخاب دوباره از مرحله 1 تکرار میشود. شبه کد روش انتخاب چرخ رولت با پذیرش اتفاقی در الگوریتم 7 آورده شده است.
Algorithm 7. Roulette-wheel selection via stochastic acceptance | ||||||||||||||||||||||
Input: A current population chromosome. Output: A selected chromosome 1:do Generate a random number R 2: if 3: return 4: end if 6: while (founding a one of the fittest solution). |
نوع | سیستم‌عامل | پردازنده | حافظه |
خوشه 1 | ubuntu-14.04.2 | 4-core, 3.07 GHZ | 4G |
خوشه 2 | ubuntu-14.04.2 | 4-core, 2.07 GHZ | 4G |
خوشه 3 | ubuntu-14.04.2 | 4-core, 2.07 GHZ | 4G |
خوشه 4 | ubuntu-14.04.2 | 4-core, 2.07 GHZ | 4G |
روش پیشنهادی و سایر الگوریتمها در زبان برنامه‌نویسی جاوا در محیط MapR پیاده‌سازی شدهاند و شبیهسازی و اجرای الگوریتمها بر روی چهار خوشه در جدول 4 با مشخصات زیر اجراشده است.
تولید گرافهای جهتدار بدون دور تصادفی این امکان را میدهد که الگوریتمهای مقایسهای تحت شرایط مختلف بررسی و ارزیابی شوند. الگوریتم پیشنهادی با سایر الگوریتمها ازلحاظ زمان اجرای کل برنامه و مصرف انرژی مقایسه شده است. زمان اجرای کل وظایف از لحظه ورود به سیستم تا زمان پاسخ دهی، چه مدت در سیستم میماند تا پاسخ خود را دریافت کند. مقدار زمان اجرای کل کارها بر حسب میلی ثانیه در نظر گرفته شده است.
هزینههای محاسباتی و ارتباطی گرافها به‌صورت تصادفی از میان یک بازه انتخاب میشوند. شکل 3 زمانهای اجرای کل گراف تصادفی را با 50 زیر وظیفه و شکل 4 زمانهای اجرای کل گراف تصادفی را با 100 زیر وظیفه را نشان میدهند. با توجه به نتایج نمودارها در شکلها، مشهود است که روش پیشنهادی زمانهای اجرای دو الگوریتم MPQGA و جعفری نویمی پور و همکاران را همواره بهبود میبخشد. بهبود زمانهای اجرای کل گرافها با افزایش تعداد زیر وظایف مشهود است.
شکل 3: زمانهای اجرای کل برنامه با 50 کار
شکل 4: زمانهای اجرای کل برنامه با 100 کار
سدر روش پیشنهادی با استفاده از هادوپ و مدل نگاشت-کاهش کاهش انرژی مصرفی کل را در پی دارد. مصرف انرژی با دو الگوریتم MPQGA و جعفری نویمی پور و همکاران مقایسه شده است. شکل 5 مصرف انرژی با تعداد وظایف مختلف وظیفه را نشان میدهند. محور افقی برابر با تعداد وظایف و محور عمودی برابر مصرف انرژی وظایف در نظر گرفته می شود. در هر باراجرا، تعداد وظایف از 10 تا 50 متغیر فرض شده است که در هر بازه که سیستم اجرا میشود، مقادیر متفاوتی به دست میآید که در شکل 5 قابل مشاهده است.
شکل 5: مصرف انرژی با تعداد وظایف مختلف
5-نتیجه گیری و پیشنهاد کارهای آتی
زمانبندی در سیستمهای رایانش توزیعشده یک مسئله مهم میباشد و الگوریتمهای زمانبندی گوناگونی در این زمینه ارائه‌شده است. در این مقاله یک الگوریتم ژنتیک موازی با استفاده از چارچوب نگاشت-کاهش برای وظایف ایستا در سیستمهای رایانش ابری ارائه گردید. این الگوریتم با ترکیب الگوریتمهای ژنتیک استفاده از الگوریتم HEFT برای تخصیص زیروظایف به پردازندهها توسعه داده شد. نتایج بدست آمده بر روی یک گراف ساده و همچنین گرافهای تولیدشده تصادفی حاکی از آن است که الگوریتم ارائه‌شده از دو الگوریتم MPQGA و جعفری نویمی پور و همکاران در زمینه زمان اجرای کل بهینه عمل کرده است. لازم به ذکر است که هزینههای محاسباتی و ارتباطی گرافها به‌صورت تصادفی از بین یک بازه انتخاب میشوند از معایب این روش محسوب میشود. از طرف دیگر، نگاشت-کاهش برنامه نویسی سطح پایین است و برای بدست آوردن تابع نگاشت و کاهش باید کدهای زیادی استفاده کرد. در این مقاله مقایسههای الگوریتم پیشنهادی با سایر الگوریتمها بر روی گرافهای جهتدار بدون دور تصادفی و یک گراف ساده صورت گرفته است. به همین دلیل مطالعات بعدی در مورد الگوریتم پیشنهادی میتواند بر روی گرافهای جهان واقعی مانند FFT23، Molecular dynamics code و غیره صورت گیرد. در شیوه نگاشت-کاهش که از سوی شرکت گوگل در سال 2004 معرفی‌شده است به‌طور مختصر همپوشانی در قسمت فازهای نگاشت و ارتباط دیده میشود. متأسفانه این همپوشانی24 در نرم‌افزارهای نوشته‌شده به شیوه نگاشت-کاهش که دارای فاز ارتباط حجیم‌تری نسبت
منابع 1. Khemka, B., et al., Utility maximizing dynamic resource management in an oversubscribed energy-constrained heterogeneous computing system. Sustainable Computing: Informatics and Systems, 2015. 5: p. 14-30. 2. Arunarani, A.R., Manjula, D. and Sugumaran, V., 2019. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems, 91, pp.407-415. 3. Zang, X., Sun, J., Zhao, J. and Zeng, W., 2018, May. Research Progress of Cloud Computing Task Scheduling Technology. In 2018 3rd International Conference on Automation, Mechanical Control and Computational Engineering (AMCCE 2018). Atlantis Press. 4. Young Choon, L. and A.Y. Zomaya, A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems. Parallel and Distributed Systems, IEEE Transactions on, 2008. 19(9): p. 1215-1223. 5. Keshanchi, B. and Navimipour, N.J., 2016. Priority-based task scheduling in the cloud systems using a memetic algorithm. Journal of Circuits, Systems and Computers, 25(10), p.1650119. 7. Khezr, S.N. and Navimipour, N.J., 2017. MapReduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. Journal of Grid Computing, 15(3), pp.295-321. 8. Topcuoglu, H., S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 2002. 13(3): p. 260-274. 9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50. 10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471. 11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329. 12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287.
|
به فاز نگاشت میباشند تأثیری چندانی روی کاهش زمان پاسخ این نرم‌افزارها ندارد. اگر بتوان راهکارهایی ارائه دهیم که توانایی همپوشانی فازهای حجیم ارتباط و کاهش را در این‌گونه نرم‌افزارها را داشته باشد میتوان زمان بحرانی اجرای برنامه را کاهش داد و همچنین از منابع در دسترس حداکثر استفاده را نمود.
tool. Communications of the ACM, 2010. 53(1): p. 72-77. 7. Khezr, S.N. and Navimipour, N.J., 2017. MapReduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. Journal of Grid Computing, 15(3), pp.295-321. 8. Topcuoglu, H., S. Hariri, and W. Min-You, Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 2002. 13(3): p. 260-274. 9. Mateos, C., E. Pacini, and C.G. Garino, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments. Advances in Engineering Software, 2013. 56: p. 38-50. 10. Ashouraie, M. and N. Jafari Navimipour, Priority-based task scheduling on heterogeneous resources in the Expert Cloud. Kybernetes, 2015. 44(10): p. 1455-1471. 11. Wang, W., et al., Cloud-DLS: Dynamic trusted scheduling for Cloud computing. Expert Systems with Applications, 2012. 39(3): p. 2321-2329. 12. Xu, Y., et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014. 270(0): p. 255-287.
|
, 2014. 270(0): p. 255-287.
13. Abed, I., et al., Optimization of the Time of Task Scheduling for Dual Manipulators using a Modified Electromagnetism-Like Algorithm and Genetic Algorithm. Arabian Journal for Science and Engineering, 2014. 39(8): p. 6269-6285.
14. Lipowski, A. and D. Lipowska, Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, 2012. 391(6): p. 2193-2196.
15. Ong, B. and M. Fukushima, Genetic algorithm with automatic termination and search space rotation. Memetic Computing, 2011. 3(2): p. 111-127.
16. Hashem, Ibrahim Abaker Targio, Nor Badrul Anuar, Mohsen Marjani, Ejaz Ahmed, Haruna Chiroma, Ahmad Firdaus, Muhamad Taufik Abdullah et al. "MapReduce scheduling algorithms: a review." The Journal of Supercomputing (2018): 1-31.
17. Keshanchi B, Souri A, Navimipour NJ. An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. Journal of Systems and Software. 2017 Feb 1;124:1-21.
18. Shabestari, F., Rahmani, A. M., Navimipour, N. J., & Jabbehdari, S. (2019). A taxonomy of software-based and hardware-based approaches for energy efficiency management in the Hadoop. Journal of Network and Computer Applications, 126, 162-177.
19. Ashouraei, M., Khezr, S. N., Benlamri, R., & Navimipour, N. J. (2018, August). A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm. In 2018 IEEE 6th International Conference on Future Internet of Things and Cloud (FiCloud) (pp. 71-76). IEEE.
20. Panahi, V., & Navimipour, N. J. (2019). Join query optimization in the distributed database system using an artificial bee colony algorithm and genetic operators. Concurrency and Computation: Practice and Experience, e5218.
21. Mirjalili, S. (2019). Genetic algorithm. In Evolutionary Algorithms and Neural Networks (pp. 43-55). Springer, Cham.
22. Malik, M., Neshatpour, K., Rafatirad, S., Joshi, R. V., Mohsenin, T., Ghasemzadeh, H., & Homayoun, H. (2019). Big vs little core for energy-efficient Hadoop computing. Journal of Parallel and Distributed Computing, 129, 110-124.
[1] . Heterogeneous distributed computing systems
[2] . Precedence constraint
[3] . Development
[4] . Execution time
[5] . Makespan
[6] . Convergence speed
[7] . Efficiency
[8] . Directed acyclic graph
[9] . List-based scheduling
[10] . Upward rank
[11] . Insertion-based approach
[12] . Downward rank
[13] .Mapping
[14] . Real world graphs
[15] Basic genetic algorithm
[16] . Unrelated
[17] . Precedence
[18] . Encoding
[19] . Genes
[20] . Seeding
[21] .Fittest
[22] . Roulette-wheel selection via stochastic acceptance
[23] . Fast Fourier transformation
[24] . Overlapping
|
|
رایمگ
الروابط
المراكز ذات الصلة
دعامة
الصفحات الرسمية
حقوق هذا الموقع الإلكتروني مملوكة لنظام Rimag Press Management. © 1438-1447