This design space is under construction. Most of these patterns will be replaced soon..

Intent:

The patterns at this level represent an intermediate stage between the problem-oriented patterns of the AlgorithmStructure design space and the machine-oriented patterns of the ImplementationMechanisms design space.

Motivation:

The patterns of the AlgorithmStructure design space capture recurring solutions to the problem of turning problems into parallel algorithms. But these patterns in turn contain recurring solutions to the problem of mapping high-level parallel algorithms into programs using a particular parallel language or library. Those solutions are what the patterns in this space capture.

Two important groups of patterns in this space are those that represent program-structuring constructs and those that represent commonly-used shared data structures. Many of the elements of this design space are not usually thought of as patterns, and indeed some of them (SharedQueue, for example) would ideally be provided to the programmer as part of a framework of reusable software components. We nevertheless document them as patterns, for two reasons: First, documenting all the elements of our pattern language as patterns provides a consistent notation for the programmer. Second, the existence of such pattern descriptions of components provides guidance for programmers who might need to create their own implementations.

Applicability:

These patterns are meant to be used in implementing patterns in the AlgorithmStructure design space.

Structure:

Patterns in this space fall into two main groups.

Patterns in the first group describe program-structuring constructs i.e., constructs for structuring source code.

• SPMD (single program, multiple data) The computation consists of N units of execution in parallel. All N UEs execute the same program code, but each operates on its own set of data. A key feature of the program code is a parameter that differentiates among the copies.
• ForkJoin. A main process or thread forks off some number of other processes or threads that then continue in parallel to accomplish some portion of the overall work before rejoining the main process or thread.
• MasterWorker. A master process or thread sets up a pool of worker processes or threads and a task queue. The workers execute concurrently, with each worker repeatedly removing a task from the task queue and processing it, until all tasks have been processed or some other termination condition has been reached. In some implementations no explicit master is present.
• Spawn. A new process or thread is created, which then executes independently of its creator. This pattern bears somewhat the same relation to the others as GOTO bears to the constructs of structured programming.

The following figure contrasts the SPMD and ForkJoin patterns.

Patterns in the second group describe commonly-used shared data structures.

• SharedQueue. This pattern represents a "thread-safe" implementation of the familiar queue abstract data type (ADT), that is, an implementation of the queue ADT that maintains the correct semantics even when used by concurrently-executing units of execution.
• SharedCounter. This pattern, like the previous one, represents a "thread-safe" implementation of a familiar abstract data type, in this case a counter with an integer value and increment and decrement operations.
• DistributedArray. This pattern represents a class of data structures often found in parallel scientific computing, namely arrays of one or more dimensions that have been decomposed into subarrays and distributed among processes or threads.

Usage:

Patterns in this space are linked to patterns in higher and lower design spaces: They are frequently used to implement patterns in the AlgorithmStructure design space, and they are usually implemented in terms of patterns in the ImplementationMechanisms design space.

Consequences:

Implementation:

Examples:

Known Uses:

Related Patterns: