يك الگوريتم زمان‌بندي وظيفه چندهدفه بر اساس الگوريتم ژنتيك براي طراحي سيستم‌هاي نهفته

A Task Mapping and Scheduling Algorithm based on Genetic Algorithm for Embedded System Design

طراحان سيستمهاي نهفته با الزامات و اهداف متعددي در طراحي (مانند زمان اجرا، انرژي مصرفي و قابليت اطمينان) مواجه هستند. ازآنجاكه در بيشتر مواقع، تلاش براي برآوردن يكي از اين الزامات در تناقض با دستيابي به ديگر الزامات طراحي است، استفاده از رويكردهاي چندهدفه در مراحل مختلف طراحي دستگاه‌هاي نهفته ازجمله زمان‌بندي وظايف امري اجتناب ناپذير به نظر مي رسد. در اين مقاله، يك روش زمان‌بندي وظيفه ايستاي چندهدفه براي طراحي دستگاه‌هاي نهفته ارائه‌شده است. در اين روش، وظايف به‌صورت يك گراف مدل شده و با در نظر گرفتن يك زيرساخت سخت‌افزاري براي سيستم نهفته، روشي براي نگاشت و زمان‌بندي وظايف بر روي معماري سخت افزاري پيشنهاد مي‌شود. به‌منظور مديريت وابستگي بين وظيفه ها در گراف وظايف، از يك روش بخش بندي استفاده‌شده است كه در هر بخش، وظايفي كه مي‌توانند به‌طور هم‌زمان اجرا شوند مشخص‌شده و در فرآيند زمان‌بندي در نظر گرفته مي شوند. در اين روش زمان‌بندي، پارامترهاي زمان اجراي وظايف، انرژي مصرفي و قابليت اطمينان به‌عنوان اهداف بهينه سازي طي يك الگوريتم بهينه‌سازي ژنتيك بهينه مي‌گردند. نتايج شبيه سازي ها نشان مي‌دهد كه روش پيشنهادي با در نظر گرفتن اهداف مختلف طراحي در مقايسه با روش هاي مشابه پيشين مانند EAG-TA، در زمان اجراي وظايف، انرژي مصرفي و قابليت اطمينان به ترتيب 21.4، 19.2 و 20 درصد بهبود داشته است. استفاده از يك راهبرد بهينه‌سازي چندهدفه اين امكان را فراهم مي‌كند كه طي مرحله نگاشت و زمان‌بندي، گزينه‌هاي متعدد طراحي پيش روي طراح قرار گيرد تا بتواند بين پارامترهاي مختلف طراحي سيستم (سخت‌افزاري/نرم‌افزاري) موازنه مدنظر خود را انجام دهد.

Embedded system designers face numerous design requirements and objectives (such as runtime, power consumption and reliability). Since meeting one of these requirements mostly contradicts other design requirements, it seem to be inevitable to apply multi-objective approaches in various stages of designing embedded systems, including task scheduling step. In this paper, a multi-objective task mapping and scheduling in the design stage of the embedded system is presented. In this method, tasks are represented by task graphs assuming that the hardware architecture platform is given and determined. In order to manage the dependencies between tasks in the task graph, a segmentation method is used, in which the tasks that can be executed simultaneously are specified in a segment and is considered in the scheduling process. In the proposed method, the task mapping and scheduling problem is modeled as a genetic algorithm-based multi-objective optimization problem considering execution time, energy consumption, and reliability. In comparison to similar previous works, the proposed scheduling method respectively provides 21.4%, 19.2%, and 20% improvement in execution time, energy consumption, and reliability. Applying a multi-objective helps the designer to pick out the best outcome according to different considerations.