Parameterized tiled loops for free

Lakshminarayanan Renganarayanan, Dae Gon Kim, Sanjay Rajopadhye, Michelle Mills Strout

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


Parameterized tiled loops - where the tile sizes are not fixed at compile time, but remain symbolic parameters until later - are quite useful for iterative compilers and "auto-tuners" that produce highly optimized libraries and codes. Tile size parameterization could also enable optimizations such as register tiling to become dynamic optimizations. Although it is easy to generate such loops for (hyper) rectangular iteration spaces tiled with (hyper) rectangular tiles, many important computations do not fall into this restricted domain. Parameterized tile code generation for the general case of convex iteration spaces being tiled by (hyper) rectangular tiles has in the past been solved with bounding box approaches or symbolic Fourier Motzkin approaches. However, both approaches have less than ideal code generation efficiency and resulting code quality. We present the theoretical foundations, implementation, and experimental validation of a simple, unified technique for generating parameterized tiled code. Our code generation efficiency is comparable to all existing code generation techniques including those for fixed tile sizes, and the resulting code is as efficient as, if not more than, all previous techniques. Thus the technique provides parameterized tiled loops for free! Our "one-size-fits-all" solution, which is available as open source software can be adapted for use in production compilers.

Original languageEnglish (US)
Pages (from-to)405-414
Number of pages10
JournalACM SIGPLAN Notices
Issue number6
StatePublished - Jun 2007
Externally publishedYes


  • Bounding box
  • Code generation
  • Fourier-Motzkin elimination
  • Parameterized tiling

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Parameterized tiled loops for free'. Together they form a unique fingerprint.

Cite this