Automatic loop transformations and parallelization for Java

ABSTRACT

From a software engineering perspective, the Java programming language provides an attractive platform for writing numerically intensive applications. A major drawback hampering its widespread adoption in this domain has been its poor performance on numerical codes. This paper describes a prototype Java compiler which demonstrates that it is possible to achieve performance levels approaching those of current state-of-the-art C, C++ and Fortran compilers on numerical codes. We describe a new transformation called alias versioning that takes advantage of the simplicity of pointers in Java. This transformation, combined with other techniques that we have developed, enables the compiler to perform high order loop transformations (for better data locality) and parallelization completely automatically. We believe that our compiler is the first to have such capabilities of optimizing numerical Java codes. We achieve, with Java, between 80 and 100% of the performance of highly optimized Fortran code in a variety of benchmarks. Furthermore, the automatic parallelization achieves speedups of up to 3.8 on four processors. Combining this compiler technology with packages containing the features expected by programmers of numerical applications would enable Java to become a serious contender for implementing new numerical applications.

REFERENCES

• 1: Pedro V. Artigas , Manish Gupta , Samuel P. Midkiff , José E. Moreira, High Performance Numerical Computing in Java: Language and Compiler Issues, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.1-17, August 04-06, 1999
• 2: U. Banerjee. Unimodular transformations of double loops. In Proc. Third Workshop on Programming Languages and Compilers for Parallel Computing, Irvine, California, August 1990.
• 3: Utpal K. Banerjee, Dependence Analysis, Kluwer Academic Publishers, Norwell, MA, 1996
• 4: A. J. C. Bik and D. B. Gannon. A note on native level 1 BLAS in Java. Concurrency, Pract. Exp. (UK), 9(11):1091-1099, November 1997.
• 5: Brian Blount , Siddhartha Chatterjee, An Evaluation of Java for Numerical Computing, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.35-46, December 08-11, 1998
• 6: R. E Boisvert, J. J. Dongarra, R. Pozo, K. A. Remington, and G. W. Stewart. Developing numerical libraries in Java. Concurrency, Pract. Exp. (UK), 10(11-13):1117-29, September-November 1998. ACM 1998 Workshop on Java for High-Performance Network Computing. URL: http : //www. cs. ucsb. edu/conferences / java98.
• 7: M. Byler, J. R. B. Davies, C. Huson, B. Leasure, and M. Wolfe. Multiple version loops. In Proceedings of the 1987 International Conference on Parallel Processing, pages 312-318, August 17-21 1987.
• 8: H. Casanova, J. Dongarra, and D. M. Doolin. Java access to numerical libraries. Concurrency, Pract. Exp. ( UK), 9( 11): 1279-91, November 1997. Java for Computational Science and Engineering - Simulation and Modeling II Las Vegas, NV, USA 21 June 1997.
• 9: M. Ciemiak and W. Li. Just-in-time optimization for high-performance Java programs. Concurrency, Pract. Exp. (UK), 9(11):1063-73, November 1997. Java for Computational Science and Engineering - Simulation and Modeling II, Las Vegas, NV, June 21, 1997.
• 10: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 11: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 12: R. Fitzgerald, T. B. Knoblock, E. Ruf, B. Steensgaard, and D. Tarditi. Marmot: an optimizing compiler for Java. Technical report, Microsoft Research, October 1998. URL: http : //research .microsoft. com/apl% discretionary//default, htm.
• 13: V. Getov, S. Flynn-Hummel, and S. Mintchev. High-performance parallel programming in Java: Exploiting native libraries. In ACM 1998 Workshop on Java for High-Performance Network Computing. ACM SIGPLAN, 1998. URL: http : //www. cs. ucsb. edu/ conferences / java 98.
• 14: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 15: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.218-229, June 20-24, 1994, Orlando, Florida, United States
• 16: Java Grande Forum. Java Grande Forum Report: Making Java Work for High-End Computing, November 1998. Java Grande Forum Panel, SC98, Orlando, FL. URL: http : //www. j avagrande, org/reports, htm.
• 17: S. P. Midkiff , J. E. Moreira , M. Snir, Optimizing array reference checking in Java programs, IBM Systems Journal, v.37 n.3, p.409-453, 1998
• 18: José E. Moreira , Samuel P. Midkiff, Fortran 90 in CSE: A Case Study, IEEE Computational Science & Engineering, v.5 n.2, p.39-49, April 1998 [doi>10.1109/99.683741]
• 19: José E. Moreira , Samuel P. Midkiff , Manish Gupta, From flop to megaflops: Java for technical computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.265-295, March 2000 [doi>10.1145/349214.349222]
• 20: J. E. Moreira , S. P. Midkiff , M. Gupta , P. V. Artigas , M. Snir , R. D. Lawrence, Java programming for high-performance numerical computing, IBM Systems Journal, v.39 n.1, p.21-56, January 2000
• 21: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 22: V. Sarkar, Automatic selection of high-order transformations in the IBM XL FORTRAN compilers, IBM Journal of Research and Development, v.41 n.3, p.233-264, May 1997
• 23: M. Schwab and J. Sehroeder. Algebraic Java classes for numerical optimization. In ACM 1998 Workshop on Java for High-Performance Network Computing. ACM SIGPLAN, 1998. URL: http : //www. CS. ucsb. edu/ conferences / java98.
• 24: V. Seshadri. IBM high performance compiler for Java. AIXpert Magazine, September 1997. URL: http:// www. developer, ibm. com/l ibrary/aixpert.
• 25: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 26: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 27: Jyh-shiarn Yur , Barbara G. Ryder , William A. Landi, An incremental flow- and context-sensitive pointer aliasing analysis, Proceedings of the 21st international conference on Software engineering, p.442-451, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302676]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Languages, Measurement, Performance, Standardization, Theory