ترکیب آتاماتای مهاجرت اشیا و الگوریتم ژنتیک برای زمانبندی گراف وظایف در معماری چند پر - Artificial Intelligence

**Astaraki** · ۱۲-۱۹-۱۳۸۸, ۰۳:۲۰ بعد از ظهر

ترکیب آتاماتای مهاجرت اشیا و الگوریتم ژنتیک برای زمانبندی گراف وظایف در معماری چند پردازنده ای

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