An adaptive cache coherence protocol: Trading storage for traffic

This paper introduces a new adaptive cache coherence protocol which minimizes energy requirements and guarantees scalability. It includes two complementary parts: a non-inclusive sparse-directory to track only actively shared blocks and a structure to determine the presence of a block in the private caches based on an improved counting bloom filter. It uses token counting to preserve the system correctness, to improve performance and to reduce the implementation complexity. Combining all these characteristics, the proposal has a low storage overhead and is able to suppress most of the traffic inherent to snoop-based protocols and reduce the size of directory-based structures. Using a capacity to track only 40% of all the blocks allocated in the private caches, this coherence protocol is able to achieve better performance than an over-provisioned sparse-directory with a capacity to track 160% of the blocks kept in private caches. The complementarity of both structures enables the coherence controller to change dynamically the way the storage available is dedicated according to the data-sharing properties of the application. Thus, applications with high-sharing degree will need more directory space while low-sharing degree patterns will need more private block-presence space to include more information. With only 5% of the private cache entries tracked, the average performance degradation is less than 8% compared to a 160% over-provisioned sparse-directory.