Title: A new strategy for multiprocessor scheduling of cyclic task graphs

Authors: Frode E. Sandnes, Oliver Sinnen

Addresses: Oslo University College, P.O. Box 4, St Olavs Plass, N-0130 Oslo, Norway. ' Department of Electrical and Computer Engineering, The University of Auckland, Private Bag 92019, Auckland, New Zealand

Abstract: A modular strategy for scheduling iterative computations is proposed. Iterative computations are represented using cyclic task graphs that are transformed into acyclic task graphs. These acyclic task graphs are subsequently scheduled using one of the many well known and high quality static scheduling strategies from the literature. Graph unfolding is not employed and the generated schedules therefore require less memory than schedules generated through graph unfolding. Further, the number of iterations does not need to be known at compile time. The paper experimentally quantifies how the task transformation affects the make span of the schedules and the effectiveness of the approach is compared to other methods including a graph unfolding strategy. A new more intuitive graph unfolding formulation is also presented.

Keywords: multiprocessor scheduling; task graphs; genetic algorithms; cyclic graphs; iterative computations; digital signal processing; high performance computing; networking; graph unfolding.

DOI: 10.1504/IJHPCN.2005.007868

International Journal of High Performance Computing and Networking, 2005 Vol.3 No.1, pp.62 - 71

Published online: 28 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article