Remote memory accesses experience long latencies in large shared-memory multiprocessors, and are one of the most serious impediments to good parallel program performance. Relaxed consistency models [6,11] can help reduce the cost of memory accesses by masking the latency of write operations. Relaxed consistency requires that memory be consistent only at certain synchronization events, and thus allows a protocol to buffer, merge, and pipeline write requests as long as it respects the consistency constraints specified in the model.
Release consistency [10] is the most widely accepted relaxed consistency model. Under release consistency each memory access is classified as an ordinary access, an acquire, or a release. A release indicates that the processor is completing an operation on which other processors may depend; all of the releasing processor's previous writes must be made visible to any processor that performs a subsequent acquire. An acquire indicates that the processor is beginning an operation that may depend on some other processor; writes by processors that have performed previous release operations must now be made locally visible.
This definition of release consistency provides considerable flexibility to a coherence protocol designer as to when to make writes by a processor visible to other processors. Hardware implementations of release consistency, as in the DASH multiprocessor [18], take an eager approach: write operations trigger coherence transactions (e.g., invalidations) immediately, though the transactions execute concurrently with continued execution of the application. The processor stalls only if its write buffer overflows, or if it reaches a release operation and some of its previous transactions have yet to be completed. This approach attempts to mask the latency of writes by allowing them to take place in the background of regular computation.
The better software coherence protocols adopt a lazier approach for distributed shared memory (DSM) emulation, delaying coherence transactions further, in an attempt to reduce the total number of messages exchanged. A processor in Munin [4], for example, buffers all of the ``write notices'' associated with a particular critical section and sends them when it reaches a release point. TreadMarks (ParaNet) [14] goes further: rather than send write notices to all potentially interested processors at the time of a release, it keeps records that allow it to inform an acquiring processor of all (and only) those write notices that are in the logical past of the releaser but not (yet) in the logical past of the acquirer.
Postponing coherence transactions allows a protocol to combine messages between a given pair of processors and to avoid many of the useless invalidations caused by false sharing [8]. Keleher et al. have shown these optimizations to be of significant benefit in their implementation of lazy release consistency [13] for DSM systems. Ideally, one might hope to achieve similar benefits for hardware-coherent systems. The sheer complexity of lazy protocols, however, has heretofore precluded their implementation in hardware. Several research groups, however, are now developing programmable protocol processors [16,20] for which the complexity of lazy release consistency may be manageable. What remains is to determine whether laziness will be profitable in these sorts of systems, and if so to devise a protocol that provides the best possible performance.
In this paper we present a protocol that combines the most desirable aspects of lazy release consistency (reducing memory latency by avoiding unnecessary invalidations) with those of eager release consistency (reducing synchronization waits by executing coherence operations in the background). This protocol supports multiple concurrent writers, overlaps the transfer of write notices with computation, and delays invalidations until acquire operations. It outperforms eager release consistency by up to 20% on a variety of applications.
We also consider a lazier protocol that delays sending write notices until release operations. Our results indicate, however, that this lazier protocol actually hurts overall program performance, since its reduction of memory access latency does not compensate for an increased synchronization overhead. This result reveals a qualitative difference between software and hardware distributed shared-memory multiprocessors: delaying coherence operations as much as possible is appropriate for DSM systems, but not for hardware-assisted coherence.
The rest of the paper is organized as follows. Section 2 describes our lazy protocol, together with the lazier variant that delays the sending of write notices. Section 3 describes our experimental methodology and application suite. Section 4 presents results. It begins with a discussion of the sharing patterns exhibited by the applications, and proceeds to compare the performance of our lazy protocols to that of an eager release consistency protocol similar to the one implemented in the DASH multiprocessor. Finally, it describes the impact of architectural trends on the relative performance of the protocols. We present related work in section 5 and conclude in section 6.