Address Correlation: Exceeding the Limits of Locality

We investigate a program phenomenon, Address Correlation, which links addresses that reference the same data.This work shows that different addresses containing the samedata can often be correlated at run-time to eliminate a load missor a partial hit. For ten of the SPEC CPU2000 benchmarks, 57 to99% of all L1 data cache load misses, and 4 to 85% of all partialhits, can be supplied from a correlated address already found inthe cache. Our source code-level analysis shows that semanticallyequivalent information, duplicated references, and frequentvalues are the major causes of address correlations. We also showthat, on average, 68% of the potential correlated addresses thatcould supply data on a miss of an address containing the samevalue can be correlated at run time. These correlated addressescorrespond to an average of 62% of all misses in the benchmarkprograms tested.