Finding Synchronization-Free Slices of Operations in Arbitrarily Nested Loops

1. Allen, R., Kennedy, K.: Optimizing Compilers for Modern Architectures, p. 790. Morgan Kaufmann, San Francisco (2001)

   Google Scholar 

2. Amarasinghe, S.P., Lam, M.S.: Communication optimization and code generation for distributed memory machines. In: Proceedings of the SIGPLAN 1993, pp. 126–138 (1993)

   Google Scholar 

3. Ancourt, C., Irigoin, F.: Scanning polyhedra with do loops. In: Proc. of the Third ACM/SIGPLAN Symp. on Principles and Practice of Parallel Programming, pp. 39–50. ACM Press, New York (1991)

   Chapter  Google Scholar 

4. Banerjee, U.: Unimodular transformations of double loops. In: Proceedings of the Third Workshop on Languages and Compilers for Parallel Computing, pp. 192–219 (1990)

   Google Scholar 

5. Bastoul, C., Cohen, A., Girbal, S., Sharma, S., Temam, O.: Putting polyhedral loop transformations to work. In: LCPC 16 Intern.l Workshop on Languages and Compilers for Parallel Computing. LNCS, vol. 2958, pp. 209–225. College Station (September 2003)

   Google Scholar 

6. Bastoul, C.: Code Generation in the Polyhedral Model Is Easier Than You Think. In: Proceedings of the PACT 13 IEEE International Conference on Parallel Architecture and Compilation Techniques, Juan-les-Pins, pp. 7–16 (2004)

   Google Scholar 

7. Beletska, A., Bielecki, W., San Pietro, P.: Extracting Synchronization-Free Slices of Operations in Perfectly-Nested Loops. In: Proceedings of PDCS 2007 (2007)

   Google Scholar 

8. Boulet, P., Darte, A., Silber, G.A., Vivien, F.: Loop parallelization algorithms: from parallelism extraction to code generation. Parallel Computing 24, 421–444 (1998)

   Article  MATH  MathSciNet  Google Scholar 

9. Cohen, A., Girbal, S., Temam, O.: A polyhedral approach to ease the composition of program transformations. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds.) Euro-Par 2004. LNCS, vol. 3149, pp. 292–303. Springer, Heidelberg (2004)

   Google Scholar 

10. Darte, A., Robert, Y., Vivien, F.: Scheduling and Automatic Parallelization. Birkhäuser Boston (2000)

    Google Scholar 

11. Feautrier, P.: Some efficient solutions to the affine scheduling problem, part i, one dimensional time. International Journal of Parallel Programming 21, 313–348 (1992)

    Article  MATH  MathSciNet  Google Scholar 

12. Feautrier, P.: Some efficient solutions to the affine scheduling problem, part ii, multidimensional time. International Journal of Parallel Programming 21, 389–420 (1992)

    Article  MATH  MathSciNet  Google Scholar 

13. Feautrier, P.: Toward automatic distribution. Journal of Parallel Processing Letters 4, 233–244 (1994)

    Article  Google Scholar 

14. Gavaldà, R., Ayguadé, E., Torres, J.: Obtaining Synchronization-Free Code with Maximum Parallelism, Technical Report LSI-96-23-R, Universitat Politècnica de Catalunya (1996)

    Google Scholar 

15. Griebl, M., Lengauer, C.: Classifying Loops for Space-Time Mapping. In: Proceedings of the Euro-Par. LNCS, pp. 467–474. Springer, Heidelberg (1996)

    Google Scholar 

16. Huang, C., Sadayappan, P.: Communication-free hyperplane partitioning of nested loops. Journal of Parallel and Distributed Computing 19, 90–102 (1993)

    Article  MATH  Google Scholar 

17. Kelly, W., Pugh, W., Rosser, E., Shpeisman, T.: Transitive Closure of Infinite Graphs and its Applications. International Journal of Parallel Programming 24(6), 579–598 (1996)

    Google Scholar 

18. Kelly, W., Pugh, W.: Minimizing communication while preserving parallelism. In: Proc. of the 1996 ACM International Conference on Supercomputing, pp. 52–60 (1996)

    Google Scholar 

19. Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., Wonnacott, D.: The omega library interface guide, Technical Report CS-TR-3445, University of Maryland (1995)

    Google Scholar 

20. Lim, W., Lam, M.S.: Communication-free parallelization via affine transformations. In: Proc. of the 7^th workshop on languages and compilers for parallel computing, pp. 92–106 (1994)

    Google Scholar 

21. Lim, W., Cheong, G.I., Lam, M.S.: An affine partitioning algorithm to maximize parallelism and minimize communication. In: Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing (1999)

    Google Scholar 

22. Lim, W., Liao, S.W., Lam, M.: Blocking and Array Contraction Across Arbitrarily Nested Loops Using Affine Partitioning. In: Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2001)

    Google Scholar 

23. Pugh, W., Wonnacott, D.: Constraint-based array dependence analysis. ACM Trans. on Programming Languages and Systems (1998)

    Google Scholar 

24. Pugh, W., Rosser, E.: Iteration Space Slicing and Its Application to Communication Optimization. In: Proc. of the International Conf. on Supercomputing, pp. 221–228 (1997)

    Google Scholar 

25. Quillere, F., Rajopadhye, S., Wilde, D.: Generation of efficient nested loops from polyhedra. International Journal of Parallel Programming 28 (2000)

    Google Scholar 

26. Weiser, M.: Program slices: formal, psychological, and practical investigations of an automatic program abstraction method, PhD thesis, University of Michigan, Ann Arbor, MI (1979)

    Google Scholar 

27. Weiser, M.: Program Slicing. IEEE Transactions on Software Engineering SE-10(7), 352–357 (1984)

    Article  Google Scholar 

28. Wolf, M.E.: Improving locality and parallelism in nested loops, Ph.D. Dissertation CSL-TR-92-538, Stanford University, Dept. Computer Science (1992)

    Google Scholar 

29. Vasilache, N., Bastoul, C., Cohen, A.: Polyhedral code generation in the real world. In: Proceedings of the International Conference on Compiler Construction (ETAPS CC 2006). LNCS, pp. 185–201. Springer, Vienna (2006)

    Google Scholar 

30. Netlib Repository at UTK and ORNL, http://www.netlib.org/benchmark/livermorec

31. http://www.nas.nasa.gov

Download references