A comparison of three approaches to language, compiler, and library support for multidimensional arrays in Java

ABSTRACT

The lack of direct support for multidimensional arrays in Java™ has been recognized as a major deficiency in the language's applicability to numerical computing. The typical approach to adding multidimensional arrays to Java has been through class libraries that implement these structures. It has been shown that the class library approach can achieve very high-performance for numerical computing, through the use of compiler techniques and efficient implementations of aggregate array operations. Because of the inconvenience of accessing array elements through method invocations, it is advocated by many that class libraries for multidimensional arrays should be combined with new language syntax to facilitate manipulation of those multidimensional arrays. Another approach that has been discussed in the literature is that of relying exclusively on the JVM to recognize those arrays of arrays that are being used to stimulate multidimensional arrays. This approach can also deliver good performance, but it does not improve the existing interfaces for numerical computing. There is yet a third approach: extending the Java language with new syntactic constructs for multidimensional arrays and directly compiling those constructs to bytecode. The new constructs provide a more convenient interface for numerical computing, without requiring a matching class library. This paper is a comparative discussion or the three approaches to adding multidimensional arrays to Java mentioned above. We present a description of the three approaches, listing the pros and cons of each. We give a more detailed description of the third approach — language constructs translated to bytecode — as it is a new contribution. We compare each of the approaches with regards to functionality, impact on the language and virtual machine specification, implementation efforts, and typical achievable performance. We show that the best choice depends on the relative importance attached to the above metrics.

REFERENCES

• 1: JSR-083, Java TM Multiarray Package. URL: http://java.sun.com/aboutJava/ communityprocess/jsr/ jsr_O83_multiarray, html.
• 2: R V. Artigas, M. Gupta, S. P. Midkiff, and J. E. Moreira. Applying high order transformations to Java. In Workshop on Compilers for Parallel Computing, pages 105-122, Aussois, France, January 2000. IBM Research Report RC21609.
• 3: Pedro V. Artigas , Manish Gupta , Samuel P. Midkiff , José E. Moreira, Automatic loop transformations and parallelization for Java, Proceedings of the 14th international conference on Supercomputing, p.1-10, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335232]
• 4: Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
• 5: 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): I 117-29, September-November 1998. ACM 1998 Workshop on Java for High-Performance Network Computing. URL: http : //www. cs. ucsb. edu/ conferences/java 9 8.
• 6: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 7: M. Ciemiak and W. Li. Just-in-time optimization for high-performance Java programs. Concurrency, Pract. Exp. (UK), 9(11): 1063-73, November 1997.
• 8: J. D. Darcy. Borneo: Adding IEEE 754 floating point support to Java. Master's thesis, Computer Science Division, University of California, Berkeley, May 1998.
• 9: 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/java9 8.
• 10: Edwin Gunthner and Michael Philippsen. Complex numbers for Java. Concurrency: Practice and Experience, 12(6):477--491, May 2000.
• 11: F. G. Gustavson, Recursion leads to automatic variable blocking for dense linear-algebra algorithms, IBM Journal of Research and Development, v.41 n.6, p.737-756, Nov. 1997
• 12: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 13: 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]
• 14: 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
• 15: M. Philippsen and E. Gianthner. cj: A new approach for the efficient use of complex numbers in Java. URL: http://wwwipd. ira. uka. de/gunthner/.
• 16: M. Schwab and J. Schroeder. 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/java9 8.
• 17: C. van Reeuwijk, F. Kuijlman, H.J. Sips, and S.V. Niemeijer. Data-parallel programming in Spar/Java. In Proceedings of the Second Annual Workshop on Java for High-Performance Computing, Santa Fe, New Mexico, pages 5 I--66, May 2000.
• 18: Peng Wu , Sam Midkiff , José Moreira , Manish Gupta, Efficient support for complex numbers in Java, Proceedings of the ACM 1999 conference on Java Grande, p.109-118, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304109]
• 19: Yelick, Semenzato, Pike, Miyamoto, Liblit, Krishnamurthy, Hilfinger, Graham, Gay, Colella, and Aiken. Titanium: A high-performance Java dialect. In ACM 1998 Workshop on Java for High-Performance Network Computing. ACM SIGPLAN, 1998. URL: http://www. cs. ucsb. edu/ conferences/java98.

INDEX TERMS

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

          Nouns: Java

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Interpreters

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

General Terms:
Design, Experimentation, Languages, Performance