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

Bo YUAN, Xiaofen LU, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

2 Citations (Scopus)

Abstract

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.
Original languageEnglish
Article number3440246
JournalTransactions on Embedded Computing Systems
Volume20
Issue number3
Early online date27 Mar 2021
DOIs
Publication statusPublished - 31 May 2021
Externally publishedYes

Bibliographical note

This 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).

Keywords

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

Fingerprint

Dive into the research topics of 'Cooperative Coevolution-based Design Space Exploration for Multi-mode Dataflow Mapping'. Together they form a unique fingerprint.

Cite this