20458

۲۰۴۵۸

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

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

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

۱۳۹۴

۱۳۹۷/۱۱/۲۴

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

برق

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

1398/02/15

An Offline Multi-objective Resource Allocation Method in Fully Reconfigurable Systems Using Evoloutionary Algorithms

2/13/2019 12:00:00 AM

Reconfigurable systems have been known for their flexibility and their strength in hardware execution in different fields of application. They can be utilized in a wide area of applications due to their adaptability in various conditions. However, managing the resources besides executing the tasks in the lowest time is one of the main challenges in these systems. Many factors affect the performance of the system such as execution time, communication cost, and required hardware resource. In this work, we propose a geneticbased scheduling algorithm considering execution time, communication cost and resource utilization of each task. In order to evaluate the proposed algorithm, a fitness function is represented and tested with a selector function to verify the mentioned function. Several experiments have been done on randomly generated DAGs and also a set of real applications DAGs to completely evaluate the proposed method. Moreover, experiments have been done based on two topological features of DAGs, the number of level one parallel tasks and critical path length. Moreover, we define a working area for the proposed method based on the topological features. The results were more satisfying in the DAGs with more level one parallel tasks and shorter critical paths. The results shows 11% and 23% fitness improvement outside and inside of the working area, relatively. Keywords: Reconfigurable Systems, Task Scheduling, Resource Allocation, Multiobjective optimization, Evolutionary Algorithms