CApRI: CAche-conscious data reordering for irregular codes

Caches play a critical role in today's computer systems and optimizing their performance has been a critical objective in the last couple of decades. Unfortunately, compared to a plethora of work in software and hardware directed code/data optimizations, much less effort has been spent in understanding the fundamental characteristics of data access patterns exhibited by application programs and their interaction with the underlying cache hardware. Therefore, in general it is hard to reason about cache behavior of a program running on a target system. Motivated by this observation, we first set up a "locality model" that can help us determine the theoretical bounds of the cache misses caused by irregular data accesses. We then explain how this locality model can be used for different data locality optimization purposes. After that, based on our model, we propose a data reordering (data layout reorganization) scheme that can be applied after any existing data reordering schemes for irregular applications to improve cache performance by further reducing the cache misses. We evaluate the effectiveness of our scheme using a set of 8 programs with irregular data accesses, and show that it brings significant improvements over the state-of-the-art on two commercial multicore machines.