On the Effectiveness of XOR-Mapping Schemes for Cache Memories

XOR-mapping schemes were initially proposed in the context of interleaved memories to provide a pseudorandom distribution of memory addresses among multiple memory modules. In that context, the objective was to allow multiple memory references to proceed in parallel by ensuring that they access different memory modules. XOR-mapping schemes can also provide significant benefits for cache memories. In this case, the objective is to avoid conflicts between different data structures that are accessed concurrently during the execution of a program. In spite of this potential benefit, there are very few proposals in the literature that make use of such schemes. This paper evaluates the performance of XOR-mapping schemes for a number of different cache organizations: direct-mapped, set-associative, victim, hash-rehash, columnassociative and skewed-associative. It also proposes novel replacement policies for some of these cache organizations. In particular, it presents a low-cost implementatio..