Selecting Locking Primitives for Parallel Programs

The only reason to parallelize a program is to gain performance. However, the synchronization primitives needed in parallel programs can consume execessive memory bandwidths, can be subject to memory latencies, consume excessive memory, and result in unfair access or even starvation. These problems can overwhelm the performance benefits of parallel execution. Therefore, it is necessary to understand these performance implications of synchronization primitives in addition to their correctness, liveness, and safety properties. This paper presents a pattern language to assist you in selecting synchronization primitives for parallel programs. This pattern language assumes you have already chosen a locking design, perhaps by using a locking design pattern language [McK95b]. 1 Overview A lock-based parallel program uses synchronization primitives to define critical sections of code in which only one CPU at a time may execute concurrently. For example, Figure 1 presents a fragment of parall..