Task Scheduling Based Redundant Task Allocation Method for the Multi-Core Systems with the DTTR Scheme

Hiroshi SAITO  Masashi IMAI  Tomohiro YONEDA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.7   pp.1363-1373
Publication Date: 2017/07/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Design Methodologies for System on a Chip)
Category: 
Keyword: 
multi-core systems,  task allocation,  fault patterns,  task scheduling,  reliability,  

Full Text: PDF(680.1KB)
>>Buy this Article


Summary: 
In this paper, we propose a redundant task allocation method for multi-core systems based on the Duplication with Temporary Triple-Modular Redundancy and Reconfiguration (DTTR) scheme. The proposed method determines task allocation of a given task graph to a given multi-core system model from task scheduling in given fault patterns. Fault patterns defined in this paper consist of a set of faulty cores and a set of surviving cores. To optimize the average failure rate of the system, task scheduling minimizes the execution time of the task graph preserving the property of the DTTR scheme. In addition, we propose a selection method of fault patterns to be scheduled to reduce the task allocation time. In the experiments, at first, we evaluate the proposed selection method of fault patterns in terms of the task allocation time. Then, we compare the average failure rate among the proposed method, a task allocation method which packs tasks into particular cores as much as possible, a task allocation method based on Simulated Annealing (SA), a task allocation method based on Integer Linear Programming (ILP), and a task allocation method based on task scheduling without considering the property of the DTTR scheme. The experimental results show that task allocation by the proposed method results in nearly the same average failure rate by the SA based method with shorter task allocation time.