Pattern Name: Introduction

FindingConcurrency Design Space


Intent:

The patterns at this level support design activities in the FindingConcurrency design space. They are used to advise the programmer about how to locate exploitable concurrency and how to design algorithms at a high level to take advantage of this concurrency.

Also Known As:

Motivation:

Looking at a problem and finding concurrency that can be effectively exploited is a difficult problem. Once the exploitable concurrency has been found, designing algorithms that can take advantage of it is even harder.

Over the last few decades, considerable experience has been gained with concurrency. This experience, however, is concentrated in the hands of a few programmers, most of whom are involved with large scientific applications. Programmers addressing more general problems, many of which are driven by commercial concerns, have largely been left out of this field.

We believe that the expert knowledge acquired by programmers working on parallel scientific programs can be useful to a wider audience; organizing and presenting that expert knowledge is the goal of our pattern language.

The goal of the patterns within the FindingConcurrency design space is, as the name implies, to help designers find the concurrency in their problems. In this design space we ignore for the moment how concurrency will be implemented and focus on identifying program elements that can be executed concurrently and determining how they interact. This is the core knowledge we will use as we move to the design spaces concerned with implementing concurrency.

Applicability:

The patterns in this design space are used early in the design process. They help programmers understand how to expose the exploitable concurrency in their problems. Experienced designers might know how to do this from the beginning, in which case they should move directly to the patterns in the AlgorithmStructure design space.

You should not use these patterns until you have analyzed your problem using standard software engineering techniques. In other words, these patterns will not help you define the key data structures and computations in your algorithm. These patterns are concerned only with how to design parallel algorithms.

These patterns don't relate directly to code. What they do is help you:

Hence you can think of these patterns as collaborating very closely with the AlgorithmStructure patterns. One of their main functions is to help you select an appropriate pattern in the AlgorithmStructure design space.

Structure:

The major patterns in this design space are:

After working through these patterns, you will have the information you need to work with the AlgorithmStructure patterns.

The patterns in this design space are organized according to the following figure.

The main pathway through the patterns begins with the GettingStarted pattern and continues with the DecompositionStrategy and DependencyAnalysis patterns. It concludes with the DesignEvaluation pattern, which is not so much a pattern as it is a consolidation point for the analysis in this design space.

Branching off from the DecompositionStrategy and DependencyAnalysis patterns are groups of patterns that help with problem decomposition and dependency analysis. These patterns are connected to the main patterns by double-headed arrows to indicate that you may need to move back and forth between the patterns repeatedly as the analysis proceeds. For example, in a dependency analysis, the programmer may group the tasks one way and then figure out how this grouping affects the data that must be shared between the groups. This sharing may imply a different way to group the tasks, leading the programmer to revisit the tasks grouping.

Consequences:

Decisions made at this level of the design process have far-reaching impact. The overall software architecture of the parallel algorithm will follow from decisions made while using these patterns. A poor decision at this level may require a great deal of work to undo.

Be very careful when making decisions at this level. Think through different scenarios with the design and explore important boundary cases before pushing the design too far.