Figure 2: Decision Tree for Selecting Algorithm Structure

Starting at the top of the tree, consider your concurrency and the major organizing principle, and use this information to select one of the three branches of the tree. Then follow the discussion below for the appropriate subtree.

2.3 Supporting Structures

This design space represents an optional intermediate stage between the Algorithm Structure and Implementation Mechanisms design spaces. While it is sometimes possible to go directly from the Algorithm Structure space to an implementation for a target programming environment, it often makes sense to construct the implementation in terms of other patterns that constitute an intermediate stage between the problem-oriented patterns of the Algorithm Structure design space and the machine-oriented "patterns" of the Implementation Mechanisms space. Two important groups of patterns in this space are those that represent program-structuring constructs (such as SPMD) and those that represent commonly used shared data structures (such as Shared Queue). We organize these patterns into the Supporting Structures design space.

The patterns of the Algorithm Structure 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 (Shared Queue, 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. 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.
Fork Join. 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.
Master Worker. 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.

Patterns in the second group describe commonly-used shared data structures.
Shared Queue. 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.
Shared Counter. 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.
Distributed Array. 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.

2.4 Implementation Mechanisms

The Implementation Mechanisms design space is concerned with how the patterns of the higher-level spaces are mapped into particular programming environments. We use it to provide pattern-based descriptions of common mechanisms for process/thread management (e.g., creating or destroying processes/threads) and process/thread interaction (e.g., monitors, semaphores, barriers, or message-passing). Patterns in this design space, like those in the Supporting Structures design space, describe entities that strictly speaking are not patterns at all. As noted previously, however, we include them in our pattern language to provide a complete path from problem description to code, and we document them using our pattern notation for the sake of consistency. The implementation of these patterns will vary greatly depending on the environment. Most of them correspond to primitives in one or more parallel programming environments.

3. Using the Divide and Conquer Algorithm For Partitioning

Consider the divide-and-conquer strategy employed in many sequential algorithms. With this strategy, a problem is solved by splitting it into subproblems, solving them independently, and merging their solutions into a solution for the whole problem. The subproblems can be solved directly, or they can in turn be solved using the same divide-and-conquer strategy, leading to an overall recursive program structure. The potential concurrency in this strategy is not hard to see: Since the subproblems are solved independently, their solutions can be computed concurrently, leading to a parallel program that is very similar to its sequential counterpart. The following figure illustrates the strategy and the potential concurrency.