Javascript must be enabled to continue!
Parameterized loop tiling
View through CrossRef
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.
Association for Computing Machinery (ACM)
Title: Parameterized loop tiling
Description:
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.
Related Results
Parameterized Strings: Algorithms and Applications
Parameterized Strings: Algorithms and Applications
The parameterized string (p-string), a generalization of the traditional string, is composed of constant and parameter symbols. A parameterized match (p-match) exists between two p...
Optimization of a Geophysical Application in GPU Through the Loop Tiling Technique
Optimization of a Geophysical Application in GPU Through the Loop Tiling Technique
This work aims to present the results obtained in optimizing a viscoacoustic geophysical model written with the DEVITO tool and optimized using the OpenACC tile directive for GPU e...
To tile or not to tile?
To tile or not to tile?
Soils and landscapes vary within centimeters to decameters, which is not captured by state-of-the-art land-surface models that operate on kilometer scale. This leads to potential m...
Tiling Periodicity
Tiling Periodicity
We contribute to combinatorics and algorithmics of words by introducing new types of periodicities in words. A tiling period of a word w is partial word u such that w can be decomp...
Evaluation of origin of driving force for loop formation in a chromatin fiber
Evaluation of origin of driving force for loop formation in a chromatin fiber
Abstract
Chromosome condensation results from the formation of consecutive chromatin loops in which excluded volume interactions lead to chromoso...
Robot assisted tiling of glass mosaics with image processing
Robot assisted tiling of glass mosaics with image processing
PurposeThis paper describes a robotic system developed for tiling mosaics based on image processing according to customer expectations.Design/methodology/approachMany varieties of ...
Application of Aperiodic Tiling to Lattice Spatial Structures
Application of Aperiodic Tiling to Lattice Spatial Structures
The aim of this report is to expand on the existing available configurations for lattice spa- tial structures and in turn widen the range of design options that can be presented to...

