بخشی از مقاله
:HSGA یک روش جدید برای زمانبندی سیستم های گرید با ترکیب الگوریتم ژنتیک و جستجوی هارمونی
چکیده
امروزه مسائل علمی، به دلیل پیچیدگی بالا نیاز به قدرت محاسباتی و فضای ذخیره سازی بالایی دارند. تکنیکهای قدیمی
همچون محاسبات توزیعی و موازی برای اینگونه مسائل مناسب نیستند.یکی از اهداف گرید کامپیوتینگ مدیریت منابع
محاسباتی برای پردازش برنامههای کاربران یا مشتریان می باشد به طوری که منجر به کیفیت بالای سرویسها، هزینه کمتر و انعطاف پذیری بیشتری شود.با افزایش منابع محاسباتی در گرید نیاز به یک سیستم گریدی احساس میشود، که بتواند به مدیریت این نوع از منابع پرداخته تا سریعتر به درخواستهای مختلف پاسخ دهد. ازاینروزمانبندی کارهای کاربران برای پردازش توسط منابع مناسب موجود در شبکه گرید، به عنوان یک مساله اساسی در رسیدن به کارایی بالا در سیستم های محاسباتی شبکه گرید مطرح شده است. این مساله از رده مسائل NP بوده و تا کنون روش های زیادی برای حل آن با استفاده از الگوریتم های ابتکاری ارائه شده است. در این مقاله برای حل مساله زمانبندی سیستم گرید محاسباتی از ترکیب
الگوریتم ژنتیک و الگوریتم جستجوی هارمونی بکار گرفته شده و برای نشان دادن کارایی این الگوریتم، با الگوریتم ژنتیک
مقایسه شده است. نتایج تجربی نشان می دهد الگوریتم پیشنهادی از کارایی بالاتری نسبت به الگوریتم ژنتیک برخوردار است.
کلید واژه: سیستم گرید محاسباتی ، الگوریتم ژنتیک، الگوریتم جستجوی هارمونی.
-1 مقدمه
امروزه مسائل علمی، به دلیل پیچیدگی بالا نیاز به قدرت محاسباتی و فضای ذخیره سازی بالایی دارند. تکنیکهای قدیمی همچون محاسبات توزیعی و موازی برای اینگونه مسائل مناسب نیستند. پردازش و ذخیره سازی حجم زیادی از
داده ها، زمان زیادی را صرف می کند. استفاده از گرید محاسباتی راه حل مناسبی برای حل اینگونه مسائل است . در گرید
شرایطی همچون وضعیت شبکه و وضعیت منابع باید مورد بررسی قرار گیرد . اگر شبکه و منابع ناپایدار باشند اجرای
کارها درحین اجرا با خطا مواجه شده و زمان اجرای کارها افزایش می یابد((1 بنابراین یک الگوریتم زمانبندی موثر برای کارها در گرید محاسباتی بسیار حائز اهمیت است به همین منظور تعدادی الگوریتم زمانبندی کار برای گرید در 2) و (3
پیشنهاد شده است . همچنین در یک مطالعه حرفه ای روی الگوریتم های زمانبندی کار و دسته بندی آنها و معرفی مسائل
باز انجام شده است. گرید محاسباتی، یک زیر بنای سخت افزاری و نرم افزاری می باشد که دست رسی قابل اعتماد،
پایدار، فراگیر و ارزان را فراهم می کند(5 و .(4
امروزه با بزرگ شدن مسائل و اهمیت یافتن سرعت رسیدن به پاسخ، روشهای کلاسیک جواب گوی حل بسیاری از مسائل نیست و از الگوریتمهای جستجوی تصادفی بیش از جستجوی همه جانبه فضای مسأله استفاده میشود.در حال حاضر الگوریتمهای ابتکاری که برای مساله زمانبندی گرید استفاده شدهاند عموما شامل الگوریتم ژنتیک، تبرید شبیه سازی
شده3، الگوریتم های ترکیبی ژنتیک و تبرید شبیه سازی شده4، جستجوی حرام5، بهینه سازی کلونی مورچگان6، و بهینه
سازی پرندگان7 هستند.
در (6) یک مطالعه ارزشمند بر روی مزایای GA جهت طراحی زمانبند موثر گرید، با هدف کمینه کردن Makespan و زمان گردش کار ارائه دادند. در((7 یک الگوریتم انطباقی بهبود یافته GA که با جستجوی همسایگی ترکیب شده بود معرفی کردند، و شبیه سازی آنها نشان داد که الگوریتم ارائه شده می تواند کارایی مساله زمانبندی گرید را به طور چشمگیری بهبود دهد.در((8 یک الگوریتم زمانبند کار بر اساس الگوریتم SA معرفی کرد که در مقایسه با ACO نتایج بهتری را بدست می آورد. در (9) یک SA تغییر یافته را برای زمانبندی کارهای مستقل در محیط گرید ارائه دادند. نتایج آزمایشگاهی نشان
داد که این الگوریتم در مقایسه با نتایجی که دیگر الگوریتمها در مقاله مورد نظر بدست آورده بودند، می تواند کارایی نمونههای ایستا را بهبود دهد. در (10) یک الگوریتم GSA موازی که مزیت های GA و SA را ترکیب کرده بود برای مساله
زمانبندی گرید پیشنهاد دادند.کاربرد الگوریتم جستجوی حرام در مساله زمانبندی گرید را میتوانید در 12) و (11 مشاهده نمایید.در (13) یک الگوریتم ACO برای حل مساله زمانبندی گرید طراحی کردند. در الگوریتم پیشنهادی آنها، وقتی که
یک منبع در گرید ثبت نام می کند،پارامترهای عملکرد آن تست شده و مقدار اولیه فرومون بر روی هر لینک محاسبه
میشود. زمانی که یک منبع جدید به سیستم گرید ملحق و یا یک منبع از آن جدا می شود، یا یک کار به آن نسبت داده
میشود، یا وقتی یک کار برگشت داده میشود، مقدار فرومون روی هر مسیر به روزرسانی می شود. در((14 یک ACO
ترکیبی برای زمانبندی کارهای مستقل در محیط محاسباتی ناهمگن ارائه کردند. این الگوریتم همواره زمانبندی بهتری را
نسبت به تکنیک های دیگر برای benchmark های مختلف به دست آورده است. در (15) یک الگوریتم ACO برای
زمانبندی پویای کار در محیط گرید تعریف کردند. بعدها Liu و همکارانش (16) یک ACO بهبود یافته به نام adaptive ACO برای مساله زمانبندی گرید پیشنهاد دادند که هم در زمانبندی بهتر کار و هم بارگذاری منبع خیلی کاراتر از الگوریتم اصلی بود. در (17)یک الگوریتم PSO بهبود یافته با قانون کدگذاری گسسته برای مساله زمانبندی گرید ارائه کردند. نتایج
تجربی نشان داد که PSO بهبود یافته پایدار بوده و تغییر پذیری کمی دارد. بعدا Izakion و همکارانش (18)یک الگوریتم
PSO برای زمانبندی meta-task در سیستم های محاسباتی ناهمگن توزیع شده برای کمینه کردن makespan معرفی کردند،
الگوریتم ارائه شده عملکرد بالاتری را نسبت به تکنیک های مقایسه شده بدست آورد.در این مقاله برای حل مساله
زمانبندی کارها در شبکه گرید کامپیوتینگ ازترکیب الگوریتم ژنتیک و الگوریتم جستجوی هارمونی استفاده شده است.
الگوریتم پیشنهادی بر تنوع عملگرهای ژنتیک و استفاده از الگوریتم جستجوی هارمونی برای جستجوی محلی تاکید دارد.ساختار ادامه مقاله به صورت زیر است: در بخش دوم مدل پیشنهادی برای شبکه گرید به همراه شرح مساله بیان شده
است. در بخش سوم مراحل انجام الگوریتم پیشنهادی بیان شده و در بخش چهارم نتایج تجربی و مقایسه الگوریتم
پیشنهادی با الگوریتمهای ژنتیک نشان داده شده است. در بخش پنجم نیز نتیجه گیری بیان شده است.
-2 شرح مساله
در محیط گرید در نظر گرفته شده در این مقاله N منبع وجود دارد که هر کدام از این منابع می تواند در هر نقطه از محیط جغرافیایی واقع شود. هر منبع از تعدادی ماشین تشکیل شده است که ماشین ها با استفاده از کانال های ارتباطی با منبع مورد نظرشان در ارتباط هستند. هر ماشین از تعدادی پردازنده برای پردازش اطلاعات با قدرت پردازش متفاوت و همچنین نوع عملکرد متفاوت تشکیل شده است. همچنین هر پردازنده دارای هزینه های متفاوتی جهت پردازش اطلاعات می باشد. پردازنده ها با استفاده از کانال های ارتباطی با ماشین مورد نظرشان در حال ارتباط هستند. در نهایت تمام این منابع به سیستم زمانبند گرید، از طریق کانال های ارتباطی متصل هستند.در جدول-1 ویژگیهای در نظر گرفته شده برای
منابع ذکر شده است.
در جدول-1 ویژگیهای در نظر گرفته شده برای منابع
در این محیط کاربران گرید در خواست های خودشان را توسط یک فایل با نرخ های ارسالی متفاوتیبرای سیستم
زمانبند گرید ارسال می کنند، سپس الگوریتم زمانبندگرید ، به اختصاص منابع برای پردازش کارهای کاربران می پردازد.
هر کاربر برای پردازش کل کارهای خود زمان خاتمه پیشنهادی و هزینه پیشنهادی تعیین می کند. هدف این الگوریتم زمانبند،اجرای کارهای کاربران در حداقل زمان ممکن و با هزینه کمتر میباشد. بعد از زمانبندی کارها توسط الگوریتم زمانبند و اجرای آنها در سیستم گرید، اطلاعات پردازش شده برای کاربران ارسال می شود.
جدول-2 پارامترهای در نظر گرفته شده برای کاربران و کارهای درخواستی
همچنین در سیستم گرید ارائه شده کارهای کاربران به صورت کاربران در نظر گرفته نشده است. هر کار باید روی پردازنده ای با وقفه برای پردازنده ها وجود ندارد، یعنی هر زمان پردازندهای به نظر پردازنده در اختیار آن باقی خواهد ماند.
off-line بوده و محدودیتی در ترتیب پردازش کارهای سیستم عامل و معماری مربوط به خود پردازش شود و یک کار اختصاص داده شد، تا پایان پردازش کار مورد
-3 الگوریتم پیشنهادی
در این مقاله برای حل مساله زمانبندی سیستم گرید محاسباتی از ترکیب دو الگوریتم ژنتیک و الگوریتم هارمونی
استفاده شده است. الگوریتم ژنتیک با وجود توانایی های بالا در جستجوی فضای مسئله از نظر پایداری و جستجوی محلی
ضعیف عمل می کند. هدف از ارائه الگوریتم پیشنهادی ترکیب قابلیتهای جستجوی عمومی الگوریتم ژنتیک با جستجوی محلی الگوریتم هارمونی است. مراحل الگوریتم پیشنهادی روی سیستم مدل گرید محاسباتی نمونه جدول-3 اجرا شده
است. این سیستم گرید دارای دو منبع است که هر کدام دارای دو ماشین، و هر ماشین برای پردازش کارها دارای دو
پردازنده می باشد.
جدول-3 اطلاعات پایه از منابع در مدل گرید محاسباتی
اطلاعات پایه مربوط به کار کاربران در جدول-4 نشان داده شده است. در این جدول 3 کاربر وجود دارد که هر کاربر
مشخصات کارهای خود را برای سیستم زمانبند گرید به صورت offline ارسال کرده است تا توسط پردازنده های موجود در سیستم گرید نمونه مورد پردازش قرار بگیرند.
جدول-4 اطلاعات پایه از کار کاربران در مدل گرید محاسباتی
در الگوریتم پیشنهادی برای شناسایی بهتر منابع و پردازنده های مربوط به جدول-3 از کدگذاری اطلاعات استفاده شده است. برای کدگذاری اطلاعات منابع موجود از اندیس گذاری پردازندهها استفاده شده است، بدین صورت که در کدگذاری جدید برای هر یک از پردازندهها یک اندیس منحصر به فرد در نظر گرفته میشود. به عنوان مثال اندیس شماره یک در جدول کدگذاری شده به پردازنده شماره دو از ماشین یک در منبع یک اشاره می کند و اندیس شماره چهار به
