TABLE OF CONTENTS Chapter 5 discussed program transformations designed to enhance the parallelism in inner loops. Those transformations improve performance on vector and superscalar architectures, where parallelism is fine-grained and found primarily in innermost loops. In this chapter we turn to the problem of finding parallelism for multiple asynchronous processors with a shared global memory. These processors are typified by the symmetric multiprocessor (SMP) found in workstations from companies like Sun, Silicon Graphics, and Compaq and the distributed shared- memory (DSM) systems typified by the SGI Origin 2000 and the HP/Convex SPP-2000.
Coarse-grained parallelism at the level of multiple processors requires a different focus; on such architectures, parallelism is employed by creating a thread on each of the processors, executing in parallel for a period of time with occasional synchronization, and synchronizing via a barrier at the end. The key to achieving high performance on such systems is to find and package parallelism with a granularity large enough to compensate for the overhead of parallelism initiation and synchronization. As a result, the focus is to find parallel loops with significant amounts of computation within their bodies. This usually means parallelization of outer loops rather than inner loops, and it often means parallelization of loops with subroutine calls, a subject discussed in Chapter 11.
When generating parallel code for coarse-grained architectures, many delicate trade-offs must be managed. One of the most difficult is minimizing communication and synchronization overhead while balancing the load evenly across all the processors. At one extreme, the absolute minimal overhead...
