High level support for divide-and-conquer parallelism

The authors present a simple language based on C for expressing divide-and-conquer computations. The language consists of a few simple extensions to C. It 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 is simplified significantly. A translator translates divide-and-conquer 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.