Title: Load balanced scheduling of independent tasks in heterogeneous computing systems

Authors: P. Chitra; R. Sruthi

Addresses: Department of Computer Science and Engineering, Thiagarajar College of Engineering, Madurai-625004, Tamil Nadu, India. ' Department of Computer Science and Engineering, Thiagarajar College of Engineering, Madurai-625004, Tamil Nadu, India

Abstract: In real world, applications with different deadline criteria exist. Based on the nature of the deadline, the applications are categorised as mission-critical, firm and soft. In this paper, a load balanced algorithm is proposed for non-pre-emptively scheduling a bag of independent tasks with different priorities and deadlines on a heterogeneous computing system (HCS). Given the execution times of tasks, the load on the machine is the sum of these times for the tasks that are currently scheduled on the machine. The major goals of the proposed scheduler are to maximise the number of mission-critical tasks meeting their deadline, to maximise the total number of tasks meeting their deadline and to achieve a load balance on all the machines by minimising the load difference factor. The proposed scheduler is compared with the other algorithms available in the literature and proved to give significantly better performance.

Keywords: deadlines; bag of tasks; BoT; load balancing; independent tasks; priority; latest slack time; task scheduling; heterogeneous computing systems.

DOI: 10.1504/IJITCC.2012.048490

International Journal of Information Technology, Communications and Convergence, 2012 Vol.2 No.2, pp.187 - 203

Published online: 16 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article