Automatic Parallelization Using the Value Evolution Graph

1. Ammarguellat, Z., Harrison, W.L.: III. Automatic recognition of induction variables and recurrence relations by abstract interpretation. In: ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, White Plains, N.Y, June 1990, pp. 283–295 (1990)

   Google Scholar 

2. Ballance, R.A., Maccabe, A.B., Ottenstein, K.J.: The Program Dependence Web: A representation supporting control-, data-, and demand-driven interpretation of imperative languages. In: ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, White Plains, N.Y, June 1990, pp. 257–271 (1990)

   Google Scholar 

3. Blume, W., Eigenmann, R.: Symbolic Range Propagation. Technical Report 1381, Univ of Illinois at Urbana-Champaign, Cntr for Supercomputing R&D (1994)

   Google Scholar 

4. Callahan, D.: Recognizing and parallelizing bounded recurrences. In: Banerjee, U., Nicolau, A., Gelernter, D., Padua, D.A. (eds.) LCPC 1991. LNCS, vol. 589, pp. 169–185. Springer, Heidelberg (1992)

   Chapter  Google Scholar 

5. Chen, S.-C., Kuck, D.J.: Time and parallel processor bounds for linear recurrence systems. IEEE Transactions on Computers 24(7), 701–717 (1975)

   Article  MATH  MathSciNet  Google Scholar 

6. Fisher, A.L., Ghuloum, A.M.: Parallelizing complex scans and reductions. In: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, pp. 135–146. ACM Press, New York (1994)

   Chapter  Google Scholar 

7. Gerlek, M.P., Stolz, E., Wolfe, M.: Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form. ACM Transactions on Programming Languages and Systems 17(1), 85–122 (1995)

   Article  Google Scholar 

8. Ghuloum, A.M., Fisher, A.L.: Flattening and parallelizing irregular, recurrent loop nests. In: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, Santa Barbara, CA, pp. 58–67. ACM Press, New York (1995)

   Chapter  Google Scholar 

9. Gu, J., Li, Z., Lee, G.: Symbolic array dataflow analysis for array privatization and program parallelization. In: Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p. 47. ACM Press, New York (1995)

   Chapter  Google Scholar 

10. Gupta, M., Mukhopadhyay, S., Sinha, N.: Automatic parallelization of recursive procedures. International Journal of Parallel Programming 28(6), 537–562 (2000)

    Article  Google Scholar 

11. Gupta, R.: Optimizing array bound checks using flow analysis. ACM Letters on Programming Languages and Systems 2(1–4), 135–150 (1993)

    Article  Google Scholar 

12. Haghighat, M.R., Polychronopoulos, C.D.: Symbolic analysis for parallelizing compilers. ACM Transactions on Programming Languages and Systems 18(4), 477–518 (1996)

    Article  Google Scholar 

13. Hall, M., Anderson, J., Amarasinghe, S., Murphy, B., Liao, S.-W., Bugnion, E., Lam, M.: Maximizing Multiprocessor Performance with the SUIF Compiler. IEEE Computer 29(12), 84–89 (1996)

    Google Scholar 

14. Hoeflinger, J.: Interprocedural Parallelization Using Memory Classification Analysis. PhD thesis, University of Illinois, Urbana-Champaign (August 1998)

    Google Scholar 

15. JàJà, J.: An Introduction to Parallel Algorithms. Addison–Wesley, Reading (1992)

    MATH  Google Scholar 

16. Liao, S.-W., Diwan, A., Jr., R.P.Bosch, Ghuloum, A.M., Lam, M.S.: SUIF explorer: An interactive and interprocedural parallelizer. In: Principles Practice of Parallel Programming, pp. 37–48 (1999)

    Google Scholar 

17. Lin, Y., Padua, D.: Analysis of irregular single-indexed array accesses and its application in compiler optimizations. In: International Conference on Compiler Construction, pp. 202–218 (2000)

    Google Scholar 

18. Lin, Y., Padua, D.A.: On the automatic parallelization of sparse and irregular fortran programs. In: O’Hallaron, D.R. (ed.) LCR 1998. LNCS, vol. 1511, pp. 41–56. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

19. Pottenger, W., Eigenmann, R.: Parallelization in the presence of generalized induction and reduction variables. Technical Report 1396, Univ. of Illinois at UrbanaChampaign, Center for Supercomp. R&D (January 1995)

    Google Scholar 

20. Pugh, W.: The Omega test: A fast and practical integer programming algorithm for dependence analysis. In: Supercomputing 1991, Albuquerque, N.M, November 1991, pp. 4–13 (1991)

    Google Scholar 

21. Rauchwerger, L., Padua, D.A.: The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization. IEEE Transactions on Parallel and Distributed Systems 10(2), 160–180 (1999)

    Article  Google Scholar 

22. Rus, S., Hoeflinger, J., Rauchwerger, L.: Hybrid analysis: static & dynamic memory reference analysis. International Journal of Parallel Programming 31(3), 251–283 (2003)

    Article  MATH  Google Scholar 

23. Rus, S., Zhang, D., Rauchwerger, L.: The value evolution graph and its use in memory reference analysis. In: 13th Conference on Parallel Architecture and Compilation Techniques, pp. 243–254. IEEE Computer Society Press, Los Alamitos (2004)

    Chapter  Google Scholar 

24. Spezialetti, M., Gupta, R.: Loop monotonic statements. IEEE Transactions on Software Engineering 21(6), 497–505 (1995)

    Article  Google Scholar 

25. Triolet, R., Irigoin, F., Feautrier, P.: Direct parallelization of Call statements. In: ACM 1986 Symp. on Comp. Constr., Palo Alto, CA, June 1986, pp. 175–185 (1986)

    Google Scholar 

26. Tu, P., Padua, D.: Gated SSA–based demand-driven symbolic analysis for parallelizing compilers. In: Proceedings of the 9th ACM International Conference on Supercomputing, Barcelona, Spain, January 1995, pp. 414–423 (1995)

    Google Scholar 

27. Wolfe, M.: Beyond induction variables. In: ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, San Francisco, Calif., June 1992, pp. 162–174 (1992)

    Google Scholar 

28. Wu, P., Cohen, A., Hoeflinger, J., Padua, D.: Monotonic evolution: An alternative to induction variable substitution for dependence analysis. In: 2001 ACM International Conference on Supercomputing, Sorrento, Italy, pp. 78–91 (2001)

    Google Scholar 

29. Wu, P., Cohen, A., Padua, D.: Induction variable analysis without idiom recognition: Beyond monotonicity. In: 2001 Workshop on Lang. and Compilers for Par. Computing, Cumberland Falls, KY, pp. 427–441 (2001)

    Google Scholar 

Download references