بخشی از مقاله
خلاصه
زمانبندی بهینه وظایف یکی از چالشهای سیستم های چند پردازنده ای است که امروزه کاربرد وسیعی در محاسبات موازی دارند. در این سیستمها این مسئله یک امر حیاتی برای داشتن سریعترین زمان پاسخ و حداقل سازی زمان انتظار است . الگوریتم های موجود همواره سعی در توزیع وظایف به پردازنده ها در جهت افزایش کارائی سیستم از دید گاه حداقل سازی زمان پاسخ و هزینه دارند. با این حال با توجه به اینکه الگوریتم های مبتنی بر روشهای قطعی بواسطه NP-Hardبودن این مسئله معمولاٌ کارا نبوده اند استفاده از رویکردهای پردازش تکاملی و به طور عمده الگوریتم ژنتیک برای حل این مسئله میتواند موثرواقع شود. در این تحقیق از الگوریتم ژنتیک بهبود یافته برای زمانبندی گراف وظایف در معماری چند پردازنده ای استفاده شده است. از ویژگیهای این الگوریتم عدم نیاز به محاسبات مربوط به تنظیم پارامترهای نرخ جهش و نرخ برش میباشد. نتایج حاصل از اجرای تکنیک پیشنهادی در آزمایشهای متفاوت نشان از بهتر شدن زمان پاسخ و توازن بار مناسب روی پردازنده ها نسبت به روش های موجود از جمله نسبت به مدل بر پایه الگوریتم ژنتیک بوده است.
کلمات کلیدی: زمانبندی گراف وظایف، معماری چند پردازنده ای، پردازش توزیع شده، الگوریتم ژنتیک بهبود یافته.
.1 مقدمه
امروزه سیستمهای چند پردازنده کاربردهای وسیعی در محاسبات موازی دارند. در سیستمهای توزیع شده یک مسئله به وظایف مختلف تقسیم میشود که هر کدام از آنها توسط یک کامپیوتر یا بیشتر حل میشود. یکی از چالشها مطرح در سیستم-های چند پردازه و محیطهای متکی به رایانش ابری، مسئله تخصیص منابع و زمانبندی اجرای کارهای ورودی است که زمانبندی گراف وظایف نامیده میشود. سید مسعود مقبلی، دانشجوی کارشناسی ارشد دانشگاه آزاد اسلامی واحد گرمسار. گرمسار- خیابان دانشجو - دانشگاه 1 Corresponding author: ×آزاد اسلامی - دانشکده فنی مهندسی - گروه کامپیوتر. تلفن: 09386637190 Email: masoudmoghbeli1395@gmail.com این زمانبندی باید به گونهای انجام گیرد که بتواندزمان اجرای کل برنامه را با توجه به زمان وظایف وارتباط بین پردازندهها، کمینه نماید.[2,1] مسئله زمانبندی گراف وظایف یک مسئله NP-Hard است.[4,3,2] بنابراین از الگوریتمهای تکاملی به عنوان راهکار مناسب برای زمانبندی گراف وظایف استفاده میشود.[5,4] در رویکردهای قبلی برای حل مسئله زمانبندی گراف وظایف نشان داده شده است که الگوریتم ژنتیک برای زمانبندی گراف وظایف، راهکار بهینهی بهتراز سایر روشهای غیرقطعی ارائه میدهد.[4,3,2] همه روشهای تکاملی استفاده شده برای زمانبندی گراف وظایف نظیر[4-8] همواره نیازمند محاسبه مقدار بهینه پارامترهای ورودی نظیر نرخ جهش و برش میباشند.
به طور کلی مقدار پارامترهای ورودی وابسته به ماهیت و اندازه مسئله ورودی میباشد و برای هر گراف با گرههای مختلف مقدار بهینه، متفاوت خواهد بود.[8,9] در این مقاله مدلی بر مبنای الگوریتم ژنتیک بهبودیافته برای حل مسئله زمانبندی گراف وظایف ارائه شده است که نیازمند محاسبه مقدار پارامترهای ورودی نظیر نرخ جهش و برش نمیباشد.[11,10] سایر بخشهای مقاله به صورت زیر سازماندهی شده است: در بخش 2، مسئله زمانبندی گراف وظایف تشریح شده است. در بخش 3، ساختار الگوریتم ژنتیک بهبود یافته معرفی شده است. در بخش 4، راهکار پیشنهادی ما یعنی یک مدل مبتنی بر مبنای الگوریتم ژنتیک بهبود یافته برای مسئله زمانبندی گراف وظایف ارائه شده است. در بخش 5 نتایج حاصل از پیاده سازی الگوریتم پیشنهای مورد ارزیابی قرار گرفته است.
.2زمانبندی گراف وظایف
قبل از این که به بیان زمانبندی پرداخته شود ورودی الگوریتم در قالب گراف در این بخش توضیح داده خواهد شد. ورودی مسئله به صورت گراف وزندار و جهت دار و بدون حلقه به نام گراف وظایف نشان داده می شود. زمانبندی گراف وظایف فرایندی است که بر مبنای آن، یک گراف وظایف را بر روی یک پلتفرم هدف اجرا میکند. گراف وظایف، گراف وزن دار و جهت دار است که هر گره، یک واحد کاری از برنامه ورودی برای اجرا را نشان می دهد به طوری که وزن این گرهها مشخص کننده زمان اجرای واحد کاری مربوط خواهد بود.[7,6] این گراف همچنین مجموعه ای از یالهارا در بردارد که بیانگر روابط پیش نیازی بین واحدهای کاری هستند، به این صورت که وجود یال , - - بیان میکند تا زمانیکه واحد کاری اجرایش را به پایان نرساند، واحد کاری نمی تواند اجرایش را آغاز کند. این یالها وزن دار بوده و وزن هر یال نشان دهنده هزینه ارتباطات و ارسال پیغام میان دو واحد کاری و میباشد.[14,13,12] شکل 1 نمونهای از گراف وظایف را نشان میدهد.
.3 معرفی الگوریتم ژنتیک بهبود یافته HPGA
.1-3 ساختار کلی الگوریتم HPGA
در این بخش به معرفی ساختار کلی الگوریتم ژنتیک بهبود یافته با نام [11@ HPGA و مزایای این الگوریتم و دلایل استفاده از این الگوریتم برای زمانبندی گراف وظایف خواهیم پرداخت. این الگوریتم مبتنی بر جمعیت میباشد و الهام گرفته از نحوه بقای باکتریها در طبیعت است. به طور طبیعی در یک جمعیت از باکتریها برای بقا همواره قوی ترین عضو جمعیت به نسبتی از ژن-های خود را به سایر اعضای گروه تزریق میکند که به واسطه این عمل اعضای ضعیف موجود در جمعیت تقویت شده و سازگاری بیشتری با محیط پیدا می کنند. شکل2 بلوک دیاگرام الگوریتم HPGA را نشان میدهد. در ادامه هر یک از بخشهای الگوریتم HPGA را توضیح خواهیم داد.
.A آغاز کار الگوریتم با تولید جمعیت اولیه شروع می شود. به این منظور به تعداد اندازه جمعیت آرگومان ورودی الگوریتم بوده و بیانگر تعداد جمعیت می باشد.
.B در الگوریتم مذکور تنها عملگر موجود BC2 می باشد، و همیشه کروموزوم اهدا کننده، بهترین کروموزوم موجود در جمعیت خواهد بود. پس ضروری است که همیشه بهترین کروموزوم برای الگوریتم معلوم باشد. در این مرحله بهترین کروموزوم و بدترین برازش موجود در جمعیت اولیه را یافته و به صورت مجزا از جمعیت ذخیره می شود.
.C در این الگوریتم زمانی که عملگر BC را بر روی تمامی کروموزوم های جمعیت اعمال شد، یک نسل طی می شود. پس برای هر نسل الگوریتم زیر اعمال می شود:
.C1 شمارنده i که برای شمارش تعداد اعضای جمعیت استفاده می شود، مقدار صفر می گیرد. .C2 کروموزوم مر بوط به شماره i در جمعیت انتخاب می شود.
.C2 اگر کروموزوم انتخابی از لحاظ ساختاری با بهترین کروموزوم یکسان بود، یک کروموزوم جدید به صورت تصادفی تولید شده و به جای آن در جمعیت قرار میگیرد. این کروموزوم جدید از لحاظ مقدار برازش با بهترین و بدترین برازش مقایسه می شود و در صورتی که نسبت به آنها به ترتیب بهتر و یا بدتر بود مقادیر بهترین کروموزوم و یا بدترین برازش به روز می شود. و چنانچه مقدار بهترین کروموزوم تغییر کرد، الگوریتم به مرحله 6 می رود.
.C3 عملگر BC را بر روی بهترین کروموزوم به عنوان کروموزوم اهدا کننده و کروموزوم انتخابی به عنوان کروموزوم گیرنده اعمال می کنیم.
.C4 کروموزوم حاصل از عملگر فوق با کروموزوم انتخابی مقایسه می شود. در صورتی که کروموزوم حاصل دارای برازش بهتری نسبت به کروموزوم انتخابی باشد. کروموزوم جدید به جای کروموزوم انتخابی در جمعیت قرار می گیرد و در آن صورت کروموزوم مذکور با بهترین کرموزوم مقایسه می شود و در صورت بهتر بودن ارزش آن، کروموزوم تولیدی به عنوان بهترین کروموزوم انتخاب خواهد شد.ولی در صورتی که کروموزوم حاصل دارای برازش بدتر نسبت به کروموزوم انتخابی باشد، کروموزوم حاصل در جمعیت قرار نخواهد گرفت. در ادامه در این حالت در صورتی که برازش کروموزوم حاصل از بدترین برازش، بدتر باشد مقدار بدترین برازش به روز رسانی می شود.
