Unconstrained static scheduling with communication weights

Abstract

In this paper, we present some new theoretical results for unconstrained static scheduling with communication weights, i.e. multiprocessor scheduling of tasks with no precedence constraints, but with arbitrary communication and computation weights. The results are obtained for a cost function that extends completion time with a simple model of communication overhead. This cost function and its variants have been studied in past work. The main results of this paper are as follows: (1) it is shown that no single-pass priority-list algorithm can yield a constant performance bound for this cost function, (2) a two-pass approach is proposed as a heuristic solution, (3) the two-pass approach is shown to have a performance bound of (1 + δ), where δ is the performance bound for the first step (scheduling on an unbounded number of processors), and (4) it is shown that no greedy-merge clustering algorithm can deliver a constant performance bound, δ, even for the first step. We also present some experimental results obtained by applying different scheduling algorithms to 150 randomly generated task graphs. Copyright © 2002 John Wiley & Sons, Ltd.