Load balanced reliable task scheduling algorithm for heterogeneous systems

Abstract

In a heterogeneous system, processor and network failure are inevitable and can have adverse effect on the complex applications executing on the systems. To reduce the rate of these failures, matching and scheduling algorithms should take into account the objectives of minimizing schedule length (makespan) and reducing the probability of failure. Equitable distribution of workload over resources contributes in reducing the probability of failure. The Heterogeneous Earliest Finish Time (HEFT) algorithm has been proved as a performance effective task scheduling algorithm, addressing the objective of minimizing makespan. Reliable Dynamic Level Scheduling (RDLS) algorithm is a bi-objective scheduling algorithm that maximizes the reliability more effectively. Though the reliable version of HEFT algorithm (RHEFT) considers failure rate in scheduling decision, the improvement in reliability is less, compared to that of RDLS. To overcome this deficiency, we propose to incorporate the task–processor pair finding step of RDLS in HEFT algorithm, since it meets both the objectives of minimizing the makespan and maximizing the reliability. We define the load on a processor as the amount of time the processor is engaged in completing the scheduled subtasks. In this paper, a modification to the HEFT is proposed as a new algorithm called Improved Reliable HEFT (IRHEFT) for minimizing the schedule length, balancing the load and maximizing the reliability of schedule. The algorithm is compared for its performance with RDLS algorithm for randomly generated task graphs and a real application task graph.