Quasidynamic layout optimizations for improving data locality

Ismail Kadayif, Mahmut Kandemir

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Compiler-directed locality optimization techniques are effective in reducing the number of cycles spent in off-chip memory accesses. Recently, methods have been developed that transform memory layouts of data structures at compile-time to improve spatial locality of nested loops beyond current control-centric (loop nest-based) optimizations. Most of these data-centric transformations use a single static (program-wide) memory layout for each array. A disadvantage of these static layout-based locality enhancement strategies is that they might fail to optimize codes that manipulate arrays which demand different layouts in different parts of the code. In this paper, we introduce a new approach which extends current static layout optimization techniques by associating different memory layouts with the same array in different parts of the code. We call this strategy "quasidynamic layout optimization." In this strategy, the compiler determines memory layouts (for different parts of the code) at compile time, but layout conversions occur at runtime. We show that the possibility of dynamically changing memory layouts during the course of execution adds a new dimension to the data locality optimization problem. Our strategy employs a static layout optimizer module as a building block and, by repeatedly invoking it for different parts of the code, it checks whether runtime layout modifications bring additional benefits beyond static optimization. Our experiments indicate significant improvements in execution time over static layout-based locality enhancing techniques.

Original languageEnglish (US)
Pages (from-to)996-1011
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - Nov 2004

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Quasidynamic layout optimizations for improving data locality'. Together they form a unique fingerprint.

Cite this