Parameterized loop tiling

Lakshminarayanan Renganarayanan, Daegon Kim, Michelle Mills Strout, Sanjay Rajopadhye

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

Loop tiling is a widely used program optimization that improves data locality and enables coarse-grained parallelism. Parameterized tiled loops, where the tile sizes remain symbolic parameters until runtime, are quite useful for iterative compilers and autotuners that produce highly optimized libraries and codes. 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. In the past, parameterized tiled code generation for the general case of convex iteration spaces being tiled by (hyper-) rectangular tiles has been solved with bounding box approaches or with sophisticated and expensive machinery. We present a novel formulation of the parameterized tiled loop generation problem using a polyhedral set called the outset. By reducing the problem of parameterized tiled code generation to that of generating standard loops and simple postprocessing of these loops, the outset method achieves a code generation efficiency that is comparable to existing code generation techniques, including those for fixed tile sizes. We compare the performance of our technique with several other tiled loop generation methods on kernels from BLAS3 and scientific computations. The simplicity of our solution makes it well suited for use in production compilers-in particular, the IBM XL compiler uses the inset-based technique introduced in this article for register tiling.We also provide a complete coverage of parameterized tiling of perfect loop nests by describing three related techniques: (i) a scheme for separating full and partial tiles; (ii) a scheme for generating tiled loops directly from the abstract syntax tree representation of loops; (iii) a formal characterization of parameterized loop tiling using bilinear forms and a Symbolic Fourier-Motzkin Elimination (SFME)-based parameterized tiled loop generation method.

Original languageEnglish (US)
Article number2160912
JournalACM Transactions on Programming Languages and Systems
Volume34
Issue number1
DOIs
StatePublished - Apr 2012
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Parameterized loop tiling'. Together they form a unique fingerprint.

Cite this