Process Scheduling Using Task Duplication in Heterogeneous Distributed Systems

Process Scheduling Using Task Duplication in Heterogeneous Distributed Systems

Jeffrey Elcock (University of the West Indies, Barbados) and Pranay Chaudhuri (Heritage Institute of Technology, India)
Copyright: © 2012 |Pages: 13
DOI: 10.4018/978-1-61350-477-2.ch014
OnDemand PDF Download:
List Price: $37.50


Task scheduling in heterogeneous parallel and distributed computing environments continues to be one of the most challenging problems. In this chapter, the authors investigate the Heterogeneous Earliest Finish Time (HEFT) algorithm, along with its alternative scheduling policies for the task prioritising phases, and the Critical Path on a Processor (CPOP) for scheduling tasks on a heterogeneous multiprocessor system. It is shown that, by combining the HEFT algorithm selection policy with the task duplication strategy, it is possible to further reduce the schedule length produced by both HEFT and CPOP. The process scheduling algorithm presented in this chapter compares favourably with other algorithms that use a similar strategy. The proposed algorithm has a time complexity of ?(|V|2(p + d)), whererepresents the number of tasks, p represents the number of processors, and d the maximum in-degree of tasks.
Chapter Preview

1. Introduction

Process scheduling in a multiprocessor environment refers to the assignment of tasks to different processors, satisfying a given set of constraints, so that the schedule length or overall task completion time is minimized. A process (or an application) consists a set of interdependent tasks and may be represented by a directed acyclic graph (DAG), where the set of nodes V, represents the set of tasks, and the set of edges E, represents the communication between tasks. If then is called the immediate predecessor of , and is called the immediate successor of . Given a task its set of immediate predecessors, denoted by is defined as. If has two or more immediate predecessors then is referred to as a join task. The immediate successors of is denoted by and is defined as . is the set of all the descendants of task, and is defined as. It is assumed that there is one entry task and one exit task for the DAG.

In both homogeneous and heterogeneous environments the process scheduling problem is NP-complete (Garey & Johnson, 1979; Ullman, 1975; Graham, Lawler, Lenstra, & Kan, 1979; Kasahara & Narita, 1984). In homogeneous environments several heuristics were proposed using both list scheduling without task duplication (Wu & Gajski, 1990; Ahmad & Kwok, 1996) and list scheduling using task duplication (Ahmad & Kwok, 1998; Bansal, Kumar & Singh, 2003; Chaudhuri & Elcock, 2005; Park & Choe, 2002). In list scheduling, tasks are assigned a priority and based on that priority a task is scheduled. In task duplication, some tasks are deliberately scheduled on more than one processor to reduce inter-processor communication.

Complete Chapter List

Search this Book: