High Level Support For Divide-and-Conquer Parallelism

In this paper we present a simple language for expressing divide and conquer computations. The language allows for many variations in the standard divide and conquer paradigm. It is implemented using the Chare Kernel parallel programming system. The Chare Kernel supports dynamic creation of work with dynamic load balancing strategies, and machine independent execution. As a result, implementation of languages and systems such as that described in this paper is simplified significantly. A translator translates divide-and-conquer programs to Chare Kernel programs, handling details of synchronization and communication automatically. The design of the language is presented, followed by a description of its implementation, and performance results on many parallel machines, including NCUBE/two, iPSC/2, and the Sequent symmetry. User programs do not have to be changed to run on any of these machines. 1 Introduction The dramatic advances in parallel computer architectures have led to an expec..