بخشی از مقاله
خلاصه
محاسبات گرید در سیستم های توزیع شده برای حل مسائل پیچیده علمی، مهندسی و ... بوسیله به اشتراک گذاشتن منابع وسیع، کاربرد دارد. زمانبندی عنوان مهمی در افزایش کارایی این سیستم ها می باشد. زمانبندی به پیدا کردن منابع مناسب جهت اختصاص به برنامه های گرید کمک میکند. مدیریت و ترکیب منابع و سرویس ها و همچنین توازن بار اجرایی پردازنده ها برای زمانبندی برنامه های کاربردی یک مسئولیت پیچیده می باشد.
در این مقاله یک روش زمانبندی با هدف برقراری توازن بار در محیط گرید بر اساس الگوریتم ژنتیک و طبقه بندی معرفی می کند. روش معرفی شده بر در نظر گرفتن حالت جاری سیستم، چندین معیار را برای زمان بندی در نظر می گیرد و روشی برای اختصاص کارها به پردازنده ها ارایه می دهد که میتواند تعادل مناسبی بین فاکتورهای کیفی متفاوت برقرار نماید. نتایج حاصل از شبیه سازی، بیانگر کیفیت مناسب روش پیشنهادی در مقایسه با سایر روش ها می باشد.
.1 مقدمه
هدف اصلی زمانبندی، به حداکثر رساندن استفاده از منابع، به حداقل رسانی زمان اجرای وظایف، کاهش مصرف انرژی و به حداقل رساندن هزینه برای کاربر پس از رفع محدودیتهای وظایف و منابع میباشد. ما به دنبال برقراری تعادلی مناسب بین سطح موردنیاز کیفیت خدمات، ضربالاجل و بودجه کاربر، میباشیم.[1] در این مقاله، یک زمانبند وظایف با حالت پویای مبتنی بر تکامل چند هدفی در شبکه را پیشنهاد دادهایم. زمانبند ما از روش بهینهسازی چند هدفی با استفاده از الگوریتم ژنتیک برای پیدا کردن زمانبندیهای کارآمد استفاده کرده است. این روش دست به کاوش فضای جستجو بهطور روشن زده تا از ایستایی جلوگیری کرده و راهحل نزدیک به بهینه را تولید نماید.[2]
پیدا کردن راهحل نزدیک به بهینه برای مشکل زمانبندی وظایف منعطف با بیش از یک هدف در یک روش کارآمد ازنظر زمانی، کاری دشوار است. محیط شبکه دارای ماهیت پویا بوده و تخصیص دوباره وظایف درنآ کاملاً آشکارکننده این وضعیت میباشد.[3] هدف این مقاله، ارائه یک زمانبند بهتر به مجریان شبکه بوده که دارای وضعیت بهتری ازنظر مدیریت هزینه، کاربری، کارآمدی انرژی و کیفیت خدمات خواهد بود. این زمانبند میتواند از عهده رفتار پویای منابع، محدودیتهای منبع و محدودیتهای مربوط به وظایف پیشین برآید.
زمانبند ارائهشده در این مقاله، فراهمکننده مزیت بیشتری در رابطه با اکثر ویژگیهای شبکه چه ازنظر مالک و چه ازنظر کاربر شبکه میباشد. محیط پویای شبکه روش پیشنهادی را تبدیل به یک زمانبند پویا بازمان واقعی میسازد. یک روش گروهبندی وظایف برای گروهبندی وظایفِ بهخوبی شبکهای شده بهمنظور تسهیل در محاسبات پیچیده پیشنهاد گردیده است. انجام آزمایشات بر روی مجموعههای مختلف دادهها و پارامترهای گوناگون نشاندهنده کارآمدی معیارهای زمانبندی چند هدفی و استخراج عملکرد از منبع شبکه بوده است. رویکرد ما در رابطه با حل مشکلات بالا با استفاده از الگوریتم تکاملی برای کوچک کردن حیطه اهداف چندگانه بهاندازهای مناسب بوده که راهبرد زمانبندی نزدیک به بهینه را بهموقع پیدا کند.
الگوریتم ژنتیک طبقهبندی غیر تحت سلطه بهعنوان یک چهارچوب بنیادین برای ماژول زمانبندی وظایف ما بکار گرفتهشده است. سازوکار طبقهبندی غیر مسلط با عملگرهای ادغام و جهشِ پیشرو، زمانبند را قادر ساخته تا دقیقهبهدقیقه فضای جستجو را موردبررسی قرار دهد. پیچیدگی زمان اجرای الگوریتم بهصورت O - GMN - بوده که در اینجا G تعداد نسلها یا تکرارها، M تعداد اهداف، N اندازه جمعیت کروموزومها یا راهبردهای زمانبندی برای اجرای الگوریتم میباشد.
-2 مروری بر کارهای موجود
ما برخی از تحقیقات مرتبط با این مساله را نشان می دهیم. نویسندگان در [4] از یک الگوریتم ژنتیک برای زمان بندی کارها در محیط شبکه توزیع شده استفاده کردند. یک گراف بدون دور جهت دار - DAG - * برای هر کار نشان داده شد که دارای محدودیت ها و زمان پردازش می باشد. نتایج نشان داد که زمان بند زمان اجرای کلی و زمان اتلاف پردازنده ها را به خوبی کاهش می دهد. نویسندگان در [5] یک الگوریتم ژنتیکی جدیدی را بر اساس ترکیب الگوریتم ژنتیک و تبرید شبیه سازی شده را برای زمان بندی شبکه معرفی نموده اند که این روش می تواند بطور موثر عمل کرده و بهینه سازی سراسری را به خوبی محاسبه کند.
در [6] یک الگوریتم زمان بندی وظایف را برای گرید محاسباتی معرفی شده است که این الگوریتم بر اساس بهینه سازی کلونی مورچه بنا نهاده شده استکه همان روش مونت کارلو می باشد. این الگوریتم تعادل بار مناسب ماشین ها را تضمین می کند. نویسندگان در [7] اجرای الگوریتم های ژنتیکی را برای زمان بندی کار روی شبکه های محاسباتی نشان می دهند که زمان کلی انجام وظایف را بهینه سازی کنند.
در [8] یک روش ترکیبی را بر اساس الگوریتم بهینه سازی ازدحام ذرات نشان داده شده است که برای حل مساله زمان بندی وظایف در محیط گرید می باشد. آزمایشات نشان داد که این الگوریتم قادر است تا زمان بندی بهتری نسبت به الگوریتم ژنتیک داشته باشد. در [9] یک موتور تصمیم گیری چند سطحی و به عنوان نمونه یک الگوریتم تصمیم گیر بعنوان دو سطحی، پیشنهاد شده است. در تصمیمات سطح اول، زمان بندی اولیه را با استفاده از الگوریتم ایجاد می گردد و سپس در سطح بعد این زمان بندی با استفاده از الگوریتم ژنتیک صورت می پذیرد. این روش به خوبی قادر خواهد بود تا از الگوریتم های بکار گرفته شده در هر دو سطح بهره ببرد.
-3 ادبیات موضوع
یک زمانبند پویا برای محیط شبکه در نظر گرفتهشده است که به حل مسئله زمانبندی وظایف بر مبنای روش بهینهسازی چند هدفی میپردازد. این مسئله در سه قسمت تعریفشده است:
الف - بهینهسازی چند هدفی بر مبنای مسئله زمانبندی کارها
ب - زمانبند پویا برای تغییر مداوم در وضعیت در دسترس بودن منبع.
ج - یک روش گروهبندی وظایف برای گروهبندی وظایف بهخوبی دانهدانه شده که به زمانبند کمک کرده تا راهبرد زمانبندی را بهموقع ارائه دهد. در اینجا مسئله موردنظر با نشانهگذاریهای مربوط به زمانبندی منابع در شبکه محاسباتی گرید توصیفشده است.
