A practical automatic polyhedral parallelizer and locality optimizer
Uday Kumar Reddy Bondhugula, Albert Hartono, Jagannathan Ramanujam et al. · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 2008
We present the design and implementation of an automatic polyhedral source-to-source transformation framework that can optimize regular programs (sequences of possibly imperfectly nested loops) for parallelism and locality simultaneously. Through this work, we show the practicality of analytical model-driven automatic transformation in the polyhedral model -- far beyond what is possible by current production compilers. Unlike previous works, our approach is an end-to-end fully automatic one driven by an integer linear optimization framework that takes an explicit view of finding good ways of tiling for parallelism and locality using affine transformations. The framework has been implemented into a tool to automatically generate OpenMP parallel code from C program sections. Experimental results from the tool show very high speedups for local and parallel execution on multi-cores over state-of-the-art compiler frameworks from the research community as well as the best native production compilers. The system also enables the easy use of powerful empirical/iterative optimization for general arbitrarily nested loop sequences.
Cited by 880 works. doi:10.1145/1375581.1375595
Authors
References
- A generalized inverse for matrices
- Theory of Linear and Integer Programming
- Theory of Linear and Integer Programming
- Automatic translation of FORTRAN programs to vector form
- A data locality optimizing algorithm
- Automated empirical optimizations of software and the ATLAS project
- A loop transformation theory and an algorithm to maximize parallelism
- Supernode partitioning
- The Omega test: a fast and practical integer programming algorithm for dependence analysis
- A practical algorithm for exact array dependence analysis