A Statistical Model of Skewed Associativity

This paper presents a statistical model of set-associativity, victim caching and skewed-associativity, with an emphasis on skewed-associativity. We show that set-associativity is not efficient when the working-set size is close to the cache size. We refer to this as the unit working-set problem. We show that victim-caching is not a practical solution to the unit working-se- t problem either, although victim caching emulates full associativity for working-sets much larger than the victim buffer itself. On the other hand we show that 2-way skewed associativity emulates full associativity for working-sets up to half the cache size, and that 3-way skewed-associativity is almost equivalent to full associativity, i.e., skewed-associativity is a practical solution to the unit working-set problem