Reducing Coherence Overheads with Multi-line Invalidation (MLI) Messages

Abstract

Most multiprocessors employ coherent caches despite the overheads of doing so. As future processors will be multi-processors with elaborate cache hierarchies, the overheads of cache coherence will be an important area for efficiency improvements. This paper proposes a novel technique, called Multi-Line Invalidation (MLI) messages, to reduce an important aspect of coherence overhead - the invalidation traffic - by combining multiple traditional (single-line) invalidation messages into a single message. MLI messages can be used alongside any traditional coherence protocols. Two empirical phenomena - the coarse-grain nature of data sharing and the trend towards programs that are free of data races - enhance the utility of MLI messages.

This paper illustrates how MLI messages could be constructed and deployed alongside an existing coherence protocol. It then presents an evaluation of their effectiveness in reducing the number of invalidation messages for several benchmark programs. We find that in several cases a significant reduction in the overall address network traffic and energy consumption could be achieved without performance degradation.