An Associativity Threshold Phenomenon in Set-Associative Caches
Michael A. Bender, Rathish Das, Martı́n Farach-Colton, Guido Tagliavini · 2023
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.