ADJUSTING A PROGRAM TRANSFORMATION FOR LEGALITY
Abstract
Program transformations are one of the most valuable compiler techniques to improve parallelism or data locality. However, restructuring compilers have a hard time coping with data dependences. A typical solution is to focus on program parts where the dependences are simple enough to enable any transformation. For more complex problems is only addressed the question of checking whether a transformation is legal or not. In this paper we propose to go further. Starting from a transformation with no guarantee on legality, we show how we can correct it for dependence satisfaction. Two directions are explored: first when transformation properties can be explicitly expressed and second when they are implicit as in the data locality transformation case. Generating code having the best properties is a direct application of this result.
References
- N. Ahmed, N. Mateev, and K. Pingali. Tiling imperfectly-nested loop nests. In SC'2000 High Performance Networking and Computing, Dallas, November 2000 . Google Scholar
- ACM Transactions on Programming Languages and Systems 9(4), 491 (1987). Crossref, ISI, Google Scholar
- U. Banerjee. Data dependence in ordinary programs. Master's thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, November 1976 . Google Scholar
-
U. Banerjee , Dependence Analysis for Supercomputing ( Kluwer Academic , 1988 ) . Crossref, Google Scholar - U. Banerjee. Unimodular transformations of double loops. In Advances in Languages and Compilers for Parallel Processing, pages 192–219, Irvine, August 1990 . Google Scholar
- C. Bastoul. Efficient code generation for automatic parallelization and optimization. In ISPDC'03 IEEE International Symposium on Parallel and Distributed Computing, pages 23–30, Ljubljana, October 2003 . Google Scholar
- C. Bastoul, A. Cohen, S. Girbal, S. Sharma, and O. Temam. Putting polyhedral transformations to work. In LCPC'16 International Workshop on Languages and Compilers for Parallel Computers LNCS 2958, pages 209–225, College Station, October 2003 . Google Scholar
- C. Bastoul and P. Feautrier. Improving data locality by chunking. In CC'12 International Conference on Compiler Construction, LNCS 2622, pages 320–335, Warsaw, April 2003 . Google Scholar
- IEEE Transactions on Electronic Computers 15(5), 757 (1966). Google Scholar
- A. Cohen, S. Girbal, and O. Temam. A polyhedral approach to ease the composition of program transformations. In Euro-Par'10 International Euro-Par Conference, Pisa, August 2004 . Google Scholar
- RAIRO Recherche Opérationnelle 22(3), 243 (1988). Crossref, ISI, Google Scholar
- International Journal of Parallel Programming 20(1), 23 (1991). Crossref, ISI, Google Scholar
- International Journal of Parallel Programming 21(5), 313 (1992). Crossref, ISI, Google Scholar
- Concurrency and Computation: Practice and Experience 16(3), 221 (2004). Crossref, ISI, Google Scholar
- M. Griebl, C. Lengauer, and S. Wetzel. Code generation in the polytope model. In PACT'98 International Conference on Parallel Architectures and Compilation Techniques, pages 106–111, 1998 . Google Scholar
- F. Irigoin and R. Triolet. Computing dependence direction vectors and dependence cones with linear systems, Technical Report ENSMP-CAI-87-E94, Ecole des Mines de Paris, Fontainebleau (France), 1987 . Google Scholar
- I. Kodukula, N. Ahmed, and K. Pingali. Data-centric multi-level blocking. In ACM SIGPLAN'97 Conference on Programming Language Design and Implementation, pages 346–357, Las Vegas, June 1997 . Google Scholar
-
D. Kuck , The Structure of Computers and Computations ( John Wiley & Sons Inc. , 1978 ) . Google Scholar - C. Lengauer. Loop parallelization in the polytope model. In International Conference on Concurrency Theory, LNCS 715: pages 398–416, Hildesheim, August 1993 . Google Scholar
- International Journal of Parallel Programming 22(2), 183 (1994). Crossref, ISI, Google Scholar
- ACM Transactions on Programming Languages and Systems 18(4), 424 (1996). Crossref, ISI, Google Scholar
- Communications of the ACM 29(12), 1184 (1996). Crossref, ISI, Google Scholar
- W. Pugh. The omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of the third ACM/IEEE conference on Super-computing, pages 4–13, Albuquerque, August 1991 . Google Scholar
-
A. Schrijver , Theory of linear and integer programming ( John Wiley & Sons , 1986 ) . Google Scholar - M. Wolf and M. Lam. A data locality optimizing algorithm. In ACM SIGPLAN'91 Conference on Programming Language Design and Implementation, pages 30–44, New York, June 1991 . Google Scholar
- M. Wolfe. Iteration space tiling for memory hierarchies. In 3rd SIAM Conference on Parallel Processing for Scientific Computing, pages 357–361, December 1987 . Google Scholar
-
M. Wolfe , High performance compilers for parallel computing ( Addison-Wesley Publishing Company , 1995 ) . Google Scholar - Parallel Processing Letters 7(4), 409 (1997). Link, Google Scholar


