Preface Parallelism is used to create programs that are intended to execute on many processors simultaneously. Today these processors may all be packed onto a single chip (known as multi-core processors), into one box (yielding a multiprocessor or parallel computer) or may be separate, autonomous machines connected by a network (a distributed system). In all cases, each processor works on part of the problem and they all proceed together, exchanging data, towards a single objective. Nowadays, parallelism is on its way to truly become the mainstream of computing. In recent years the most powerful computer system, by definition, has been a parallel computer. A simple reason for this is that once manufacturers have built the fastest processor that current technology can support, two of them are expected to execute faster. Today computer manufacturers are discovering that adding more processors to the same computer is often a highly efficient way to achieve more computing power at a low incremental cost. Hence, recent multiprocessor computers are often more powerful, and relatively less expensive. The computer market tends towards systems based on multiple processors. Within the next few years, software companies will need to start producing and selling applications that execute on these multiprocessor computers. A parallel application or program can be defined in general terms as the specification of a set of processes that execute simultaneously, communicating among themselves to achieve a common objective. The design of parallel programs deals not only with known problems and issues present in programming single-processor computers, but must also engage with those that properly arise from the basic concurrent or simultaneous execution of processes. Due to this, designing parallel programs can be difficult, and sometimes frustrating: When designing a parallel program many issues arise that are related to partitioning an algorithm and its data. For example, how best to choose a parallel software description that is not too hard to program, but which offers substantial performance improvement when compared to execution on a single-processor? The overheads involved in synchronization among processes and processors may actually reduce the performance of an overall parallel software implementation. How can this problem be anticipated and mitigated? Like many performance improvements, parallelizing increases the complexity of a program. How can such complexity best be managed? These are tough problems, and there are as yet no definitive answers about how to solve a computing problem of arbitrary size on a parallel system efficiently. Designing parallel programs at the current stage of development cannot offer universal solutions. Nevertheless, we can try to provide some simple ways to get started. The current use of parallel computers implies that software plays an increasingly important role. From clusters to supercomputers, success depends heavily on the design skills of software developers. However, besides the inherently difficult task of software design in the classical, algorithmic sense, the design of parallel software requires special skills and consideration of other particular design aspects. Parallel software design is presented here as a study of how and at what point the organization of a parallel software system affects its performance and development. Parallel software design proposes concepts and techniques to deal with the parallelization of a problem described in algorithmic terms. Research in this area covers several approaches that provide forms for organizing software with relatively independent components that make use of multiple processors efficiently By sticking with software patterns commonly used in parallel programming it is possible to avoid a lot of errors and aggravation. By using these software patterns, we may perhaps eventually improve our knowledge of how parallel programming actually works and how to deal with its problems and issues. This books presents patterns for parallel software design based on existing design knowledge, drawn from both well-known classic design experience as well as new and promising designs. A pattern-oriented approach to parallel software design is not only a design method in the classic sense, but a new way of managing and exploiting existing design knowledge for designing parallel programs. Using this approach leads to parallel software systems that can be considered better designed: they are modular, adaptable, understandable, evolvable and so on. Moreover, such an approach to parallel software design aims to enhance not only the build-time properties of parallel systems, but particularly also their runtime properties. In the last decade several Pattern-Oriented Software Architecture (POSA) books [POSA1] [POSA2] [POSA4] have provided software patterns for the design and implementation of general, concurrent and distributed software systems. This book, about patterns for parallel software design, attempts to complement the software patterns presented in those POSA books. The approach taken is as follows: Provide architectural patterns that describe how to divide an algorithm and/or data to find a suitable partitioning and link it with a coordination scheme that allows for such a division. Similarly, consider design patterns that allow a communication mechanism between parallel components to be selected based on actual characteristics, such as the memory organization of the hardware platform and the partitioning of the problem. Offer some idioms that describe synchronization mechanisms in commonly used programming languages for parallel programming. Provide a method for parallel software design based on several software patterns that are applied to the development of coordination, communication and synchronization of a parallel software system.

The Structure of the Book

Chapters 1 and 2 are introductory chapters about the two main issues that this book covers: software patterns and parallel programming. Chapter 1, Software Patterns, introduces some basic concepts that are used as background for presenting the software patterns in the book: definition, description, mining, languages and systems, and categories. In the same way, Chapter 2, A Brief Introduction to Parallel Programming, introduces some common concepts and elements of parallel programming, which are used in the descriptions of the software patterns in this book. Chapters 3 through 5 present the actual patterns for parallel programming. Chapter 3, Architectural Patterns for Parallel Programming, presents the basic organizational structures commonly used in the composition of parallel software systems. Chapter 4, Design Patterns for Communication Components, introduces some common software subsystems used for enabling communication between and among parallel components. Chapter 5, Some Idioms for Synchronization Mechanisms, provides the descriptions of synchronization mechanisms as idioms in some parallel programming languages. Chapter 6, Two Case Studies, introduces two broader examples that involve and span many of the patterns presented in Chapters 3, 4 and 5. The idea is to explain how architectural patterns for parallel programming, design patterns for communication components and idioms for synchronization mechanisms are used together to solve each example. From these example descriptions, a common general method for parallel software design is obtained: this method is explicitly presented in Chapter 7, Parallel Software Design. This chapter describes the concept of parallel software design as a result of considering software design issues within parallelism. It presents a method for parallel software design that is based on the concepts of coordination, communication and synchronization. These concepts are the unifying elements of concurrent, distributed and parallel programming. Furthermore, they map precisely to the patterns proposed here: Architectural patterns for parallel programming are used for designing the coordination of a parallel software system. Design patterns for communication components are applied to the design and implementation of communication within a coordination scheme. Idioms for synchronization components are used in implementing the communication scheme. The design method is complete when a total parallel software system is produced by including the sequential code that performs the actual processing of data. Chapter 8, Parallel Software Architecture, discusses how a software architecture for parallel software systems is proposed, relating parallel software design to parallel software theory and technology Finally, Chapter 9, Directions in Patterns for Parallel Programming, concludes the book by pointing out directions that more complete efforts in software patterns for parallel programming would have to take, as well as two problems considered for further development in parallel software design: tangible description and the need for measurements. This chapter finishes with a remark about the future of this area.

About the Author

Dr Jorge Luis Ortega-Arjona is a full-time titular lecturer in the Department of Mathematics, Faculty of Sciences, UNAM. He obtained a BSc in Electronic Engineering from the Faculty of Engineering, UNAM, in 1992, an MSc in Computer Science at UNAM in 1996 and a PhD from the...