A Generalized Theory of Collaborative Caching

作者：Gu Xiaoming; Ding Chen

来源：ACM Sigplan Notices, 2012, 47(11): 109-119.

DOI：10.1145/2426642.2259012

• Algorithms
• Performance
• Theory
• collaborative caching
• cache replacement policy
• priority cache hint
• priority LRU
• optimal size-oblivious hint

Collaborative caching allows software to use hints to influence cache management in hardware. Previous theories have shown that such hints observe the inclusion property and can obtain optimal caching if the access sequence and the cache size are known ahead of time. Previously, the interface of a cache hint is limited, e.g., a binary choice between LRU and MRU.
In this paper, we generalize the hint interface, where a hint is a number encoding a priority. We show the generality in a hierarchical relation where collaborative caching subsumes non-collaborative caching, and within collaborative caching, the priority hint subsumes the previous binary hint. We show two theoretical results for the general hint. The first is a new cache replacement policy, priority LRU, which permits the complete range of choices between MRU and LRU. We prove a new type of inclusion property-non-uniform inclusion-and give a one-pass algorithm to compute the miss rate for all cache sizes. Second, we show that priority hints can enable the use of the same hints to obtain optimal caching for all cache sizes, without having to know the cache size beforehand.

• 出版日期2012-11