سعید پارسا - دانشگاه علم و صنعت ایران
حبیب ایزدخواه - دانشگاه علم و صنعت ایران
امیر حسین زاده - دانشگاه علم و صنعت ایران

امروزه سیستمهای چندپردازنده ای کاربرد وسیعی در محاسبات موازی دارند . در این سیستمها زمانبندی مؤثر برای اجرای یک برنامه موازی جهت نائل شدن به کارآیی بالا امری حیاتی است . این زمانبندی باید به گونه ای انجام گیرد که بتواند زمان اجرای کل برنامه را ب ا توجه به زمان وظایف و ارتباط بین پردازنده ها، کمینه نماید . با توجه به NP-Hard بودن مسئله زمانبندی گراف وظایف، رویکرد های مبتنی بر روشهای قطعی در این زمینه کارا نخواهند بود؛ بنابر این استفاده از پردازش تکاملی و به طور عمده الگوریتمهای ژنتیک و الگوریتم های ترکیبی برای حل این مسئله موثر می باشد . با ترکیب الگوریتم ژنتیکی و آتاماتای یادگیر و تلفیق مفاهیم ژن، کروموزوم، اقدام و عمق، می توان به یک روش جستجوی کارا برای حل مسالهگراف وظایف دست یافت، بطوریکه با استفاده هم زمان از آتاماتای یادگیر و الگوریتم ژنتیک در فرآیند جستجو، سرعت رسیدن به جواب، افزایش چشم گیری پیدا می کند و از بدام افتادن الگوریتم در حداقل های محلی جلوگیری می شود . الگوریتم پیشنهادی در این مقاله کوششی است در جهت خودترمیمی، تولید مثل، جریمه و پاداش ( هدایت ) که از ویژگی های مهم الگوریتم ترکیبی است . رویکرد جدید در این الگوریتم علاوه بر ترکیبی بودن الگوریتم، بر پایه کوتاهتر کردن طول مسیر بحرانی و کاهش هزینه ارتباطات بین پردازنده ای است . در نهایت نتایج عملی حاصل از پیاده سازی روش ارایه شده نشان می دهد که می توان یک زمانبندی مناسب در زمان بسیار کمتری نسبت به الگوریتمهای مشابه پیدا کرد .

زمانبندی چند پردازنده ای، گراف وظایف و الگوریتمهای