Multi-objective redundancy hardening with optimal task mapping for independent tasks on multi-cores

Bo YUAN, Bin LI, Huanhuan CHEN, Zhigang ZENG, Xin YAO

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

1 Citation (Scopus)

Abstract

The rate of transient faults has increased significantly as the technology scales up. The tolerance of transient faults has become an important issue in the system design. Dual modular redundancy (DMR) and triple modular redundancy (TMR) are two commonly used techniques that can achieve fault detection and masking through executing redundant tasks. As DMR and TMR have different time and cost overheads, we must carefully determine which one should be used for each task (i.e., task hardening) to achieve the optimal system design. Furthermore, for multi-core systems, the system-level design includes the allocation of cores for the tasks (i.e., task mapping) as well. This paper aims at task hardening and mapping simultaneously for independent tasks on multi-cores with heterogeneous performances, in order to minimize the maximum completion time of all tasks (i.e., makespan). We demonstrate that once task hardening is given, task mapping of independent tasks can be achieved by employing min–max-weight perfect matching with a polynomial time complexity. Besides, as there is a trade-off between cost and time performance, we propose a multi-objective memetic algorithm (MOMA)-based task hardening method to obtain a set of solutions with different numbers of cores (i.e., costs), so the designer can choose different solutions according to different requirements. The key idea of the MOMA is to incorporate problem-specific knowledge into the global search of evolutionary algorithms. Our experimental studies have demonstrated the effectiveness of the proposed method and have shown that by combining the results of MOMA and MOEA we can provide a designer with a highly accurate set of solutions within a reasonable amount of time. © 2019, The Author(s).
Original languageEnglish
Pages (from-to)981-995
Number of pages15
JournalSoft Computing
Volume24
Issue number2
Early online date27 Mar 2019
DOIs
Publication statusPublished - Jan 2020
Externally publishedYes

Bibliographical note

This work was supported by the National Key R&D Program of China (Grant No. 2017YFC0804002), the Royal Society (NA160545), the National Natural Science Foundation of China (Grant Nos. 61503357 and 617611360), the Program for Guangdong Introducing Innovative and Entrepreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), the Science and Technology Innovation Committee Foundation of Shenzhen (Grant Nos. ZDSYS201703031748284, JCYJ20170307105521943, JCYJ20170817112421757 and JCYJ20180504165652917), and the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008).

Keywords

  • Fault tolerance
  • Memetic algorithms
  • Multi-cores
  • Multi-objective optimization
  • Task hardening
  • Task mapping

Fingerprint

Dive into the research topics of 'Multi-objective redundancy hardening with optimal task mapping for independent tasks on multi-cores'. Together they form a unique fingerprint.

Cite this