Task Scheduling Based Redundant Task Allocation Method for the Multi-Core Systems with the DTTR Scheme
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.7 pp.1363-1373
- Publication Date
- 2017/07/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1363
- Type of Manuscript
- Special Section PAPER (Special Section on Design Methodologies for System on a Chip)
- Category
Authors
Hiroshi SAITO
the University of Aizu
Masashi IMAI
Hirosaki University
Tomohiro YONEDA
National Institute of Informatics
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroshi SAITO, Masashi IMAI, Tomohiro YONEDA, "Task Scheduling Based Redundant Task Allocation Method for the Multi-Core Systems with the DTTR Scheme" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 7, pp. 1363-1373, July 2017, doi: 10.1587/transfun.E100.A.1363.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1363/_p
Copy
@ARTICLE{e100-a_7_1363,
author={Hiroshi SAITO, Masashi IMAI, Tomohiro YONEDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Task Scheduling Based Redundant Task Allocation Method for the Multi-Core Systems with the DTTR Scheme},
year={2017},
volume={E100-A},
number={7},
pages={1363-1373},
abstract={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.},
keywords={},
doi={10.1587/transfun.E100.A.1363},
ISSN={1745-1337},
month={July},}
Copy
TY - JOUR
TI - Task Scheduling Based Redundant Task Allocation Method for the Multi-Core Systems with the DTTR Scheme
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1363
EP - 1373
AU - Hiroshi SAITO
AU - Masashi IMAI
AU - Tomohiro YONEDA
PY - 2017
DO - 10.1587/transfun.E100.A.1363
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2017
AB - 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.
ER -
English
