A graph transformational approach to the multiprocessor scheduling of iterative computations
A modular strategy for scheduling iterative computations is proposed. An iterative computation is represented using a cyclic task-graph. The cyclic task-graph is transformed into an acyclic task-graph. This acyclic task-graph is 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 effectiveness of the approach is compared to other methods including a graph unfolding strategy. In addition, the paper experimentally quantifies how the task transformation affects the make-span of the schedules.
multiprocessor scheduling iterative computation task-graphs genetic algorithms
Frode Eika Sandnes Oliver Sinnen
Dept.Computer Science Faculty of Engineering, Oslo University College Cort Adelers gate 30, N-0276 O INESC-ID Rua Alves Redol 9-2, Sala 236 1000-029 Lisboa, Portugal
国际会议
成都
英文
571-576
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）