The Parallel Asynchronous Recursion Model

This extended abstract introduces and evaluates a new model of parallel computation, called the Parallel Asynchronous Recursion (PAR) model. This model offers distinct advantages to the program designer and the parallel machine architect, while avoiding some of the PRAM's shortcomings. The PAR model can be thought of as a procedural programming language augmented with a process control structure that can, in parallel, recursively fork independent processes and merge their results. The unique aspect of the PAR model lies in its memory semantics, which differ substantially from both global and distributed memory models. It provides a high level of abstraction that removes the tasks of explicit processor scheduling and synchronization. Efficient simulations of the PAR model on well established models confirm that the PAR model's advantages can be obtained at a reasonable cost. 1. Introduction Though the PRAM is a widely studied model of parallel computation, it is not universally accepte..