Loop transformations
Authors:
Open Access
- 26 January 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 46 (1) , 549-562
Abstract
High-level loop transformations are a key instrument in mapping computational kernels to effectively exploit the resources in modern processor architectures. Nevertheless, selecting required compositions of loop transformations to achieve this remains a significantly challenging task; current compilers may be off by orders of magnitude in performance compared to hand-optimized programs. To address this fundamental challenge, we first present a convex characterization of all distinct, semantics-preserving, multidimensional affine transformations. We then bring together algebraic, algorithmic, and performance analysis results to design a tractable optimization algorithm over this highly expressive space. Our framework has been implemented and validated experimentally on a representative set of benchmarks running on state-of-the-art multi-core platforms.Keywords
This publication has 31 references indexed in Scilit:
- The Polyhedral Model Is More Widely Applicable Than You Think2010
- Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory HierarchiesInternational Journal of Parallel Programming, 2006
- Meta optimizationACM SIGPLAN Notices, 2003
- Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop TilingParallel Processing Letters, 1997
- A Parametrized Loop Fusion Algorithm for Improving Parallelism and Cache LocalityThe Computer Journal, 1997
- Fuzzy Array Dataflow AnalysisJournal of Parallel and Distributed Computing, 1997
- Improving data locality with loop transformationsACM Transactions on Programming Languages and Systems, 1996
- Some efficient solutions to the affine scheduling problem. I. One-dimensional timeInternational Journal of Parallel Programming, 1992
- Tiling multidimensional iteration spaces for multicomputersJournal of Parallel and Distributed Computing, 1992
- Dataflow analysis of array and scalar referencesInternational Journal of Parallel Programming, 1991