On Null Spaces and their Application to Model Randomisation and Interleaving in Cache Memories

Cache memories bridge the growing access-time gap between the processor and the
main memory. Cache memories use randomisation functions for two purposes: (i) to
limit the amount of search when looking up an address in the cache and (ii) to interleave
the access stream over multiple independent banks, allowing multiple simultaneous accesses. Sine the evaluation of these functions ours in the critical path, they have
to be quite simple. Most often, XOR-based functions are used because they an be
evaluated with low overhead. This report presents a mathematical model of XOR-based randomisation functions. The presented model is based on the null space representation of the functions. This representation allows results to be obtained very easily. The model is used to characterise several aspects of their behaviour, including local dispersion, inter-bank dispersion in skewed-associative caches and the interaction between set index functions and interleaving functions in interleaved caches.