Patterns for Parallel Software Design E-Book

Jorge Luis Ortega-Arjona

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Software Patterns Series
• Sprache: Englisch

Seitenzahl: 543

Veröffentlichungsjahr: 2010

Beschreibung

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.

Leseprobe

Table of Contents

Wiley Series in Software Design Patterns

Title Page

Copyright Page

Dedication

Acknowledgements

Foreword

Preface

The Structure of the Book

About the Author

Acknowledgements

Contributor Biography

CHAPTER 1 - Software Patterns

1.1 The Concept of a Software Pattern

1.2 Pattern Description, Organization and Categorization

1.3 Summary

CHAPTER 2 - A Brief Introduction to Parallel Programming

2.1 Parallel Programming

2.2 Factors that Influence the Performance of a Parallel Program

2.3 Advantages and Disadvantages of Parallel Programming

2.4 Summary

CHAPTER 3 - Architectural Patterns for Parallel Programming

3.1 Parallel Pipes and Filters

3.2 Parallel Layers

3.3 Communicating Sequential Elements

3.4 Manager-Workers

3.5 Shared Resource

3.6 Summary

CHAPTER 4 - Design Patterns for Communication Components

4.1 Shared Variable Pipe

4.2 Multiple Local Call

4.3 Message Passing Pipe

4.4 Multiple Remote Call

4.5 Shared Variable Channel

4.6 Message Passing Channel

4.7 Local Rendezvous

4.8 Remote Rendezvous

4.9 Summary

CHAPTER 5 - Some Idioms for Synchronization Mechanisms

5.1 Semaphore

5.2 Critical Region

5.3 Monitor

5.4 Message Passing

5.5 Remote Procedure Call

5.6 Summary

CHAPTER 6 - Two Case Studies

6.1 1 Blood Vessel Segmentation

6.2 Adaptive 3D Grid-Based Eulerian (Gasdynamic) Program

6.3 Summary

CHAPTER 7 - Parallel Software Design

7.1 A General Parallel Software Design Process

7.2 A Pattern-Based Parallel Software Design Method

7.3 Problem Analysis

7.4 Coordination Design - Architectural Patterns

7.5 Communication Design - Design Patterns

7.6 Detailed Design - Idioms

7.7 Implementation and Evaluation

7.8 Summary

CHAPTER 8 - Parallel Software Architecture

8.1 A Definition of Parallel Software Architecture

8.2 Parallel Software Design

8.3 Summary

Glossary

Notations

References

Index of Patterns

Index

Wiley Series in Software Design Patterns

The WILEY SERIES IN SOFTWARE DESIGN PATTERNS is designed to meet the needs of today’s software architects, developers, programmers and managers interested in design patterns. Frank Buschmann (Series Editor), as well as authors, shepherds and reviewers work collaboratively within the patterns community to strive for high-quality, highly researched, thoroughly validated, classic works, which document accepted and acknowledged design experience. Priority is given to those titles that catalog software patterns and pattern languages with a practical, applied approach in domains such as:

• Distributed systems

• Real time systems

• Databases

• Business information systems

• Telecommunications

• Organizations

• Concurrency

• Netvrorking

Books in the series will also cover conceptual areas of how to apply patterns, pattern language developments and architectural/component-based approaches to pattern-led software development.

TITLES PUBLISHED

• PATTERN-ORIENTED SOFTWARE ARCHITECTURE, Volume 1

Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad and Michael Stal

978-0471-95869-7 476pp 1996 Hardback

• PATTERN-ORENTED SOFTWARE ARCHITECTURE, Volume 2

Douglas Schmidt, Michael Stal, Hans Rohnert and Frank Buschmann

978-0471-60695-6 636pp 2000 Hardback

• A PATTERN APPROACH TO INTERACTION DESIGN

Jan Borchers

978-0471-49828-5 250pp 2001 Hardback

• SERVER COMPONENT PATTERNS

Markus Völter, Alexander Schmid, Eberhard Wolff

978-0470-84319-2 462pp 2002 Hardback

• ARCHITECTING ENTERPRISE SOLUTIONS

Paul Dyson, Andy Longshaw

978-0470-85612-3 384pp 2004 Hardback

• PATTERN-ORIENTED SOFTWARE ARCHITECTURE, Volume 3

Michael Kircher, Prashant Jain 978-0470-84525-7 312pp 2004 Hardback

• SECURITY PATTERNS

Markus Schumacher, Eduardo Fernandez-Buglioni, Duane Hybertson, Frank Buschmann, Peter Sommerlad

978-0-470-85884-4 600pp 2005 Hardback

• PATTERN-ORIENTED SOFTWARE ARCHITECTURE, Volume 4

Frank Buschmann, Kevlin Henney, Douglas C. Schmidt

978-0-470-05902-9 363pp 2007 Hardback

• PATTERN-ORIENTED SOFTWARE ARCHITECTURE, Volume 5

Frank Buschmann, Kevlin Henney, Douglas C. Schmidt

978-0471-48648-0 490pp 2007 Hardback

• PATTERNS FOR COMPUTER-MEDIATED INTERACTION

Till Schümmer, Stephan Lukosch

978-0-470-02561-1 600pp 2007 Hardback

• PATTERNS FOR FAULT TOLERANT SOFTWARE

Robert Hanmer

978-0-470-31979-6 308pp 2007 Hardback

• WHERE CODE AND CONTENT MEET

Andreas Rüping

978-0-470-74845-9 216pp 2009 Hardback

• PATTERNS FOR PARALLEL SOFTWARE DESIGN

Jorge Luis Ortega-Arjona

978-0-470-69734-4 440pp 2010 Hardback

This edition first published 2010

© 2010 John Wiley & Sons, Ltd.

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, P019 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

A catalogue record for this book is available from the British Library.

eISBN : 978-0-470-97087-4

Set in 10/12 point Sabon by WordMongers Ltd, Treen, Penzance, Cornwall

A Lucía

Publisher’s Acknowledgements

Some of the people who helped bring this book to market include the following:

Editorial and Production

VP Consumer and Technology Publishing Director: Michelle Leete

Associate Director- Book Content Management: Martin Tribe

Associate Publisher: Chris Webb

Executive Commissioning Editor: Birgit Gruber

Assistant Editor: Colleen Goldring

Publishing Assistant: Ellie Scott

Project Editor: Juliet Booker

Marketing

Senior Marketing Manager: Louise Breinholt

Marketing Executive: Kate Batchelor

Composition Services

Project Management, Composition and Indexing: Steve Rickaby, WordMongers Ltd

Foreword

The steady increases in processor speeds associated with Moore’s Law has improved software performance for decades without necessitating significant changes in software designs or practices. Over the past several years, however, the exponential growth in CPU speed has stalled. Increases in software performance now stem largely from exploiting parallel processing to exchange data reliably and scalably across high-speed interconnects, dynamically balance workload in computation grids, and efficiently synchronize access to shared resources. Researchers and practitioners rely on parallel processing to accelerate scientific discoveries and deliver value to users in a wide range of application domains, including high-performance scientific computing, weather forecasting, financial services, animation rendering, text mining, homeland security and enterprise content management.

Although parallel processors and interconnects continue to improve, it remains tedious and error-prone to develop complex application and infrastructure software that can meet challenging - and changing - user requirements. This situation has yielded a ‘parallel software crisis’, in which the hardware becomes ever more capable but the software remains hard to develop, debug, optimize and evolve. Much of the effort expended on parallel software is spent rediscovering core concepts such as coordination, communication, and synchronization, and reinventing common components such as active objects, dynamic load balancers, job schedulers, message brokers and notification engines. Moreover, despite advances in key technologies, such as concurrent programming languages, vectorizing and optimizing compilers, operating system clustering techniques and grid computing middleware, many software developers lack experience of how and when to best apply these technologies.

Addressing the parallel software crisis therefore requires more than just adopting the latest technologies - it requires learning and applying successful parallel software patterns that document recurring architectures and designs and convey proven parallel software structures, algorithms and best practices. Knowledge of patterns helps researchers and practitioners to avoid rediscovering and reinventing core concepts and common components of parallel software. Patterns can also explain how and when to best apply parallel technologies.

Popular patterns such as Adapter, Bridge, Reactor and Strategy have captured and guided the designs of application and infrastructure software for two decades. Many of these patterns were identified initially by developers of object-oriented graphical user interface frameworks that work in contexts where quality factors like usability, extensibility and portability are paramount. In addition to these quality factors, developers of parallel software must also understand and apply patterns that work in contexts in which low latency and high throughput, reliability and scalability are paramount.

Over the years, isolated coverage of parallel software patterns has appeared in various conference proceedings and books. For example, those associated with the Pattern Languages of Programming (PLoP) conferences present patterns for scalable locking and threading, synchronous and asynchronous event handling, and loosely-coupled group communication. Likewise, the Pattern-Oriented Software Architecture (POSA) series of books presents patterns for pipeline parallelism, master/slave processing, distributed request brokering and dynamic resource management. Until Jorge Ortega-Arjona published this book on patterns for parallel software design, however, no single source provided such a broad and deep spectrum of architectural patterns, design patterns and common idioms for developing parallel software.

The patterns and idioms that Jorge present in this book help to resolve key parallel software challenges such as coordinating interactions between concurrently executing tasks, partitioning parallel algorithms and data to improve performance substantially, and minimizing synchronization overhead in local and distributed shared memory In addition to describing the structure and functionality of essential parallel software patterns and idioms, Jorge also presents many examples from a range of applications domains, including high-performance scientific computing, image processing and animation rendering. Moreover, Jorge’s detailed case studies extend the book beyond a catalog of parallel software patterns to provide keen insights into parallel software design processes and methods that help alleviate key accidental and inherent complexities in parallel software development projects.

For parallel software development to develop from an art to an engineering discipline, successful practices and design expertise must be documented systematically and disseminated broadly My colleagues and I have documented and applied patterns in a wide range of distributed and parallel application and infrastructure software, including the ACE, TAO and Zircomp middleware. We’ve found that studying and applying patterns helps to:

• Facilitate reuse of architecture and design artifacts, which reduces the effort required to develop high-quality parallel software frameworks and application components. These patterns can be reused even when reuse of algorithms, implementations, interfaces or detailed designs is not feasible due to heterogeneous software and hardware platforms.

• Document ‘best practices’ of parallel software systems, which have traditionally resided in the minds of expert developers or buried within complex source code. Capturing the most useful strategies and tactics of parallel software in terms of patterns makes the learning curve for new developers more gentle, by giving them good role models for developing parallel software applications and infrastructure.

• Preserve important design information, which is often lost over time in conventional development processes, causing increased maintenance costs and software defects. Software evolution effort can thus be reduced significantly by documenting the intent, structure and behavior of parallel software components in terms of the patterns they reify, as well as explaining how and when to best apply these components in various contexts.

• Guide design choices for new systems, since patterns capture proven experience in a form that can be used to address new design challenges. By understanding the potential traps and pitfalls in their domains, developers can select suitable parallel software architectures, protocols and platform features without wasting time and effort implementing solutions that are known to be inefficient or error-prone.

A thorough understanding of the parallel software patterns, processes and methods in Jorge’s book will help you develop better parallel software applications and infrastructure likewise. If you want a thorough coverage of the key pattern-oriented software architectures that are shaping the next-generation of parallel software, then read this book. I’ve learned much from it and I’m confident that you will too.

Douglas C. SchmidtNashville, Tennessee, USA

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 Department of Computer Science, University College London (UCL), UK in 2007. His research interests include software architecture and design, software patterns, parallel processing and parallel software design.

Acknowledgements

Before ending this preface, it is a pleasure to acknowledge my indebtedness to several people and sources. First of all, I would like to thank the Pattern Community, a group that is devoted to the treatment of the design and implementation of computing problems, from whom I have learned much and continue to learn. The Pattern Community has done much valuable work in the field of software design and implementation, from whose many stimulating conversations this book is a result.

I would like to record a special debt of gratitude to Frank Buschmann, who appreciated the importance of software patterns applied to parallel programming from an early stage, and convinced me to take on the challenge of writing this book. Special gratitude should also be given here to Peter Sommerland, Douglas C. Schmidt, Kevlin Henney, and especially Eduardo B. Fernandez. All these colleagues and friends have provided a lot of insight and advice, without which this book could not have been developed.

Many of the results presented here were obtained in collaboration with fellow computer scientists. The design and implementation of the case studies were developed in conjunction with Miguel Angel Palomera-Pérez. It is also important to mention that the results for the 2D heat equation were obtained with the cooperation of Sergio Rajsbaum-Gorodezky, who provided access to the multi-core platform required.

I should like to thank current and former staff of John Wiley and Sons, particularly Rosie Kemp, Colleen Goldring, Birgit Gruber and Ellie Scott, whose efforts have greatly benefited the production of this book. I should also like to thank Steve Rickaby of WordMongers, who read the final manuscript through with great care and made a number of useful suggestions and corrections.

Finally, I would like to thank my parents, Pedro and Edith, my brother Pedro and my sisters Edith and Tere for all their support and encouragement during my life. Last but not least, this is a book dedicated to Lucía, who has been my wife, my friend and my support during good and bad times we have had together. To me, this book represents a personal achievement which I could not have done without you.

Jorge L. Ortega-ArjonaMexico City, 2009

Contributor Biography

Dr Douglas C Schmidt is a Professor of Computer Science at Vanderbilt University. He has published nine books and over 400 technical papers that cover a range of research topics, including patterns, optimization techniques and empirical analyses of software frameworks and domain-specific modeling environments that facilitate the development of distributed real-time and embedded (DRE) middleware and applications running over high-speed networks and embedded system interconnects. In addition to his academic research, Dr Schmidt has twenty years of experience leading the development of ACE, TAO, CIAO and CoSMIC, which are widely used, open source DRE middleware frameworks and model-driven tools that contain a rich set of components and domain-specific languages that implement patterns and product-line architectures for high-performance DRE systems.

CHAPTER1

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. Sommerland and M. StalA 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 be performed independently between any rectangle from A and any rectangle from B.

• Although rectangles have different sizes, the overlaying operation requires a representation of the rectangles (normally, their coordinates within the map).

• The Manager-Workers organization ensures that adding a new worker does not affect the rest of the workers, but it can influence the total execution time of the parallel program.

Considering the previous analysis of the context, problem, and forces for the Polygon Overlay problem, our conclusion is to use the Manager-Workers pattern to create a parallel solution. Such a parallel solution can be described as follows (Figure 1.2): using the Manager-Workers pattern, a set of workers do the actual polygon overlaying by simultaneously finding intersections for each sub-map in A with each sub-map in B. For the two input maps, the manager divides all the polygons belonging to A into sub-maps, and for each of them the workers find all the intersections with a sub-map of B (Figure 1.4). The key for the parallel solution is to limit the part of both maps, A and B, that workers must examine to find the overlaps. The manager is responsible for tracking which sub-map is sent to which worker so that each overlaying is performed in the right order. At the end of the whole process, each worker returns its result map to the manager, which assembles them into a complete result map.

Figure 1.4: A Manager-Workers block diagram for solving the Polygon Overlay problem

The solution to the Polygon Overlay problem using the Manager-Workers pattern can be developed further to obtain a complete parallel program. Nevertheless, our objective with this case study is simply to show how a software pattern can be used to design a solution from a problem description, so we stop here. Several questions, however, arise from this example, such as ‘Why use the Manager-Workers pattern to solve the Polygon Overlay problem?’, ‘Why not use another pattern?’, ‘What are the characteristics and features of this problem that lead us to select Manager-Workers pattern as a description of the coordination of its solution?’. The rest of this book attempts to provide answers to questions like these; first, however, the following sections address other issues about software patterns.

1.2 Pattern Description, Organization and Categorization

Describing Patterns: The POSA Form

Software patterns are usually documented in several forms. These forms are known as pattern schemata, pattern forms or pattern templates. Numerous examples of these templates can be found in the literature [GHJV95] [POSA1] [PLoP1]. The typical form is a collection of sections that characterize different aspects of a software pattern. The collection of sections varies from author to author and from domain to domain.

In parallel programming, as in other software domains, the most common forms are the ‘Gang of Four’ (GoF) form [GHJV95] and the ‘Pattern-Oriented Software Architecture’ (POSA) form [POSA1]. Both forms use diagrams based on Unified Modeling Language (UML) and plain text. This book uses the POSA form to describe software patterns. This form uses the following sections [POSA1]:

• Name. A word or phrase that essentially describes the pattern.

• Brief. A description of the pattern stating what it does.

• Example. A real-world example that shows the existence of a problem and the need for the pattern.

• Context. The situation or circumstance in which the pattern is applied.

• Problem. A description of the conflict the pattern solves, including a discussion about the forces.

• Solution. A description of the fundamental principle of the solution which serves as base for the pattern.

• Structure. A detailed specification (usually based on UML diagrams) describing structural aspects of the pattern.

• Dynamics. Typical scenarios describing the behavior through time of the participants within the pattern. Normally UML sequence diagrams are used.

• Implementation. Guidelines for implementing the pattern.

• Example resolved. Restating the Example section, this section presents a discussion about any important aspects of solving the problem proposed as the example.

• Known uses. Example uses of the pattern (at least three) taken from existing systems.

• Consequences. Benefits and liabilities that occur when applying the pattern.

• See also. References to other patterns that solve similar problems, or to patterns that help to refine the pattern being defined.

Pattern Languages and Systems: Organizing Patterns

In general - and independently of the domain - patterns are distilled from successful designs, which means that the main source of patterns is the analysis of existing successful solutions, identifying their recurring forms and designs. This discovery and documentation of patterns produces a large number of them: every day someone somewhere discovers a pattern and works on documenting it. Nevertheless, patterns are only useful if they can be organized in a way that makes them easy to select and use. Normal practice is to gather related patterns into structured pattern collections [POSA5].

When the pattern organization process advances, it often yields a network of relations between patterns known as a pattern language or pattern system. These networks are collections of interrelated patterns that can be used to describe or design a concrete system in a domain [PLoP1]. The term ‘pattern language’ was originally suggested by Alexander et al. [AIS+77]: the term ‘pattern system’ was proposed later by Buschmann et al. [POSA1].

A pattern language or system is a set of patterns complete enough for design within a domain. It is a method for composing patterns to synthesize solutions to diverse objectives [POSA1]. Hence software patterns become the building blocks for design, or suggest important elements that should be presented in the software system. Each software pattern suggests instructions for solution structure or contains a solution fragment. The fragments and instructions are merged to yield a system design.

Software Pattern Categories

Software patterns cover various levels of scale and abstraction. They range from those that help in structuring a software system into subsystems, through those that support the refinement of subsystems and components, to those that are used to implementing particular design aspects in a specific programming language. Based on a description such as this, software patterns are commonly grouped into three categories, each one consisting of patterns having a similar level of scale or abstraction [POSA1]:

• Architectural patterns. ‘An architectural pattern expresses a fundamental structural organization schema for Software systems. It provides a set of predefined subsystems, specifies their responsibilities, and includes rules and guidelines for organizing the relationships between them’.

• Design patterns. ‘A design pattern provides a scheme for refining the subsystems or components of a Software system, or the relationship between them. It describes a commonly-recurring Structure of communicating components that solves a general design problem within a particular context’.

• Idioms. An idiom is a low-level pattern specific to a programming language. An idiom describes how to implement particular aspects of components or the relationship between them using the features of the given language’.

In this book we are concerned about architectural patterns as high-level software patterns used for specifying the coordination of parallel software systems, about design patterns as refinement schemes for inter-component communication, and about idioms as low-level patterns used for describing synchronization mechanisms in different languages.

1.3 Summary

This chapter has briefly introduced the reader to the field of software patterns. Addressing issues such as the concept of a software pattern, its description, organization and categorization, this chapter has provided a simple introduction intended to help clarify the remaining patterns for parallel software design presented in this book.

CHAPTER2

A Brief Introduction to Parallel Programming

‘Hard work is a series o simple jobs that were not carried out on time’

Anonymous

Parallel computing involves the simultaneous use of multiple computer resources to solve a single computational problem. The problem is divided into multiple discrete series of instructions that can be executed simultaneously on different processors. Parallel computing has traditionally been associated with ‘high performance computing’, which uses high-end computer resources to solve ‘grand challenge’ computational problems. With the advent of commodity-market multi-core processors [AMD08] [Inte108] and clusters of blade computers or low-cost servers, parallel computing is now available to many application developers. Regardless of the parallel computing infrastructure, however, many computational problems can be divided into discrete parts that can be solved simultaneously, and hence solved in less time than with a single-core computer resource. Parallel computing is also commonly used to conduct numerical simulations of complex systems in diverse domains, such as cosmology, weather forecasting, biology and genetics, business operations, material science and so on.

2.1 Parallel Programming

Parallel programming is based on the division of a processing task among multiple processors or processor cores that operate simultaneously. A parallel program is thus defined as the specification of a set of processes executing simultaneously, and communicating among themselves to achieve a common objective. The expected result is a faster computation compared to execution on a single-processor/core system. The main advantage of parallel programming is its ability to handle tasks of a scale that would not be realistic or cost-effective for other systems.

In theory, parallel programming should simply involve applying multiple processes to solve a single problem. In practice, however, parallel programming is often difficult and costly, since it requires greater effort from software designers, who must develop new forms of understanding and programming to suit a parallel execution environment. Moreover, techniques used in single processor/core systems for reviewing and correcting defects, as well as for improving the performance, are not directly applicable to parallel programming. Parallel execution environments, such as a multi-core processor, a network of workstations, a grid of personal computers or a high-performance parallel processing system, can be unstable and unpredictable, or simply non-deterministic. It is not uncommon for parallel programs to yield incorrect results or execute more slowly that their sequential counterparts even after months of programming.

Optimizing performance has historically been considered the driving factor for parallel programs. Performance refers to the response capability of a parallel system - that is, the time required to respond to stimuli (events) or the number of events processed in a specific interval [Smi90]. Ultimately, performance is the main reason for using parallel systems [PB90] [Pan96].

2.2 Factors that Influence the Performance of a Parallel Program

Parallel programming is a complex activity that is aimed at developing the specifications of parallel processes that execute simultaneously and non-deterministically to obtain gains in execution time. The performance obtained when applying parallel programming is affected by the hardware platform, the programming language and the problem to be solved [Pan96]. Some important features of these factors are described below

The Hardware Platform

A parallel computer is generally considered as any collection of processing elements connected through some type of communication network, where a ‘processing element’ is composed of hardware devices such as a processor and its associated memory Contemporary parallel computers range in price and size from a single multi-core chip, through a group of workstations connected through a LAN, to a high-performance (and cost) computer involving hundreds or thousands of processors connected via a high-speed network. The performance of any parallel application is ultimately bounded by the speed, capacity and interfaces of each processing element.

Programming a parallel computer depends on how the memory of the hardware platform is organized or divided among the processors. There are two commonly used memory organizations: shared memory and distributed memory Depending on which is used for a parallel computer, different mechanisms for process communication are selected for programming, as we discuss below

Shared Memory

In a shared memory parallel computer, all processors have access to all memory in the form of a global address space. A shared memory multiprocessor system therefore allows access from any processor to any location within a common memory via an interconnection network (Figure 2.1).

Figure 2.1: Structure of shared memory multiprocessors

Multiple processors normally operate independently, sharing the same memory resources. Changes in a memory location produced by a processor are (eventually) visible to all other processors. In most cases, the interconnection network is completely hardware controlled, independent of the activity of the programmer, who only perceives a shared, central and continuous memory. Each memory location or address is unique and identical for any processor of the system.

In shared memory computers and at the programming level, communication between processes is normally performed by reading or writing shared variables. When a processor reads from or writes to a specific memory address, the interconnection network automatically selects the appropriate memory device. To ensure data integrity, programming mechanisms have been devised to support communication between processes, providing planning, synchronization and coordination between communicating processes. Common programming mechanisms for shared memory computers include mutexes [And91] [And00], semaphores [Dij68] and monitors [Hoa74].

Shared memory multiprocessors have two main advantages:

• The concept of a global address space simplifies programming, since memory can be read from and written to in a manner that is similar to non-parallel programs.

• Sharing data between processes is fast and uniform, given the proximity of memory to processors.

Nevertheless, shared memory systems also have some disadvantages:

• It is hard to scale the amount of memory and processors in shared memory computers. Adding more processors tends to increase the traffic between memory and processors geometrically, which complicates cache coherency management[And00] [HX98].

• In shared memory systems, programmers are responsible for providing adequate synchronization constructs to ensure ‘correct’ access to shared variables within the global address space.

• Shared memory systems are often expensive. It is particularly costly to design and produce shared memory computers with a large number of processors.

Examples of shared memory parallel computers are the parallel vector processor (PVP) computers, such as NEC SX-4, Cray C-90 and Cray T-90 [HX98], symmetric multiprocessor (SMP) computers such as the DEC Alpha server 8400, the SGI Power Challenge and the IBM R50 [HX98], and, in the area of personal computers nowadays, platforms based on multi-core processors such as the Xeon and Core 2 Duo and Quad processors from Intel [Inte108]. The Opteron and Phenom II processors from AMD [AMD08] are also considered SMP computers.

Distributed Memory

A distributed memory multiprocessor system only allows each processor direct access to its own local memory Communication with the memory of other processors is performed using explicit I/O operations via interprocess communication (IPC) mechanisms provided by an interconnection network (Figure 2.2).

Since each processor has its own local memory, memory addresses of a specific processor do not map to another processor’s address space, so there is no global address space shared between processors. Changes in a processor’s local memory have no effect on the memory of other processors, and thus the concept of cache coherency has no meaning, since processors operate independently. When a processor needs data from the memory of another processor, programmers must explicitly define how and when to communicate the data. Programmers must also explicitly synchronize processes.

Figure 2.2: Structure of distributed memory systems

The interconnection network is composed of a set of links between processors or nodes, based on a specific topology such as linear, ring, star, mesh, tree, hypercube and so on. The network is the media used for data exchange. During the execution of a parallel program, the network may remain the same (static) or change (dynamic), in accordance with the program’s needs.

Communication between processes in a distributed memory system is performed through message passing, which implies explicit I/O operations to send and receive IPC messages. Each processor ‘recognizes’ the difference between its local address space and the address space of other processors, so is able to read and write data freely from its local address space. Nevertheless, when a processor must read or write data from another processor’s address space, it does so via an explicit request by a message passing operation.

Message passing is defined as a communication model for distributed memory systems. Common IPC mechanisms used for message passing include input/output operations [Hoa78] [Hoa85], channels [PM87] and remote procedure calls [Bri78].

Distributed memory systems have several advantages:

• Memory normally scales with the number of processors. Increasing the number of processors implies that the size of the memory also increases.

• Each processor can access its own memory rapidly and without any interference or overhead due to cache coherency being preserved.

• Distributed systems are cost-effective. They may use commodity off-the-shelf processors and networking, or even high-performance processors and networks.

Distributed memory systems have some disadvantages, however:

• Data communication between processors is the responsibility of programmers, who must consider many details of data exchange.

• It is hard to map common data structures (based on global memory) to a distributed memory organization.

• Distributed systems provide access times comparable with shared-memory times. Examples of distributed memory parallel platforms are the ‘massively parallel processor’ (MPP) computers such as the Intel Paragon TFLOP [HX98], ‘clusters of workstations’ (COW) such as the Berkeley NOW, the IBM SP2 and the Beowulf clusters [HX98], and distributed shared memory (DSM) systems such as the Stanford DASH computer [HX98].

Programming Languages

The programming language obviously affects the performance of a parallel system as well as the effort required to parallelize an application. Moreover, extreme variation in compiler capabilities and runtime support environments means that the language also constrains the attainable performance. The type of programming libraries that can be used by parallel programs is often a key indicator of both the effort and the performance that can be achieved by using a particular programming language.

In general, a parallel language can be evaluated by its capacity to express basic characteristics of parallelism, sequencing, communication and synchronization, and control of non-determinism between processes [Hoa78], as described below.

Parallelism

A parallel language should be able to describe the parallel execution of processes, using a construct for parallel composition. This construct is required because sequential programming languages normally do not have a programming construction to express parallelism. The need for such an construct has been common since the beginning of parallel programming [Dij68] [Hoa78].

Examples of such a parallel construct are provided by several authors. For example, Dijkstra [Dij68] proposes an extension to ALGOL60, using a structure based on the delimiters parbegin ... parend., as shown in Figure 2.3.

Figure 2.3: Example of two concurrent open file operationsusing Dijkstra’s parbegin...parend delimiters

This code defines two openFile statements that execute simultaneously. The target files InputA and InputB are two separate files, so the execution of both statements is disjoint. Constructs like this are considered a parallel composition. Dijkstra’s work has resulted in what constitutes the parallel construction in several programming languages, which represents the simultaneous activation of disjoint processes with independent execution speeds among themselves. The parallel parbegin...parend construct completes successfully only when all the processes it generated finish successfully

There are various derivations of the parallel construction, depending on the language. Other examples of parallel instructions are the construction P1 II I P2 I I ... I PN of CSP [Hoa78] [Hoa85] and the instruction PAR from the Occam programming language [PM87]. Figure 2.4 shows an example of the use of the PAR instruction.

Figure 2.4: Example of use of the PAR instruction in Occam

This expresses the parallel execution of two sequential processes, which allow simultaneously reading from the keyboard and writing to screen. Both processes communicate through a channel c. These instructions represent what is considered as interprocess parallelism.

There are other examples of mechanisms that represent intraprocess parallelism, as is the case with Java threads [Smi00]. Figure 2.5 shows the two ways of spawning Java threads.

Figure 2.5: Two ways of creating threads in Java: (a) extending the class Threadand (b) implementing the interface Runnable

The first way to spawn a thread in Java extends the class Thread and overrides the run( ) method with the code for the new thread subclass. It is thus possible to create an instance of the subclass and invoke the method start ( ), which in turn spawns a thread and calls the run ( ) method. The second way to spawn a Java thread is to implement the interface Runnable in a class with a public run( ) method. This approach makes it possible to create an instance of the class, passing a reference to this instance to the Thread constructor, which calls the start ( ) method to spawn a thread and invoke the run ( ) method.

Sequencing

The expression of sequential constructs is present as the basic feature of many programming languages. In a parallel programming language, however, it is necessary explicitly to represent a sequential composition (or sequential construct) to contrast its action with parallel composition.

The sequential construct expresses a set of disjoint processes that activate in sequence as they appear within the instruction. It successfully finalizes if every process in the sequence finalizes: if it is interrupted, its execution fails [Hoa78].

In general, several programming languages express the sequential construct explicitly through the inclusion of the symbol ‘;’ between the instructions of the sequence. Languages such as ALGOL60, Pascal, C and others present such an expression, which has also been considered by several parallel languages. Examples are the construction P1; P2; ...; PN in CSP [Hoa78] [Hoa85], Concurrent Pascal [Bri78] and SuperPascal [Bri95]. Figure 2.6 shows some examples of sequential constructions in SuperPascal.

Figure 2.6: Examples of some sequential functions in SuperPascal that implement commonoperations on complex numbers. Notice the use of‘;’ between operations.

Other parallel languages such as Occam introduce the SEQ construct explicitly [PM87], as shown by the example in Figure 2.7. This expresses sequential reading from the keyboard and writing to screen: a process is defined in which characters are repeatedly read from a keyboard process and sequentially sent to a screen process. Note the use of the SEQ construction.

Figure 2.7: Example of use of the SEQ instruction in Occam

Communication and Synchronization

A parallel language should provide expressions for communicating between, and synchronization of, processes. There are several mechanisms for communicating between and synchronization of parallel processes. Normally, their use depends on the organization of memory: shared memory or distributed. A parallel language for a shared memory system expresses communication through shared variables by primitives for reading or writing (or simply assigning) such variables. The synchronization of such actions is based on the use of mechanisms such as semaphores [Dij68] or monitors [Hoa74]. A parallel language for a distributed memory system expresses communication through message passing by IPC primitives for sending and receiving messages [Hoa78] [Bri78].

For message passing in distributed memory systems in particular, synchronization is based on blocking the processes during communication. For example, message passing is represented in CSP by the send (!) and receive (?) instructions [Hoa78] [Hoa85], as shown in Figure 2.8.

Figure 2.8: Example of use of ! and? communication instructionsfor send and receive respectively in CSP

This example copies a characters from the input process to the output process.

In Occam, the send (!) and receive (?) instructions [PM87] use channels for message passing purposes, as shown in Figure 2.9.

Figure 2.9: Example of use of! and? communication instructionsfor send and receive respectively in Occam

Finally, Java includes the synchronized keyword [Smi00] to serialize access to shared variables, as shown in Figure 2.10. Both read ( ) and write ( ) methods are made atomic.

Figure 2.10: Example of Java communication over a shared variable (data)using the synchronized keyword

Non-Determinism

A parallel language should provide expressions for controlling non-determinism. Non-determinism is a characteristic of concurrent and parallel programming in which the order of simultaneous operations performed by a set of parallel processes (each one executing at different speed) is arbitrary. If such operations are, for example, send or receive operations, the characteristic of non-determinism establishes that the order of those send and receive operations cannot be known beforehand. Each execution of the program can thus produce a (probabilistically) different order of instructions performed through time. Nevertheless, the simultaneous sequential processes involved in the parallel program are still expected to execute their operations in the order defined for each of them.

Although non-determinism is generally considered a consequence of parallel execution, it may not be convenient to allow completely random parallel execution. Non-determinism can be controlled using a Boolean expression, known as guard, that conditionally executes particular instructions. The set of guards and instructions are known as guarded commands, and is the basis of another kind of instructions used for dealing with non-determinism: the alternative instruction [Hoa78].

In an alternative instruction, all guards are simultaneously evaluated, executing only the guarded command associated with the successful guard - that is, the Boolean expression which evaluates to true. If more than one guard evaluates to true, the instruction arbitrarily selects a guarded command associated with one of the successful guards. The alternative instruction is executed, expecting that at least one guard is verified. If no guard is verified, the instruction fails.

An example of an alternative instruction is the instruction [C1P1 []...[ ]CNPN], previously shown in Figure 2.8 for the Copy process in CSP [Hoa78] [Hoa85]. Another example of the use an alternative instruction is the ALT instruction shown in Figure 2.9 for the Copy process in Occam [PM87].

Various parallel languages, such as C, C++, Java, FortranM, Occam, Linda and so on are now available that represent several ways of introducing parallel programming features. These languages enable programmers to focus not only on data and operations, but also on coordination of the independent processes that compose parallel programs. Parallel languages should thus define the activities that can be performed simultaneously, the mechanisms for communicating between these activities, as well as other features such as non-determinism. Moreover, effective parallelization must address other concerns, such as how processor (or process) activities can be coordinated and how to ensure data correctness when the order of operations is unpredictable.

The Problem of Parallelization

A key to the success or failure of a parallel program is how a problem, expressed as an algorithm and/or a set of data, can be parallelized or divided into parts that can run in parallel. In particular, the patterns for data access and the algorithmic order indicate the way in which processing is performed, which in turn is related to performance. Moreover, if partitioning of an algorithm and/or data is the basis for parallel execution, then parallel programming is strongly affected by the order and dependence among instructions (as elementary parts of the algorithm) and/or datum (as basic part of the data), independently of the nature of the actual problem to solve. This is due to the ‘orthogonal dimension’ [Weg87] that characterizes concurrent execution. This means that a parallel software system is composed not only of a correct solution to the problem, but also by a coordination that organizes its execution.

Even though some simple well-structured problems have been solved successfully by improvements in compilers (for example, the automatic parallelization in Fortran, as developed by Burke et al. [BCF+88], Kuck et al. [KDL+98] and many others), other problems remain a challenge for efficient parallel solution.