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 under- standing the fundamental characteristics of data access pat- terns exhibited by application programs and their interac- tion with the underlying cache hardware. Therefore, in gen- eral 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 deter- mine 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 irreg- ular 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 ac- cesses, and show that it brings significant improvements over the state-of-the-art on two commercial multicore machines.