Distributed extension of the parallel graph reduction. GRACE: compact and efficient dynamic parallelization technology for the heterogeneous computing systems

摘要

Parallel graph reduction (PGR) is a powerful and well known method for dynamic parallelization of programs. Its variants (even without direct references) are used in a number of parallel computation environments, such as Cilk and SISAL. These implementations are very efficient for SMP-computers, but do not succeed in distributed computation environments due to the following reason: they do not extend mathematical essence of parallel graph reduction approach to the distributed execution model. The most significant idea of GRA CE (Graph Reduction Approach for the Cluster Environments) is to carefully extend parallel graph reduction method to reach efficient usage of heterogeneous (and even hybrid) computational systems. It leads to compact and efficient implementation, which can be used as the basis for wide range of high-performance applications. In this paper we describe most important ideas of distributed PGR extensions and algorithms used in the current GRACE implementation.