|
PatternLanguage |
Introduction |
A design pattern is a solution to a problem in a context. We find design patterns by looking at high-quality solutions to recurring problems. The design pattern is written down in a systematic way giving us a record of that quality-without-a-name that distinguishes a good solution from a poor one.
We can design complex systems in terms of patterns. At each decision point, the designer selects the appropriate pattern from a pattern catalog. Each pattern leads to other patterns, resulting in a final design as a web of patterns.
A structured catalog of patterns that supports this design style is called a pattern language. It is more than just a catalog of patterns. A pattern language embodies a design methodology and provides domain-specific advice to the designer.
The pattern language described here is intended for application programmers who want to design new programs for execution on parallel computers. The top-level patterns help the designer expose exploitable concurrency. The lower-level patterns guide the programmer as they decide how to take advantage of the problem's concurrency. Finally, the lowest-level patterns encode specific constructs that coordinate the execution of concurrent tasks.
Parallel programs are hard to write. There is plenty of concurrency in common algorithms, but few programmers take advantage of it. This is unfortunate, as there are many benefits to concurrent programs. They run faster on multiprocessor systems, manage resource contention better, and can provide improved responsiveness to the end user.
How can we make it easier for programmers to write parallel programs? One answer is to provide them with a pattern language. The pattern language encodes expert knowledge about parallel programming. The patterns include high-level algorithmic structures that commonly appear in good parallel software. They address the software reuse problem by helping programmer reuse software designs. Finally, the patterns provide a vocabulary for programmers when they design new parallel programs and talk about them to others.
A pattern language is designed with a particular class of problems in mind. Our pattern language is designed to help software developers write new applications for parallel computers. The top-level patterns help the designer decompose a problem into components that can run concurrently. (They also address the issue of whether the problem will benefit from a parallel solution.) The lower-level patterns help the designer express this concurrency in terms of parallel algorithms and finally at the lowest levels in terms of primitive coordination operations.
Experienced parallel programmers may choose to skip the top-level patterns and move directly to the AlgorithmStructure patterns. In this case, the top-level patterns are only used indirectly to help organize the low-level patterns.
While we try to handle any type of parallel computer system, when portability must be compromised, we specialize to shared-memory systems with a moderate number of processors.
Note that this pattern language addresses only concurrency. It does not replace more traditional design methodologies. Before programmers can work with this pattern language, they must understand the core objects, mathematics, and abstract algorithms involved with the problem.
In this pattern language, we refer to design activities that take place in the problem domain and outside of this pattern language as reasoning in the problem space. From time to time, this pattern language will point out areas where more work is required within the problem domain. The pattern language will use the results from problem space reasoning, but it will not help the programmer carry it out.
Our pattern language is organized around four core software design spaces, described in the Implementation section below.
The pattern language is structured as a linear list consisting of these four design spaces: starting at the FindingConcurrency space, followed by the AlgorithmStructure space, possibly passing through the SupportingStructures space, and at last leading to actual code with the ImplementationMechanisms design space patterns. Many programmers, however, will not traverse the list in this linear order. Experienced parallel programmers will jump in at the middle and go directly to the AlgorithmStructure or ImplementationMechanisms levels. Programmers new to parallel computing will spend a significant amount of time analyzing their problems with patterns from the FindingConcurrency design space.
The patterns in this language work with higher-level analysis in the problem domain. We assume that the designer has already analyzed the problem to define the basic data structures. We assume that the designer already knows the core subproblems or algorithms required by the problem. To this end, we created our pattern language so it would complement other pattern-based design systems.
The patterns are encoded using a consistent format, described in our Notation pattern. This format is based on the one used in the well-known "gang of four" book.
As mentioned above, the pattern language is implemented in terms of four categories of patterns (or design spaces). For each of these design spaces, there is an introductory document (written as a pattern) that describes how to use the patterns within the space. You can enter the pattern language at any level by going to the desired design space and opening the introductory pattern. If you want to start at the very top of the language, start with the GettingStarted pattern in the FindingConcurrency design space.
The pattern language is structured as a linear list consisting of these four design spaces: starting at the FindingConcurrency space, followed by the AlgorithmStructure space, possibly passing through the SupportingStructures space, and at last leading to actual code with the ImplementationMechanisms design space patterns. Many programmers, however, will not traverse the list in this linear order. Experienced parallel programmers will jump in at the middle and go directly to the AlgorithmStructure or ImplementationMechanisms levels. Programmers new to parallel computing will spend a significant amount of time analyzing their problems with patterns from the FindingConcurrency design space.
This design space is concerned with structuring the problem to expose exploitable concurrency. The designer working at this level focuses on high-level algorithmic issues and reasons about the problem to expose potential concurrency.
This design space is concerned with structuring the algorithm to take advantage of potential concurrency. That is, the designer working at this level reasons about how to use the concurrency exposed in the previous level. Patterns in this space describe overall strategies for exploiting concurrency.
This design space represents an optional intermediate stage between the AlgorithmStructure and ImplementationMechanisms design spaces. While it is sometimes possible to go directly from the AlgorithmStructure 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 AlgorithmStructure design space and the machine-oriented "patterns" of the ImplementationMechanisms 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 SharedQueue). We organize these patterns into the SupportingStructures design space.
This 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 SupportingStructures space, describe entities that strictly speaking are not patterns at all. We include them in our pattern language anyway, however, to provide a complete path from problem description to code, and we document them using our pattern notation for the sake of consistency.