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

نیاز به سرعت و قدرت بالای محاسباتی در بسیاری از کاربردهای علمی به اندازه ای زیاد است که کامپیوترهای عادی توان پاسخگویی به آن را ندارند. بنابراین امروزه استفاده از قدرت محاسباتی چندین پردازنده برای دستیابی به سرعت مطلوب به عنوان یک اصل مطرح می باشد مساله تطبیق و زمانبندی وظایف در سیستمهای توزیع شده محاسباتی به دلیل استفاده بهینه از ماشینهای محاسباتی موجود و همچنین صرف زمان کمتر برای اجرای الگوریتم زمانبندی از اهمیت ویژه ای برخوردار است باتوجه به مشکل بودن پیجیدگی زیاد مساله زمانبندی گراف وظایف جهت اجرای روی سیستمهای چند پردازنده ای استفاده از الگوریتمهای کلاسیک چون برنامه نویسی و پویا و برگشت به عقب نیاز به زمان محاسبه زیادی دارد. به همین دلیل تلاشهای بسیاری برای یافتن راه حل نزدیک به بهینه با استفاده از پردازش تکاملی و بخصوص الگوریتم ژنتیک صورت پذیرفته است در این مقاله برای زمانبندی گراف وظایف، ابتدا مبادرت به خوشه بندی وظایف کرده و سپس با استفاده از الگوریتم ژنتیک به حل خوشه ها پرداخته شده است افزایش سرعت رسیدن به جواب و ایجاد تعادل کاری میان پردازنده ها از ویژگی های الگوریتم پیشنهاد می باشد. در نهایت نتایج عملی حاصل از پیاده سازی روش ارایه شده نشان می دهد که می توان یک زمانبندی مناسب و پایداری در زمان بسیار کمتری نسبت به الگوریتمهای مشابه پیدا کرد.

Keywords:

زمانبدی ایستای کارها , سیستمهای محاسباتی توزیع همگن , پردازش تکاملی , الگوریتم ژنتیک