Patterns for Parallel Software Design

Jorge Luis Ortega-Arjona

• Publisher: Wiley
• Year: 2010
• ISBN:
  9780470970874
• Edition: 1
• Topic: Computer Science
• Subtopic: Object Oriented Programming
• Index: Computer Science

Essential reading to understand patterns for parallel programming

Software patterns have revolutionized the way we think about how software is designed, built, and documented, and the design of parallel software requires you to consider other particular design aspects and special skills. From clusters to supercomputers, success heavily depends on the design skills of software developers.

Patterns for Parallel Software Design presents a pattern-oriented software architecture approach to parallel software design. This approach is not a design method in the classic sense, but a new way of managing and exploiting existing design knowledge for designing parallel programs. Moreover, such approaches enhance not only build-time properties of parallel systems, but also, and particularly, their run-time properties.

• Features known solutions in concurrent and distributed programming, applied to the development of parallel programs
• Provides architectural patterns that describe how to divide an algorithm and/or data to find a suitable partition and link it with a programming structure that allows for such a division
• Presents an architectural point of view and explains the development of parallel software

Patterns for Parallel Software Design will give you the skills you need to develop parallel software.

CHAPTER 1

Software Patterns

‘Patterns expose knowledge about software construction that has been gained by experts over many years. All work on patterns should therefore focus on making this precious resource widely available. Every software developer should be able to use patterns effectively when building software systems. When this is achieved, we will be able to celebrate the human intelligence that patterns reflect, both each individual pattern and in all patterns in their entirety.’

F. Buschmann, R. Meunier, H. Rohnert, P. Sommerlad and M. Stal
A Final Remark’, Pattern-Oriented Software Architecture (1996), p. 428.

This introductory chapter about software patterns presents some basic concepts, such as definition, description, languages and systems and categories. This chapter also addresses key questions related to software patterns, such as ‘What are patterns?’ and ‘How are patterns documented?’

1.1 The Concept of a Software Pattern

Current interest in software patterns was originally inspired by the work of the British architect Christopher Alexander and his colleagues [AIS+77] [Ale79]. Alexander was the first to describe what he called a pattern language, which mapped various problems in building architecture to proven solutions. In Alexander’s terms, a pattern is ‘a three-part rule, which expresses a relation between a certain context, a problem, and a solution’ [Ale79].

Since the mid-1990s, pattern-based design has been adapted for use by the software development community. The resulting software patterns are literary forms that describe recurring designs used in software development. They have been used extensively in the development of object-oriented systems, and have been highly effective in capturing, transferring and applying design knowledge at different levels of software design [Ram98]. In general, patterns exist in any context in which there are design decisions to be made.

Software patterns focus on capturing and systematizing successful experience and techniques used in previous software development. They describe successful solutions to common software problems with the intention of creating handbooks of good design and programming practices for software development. Their long term goal is to gather design experience and techniques for software development. Even though much work remains before that goal is reached, two decades of applying pattern-oriented software architectures and techniques have shown that software patterns help developers reuse successful software practices [POSA1] [POSA2] [POSA4] [POSA5]. Moreover, they help developers to communicate their experience better, reason about what they do and why they do it.

Software patterns are found at every level of software development: from the programming language level (the ‘language idioms’) to entire software systems, known as ‘architectural patterns’. They are also commonly used to describe software processes. Moreover, classic algorithms and data types can be considered as programming-language level pattern-like entities. In particular, software patterns are viewed as well-documented design descriptions for software design.

What is a Pattern?

Defining a software pattern is not easy. Inside the pattern community it is generally accepted that a pattern is ‘a recurring solution to a standard problem’ [Cop94] [Gab96]. In a wider sense, a pattern is ‘a way to capture and systemize proven practice in any discipline’ [AIS+77] [Ale79].

For our purposes we consider a software pattern as a function-form relation that occurs in a context, where the function is described in problem domain terms as a group of unresolved trade-offs or forces, and the form is a structure described in solution domain terms that achieves a good and acceptable equilibrium among those forces. This definition of a software pattern is consistent with the previous definitions and relates software patterns with software design.

In general, the concept of software patterns is not confined to a particular software domain. As software patterns express recurring designs, they can be used to document design decisions at any level in any software domain. This generality is particularly important for parallel software design: software patterns are useful in documenting the design decisions in any aspects of a complete parallel system: for example, to document hardware systems or subsystems, communication and synchronization mechanisms, partitioning and mapping policies and so on.

An Example: The Manager-Workers Pattern

To show how software patterns are applied to parallel programming, a well-known example is presented in this section: the Manager-Workers pattern. This is a simple and classical example, presented in many parallel programming books and publications [Hoa78] [And91] [FP92] [Fos94] [KSS96] [Har98] [And00] [Ort04].

The Manager-Workers organization is one of the simplest patterns for parallel programs. It is often used to solve problems in which a single algorithm is applied independently to many different pieces of data. A manager (usually associated with the main process of the parallel program) partitions work (commonly the pieces of data to process) among a set of workers. These are launched together and executed simultaneously, assigning each one a separate portion of work. The manager waits for all workers to complete their work, then continues. A diagram showing the structure of the Manager-Workers pattern is shown in Figure 1.1.

Figure 1.1: A Manager-Workers organization block diagram

The Manager-Workers pattern describes a simple kind of parallel execution, used when the amount of data on which to operate is known in advance and where it is easy to partition such data into roughly equal parts whose operation does not depend on each other. The absence of data dependencies is a key requirement that ensures no synchronization is required among the workers. A summary of the Manager-Workers pattern [Ort04] is shown in Figure 1.2.

Figure 1.2: A summary of the Manager-Workers pattern

To illustrate an application of the Manager-Workers pattern, we present a case study based on the Polygon Overlay problem [Ort04] [WL96]. The objective of this case study is to obtain the overlay of two rectangular maps, A and B, each covering the same area, which is decomposed into a set of non-overlapping rectangular polygons. This type of problem is common in geographical information systems, in which one map represents, for example, soil type, and another, vegetation. Their conjunction is thus an overlay that represents how combinations of soil type and vegetation are distributed. Overlaying both maps therefore creates a new map consisting of the non-empty polygons in the geometric intersection of A and B.

To simplify this problem for practical purposes, all polygons are considered as non-empty rectangles, with vertices on a rectangular integer grid [0...N]x[0...M] (Figure 1.3). Both input maps have identical extents, each completely covered by its rectangular decomposition.

Figure 1.3: The polygon overlay problem for two maps A and B

A sequential solution to this problem iterates through each polygon belonging to A and finds all intersections with any polygon in B. Although this is an effective solution, it can run slowly, depending on the number of polygons into which each map is divided. It is possible to obtain intersections in parallel, however, since the overlaying operation of two polygons can be performed potentially independently of the overlay of any other two polygons.

For experienced parallel programmers, developing a parallel solution for the Polygon Overlay problem is straightforward: simply link the concrete requirements of functionality of the problem with a concrete solution based on a parallel technology Moreover, since experienced programmers understand typical structures of parallel programs, they would immediately recognize a solution to the problem based on the Manager-Workers pattern, as well as its partitioning policies, its communication and synchronization mechanisms, its mapping strategies and so on.

Nevertheless, consider novice parallel programmers, who might learn about the Manager-Workers pattern and parallel systems by reading the literature [And91] [Fos94] [Har98] [And00], but cannot adequately and efficiently exploit such knowledge to solve the Polygon Overlay problem. The main problem faced by novice parallel programmers is their lack of design experience, which could prevent them from linking the functionality of the problem with a parallel programming solution. The typical effects of this lack of experience are design problems that might be detected late in subsequent development, for example in the form of poor performance or deadlocks during execution.

The main objective of this book is to show how a solid understanding of groups of software patterns for parallel programming during the design process can enable novice programmers to leverage the knowledge of experienced parallel programmers. Such novices must find pattern(s) that describe (or nearly describe) their problem, understand whether the forces match the constraints of such a problem, grasp the solution description(s) and map them to a design. During this process parallel programmers can start to formulate their own body of experience. Although this process may sound simple, we will show how it works for the Polygon Overlay problem using the Manager-Workers pattern as a design guide.

As described in the Context section of the Manager-Workers pattern (Figure 1.2), we are just about to start the design of a parallel program. In parallel programming, the programming language and the parallel hardware are typically given resources. Nevertheless, let us assume that the Polygon Overlay problem involves tasks of a scale that would be unrealistic or not cost-effective for a sequential system to handle (Figure 1.2). The solution to the Polygon Overlay problem thus lends itself to using parallelism, as explained later when describing the parallel solution.

Note also that the Polygon Overlay problem matches the Problem description provided by the pattern (Figure 1.2), since it involves only a single overlaying operation that is performed repeatedly on all the rectangles, which are ordered inside each map. The rectangles can be overlaid without a specific order. It is important to preserve the order of rectangles in the final result, however, so we need to keep track of which rectangle in A is overlaid with which rectangle in B. As mentioned earlier, if the overlaying is performed serially, it would be executed as a sequence of serial jobs, applying the same operation to each rectangle iteratively, which takes a long time to run. Nevertheless, we can take advantage of the independence between overlaying different sections of both maps, and hence perform the whole overlaying process as efficiently as possible.

Notice that most of the forces, as described in the Manager-Workers pattern (Figure 1.2) are present in the Polygon Overlay problem:

• The Polygon Overlay problem requires that its solution preserves the order of rectangles from maps A and B. Nevertheless, notice that all pairs of rectangles, one from A and one from B, can be overlaid without a specific order among them.

• The overlaying can b...

Table of contents

• Wiley Series in Software Design Patterns
• Title Page
• Copyright Page
• Dedication
• Acknowledgements
• Foreword
• Preface
• CHAPTER 1 - Software Patterns
• CHAPTER 2 - A Brief Introduction to Parallel Programming
• CHAPTER 3 - Architectural Patterns for Parallel Programming
• CHAPTER 4 - Design Patterns for Communication Components
• CHAPTER 5 - Some Idioms for Synchronization Mechanisms
• CHAPTER 6 - Two Case Studies
• CHAPTER 7 - Parallel Software Design
• CHAPTER 8 - Parallel Software Architecture
• Glossary
• Notations
• References
• Index of Patterns
• Index
• End User License Agreement