Intent:

This note (written in the form of a pattern) provides background information for this project. Together with the other background documents linked from it, it defines the core concepts and the terminology used in our parallel application pattern language.

Motivation:

Parallel computing is complex and can be very confusing. We hope to reduce this complexity and make parallel computing acceptable to the general programmer by creating a pattern language for parallel application computing.

Patterns are represented as text. To make this text understandable to a broad audience, we need to be very clear about our terminology. Actually, this is equally important for those writing patterns, since parallel computing, like any new field of study, lacks a uniform terminology, and there is considerable variation in what meanings are attached to different terms. If we want our patterns to use a uniform terminology, we need to define one. This document is the gateway to our notes describing current technology and the terminology we will use.

Our introduction (which consists of this note and the documents linked from it) serves two distinct purposes. For programmers new to parallel computing, it provides an introduction to parallel computing. This introduction is not complete and cannot provide your full education in parallel computing. It includes, however, an annotated bibliography that can help you find the references you need to fill holes in your parallel-computing background. For the experienced programmer (and pattern writers), our introduction defines our terminology and hopefully will prevent communication problems from detracting from the language.

Structure:

The set of documents at this level provides an overview of parallel computing. The set includes the following elements:

• A self-contained overview of the pattern language and our motivations for creating it, plus an example, based on a paper we submitted to PDSE'99. (Note that some details of this paper are no longer consistent with the current state of the pattern language, but the paper is nonetheless a good overview.)
• A description of the notation we use to write down patterns.
• An introduction to parallel hardware including a taxonomy of parallel computer systems.
• A description of key parallel programming environments with links you can follow for additional information.
• A general model of parallel algorithms and a supporting computational model.
• A bibliography supporting this project.
• A glossary for this project.
• A summary of research on the psychology of programming and how it applies to our pattern language. This is an aside to the project and doesn't really fit in here. It does provide, however, justification for why we believe design patterns are so important.

Implementation:

In parallel computing, you use concurrency to decrease the elapsed time to run a program. There are several good textbooks written about parallel computing, and we cannot replace the need for you to use one of them. We can, however, provide a quick introduction to the field and describe the terms we use throughout the pattern language.

Elements.

Taxonomy of parallel computer systems.

A good place to start is with the parallel computing system itself. A parallel computer contains multiple processing elements (PEs) connected by some sort of network. There are dozens of ways to build a parallel computer, and keeping these straight can be tough. To quickly get a handle on all these systems, we have organized them into a simple taxonomy of parallel hardware. You can probably skip these details altogether, however, since just about every parallel computer in use today can be though of as a cluster of SMP workstations. In other words, you can almost always get away with thinking of a parallel computer as a collection of workstations, each with multiple processors tightly coupled through a shared-memory interface (i.e., each an SMP workstation), all connected by some type of interconnection network (the cluster).

Model of parallel algorithms.

Once you have a parallel computer system, you need software that can take advantage of the multiple processing elements. This is where things get interesting. First, you need a problem that contains concurrency. By this we mean that the problem can be solved with several activities taking place at the same time. When the goal of the concurrency is to make your program run faster, we refer to the program as a parallel program.

It is the purpose of our pattern language to help you develop a parallel algorithm and then turn this algorithm into a correctly executing, efficient parallel program. To help us in this task, we need a general (i.e., vague enough to apply in many cases) model of the parallel computation. This model describes the parallel algorithm and its execution in terms of tasks, "units of execution" (UEs), and a mapping onto the processing elements (PEs) of a parallel computer. This model is intuitive to an experienced parallel programmer. Since we use the language of this model in the higher level patterns, it's probably a good idea to look it over and make sure we're speaking the same language. You can find the model and a brief explanation of how it fits in with models computer scientists like here.

Description of key parallel programming environments.

Models and patterns are great for producing a software design, but they don't in and of themselves result in code that can execute on the parallel computer. For this you need a programming environment that supports parallel computing. This is beyond the scope of our pattern language, so we don't go into great detail. Still, it would be irresponsible to dodge this point altogether, so we include a brief description of some important programming environments.

Bibliography.

There are a host of other details we could go into, but this discussion and the links we've provided should be enough to get you started. If you are still confused on some of the background issues, take a look at our annotated bibliography or any of the many good introductory texts on parallel computing.