Mapping Iterative Task Graphs on Distributed Memory Machines.
Tao Yang, Cong Fu, Apostolos Gerasoulis, Vivek Sarkar · 1995
This paper addresses the problem of scheduling iterative task graphs on distributed memory architectures with nonzero communication overhead. The proposed algorithm incorporates techniques of software pipelining, graph unfolding and directed acyclic graph scheduling. The goal of optimization is to minimize overall parallel time, which is achieved by balancing processor loads, exploring task parallelism within and across iterations, overlapping communication and computation, and eliminating unnecessary communication. This paper gives a method to execute static schedules, studies the sensitivity of run-time performance when weights are not estimated accurately at compile-time, and presents experimental results to demonstrate the effectiveness of this approach. 1 Introduction Many scientific applications can be viewed as the repeated execution of a set of computational tasks and can be modeled by iterative task graphs (ITGs). Mapping weighted iterative task graphs on messagepassing archi...