In this chapter, we have described a four-step approach to parallel algorithm design in which we start with a problem specification and proceed as follows:
We have also provided design checklists that can be used to evaluate designs as they are developed. These informal questions are intended to highlight nonscalable or inefficient features in designs.
Successful application of this design methodology, together with the use of the performance modeling techniques described in Chapter 3, produces one or more parallel algorithms that balance in an appropriate fashion the potentially conflicting requirements for concurrency, scalability, and locality. The next stage in the design process is to consider how such algorithms fit into the larger context of a complete program. As we shall see in Chapter 4, additional concerns must be addressed at that level, which may require revisions to the designs of individual components. Agglomeration and mapping decisions are particularly prone to modification; therefore, we make these decisions last, when they can be most easily changed.
© Copyright 1995 by Ian Foster