Eliminating Cache Conflict Misses Through XOR-based Placement Functions

Antonio González, Mateo Valero, Nigel Topham, Joan M. Parcerisa

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationProceedings of the 11th International Conference on Supercomputing
Place of PublicationNew York, NY, USA
Number of pages8
ISBN (Print)0-89791-902-5
Publication statusPublished - 1997

Publication series

NameICS '97


  • XOR-based placement functions, cache memory, conflict misses


Dive into the research topics of 'Eliminating Cache Conflict Misses Through XOR-based Placement Functions'. Together they form a unique fingerprint.

Cite this