2.9 Summary

  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:

1. We first partition a problem into many small pieces, or tasks. This partitioning can be achieved by using either domain or functional decomposition techniques.
2. Next, we organize the communication required to obtain data required for task execution. We can distinguish between local and global, static and dynamic, structured and unstructured, and synchronous and asynchronous communication structures.
3. Then, we use agglomeration to decrease communication and development costs, while maintaining flexibility if possible.
4. Finally, we map tasks to processors, typically with the goal of minimizing total execution time. Load balancing or task scheduling techniques can be used to improve mapping quality.

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.