بخشی از مقاله
چکیده
مسئله تضمین کیفیت سرویس به کاربران گرید از طریق رزرو نمودن پیشاپیش1 منابع فراهم می شود. رزرو نمودن پیشاپیش، مکانیسمی است که توانایی تخصیص منابع به کاربران را براساس توافق بر روی نیازمندی های کیفیت سرویس و افزایش تعداد درخواست های پذیرفته شده کاربران در سیستم گرید فراهم می کند. زمانبندی و رزرو نمودن پیشاپیش منابع در گرید یک مساله NP-complete است، پس نمی توان از الگوریتم های قطعی برای بهبود آن استفاده نمود.
روش های هیوریستیک برای این منظور عبارتند از الگوریتم ژنتیک، سرمایش شبیه سازی شده، تپه نوردی و روش های جستجوی دیگر. در این مقاله روش هیوریستیک جدیدی به نام الگوریتم جستجوی تصادفی تقلید نیروی گرانشی GELS برای حل مساله زمانبندی و رزرو نمودن پیشاپیش منابع در گرید را نشان می دهیم. این الگوریتم بر پایه مفاهیم جستجوی تصادفی، دو تا از چهار پارامتر اصلی سرعت2 و نیروی گرانشی3 در فیزیک استفاده می نماید. الگوریتم پیشنهادی را GELSAR4 نامیده و برای تصدیق آن، الگوریتم را پیاده سازی نموده و با الگوریتم ژنتیک مقایسه نموده ایم. بر اساس نتایج بدست آمده مشاهده می شود که تعداد کارهای رزروشده نسبت به الگوریتم ژنتیک 7.5 درصد افزایش یافته و نیز زمان اجرای الگوریتم تا 50 درصد کاهش می یابد.
.1مقدمه
موضوع همکاری منابع توزیع شده جغرافیایی برای حل مسائل بزرگ، گرید محاسباتی نام گرفته است. گرید محاسباتی، یک مدل محاسباتی توزیع شده است که دسترسی به منابع ناهمگون را که از لحاظ جغرافیایی پراکنده هستند، فراهم می آورد. امروزه استفاده از این نوع گرید در اشتراک گذاری، انتخاب و جمع آوری منابع محاسباتی متداول شده است بطوریکه توانایی به اشتراک گذاری و تخصیص پویا در محیط های توزیع شده و افزایش کارایی منابع محاسباتی را فراهم می کند.[6,8,9] همچنین دسترسی به منابع را برای بالابردن انعطاف پذیری و همکاری میان سازمانهای مختلف آسان می نماید.
این به اشتراک گذاری عمدتا برای مقاصد علمی و کاربردهای اقتصادی می باشد.[12] با توجه به اینکه منابع موجود در گرید ناهمگون، متعلق به سازمان ها و مکان های مختلف با سیاست ها و دسترسی های متفاوت و از نظر بار کاری دارای ذاتی دینامیک می باشند، مدیریت منابع و درخواست های محاسباتی در گرید یک امر حیاتی و پیچیده می باشد به طوریکه زمانبندی و مدیریت منابع در گرید یکی از حوزه های تحقیقاتی در حال پیشرفت و توسعه می باشد.
رزرو نمودن پیشاپیش منابع توانایی زمانبند را برای تضمین در دسترس بودن منابع در زمان خاصی در آینده فراهم می نماید، این مسئله حوزه مورد علاقه[6,12] در اجتماع گرید است. برای این منظور باید باقیمانده و یا تکه منابع قابل استفاده ودر دسترس را نگهداری نمود. اگر این تکه ها بوسیله الگوریتم های زمانبندی بحساب نیایند، در نتیجه بهره وری ضعیف شده و نرخ عدم پذیرش کارها افزایش می یابد. به عبارت دیگر الگوریتم ها تلاش می کنند تااین تکه منابع را مورد استفاده قرار دهند، اما طرح نادرست، زمان اجرای غیرقابل قبول زیادی را ازتعدادی منابع و نیز تعداد درخواست های رد شده را افزایش می دهد.
در سیستم محاسباتی گرید، با چندین درخواست همزمان کاربر برای استفاده از منابع در آینده، باید از یک الگوریتم زمانبندی موثر برای رزرو نمودن پیشاپیش منابع استفاده نمود، بطوریکه تعداد درخواست های بیشتری پذیرفته شود. توانایی ارائه و تضمین سرویس به کاربران، یکی از مسائل با اهمیت در گرید است. بدون تضمین، کاربران هیچ میلی به پرداخت پول برای سرویس های گرید یا شرکت دادن منابع اشان در گرید ندارند که این باعث جلوگیری از توسعه مدل گرید می شود. بنابراین باید چارچوبی برای طراحی موثر و کارامد الگوریتم های زمانبندی برای رزونمودن پییشاپیش منابع و تضمین سرویس به کاربران استفاده نمود.
محیطی که در آن کاربران، کارهایشان را ارائه نموده و این کارها ممکن است در زمان آینده شروع شده و باید در یک موعد زمانی خاصی تکمیل شود. به کمک مفاهیم محاسبات هندسی ونیز ماتریس منابع، چگونگی مدیریت موثر تکه منابع مورد استفاده در رزرو نمودن پیشاپیش را نشان می دهیم. الگوریتم های زمانبندی برای رزرونمودن پییشاپیش منابع درسیستم محاسباتی گرید بصورت یک مشکل NP-complete است که نمی توان با استفاده از الگوریتم های سنتی آن را حل نمود.
بنابراین روشی نیاز است که توانایی حل چنین مسائلی را داشته باشد. از جمله روش های شناخته شده ای که برای حل چنین مسائلی استفاده می شوند [5,7,10,11]عبارتند از الگوریتم ژنتیک، سرمایش شبیه سازی شده، تپه نوردی و روش های جستجوی مکاشفه ای دیگر... . در این مقاله از روش جدیدی به نام GRAVITY برای حل این چنین مسائل استفاده می کنیم. در این روش با تخصیص منابع محاسباتی گرید به درخواست های کاربران به صورت اولیه کار را شروع می نماییم.
ساختارمقاله به صورت زیر سازماندهی شده است: در بخش 2 به بیان مساله زمانبندی و رزرونمودن پیشاپیش منابع پرداختیم. در بخش 3 به شرح الگوریتم GELS پرداخته و در بخش 4 به جزیئات بیشتر الگوریتم GELS برای زمانبندی و رزرو منابع پرداخته والگوریتم جدید را GELSAR نامیدیم. در بخش 5 نتایج شبیه سازی را با پارامتر های کارآیی مختلف نشان دادیم و با نتیجه گیری مقاله را به پایان رساندیم.
