Accession Number:

ADA289893

Title:

Eliminating Useless Messages in Write-Update Protocols on Scalable Multiprocessors.

Descriptive Note:

Technical rept.,

Corporate Author:

ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Report Date:

1994-10-01

Pagination or Media Count:

32.0

Abstract:

Cache coherence protocols for shared-memory multiprocessors use invalidations or updates to maintain coherence across processors. Although invalidation protocols usually produce higher miss rates, update protocols typically perform worse. Detailed simulations of these two classes of protocol show that the excessive network traffic caused by update protocols significantly degrades performance, even with infinite bandwidth. Motivated by this observation, we categorize the coherence traffic in update-based protocols and show that, for most applications, more than 90 of all updates generated by the protocol are unnecessary. We identify application characteristics that generate useless update traffic, and compare the isolated and combined effects of several software and hardware techniques for eliminating useless updates. These techniques include dynamic and static hybrid protocols, false sharing elimination strategies, and coalescing write buffers. Our simulations show that software caching where coherence is managed under programmer or compiler control and the dynamic hybrid protocol reduce useless updates the most, but coalescing write buffers produce fewer, albeit larger, coherence messages. As a result, coalescing write buffers usually produce the best running time, except when the block size is large or the bandwidth is limited. Finally, based on the observation that the techniques we consider are unable to eliminate a large number of useless updates, we suggest directions for further reducing the useless traffic in update-based protocols.

Subject Categories:

  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE