An Associativity Threshold Phenomenon in Set-Associative Caches
An Associativity Threshold Phenomenon in Set-Associative Caches
复制标题
DOI：
10.1145/3558481.3591084
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
M. A. Bender;Rathish Das;Martín Farach-Colton;Guido Tagliavini
中科院分区：
文献类型：
--
作者：
M. A. Bender;Rathish Das;Martín Farach-Colton;Guido Tagliavini
In an α-way set-associative cache, the cache is partitioned into disjoint sets of size α, and each item can only be cached in one set, typically selected via a hash function. Set-associative caches are widely used and have many benefits, e.g., in terms of latency or concurrency, over fully associative caches, but they often incur more cache misses. As the set size α decreases, the benefits increase, but the paging costs worsen. In this paper we characterize the performance of an α-way set-associative LRU cache of total size k, as a function of α = α(k). We prove the following, assuming that sets are selected using a fully random hash function: For α = ω(log k), the paging cost of an α-way set-associative LRU cache is within additive O(1) of that a fully-associative LRU cache of size (1-o(1))k, with probability 1 - 1 / poly (k), for all request sequences of length poly (k). For α = o(log k), and for all c = O(1) and r = O(1), the paging cost of an α-way set-associative LRU cache is not within a factor c of that a fully-associative LRU cache of size k/r, for some request sequence of length O(k1.01). For α = ω(log k), if the hash function can be occasionally changed, the paging cost of an α-way set-associative LRU cache is within a factor 1 + o(1) of that a fully-associative LRU cache of size (1-o(1))k,概率为1-1/poly（k），用于任意的请求序列（例如，超级多项式）长度，我们的某些结果推广到LRU以外的其他分页算法，例如最不经常使用（LFU）。
In an α-way set-associative cache, the cache is partitioned into disjoint sets of size α, and each item can only be cached in one set, typically selected via a hash function. Set-associative caches are widely used and have many benefits, e.g., in terms of latency or concurrency, over fully associative caches, but they often incur more cache misses. As the set size α decreases, the benefits increase, but the paging costs worsen. In this paper we characterize the performance of an α-way set-associative LRU cache of total size k, as a function of α = α(k). We prove the following, assuming that sets are selected using a fully random hash function: For α = ω(log k), the paging cost of an α-way set-associative LRU cache is within additive O(1) of that a fully-associative LRU cache of size (1-o(1))k, with probability 1 - 1 / poly (k), for all request sequences of length poly (k). For α = o(log k), and for all c = O(1) and r = O(1), the paging cost of an α-way set-associative LRU cache is not within a factor c of that a fully-associative LRU cache of size k/r, for some request sequence of length O(k1.01). For α = ω(log k), if the hash function can be occasionally changed, the paging cost of an α-way set-associative LRU cache is within a factor 1 + o(1) of that a fully-associative LRU cache of size (1-o(1))k, with probability 1 - 1/poly (k), for request sequences of arbitrary (e.g., super-polynomial) length. Some of our results generalize to other paging algorithms besides LRU, such as least-frequently used (LFU).