From flop to megaflops: Java for technical computing

ABSTRACT

Although there has been some experimentation with Java as a language for numerically intensive computing, there is a perception by many that the language is unsuited for such work because of performance deficiencies. In this article we show how optimizing array bounds checks and null pointer checks creates loop nests on which aggressive optimizations can be used. Applying these optimizations by hand to a simple matrix-multiply test case leads to Java-compliant programs whose performance is in excess of 500 Mflops on a four-processor 332MHz RS/6000 model F50 computer. We also report in this article the effect that various optimizations have on the performance of six floating-point-intensive benchmarks. Through these optimizations we have been able to achieve with Java at least 80% of the peak Fortran performance on the same benchmarks. Since all of these optimizations can be automated, we conclude that Java will soon be a serious contender for numerically intensive computing.

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: Jonathan M. Asuru, Optimization of array subscript range checks, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.109-118, June 1992 [doi>10.1145/151333.151392]
• 3: ATWOOD, C. A., GARG, R. P., AND DERYKE, D. 1997. A prototype computational fluid dynamics case study in Java. Concurrency, Pract. Exp. (UK) 9, 11 (November), 1311-1318. Java for Computational Science and Engineering - Simulation and Modeling II Las Vegas, NV, USA 21 June 1997.
• 4: BANERJEE, U. 1990. Unimodular transformations of double loops. In A. NICOLAU ET AL. (Eds.), Advances in Languages and Compilers for Parallel Processing, Third Workshop on Languages and Compilers for Parallel Computing, pp. 192-219. The MIT Press.
• 5: BIK, A. AND GANNON, D. 1998. A prototype bytecode parallelization tool. Concurrency, Pract. Exp. (UK) 10, 11-13 (September-November), 879-886. ACM 1998 Workshop on Java for High- Performance Network Computing. URL: http ://www. cs. ucsb. edu/conferences/j ava98.
• 6: BIK, t., VILLACIS, J., AND GANNON, D. 1997. javar: A prototype Java restructuring compiler. Concurrency, Pract. Exp. (UK) 9, 11 (November), 1181-1191. Java for Computational Science and Engineering - Simulation and Modeling II Las Vegas, NV, USA 21 June 1997.
• 7: BOISVERT, R. F., DONGARRA, J. J., POZO, R., REMINGTON, K. A., AND STEWART, G. W. 1998. Developing numerical libraries in Java. Concurrency, Pract. Exp. (UK) 10, 11-13 (September- November), 1117-1129. ACM 1998 Workshop on Java for High-Performance Network Computing. URL: http ://www. cs. ucsb. edu/conferences/j ava98.
• 8: BUDIMLIC, Z. AND KENNEDY, I~. 1997. Optimizing Java: Theory and practice. Concurrency, Pract. Exp. (UK) 9, 11 (November), 445-463. Java for Computational Science and Engineering - Simulation and Modeling II Las Vegas, NV, USA 21 June 1997.
• 9: BYLER, M., DAVIES, J. R. B., HUSON, C., LEASURE, B., AND WOLFE, M. 1987. Multiple version loops. In Proceedings of the 1987 International Conference on Parallel Processing, pp. 312-318.
• 10: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 11: CASANOVA, H., DONGARRA, J., AND DOOLIN, D. M. 1997. Java access to numerical libraries. Concurrency, Pract. Exp. (UK) 9, 11 (November), 1279-1291. Java for Computational Science and Engineering - Simulation and Modeling II Las Vegas, NV, USA 21 June 1997.
• 12: CIERNIAK, M. AND LI, W. 1997. Just-in-time optimization for high-performance Java programs. Concurrency, Pract. Exp. (UK) 9, 11 (November), 1063-1073. Java for Computational Science and Engineering - Simulation and Modeling II, Las Vegas, NV, June 21, 1997.
• 13: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 14: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• 15: Steven M. German, Automating proofs of the absence of common runtime errors, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.105-118, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512772]
• 16: Jack J. Dongarra , Iain S. Duff , Danny C. Sorensen , Henk Van Der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990
• 17: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 18: GOSLING, J. 1997. The evolution of numerical computing in Java. URL: http://java, sun. corn/ people/jag/FP.html. Sun Microsystems.
• 19: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 20: GUPTA, M., MIDKIFF, S. P., AND MOREIRA, J. E. 1998. Method for optimizing array bounds checks in programs. Patent pending, IBM Docket ~pYO-998-052, filed with U. S. Patent Office, April 24th, 1998.
• 21: Rajiv Gupta, A fresh look at optimizing array bound checking, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.272-282, June 1990, White Plains, New York, United States
• 22: Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993 [doi>10.1145/176454.176507]
• 23: HARRISON, W. H. 1977. Compiler analysis for the value ranges for variables. IEEE Transactions on Software Engineering SE3, 3 (May), 243-250.
• 24: INTERNATIONAL BUSINESS MACHINES CORPORATION. 1997. IBM Engineering and Scientific Subroutine Library for AIX- Guide and Reference. INTERNATIONAL BUSINESS MACHINES CORPO- RATION.
• 25: JAVA GRANDE FORUM. 1998. Java Grande Forum Report: Making Java Work for High-End Computing. JAVA GRANDE FORUM. Java Grande Forum Panel, SC98, Orlando, FL. URL: http ://www. j avagrande, org/report s. htm.
• 26: Priyadarshan Kolte , Michael Wolfe, Elimination of redundant array subscript range checks, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.270-278, June 18-21, 1995, La Jolla, California, United States
• 27: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 28: Victoria Markstein , John Cocke , Peter Markstein, Optimization of range checking, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.114-119, June 23-25, 1982, Boston, Massachusetts, United States
• 29: 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
• 30: MOREIRA, J. E., iV{IDKIFF, S. P., GUPTA, iV{., AND ARTIGAS, P. V. 1999. Numerically Intensive Java. URL: http ://www. alphaWorks, ibm. com/tech/ninj a. A sequential version of the Array package is available for download.
• 31: 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
• 32: David Orchard, Better performance with exceptions in Java, BYTE, v.23 n.3, p.53-54, Mar. 1998
• 33: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in FORTRAN (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 34: 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
• 35: SCHWAB, ~/{. AND SCHROEDER, J. 1998. Algebraic Java classes for numerical optimization. Concurrency, Pract. Exp. (UK) 10, 11-13 (September-November}, 1155-1164. ACM 1998 Workshop on Java for High-Performance Network Computing. URL: http://www.cs.ucsb.edu/ conf erences/j ava98.
• 36: B. Schwarz , W. Kirchgässner , R. Landwehr, An optimizer for Ada - design, experiences and results, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.175-184, June 20-24, 1988, Atlanta, Georgia, United States
• 37: SESHADRI, V. 1997. IBM high performance compiler for Java. AIXpert Magazine. URL: http:// www. developer, ibm. com/library/aixpert.
• 38: 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 ]
• 39: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 40: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

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

          Nouns: Java

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Run-time environments

General Terms:
Languages, Performance

Keywords:
arrays, compilers, java