language: en

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

Cong Fu and Tao Yang
Department of Computer Science University of California
Santa Barbara, CA 93106
{cfu,tyang}@cs.ucsb.edu

Abstract Automatic scheduling for directed acyclic graphs (DAG) and its applications for coarse-grained 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 that the automatically scheduled code has achieved scalable performance for these problems and the run-time overhead is small compared to the total execution time.

1 Introduction