Andy Glew's comp-arch.net wiki, http://semipublic.comp-arch.net
If you are reading this elsewhere, e.g. at site waboba.info, it is an unauthorized copy, and probably a malware site.
comp-arch.net wiki on hold from October 17, 2011
Cache inclusion
From CompArch
http://semipublic.comp-arch.net/wiki/Cache_inclusion
Cache inclusion is a property, or design principle, for multilevel and shared caches and hierarchies thereof.
Terminology
- Inclusive cache
- An inclusive cache is an outer cache that includes all cache lines in any inner cache(s) that it surrounds or dominates.
- This inclusion property allows, for example, the outer cache to filter all requests from the outside world (in some situations).
- Exclusive cache
- An exclusive cache is an outer cache that is guaranteed not to contain any cache lines present in any of its inner cache(s).
Since the set of inner cache(s) and exclusive outer cache has more lines than the set of inner cache(s) with inclusive outer cache, the exclusive cache hierarchy is likely to have a higher cache hit rate than the inclusive cache hierarchy. However, an exclusive cache cannot snoop filter in and of itself. And the extra data movement required - typically a clean cache line evicted from an inner cache must be moved back to an exclusive outer cache - results in increased power, and sometimes slows down the entire cache hierarchy.
Typically an exclusive cache arrangement is used when the inner and outer caches are close in size, e.g. 1:4 or 1:8.
Exclusive caches are not so well suited to be used as shared caches; or, rather, exclusive caches are not so well suited to be used as the cache through which sharing is done. Exclusive caches can be used in shared systems, e.g. when the inner caches are closely cooperating peer caches with cache to cache transfers - in which case an exclusive outer cache is basically just a victim cache for the pool of peer shared caches.
- Non-inclusive/non-exclusive cache (NI/NE)
- A NI/NE cache is a cache that is neither inclusive nor exclusive. Wen-Hann Wang, the inventor of both cache inclusion and NI/NE, called it accidentally inclusive. To a first order, the inner and outer caches operate independently, doing whatever they want, managing LRU any way the want. All inner and outer caches in an NI/NE hierarchy must be probed or snooped - there is no cache inclusion property to support probe filtering. However, NI/NE caches may use LRU leak-through to somewhat coordinate the caches - just as inclusive caches should also.
Many students, educated via early versions of Hennessy & Patterson, are surprised when they encounter the Intel P6 family's non-inclusive/non-exclusive caches. In fact, it is not just students and new college graduates - many experienced researchers from other companies, when hired by, or when their companies were absorbed by Intel, were surprised to learn about NI/NE. Many have thought that their first big revolutionary contribution to Intel would be to change over to proper cache inclusion.
They might also be surprised to learn that these NI/NE caches were actually invented by Wen-Hann Wang, the guy who invented cache inclusion.
Suffice it to say that the most widely sold cache hierarchy, 1995-2010, was neither inclusive nor exclusive. That there are reasons, both technical for particular design points, and historical, for an NI/NE design. See Why non-inclusive/non-exclusive caches?
Lest I seem too assertive, let me also say that there are also good reasons not to use NI/NE, to to instead use inclusion and/or exclusion. And that, in 2011, NI/NE designs are probably usually not the favored design point.
However, let me also express an opinion that inclusive caches are probably overused. In many cases an inclusive cache filter and a non-inclusive/non-exclusive cache is sometimes a better design solution.
Academic References
Wen-Hann Wang's research, in this thesis and other publications, is, I believe, the origin of cache inclusion:
- J.-L. Baer and W.-H. Wang. 1988. On the inclusion properties for multi-level cache hierarchies. In Proceedings of the 15th Annual International Symposium on Computer architecture (ISCA '88). IEEE Computer Society Press, Los Alamitos, CA, USA, 73-80.
- J.-L. Baer and W.-H. Wang. 1988. On the inclusion properties for multi-level cache hierarchies. SIGARCH Comput. Archit. News 16, 2 (May 1988), 73-80. DOI=10.1145/633625.52409
- Wen-Hann Wang. 1989. Multilevel Cache Hierarchies. Ph.D. Dissertation. University of Washington. AAI9013828.
- Jean-Loup Baer, Wen-Hann Wang, Multilevel cache hierarchies: Organizations, protocols, and performance, Journal of Parallel and Distributed Computing, Volume 6, Issue 3, June 1989, Pages 451-476, ISSN 0743-7315, DOI: 10.1016/0743-7315(89)90001-4.
(http://www.sciencedirect.com/science/article/B6WKJ-4BRJHWS-R/2/c3f0652e1deaafed5e1072978fc3a23a)
He received the first ACM SIGARCH and IEEE-CS TCCA ISCA Influential Paper Award http://www.sigarch.org/influential_paper.html for the 1988 ISSCA paper.
