Parallel Program Archetypes

An archetype is (a) a method of problem-solving, (b) a program design strategy associated with the method, (c) a collection of examplar problems to which the method can be applied, and a collection of reference implementations in different languages and runtime systems and on different architectures of each examplar problem. The program design strategy associated with an archetype has several parts including:

1. The software architecture of a class of programs, where the software architecture includes the control and data-flow structure of the program.
2. Methods of developing parallel and sequential applications from specifications. In many cases, the de facto specification is an existing sequential program that has to be parallelized; so, associated with an archetype are methods for parallelizing sequential code.
3. Frameworks for reasoning about correctness and performance of programs that are instances of the archetype.
4. Suggestions for test suites and debugging based on the software architecture of the archetype and from experience of others who have developed similar applications.
5. Suggestions for performance tuning on different target architectures. These suggestions are based on performance models as well as experience and measurement of performance of applications executing on different machines.
6. Detailed documentation of the archetype, and suggestions for tailoring the archetype documentation to get documentation specific for an application.
7. A description of other archetypes used by this archetype.

The Hypothesis

This work is predicated on the following hypothesis: a library of parallel program archetypes can be developed, and it can reduce the effort required to develop correct efficient parallel programs using languages, runtime systems and machines that the user chooses.

Experiments conducted over several years will tell whether the hypothesis has merit.