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

Personal Author(s) : Bianchini, Ricardo ; LeBlanc, Thomas J. ; Veenstra, Jack

PDF Url : ADA289893

Report Date : OCT 1994

Pagination or Media Count : 32

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.

Descriptors :   *COMMUNICATIONS TRAFFIC, *DATA REDUCTION, *MULTIPROCESSORS, *MESSAGE PROCESSING, COMPUTER PROGRAMS, BUFFERS, CONTROL, STRATEGY, DATA TRANSMISSION SYSTEMS, SIZES(DIMENSIONS), VALIDATION, DYNAMICS, OBSERVATION, COHERENCE, TIME, SHARING, DATA ACQUISITION, HYBRID SYSTEMS, COMPUTER NETWORKS, BANDWIDTH, STATICS, COMPILERS, ELIMINATION.

Subject Categories : Computer Hardware
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE