4.1 Introduction

The Previous Chapter Focused on Exploiting loop-level parallelism using OpenMP. This form of parallelism is relatively easy to exploit and provides an incremental approach towards parallelizing an application, one loop at a time. However, since loop-level parallelism is based on local analysis of individual loops, it is limited in the forms of parallelism that it can exploit. A global analysis of the algorithm, potentially including multiple loops as well as other noniterative constructs, can often be used to parallelize larger portions of an application such as an entire phase of an algorithm. Parallelizing larger and larger portions of an application in turn yields improved speedups and scalable performance.

This chapter focuses on the support provided in OpenMP for moving beyond loop-level parallelism. This support takes two forms. First, OpenMP provides a generalized parallel region construct to express parallel execution. Rather than being restricted to a loop (as with the parallel do construct discussed in the previous chapter), this construct is attached to an arbitrary body of code that is executed concurrently by multiple threads. This form of replicated execution, with the body of code executing in a replicated fashion across multiple threads, is commonly referred to as "SPMD"-style parallelism, for "single-program multiple-data."

Second, within such a parallel body of code, OpenMP provides several constructs that divide the execution of code portions across multiple threads. These constructs are referred to as work-sharing constructs and are used to partition work across the multiple threads. For instance,...