Compile-time composition of run-time data and iteration reorderings

Michelle Mills Strout, Larry Carter, Jeanne Ferrante

Research output: Contribution to journalConference articlepeer-review

24 Scopus citations


Many important applications, such as those using sparse data structures, have memory reference patterns that are unknown at compile-time. Prior work has developed run-time reorderings of data and computation that enhance locality in such applications. This paper presents a compile-time framework that allows the explicit composition of run-time data and iteration-reordering transformations. Our framework builds on the iteration-reordering framework of Kelly and Pugh to represent the effects of a given composition. To motivate our extension, we show that new compositions of run-time reordering transformations can result in better performance on three benchmarks. We show how to express a number of run-time data and iteration-reordering transformations that focus on improving data locality. We also describe the space of possible run-time reordering transformations and how existing transformations fit within it. Since sparse tiling techniques are included in our framework, they become more generally applicable, both to a larger class of applications, and in their composition with other reordering transformations. Finally, within the presented framework data need be remapped only once at runtime for a given composition thus exhibiting one example of overhead reductions the framework can express.

Original languageEnglish (US)
Pages (from-to)91-102
Number of pages12
JournalSIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Issue number5
StatePublished - May 2003
Externally publishedYes
EventProceedings of the ACM Sigplan 2003 Conference on Programming Language Design and Implementation - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003


  • Data remapping
  • Inspector/executor
  • Iteration reordering
  • Optimization
  • Run-time transformations
  • Sparse tiling

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Compile-time composition of run-time data and iteration reorderings'. Together they form a unique fingerprint.

Cite this