World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ADJUSTING A PROGRAM TRANSFORMATION FOR LEGALITY

    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
    • J. Allen and K. Kennedy, ACM Transactions on Programming Languages and Systems 9(4), 491 (1987). Crossref, ISIGoogle 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 ) . CrossrefGoogle 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
    • A. Bernstein, 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
    • P. Feautrier, RAIRO Recherche Opérationnelle 22(3), 243 (1988). Crossref, ISIGoogle Scholar
    • P. Feautrier, International Journal of Parallel Programming 20(1), 23 (1991). Crossref, ISIGoogle Scholar
    • P. Feautrier, International Journal of Parallel Programming 21(5), 313 (1992). Crossref, ISIGoogle Scholar
    • M. Griebl, P. Faber and C. Lengauer, Concurrency and Computation: Practice and Experience 16(3), 221 (2004). Crossref, ISIGoogle 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
    • W. Li and K. Pingali, International Journal of Parallel Programming 22(2), 183 (1994). Crossref, ISIGoogle Scholar
    • K. McKinley, S. Carr and C. Tseng, ACM Transactions on Programming Languages and Systems 18(4), 424 (1996). Crossref, ISIGoogle Scholar
    • D. Padua and M. Wolf, Communications of the ACM 29(12), 1184 (1996). Crossref, ISIGoogle 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
    • J. Xue, Parallel Processing Letters 7(4), 409 (1997). LinkGoogle Scholar