Process Scheduling in Heterogeneous Multiprocessor Systems Using Task Duplication

Process Scheduling in Heterogeneous Multiprocessor Systems Using Task Duplication

Pranay Chaudhuri (Heritage Institute of Technology, India) and Jeffrey Elcock (University of the West Indies, Barbados)
DOI: 10.4018/jbdcn.2010010104

Abstract

Scheduling tasks in heterogeneous parallel and distributed computing environments continues to be a challenging problem. In this paper, the authors investigate the Heterogeneous Earliest Finish Time (HEFT) algorithm, along with alternative scheduling policies for task prioritising phases and the Critical Path on a Processor (CPOP) for scheduling tasks on a heterogeneous multiprocessor system. The authors show 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 paper 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.
Article Preview
Top

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), jbdcn.2010010104.m02where the set of nodes V, represents the set of tasks, and the set of edges E, represents the communication between tasks. If jbdcn.2010010104.m03then jbdcn.2010010104.m04 is called the immediate predecessor of jbdcn.2010010104.m05, and jbdcn.2010010104.m06 is called the immediate successor of jbdcn.2010010104.m07. Given a task jbdcn.2010010104.m08 its set of immediate predecessors, denoted by jbdcn.2010010104.m09 is defined asjbdcn.2010010104.m10. If jbdcn.2010010104.m11 has two or more immediate predecessors then jbdcn.2010010104.m12 is referred to as a join task. The immediate successors of jbdcn.2010010104.m13 is denoted by jbdcn.2010010104.m14and is defined as jbdcn.2010010104.m15. jbdcn.2010010104.m16 is the set of all the descendants of taskjbdcn.2010010104.m17, and is defined asjbdcn.2010010104.m18. It is assumed that there is one entry task jbdcn.2010010104.m19and one exit task jbdcn.2010010104.m20for the DAG.

In both homogeneous and heterogeneous environments the process scheduling problem is NP-complete (Garey & Johnson, 1979; Graham, Lawler, Lenstra, & Kan, 1979; Kasahara & Narita, 1984; Ullman, 1975). In homogeneous environments several heuristics were proposed using both list scheduling without task duplication (Ahmad & Kwok, 1996; Wu & Gajski, 1990) 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 Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 16: 2 Issues (2020): Forthcoming, Available for Pre-Order
Volume 15: 2 Issues (2019)
Volume 14: 2 Issues (2018)
Volume 13: 2 Issues (2017)
Volume 12: 2 Issues (2016)
Volume 11: 2 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing