Unconstrained static scheduling with communication weights

✍ Scribed by Vivek Sarkar

• Book ID: 102397816
• Publisher: Springer US
• Year: 2002
• Tongue: English
• Weight: 179 KB
• Volume: 5
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/jos.114

✦ Synopsis

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 ÿrst 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 ÿrst step. We also present some experimental results obtained by applying di erent scheduling algorithms to 150 randomly generated task graphs.