تخصيص چندهدفه منابع به صورت برون خط با استفاده از الگوريتم هاي تكاملي در سامانه هاي قابل بازپيكره بندي كامل

كارشناسي ارشد

انعطاف¬پذيري و توانايي بالاي اجرايي سامانه¬هاي قابل بازپيكره¬بندي، آنها را به ابزاري مناسب براي اجراي برنامه¬ها به صورت موازي و با مدت زمان اجراي كم تبديل كرده است. مساله زمان¬بندي در اين سامانه¬ها، به تعيين توالي اجراي وظايف براي اجرا بر روي فضاي محدود قابل بازپيكره¬بندي اطلاق مي¬گردد كه يك مساله NP-Complete است. در پژوهش انجام شده، به ارائه دو روش، ابتكاري و مبتني بر الگوريتم ژنتيك، براي حل مساله زمان¬بندي با در نظر گرفتن زمان اجراي وظايف، هزينه ارتباطي موجود بين وظايف و ميزان استفاده از منابع سخت¬افزاري پرداخته شده است. در روش ابتكاري ارائه شده، با ارائه يك تابع انتخاب¬گر به تعيين توالي اجرا مي¬پردازيم. در روش مبتني بر الگوريتم ژنتيك با استفاده از يك شيوه برچسب¬گذاري كروموزوم¬ها، ابتدا قيود تقدم و تاخر را رفع كرده و سپس با اعمال الگوريتم ژنتيك به صورت آزادانه به يافتن بهترين پاسخ براي مساله زمان¬بندي مي¬پردازيم. ارزيابي¬هاي صورت گرفته بر روي گراف¬هاي تصادفي و گراف¬هاي نمونه علاوه بر نمايش برتري روش مبتني بر الگوريتم ژنتيك نسبت به روش مشابه، تاثير توپولوژي گراف بر روي عملكرد سامانه را نيز به صورت مختصر بررسي مي¬كند. با انجام آزمايشات متعدد، محدوده كاري براي روش ارائه شده بر اساس دو ويژگي توپولوژيكي تعداد وظايف موازي سطح اول و طول مسير بحراني بدست مي¬آيد. روش ارائه شده در گراف¬هايي با تعداد وظايف موازي سطح اول و طول مسير بحراني كوتاه¬تر، بهترين پاسخ را از خود ارائه مي¬دهد و به طور متوسط نسبت به روش مشابه، در محدوده كاري حدود 23 درصد و در خارج محدوده كاري حدود 11 درصد بهبود در تابع شايستگي را به نسبت روش مشابه، مشاهده مي¬كنيم. واژه‌هاي كليدي: سامانه¬هاي قابل بازپيكره‌بندي، زمان¬بندي وظايف، تخصيص منابع، بهينه¬سازي چند هدفه، الگوريتم¬هاي تكاملي

192825

دانشگاه علم و صنعت ايران

الكترونيك ديجيتال

دكتر هادي شهريار شاه حسيني