Run-time Techniques for Exploiting Irregular Task Parallelism on Distributed Memory Architectures

Automatic scheduling for directed acyclic graphs (DAG) and its applications for coarsegrained irregular problems such as large n-body simulation have been studied in the literature. However solving irregular problems with mixed granularities such as sparse matrix factorization is challenging since it requires efficient run-time support to execute a DAG schedule. In this paper, we investigate run-time optimization techniques for executing general asynchronous DAG schedules on distributed memory machines. Our solution tightly integrates the run-time scheme with a fast communication mechanism to eliminate unnecessary overhead in message buffering and copying. We discuss a consistency model incorporating the above optimizations, and taking advantage of task dependence properties to ensure the correctness of execution. We demonstrate the applications of this scheme in sparse factorizations and triangular solver for which actual speedups are hard to obtain. Our experiments on Meiko CS-2 show..