会议专题

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

国际会议

Proceedings of The Fourth International Conference on Parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

成都

英文

571-576

2003-08-27(万方平台首次上网日期,不代表论文的发表时间)