| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] |
¡@
Keqin Li
Department of Computer Science
State University of New York
New Paltz, New York 12561, U.S.A.
E-mail: lik@newpaltz.edu
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.
Received March 25, 2003; revised May 21, 2004; accepted July 9, 2004.
Communicated by Chu-Sing Yang.