next up previous
Next: Related Work Up: Results Previous: Lazy v. Eager

How Much Laziness is Required?


Figure 4: Normalized execution time for lazy and lazy-extended consistency on 64 processors

Figure 5: Overhead analysis for lazy, lazy-extended, and sequential consistency (left to right) on 64 processors

Unlike the basic lazy protocol we have evaluated so far, software-coherent systems implementing lazy release consistency attempt to further postpone the processing of writes to shared data, by combining writes and processing them at synchronization release points. This ``aggressive laziness'' allows unrelated acquire synchronization operations to proceed without having to invalidate cache lines that have been modified by the releasing processor. As a result programs experience reduced miss rates and reduced miss latencies. However, moving the processing of write operations to release points has the side effect of increasing the amount of time a processor spends waiting for the release to complete. For software systems this is not usually a problem, since write notices cannot be processed in parallel with computation, and the same penalty has to be paid regardless of when they are processed. On systems with hardware support for coherence, however, the coherence overhead associated with writes can be overlapped with the program's computation, so long as the program has something productive to do. The aggressively lazy protocol effectively eliminates this overlap, and can end up hurting performance due to increased synchronization costs.

Figure 4 shows the normalized execution times of our original lazy protocol and its lazier variant. We will refer to the lazier protocol from now on as lazy-ext. The analysis of overheads for the two versions of the protocols is shown in figure 5. As in the previous section normalization is done with respect to the run time and the overheads experienced by a sequentially consistent protocol.

For all but one of the applications the lazier version of the protocol has poorer overall performance. This finding stands in contrast to previously-reported results for DSM systems [13], and is explained by the ability to overlap the processing of non-delayed write notices. As can be seen from figure 5, the lazy-ext protocol improves the miss latency experienced by the programs, but increases the amount of time spent waiting for synchronization. The former is insufficient to offset the latter, resulting in program performance degradation. The exception to this observation is fft. Fft computes a 1-D FFT in phases, separated by a barrier. Delaying the processing of writes allows home nodes to combine the processing of write requests to the same block, since these requests arrive more-or-less simultaneously at the time of the barrier. There is no increase in synchronization time, and processors experience shorter delays between barriers since all events between barriers are local. The observed miss rate for the applications also agrees with the observed miss latency, and is lowest under the lazy-ext protocol.

We have also run experiments varying the latency, bandwidth, and cache line size parameters for our systems. We have found that as latency and bandwidth increase the performance gap between the lazy and eager protocols decreases, with the lazy protocol maintaining a modest performance advantage over all latency/bandwidth combinations. Varying the cache line size results in predictable behavior. Longer cache lines increase the performance gap between the lazy and eager protocols since they induce higher degrees of false sharing. While the trend toward increasing block sizes is unlikely to go on forever [2], 256-byte cache blocks seem plausible for the near-term future, suggesting that lazy protocols will become increasingly important. A performance comparison among the lazy and eager protocols for a future hypothetical machine with high latency (40 cycles memory startup), high bandwidth (4bytes/cycle), and long cache lines (256 bytes) can be seen in figure 6. Lazy release consistency can be seen to outperform the eager alternative for all applications. In the applications where lazy release consistency was important in our earlier experiments, the performance gap has increased even further. In mp3d the performance gap has widened by an additional 6% over the original experiment; lazy consistency outperforms the eager variant by 23%. Similar gains were achieved by the other applications as well. The performance gap between lazy and eager release consistency has increased by 2 to 4 percentage points when compared with the performance difference seen in the original experiments. The observations made for the earlier overhead breakdown graphs continue to apply. As can be seen in figure 7 the lazy protocols trade increased synchronization time for decreased read latency and write buffer stall time. The additional advantage of laziness for this future machine stems from increases in cache line size and memory startup latency (as measured in processor cycles): longer lines increase the potential for false sharing, and increased memory startup costs increase the cost of servicing read misses.

Figure 6: Performance trends for lazy, lazier, and eager release consistency (execution time)

Figure 7: Performance trends for lazy, lazier, eager, and sequential consistency (left to right), (overhead analysis)

next up previous
Next: Related Work Up: Results Previous: Lazy v. Eager

Leonidas Kontothanassis
Mon Jul 24 22:40:09 EDT 1995