Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow Mapping

Bo Yuan; Xiaofen Lu; Ke Tang; Xin Yao

2021-03

10.1145/3440246

ACM Transactions on Embedded Computing Systems   影响因子和分区

1539-9087

1558-3465

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 2x-3x better quality using less (1/2-1/3) optimization time.

Cooperative co-evolutionary algorithm multi-mode dataflow heterogeneous multiprocessor task mapping

SCI ; EI

英语

第一 ; 通讯

National Natural Science Foundation of China[61976111,61906082] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Program for Guangdong Introducing Innovative and Entrepreneurial Teams[2017ZT07X386] ; Shenzhen Science and Technology Program["KQTD2016112514355531","JCYJ20180504165652917"]

Computer Science

Computer Science, Hardware & Architecture ; Computer Science, Software Engineering

WOS:000644451500005

ASSOC COMPUTING MACHINERY

20211910309242

Computer aided design ; Data flow analysis ; Health ; Mapping ; NP-hard ; Response time (computer systems) ; Signal processing

Surveying:405.3 ; Medicine and Pharmacology:461.6 ; Information Theory and Signal Processing:716.1 ; Computer Applications:723.5

人工提交

Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

Bo Yuan,Xiaofen Lu,Ke Tang,et al. Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow Mapping[J]. ACM Transactions on Embedded Computing Systems,2021,20(3):1-25.

Bo Yuan,Xiaofen Lu,Ke Tang,&Xin Yao.(2021).Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow Mapping.ACM Transactions on Embedded Computing Systems,20(3),1-25.

Bo Yuan,et al."Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow Mapping".ACM Transactions on Embedded Computing Systems 20.3(2021):1-25.