Algorithms for Categorizing Multiprocessor Communication Under Invalidate andUpdate-Based Coherence Protocols

摘要

In this paper, we present algorithms that characterize the main sources ofcommunication 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.