Address correlation: Exceeding the limits of locality

1—We investigate a program phenomenon, Address Correlation, which links addresses that reference the same data. This work shows that different addresses containing the same data can often be correlated at run-time to eliminate a load miss or a partial hit. For ten of the SPEC CPU2000 benchmarks, 57 to 99% of all L1 data cache load misses, and 4 to 85% of all partial hits, can be supplied from a correlated address already found in the cache. Our source code-level analysis shows that semantically equivalent information, duplicated references, and frequent values are the major causes of address correlations. We also show that, on average, 68% of the potential correlated addresses that could supply data on a miss of an address containing the same value can be correlated at run time. These correlated addresses correspond to an average of 62% of all misses in the benchmark programs tested.