Parameterized tiled loops for free
Authors:
Open Access
- 10 June 2007
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 42 (6) , 405-414
Abstract
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.Keywords
This publication has 21 references indexed in Scilit:
- Implicit and explicit optimizations for stencil computations2006
- Dynamic tiling for effective use of shared caches on multithreaded processorsInternational Journal of High Performance Computing and Networking, 2004
- An efficient code generation technique for tiled iteration spacesIEEE Transactions on Parallel and Distributed Systems, 2003
- Register tiling in nonrectangular iteration spacesACM Transactions on Programming Languages and Systems, 2002
- Iterative Compilation2002
- Optimal Orthogonal Tiling of 2-D IterationsJournal of Parallel and Distributed Computing, 1997
- SUIFACM SIGPLAN Notices, 1994
- (Pen)-ultimate tiling?Integration, 1994
- Tiling multidimensional iteration spaces for multicomputersJournal of Parallel and Distributed Computing, 1992
- A practical algorithm for exact array dependence analysisCommunications of the ACM, 1992