Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible.

Parallel programs display two fundamentally different kinds of execution behavior: synchronous and asynchronous.Some methodologies, such as distributed data structures, are best suited to the construction of asynchronous programs.In this paper, we propose a methodology for synchronous parallel programming based on the notion of a coordination structure, a direct representation of the multidimensional dataflow patterns common to synchronous programs.We introduce Delirium, a language in which one can concisely express many useful coordination structures.

The authors outline a strategy for expressing coordination of sequential subcomputations, realized in the embedding language Delirium. In contrast to existing embedded languages, the notation clearly expresses the coordination framework of the application. All the coordination required to execute the program is expressed in a unified Delirium program. The program contains the computational code in the form of embedded operators, written using conventional tools. The proposed environment, which executes on a variety of shared-memory multi processors, provides tools which make it possible to develop parallel applications quickly. It supports a coordination model than can guarantee deterministic execution. Programmers who remain within the restrictions of the model can develop a program on a sequential machine and be certain that it will execute deterministically on a variety of parallel architectures.>