Some signal processing and multimedia applications can be specified by synchronous dataflow (SDF) models. The problem of SDF mapping to a given set of heterogeneous processors has been known to be NP-hard and widely studied in the design automation field. However, modern embedded applications are becoming increasingly complex with dynamic behaviors changes over time. As a significant extension to the SDF, the multi-mode dataflow (MMDF) model has been proposed to specify such an application with a finite number of behaviors (or modes) and each behavior (mode) is represented by an SDF graph. The multiprocessor mapping of an MMDF is far more challenging as the design space increases with the number of modes. Instead of using traditional genetic algorithm (GA)-based design space exploration (DSE) method that encodes the design space as a whole, this article proposes a novel cooperative co-evolutionary genetic algorithm (CCGA)-based framework to efficiently explore the design space by a new problem-specific decomposition strategy in which the solutions of node mapping for each individual mode are assigned to an individual population. Besides, a problem-specific local search operator is introduced as a supplement to the global search of CCGA for further improving the search efficiency of the whole framework. Furthermore, a fitness approximation method and a hybrid fitness evaluation strategy are applied for reducing the time consumption of fitness evaluation significantly. The experimental studies demonstrate the advantage of the proposed DSE method over the previous GA-based method. The proposed method can obtain an optimization result with 2×-3× better quality using less (1/2-1/3) optimization time. © 2021 ACM.
Bibliographical noteThis work was supported by the National Natural Science Foundation of China (Grants No. 61976111 and No. 61906082), Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Entrepreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Science and Technology Program (Grants No. KQTD2016112514355531 and No. JCYJ20180504165652917).
- Cooperative co-evolutionary algorithm
- heterogeneous multiprocessor
- multi-mode dataflow
- task mapping