Eliminating Cache Conflict Misses Through XOR-based Placement Functions

functions for cache memories. It shows that these XOR-mapping
schemes can eliminate many conflict misses for direct-mapped and
victim caches and practically all of them for (pseudo) two-way
associative organizations. The paper evaluates the performance of
XOR-mapping schemes for a number of different cache
organizations: direct-mapped, set-associative, victim, hash-rehash,
column-associative and skewed-associative. It also proposes novel
replacement policies for some of these cache organizations. In
particular, it presents a low-cost implementation of a pure LRU
replacement policy which demonstrates a significant improvement
over the pseudo-LRU replacement previously proposed. The paper
shows that for a 8 Kbyte data cache, XOR-mapping schemes
approximately halve the miss ratio for two-way associative and
column-associative organizations. Skewed-associative caches,
which already make use of XOR-mapping functions, can benefit
from the LRU replacement and also from the use of more
sophisticated mapping functions. For two-way associative, columnassociative
and two-way skewed-associative organizations, XORmapping
schemes achieve a miss ratio that is not higher than 1.10
times that of a fully-associative cache. XOR mapping schemes also
provide a very significant reduction in the miss ratio for the other
cache organizations, including the direct-mapped cache.
Ultimately, the conclusion of this study is that XOR-based
placement functions unequivocally provide highly significant
performance benefits to most cache organizations.