Replacing Locks by Higher-Level Primitives

Locks are used in shared memory parallel programs to achieve a variety of synchronization objectives. They may provide mutual exclusion for a critical section, or they may provide synchronized access to a task queue. In the former case, no ordering is implied between data operations outside of the critical sections, while in the latter case the operations preceding the enqueue of a task are ordered before the operations following a dequeue of that task. In this paper we argue that many uses of locks can be replaced by higher-level primitives that directly express the intended behavior, such as, for example, enqueue and dequeue operations on a task queue. This approach not only simplifies the programming model, but also allows a more efficient implementation. By making the intended use explicit, we can tailor the implementation of each primitive accordingly, thereby achieving reductions in latency and communication overhead. Synchronization latency has been shown to be one of the major ..