JISE


  [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


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. 
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.


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

  Retrieve PDF document (JISE_200502_04.pdf)