Our work builds on the research in programmable protocol processors being pioneered by the Stanford FLASH [16] and Wisconsin Typhoon [20] projects. In comparison to silicon implementations, dedicated but programmable protocol processors offer the opportunity to obtain significant performance improvements with no appreciable increase in hardware cost.
On the algorithmic side, our work bears resemblance to a number of systems that provide shared memory and coherence in software using a variant of lazy release consistency. Munin [4] collects all write notices from a processor and posts them when the processor reaches a synchronization release point. ParaNet (Treadmarks) [14] relaxes the Munin protocol further by postponing the posting of write notices until the subsequent acquire. Both Munin and ParaNet are designed to run on networks of workstations, with no hardware support for coherence.
Petersen and Li [19] have presented a lazy release consistent protocol for small scale multiprocessors with caches but without cache coherence. Their approach posts notices eagerly, using a centralized list of weak pages, but only processes notices at synchronization acquire points. The protocol presented in this paper is most closely related to a protocol developed for software coherence on large-scale NUMA multiprocessors [15]. Both protocols use the concept of write notices and of a distributed directory. Unlike the software protocol, however, the one presented here works better when it does not postpone posting notices. It has also been modified to execute coherence operations and application code in parallel, and to deal with the fact that a processor can lose a block due to capacity and conflict evictions.
Our work is also similar to the delayed consistency protocol and
invalidation scheduling work of Dubois et
al. [7,8]. Both
protocols (ours and theirs) attempt to reduce the impact of false
sharing in applications. Their work however assumes a single owner
and requires a processor to obtain a new copy on write hits to a stale
block.
Their protocol incurs longer delays for write accesses to
falsely-shared blocks and increases the application's miss rate.
Their experiments also assume infinite caches, which exaggerate the
importance of coherence misses, and they use miss rate as the measure
of performance. As we have shown in section 4.3, miss
rate is only a partial indicator of program performance and can sometimes be
misleading. Excessively lazy protocols can actually hurt performance,
even though they improve the application's miss rate.
The formalization of data-race-free-1 by Adve and Hill [1] allows the same optimizations as used in our protocol. We focus however on the hardware design and performance evaluation aspects of the protocol, while they concentrate on formally defining the behavior of the consistency model for different access patterns.
False sharing can be dealt with in software using compiler techniques [9]. Similarly, the latency of write misses on blocks that are already cached read-only can be reduced by a compiler that requests writable copies when appropriate [22]. These techniques are not always successful, however. The former must also be tuned to the architecture's block size, and the latter requires a load-exclusive instruction. We view our protocol as complementary to the work a compiler would do. If the compiler is successful then our protocol will incur little or no additional overhead over eager release consistency. If, however, the application still suffers from false sharing, or from a significant number of write-after-read delays, then lazy release consistency will yield significant performance improvements.