CApRI: CAche-conscious data reordering for irregular codes

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)477-489
Number of pages13
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 20 2014
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2014 - Austin, United States
Duration: Jun 16 2014Jun 20 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'CApRI: CAche-conscious data reordering for irregular codes'. Together they form a unique fingerprint.

Cite this