online read us now
Paper details
Number 4 - December 2016
Volume 26 - 2016
Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs
Włodzimierz Bielecki, Marek Pałkowski
Abstract
A novel approach to generation of tiled code for arbitrarily nested loops is presented. It is derived via a combination of
the polyhedral and iteration space slicing frameworks. Instead of program transformations represented by a set of affine
functions, one for each statement, it uses the transitive closure of a loop nest dependence graph to carry out corrections
of original rectangular tiles so that all dependences of the original loop nest are preserved under the lexicographic order
of target tiles. Parallel tiled code can be generated on the basis of valid serial tiled code by means of applying affine
transformations or transitive closure using on input an inter-tile dependence graph whose vertices are represented by target
tiles while edges connect dependent target tiles. We demonstrate how a relation describing such a graph can be formed. The
main merit of the presented approach in comparison with the well-known ones is that it does not require full permutability
of loops to generate both serial and parallel tiled codes; this increases the scope of loop nests to be tiled.
Keywords
tiling, transitive closure, source-to-source compiler, polyhedral model, iteration space slicing