The design space exploration (DSE) of fault-tolerant multiprocessor systems is very complex, as it contains three interacting NP-hard problems: 1) task hardening; 2) task mapping; and 3) task scheduling. In addition, replication-based task hardening can introduce new tasks, called replicas, into the system, enlarging the design space further. As a population-based global optimization algorithm, evolutionary algorithms (EAs) have been widely used to explore this huge design space over the last decade. However, as analyzed in this paper, the search space of previous works is highly redundant, resulting in poor efficiency and scalability. This paper proposes an efficient EA-based DSE method for the design of large-scale fault-tolerant multiprocessor systems. The main novelties of this paper include: 1) mapping exploration is explicitly separated, i.e., task mapping is optimized during the evolutionary search, while replica mapping is constructed heuristically according to the current co-synthesis state; 2) the design space of task hardening and task mapping are explored independently by a cooperative co-EA; and 3) as a complement to global search of EA, problem-specific local search operators are designed for both task hardening and task mapping, reducing the number of fitness evaluations required. Compared with the most relevant state-of-the-art method, the superiority of the proposed method is demonstrated using extensive experiments on a large set of benchmarks, e.g., 1.75\times \sim 2.50\times better results can be obtained on the benchmarks of 300 tasks and 30 processors. © 1997-2012 IEEE.
Bibliographical noteThis work was supported in part by the National Key Research and Development Program of China under Grant 2017YFC0804002, in part by the National Natural Science Foundation of China under Grant 91846111, Grant 91746209, and Grant 617611360, in part by the Program for Guangdong Introducing Innovative and Entrepreneurial Teams under Grant 2017ZT07X386, in part by the Shenzhen Peacock Plan under Grant KQTD2016112514355531, in part by the Science and Technology Innovation Committee Foundation of Shenzhen under Grant ZDSYS201703031748284, Grant JCYJ20170817112421757, and Grant JCYJ20180504165652917, and in part by the Program for University Key Laboratory of Guangdong Province under Grant 2017KSYS008.
- Bi-level optimization
- cooperative co-evolutionary algorithm (CCEA)
- design space exploration (DSE)
- multiprocessor system
- task mapping