Efficient Parallel Multi-Objective Optimization for Real-time Systems Software Design Exploration

International audienceReal-time embedded systems may be composed of a large number of time constrained functions. When such systems are implemented on top of multitasks real-time operating systems (RTOS), the functions have to be assigned to tasks of the target RTOS. This is a challenging work due to the large number of valid candidate functions to tasks assignment solutions. Moreover, the impact of the assignment on the system performance criteria (often conflicting) should be taken intoaccount in the architecture exploration. The automation of the software design exploration by the use of metaheuristics such as multi-objective evolutionary algorithm (MOEA) is a suitable way to help the designers. Indeed, MOEAs approximate near optimal alternatives at a reasonable time when compared to an exhaustive and exact search method. However, for large scale systems (i.e having a huge number of functions) even a MOEA method is impractical due to the increased time required to solve a problem instance. This may raise a threat to the scalability of the software design exploration method. To tackle this problem, we present in this article a parallel implementation of the Pareto Archived Evolution Strategy (PAES) algorithm used as a MOEA for the software design exploration. The proposed parallelization method is based on the well-known master-slave paradigm. Additionally, it involves a new selection scheme in the PAES algorithm. Results of experimentations provide evidence that, on one hand, the parallel approach can considerably speed up the design exploration and the optimization processes. On the other hand, the proposed selection strategy improves the quality of obtained solutions as compared to the original PAES selection schema