Accession Number : ADA290022

Title :   Algorithms for Categorizing Multiprocessor Communication Under Invalidate and Update-Based Coherence Protocols.

Descriptive Note : Technical rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Bianchini, Ricardo ; Kontothanassis, Leonidas

PDF Url : ADA290022

Report Date : SEP 1994

Pagination or Media Count : 24

Abstract : In this paper, we present algorithms that characterize the main sources of communication generated by parallel applications under both invalidate and update based cache coherence protocols. The algorithms provide insight into the reference and sharing patterns of parallel programs and into the amount of useless traffic entailed by each coherence protocol. Under an invalidate based protocol, our algorithms classify the data traffic caused by the different types of cache misses. Under an update based protocol, our algorithms not only categorize the data traffic, but also classify update transactions with respect to the sharing patterns that caused them. Although our algorithms deal with numerous hardware features such as finite sized caches and coalescing write buffers, our categorization is widely applicable and can be easily simplified for use in less detailed environments. Our work extends previous categorizations of cache misses in write invalidate protocols, while introducing a new categorization of the coherence traffic in update based protocols.

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSING, *MULTIPROCESSORS, COMPUTERIZED SIMULATION, BUFFERS, COMPUTER COMMUNICATIONS, COMMUNICATIONS TRAFFIC, COHERENCE, SHARING, PATTERNS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE