A new strategy for multiprocessor scheduling of cyclic task graphs. (29th September 2005)

• Record Type: Journal Article
• Authors: Sandnes, Frode E.; Sinnen, Oliver
• Is Part Of: International journal of high performance computing and networking. Volume 3:Number 1(2005)
• Page Start: 62
• Page End: 71
• Publication Date: 2005-09-29
• Subjects: multiprocessor scheduling -- task graphs -- genetic algorithms -- cyclic graphs -- iterative computations -- digital signal processing -- high performance computing -- networking -- graph unfolding; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

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.