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

摘要

We present an algorithm for scheduling precedence constrained parallel tasks on multiprocessors with noncontiguous processor allocation. The algorithm is called LLH_m (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. There are three basic techniques employed in algorithm LLH_m. 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 H_m developed in [13] for scheduling independent parallel tasks. The list scheduling method is used to implement algorithm H_m. Third, the harmonic system partitioning scheme is used as the processor allocation strategy. It is shown that for wide task graphs and some common task size distributions, as the size of a computation and m increase and the task sizes become smaller, the average-case performance ratio of algorithm LLH_m approaches one.