Heuristic Algorithms for Scheduling Iterative Task Computationson Distributed Memory Machines

Many partitioned scientific programs can be modeled as iterative execution ofcomputational tasks, represented by iterative task graphs (ITGs). In thispaper, we consider the symbolic scheduling of ITGs on distributed memoryarchitectures with nonzero communication overhead without searching the entireiteration space. An ITG may or may not have dependence cycles and we proposeheuristic algorithms for mapping cyclic and acyclic ITGs, which incorporatetechniques of software pipelining, graph unfolding, directed acyclic graph(DAG) scheduling and load balancing.We provide an analysis for computing near-optimal unfolding factors andcomparing the performance of the proposed heuristic algorithms with the optimalsolutions. We also study the stability of run-time performance when weightsare not estimated accurately at compile-time. Our experiments study thescheduling performance of solving several scientific computing problems andanalyze the effectiveness of optimization techniques used in our methods. Wealso present experimental results for mapping SOR-based iterative computationin solving sparse and banded matrix systems, and compare our approach with themulti-coloring method.