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

Michelle Mills Strout, Larry Carter, Jeanne Ferrante

Research output: Contribution to conferencePaperpeer-review

50 Scopus citations

Abstract

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 re-ordering 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)
Pages91-102
Number of pages12
DOIs
StatePublished - 2003
Externally publishedYes
EventACM SIGPLAN Conference on Programming Language Design and Implementation - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Conference

ConferenceACM SIGPLAN Conference on Programming Language Design and Implementation
Country/TerritoryUnited States
CitySan Diego, CA
Period6/9/036/11/03

Keywords

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

ASJC Scopus subject areas

  • Software

Fingerprint

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

Cite this