Finding Concurrency

Before starting to work with the patterns in this design space, the algorithm designer must first consider the problem to be solved and make sure the effort to create a parallel program will be justified: Is the problem sufficiently large, and the results sufficiently significant, to justify expending effort to solve it faster? If so, the next step is to make sure the key features and data elements within the problem are well understood. Finally, the designer needs to understand which parts of the problem are most computationally intensive, since it is on those parts of the problem that the effort to parallelize the problem should be focused.

Once this analysis is complete, the patterns in the Finding Concurrency design space can be used to start designing a parallel algorithm. The patterns in this design space can be organized into three groups as shown in the figure.

$ b$ ,

Decomposition Patterns There are two decomposition patterns. These patterns are used to decompose the problem into pieces that can execute concurrently.

Task Decomposition
How can a problem be decomposed into tasks that can execute concurrently?

Data Decomposition
How can a problem's data be decomposed into units that can be operated on relatively independently?

Dependency Analysis Patterns. This group contains three patterns that help group the tasks and analyze the dependencies among them

Group Tasks
How can the tasks that make up a problem be grouped to simplify the job of managing dependencies?

Order Tasks
Given a way of decomposing a problem into tasks and a way of collecting these tasks into logically related groups, how must these groups of tasks be ordered to satisfy constraints among tasks?

Data Sharing
Given a data and task decomposition for a problem, how is data shared among the tasks?

Nominally, the patterns are applied in this order. In practice, however, it is often necessary to work back and forth between them, or possibly even revisit the decomposition patterns.

The Design Evaluation Pattern.
Is the decomposition and dependency analysis so far good enough to move on to the Algorithm Structure design space, or should the design be revisited?