Trading off execution time for reliability in scheduling precedence-constrained tasks in heterogeneous computing

Abstract

This paper investigates the problem of matching and scheduling of an application, which is composed of tasks with precedence constraints, to minimize both execution time and probability of failure of the application in a heterogeneous computing system. In general, however, it is impossible to satisfy both objectives at the same time because of conflicting requirements. The best one can do is to trade off execution time for reliability or vice versa, according to users' needs. Furthermore, there is a need for an algorithm which can assign tasks of an application to satisfy both of the objectives to some degree. Motivated from these facts, two different algorithms, which are capable of trading off execution time for reliability, are developed. To enable the proposed algorithms to account for the reliability of resources in the system, an expression which gives the reliability of the application under a given task assignment is derived. The simulation results are provided to validate the performance of the proposed algorithms