An Associativity Threshold Phenomenon in Set-Associative Caches

Michael A. Bender, Rathish Das, Martín Farach-Colton +1

In an $\alpha$-way set-associative cache, the cache is partitioned into disjoint sets of size $\alpha$, and each item can only be cached in one set, typically selected via a hash function. S…