Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43820
Title: Reliability-guaranteed task assignment and scheduling for heterogeneous multiprocessors considering timing constraint
Authors: Yi, J
Zhuge, Q
Hu, J
Gu, S
Qin, M
Sha, EHM
Keywords: Heterogeneous
Multiprocessor
Scheduling
System reliability
Task assignment
Issue Date: 2015
Publisher: Springer
Source: Journal of signal processing systems, 2015, v. 81, no. 3, p. 359-375 How to cite?
Journal: Journal of signal processing systems 
Abstract: Heterogeneous multiprocessors have become the mainstream computing platforms nowadays and are increasingly employed for critical applications. Inherently, heterogeneous systems are more complex than homogeneous systems. The added complexity increases the potential of system failures. This paper addresses this problem by proposing a reliability-guaranteed task assignment and scheduling approach for heterogeneous multiprocessors considering timing constraint. We propose a two-phase approach to solve this problem. In the first phase, we determine assignments for heterogeneous multiprocessors such that both reliability requirement and timing constraint can be satisfied with the minimum total system cost. Efficient algorithms are proposed to produce optimal solutions for simple-path and tree-structured task graphs in polynomial time. When the input graph is a directed acyclic graph (DAG), the task assignment problem is NP-Complete. In this situation, we first develop an Integer Linear Programming (ILP) formulation to generate optimal solutions. Then, we propose a polynomial-time heuristic algorithm to find near optimal solutions. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. Experimental results show that the proposed algorithms and the ILP formulation can effectively reduce the total cost compared with the previous work.
URI: http://hdl.handle.net/10397/43820
ISSN: 1939-8018 (print)
1939-8115 (online)
DOI: 10.1007/s11265-014-0958-0
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

21
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.