Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]


Journal of Information Science and Engineering, Vol. 21 No. 2, pp. 309-326 (March 2005)

Scheduling Precedence Constrained Parallel Tasks
on Multiprocessors Using the Harmonic System
Partitioning Scheme

Keqin Li
Department of Computer Science
State University of New York
New Paltz, New York 12561, U.S.A.

We present an algorithm for scheduling precedence constrained parallel tasks on multiprocessors with noncontiguous processor allocation. The algorithm is called LLHm (Level-by-level and List scheduling using the Harmonic system partitioning scheme), where m ? 1 is a positive integer, which is a parameter for the harmonic system partitioning scheme. Three basic techniques are employed in algorithm LLHm. First, a task graph is divided into levels, and tasks are scheduled level by level to follow the precedence constraints. Second, tasks in the same level are scheduled using algorithm Hm developed in [16] for scheduling independent parallel tasks. The list scheduling method is used to implement algorithm Hm. Third, the harmonic system partitioning scheme is used for processor allocation. It is shown here that for wide task graphs and some common task size distributions, as the size of a computation and m increase, and as the task sizes become smaller, the average-case performance ratio of algorithm LLHm approaches one.

Keywords: asymptotic average-case performance ratio, harmonic system partitioning scheme, parallel task, precedence constraint, task scheduling, wide task graph

Full Text () Retrieve PDF document (200503_04.pdf)

Received March 25, 2003; revised May 21, 2004; accepted July 9, 2004.
Communicated by Chu-Sing Yang.