Ninja External Web Page

Ninja: Numerically Intensive Java

The Ninja project is working to make Java competitive with Fortran and C++ in the domain of technical computing. This we do by benchmarking to find Java performance bottlenecks, and then developing and implementing optimization techniques to remove those bottlenecks. We are also actively involved in standards work, particularly in the areas of technical computing.

Refereed publications
Refereed publication abstracts
Technical reports
Technical report abstracts
Presentations and tutorials
Group members
Call for Papers and Participation for selected conferences and workshops
Related links

Refereed publications

Some of our publications are not available for download. If you are unable to locate the paper in the referenced source, please contact us at smidkiff@us.ibm.com, and we will send you the publication in either postscript or pdf.

Automatic Transformations and Parallization for Java, submitted, Parallel Processing Letters
Automatic Transformations and Parallization for Java, 2000 International Conference on Supercomputing, May, Santa Fe, NM
Escape Analysis for Java, ACM 1999 Conference on Object-Oriented Programming Systems, Languages and Applications, Nov. 1-5, Denver, CO.
Work done with members of the Jalapeño group.
From Flop to MegaFlops: Java for Technical Computing, to appear, ACM TOPLAS
Parallel Data Mining Using the Array Package for Java, Proceedings of SuperComputing '99, Nov. 13-19, 1999, Portland, OR.
High Performance Numerical Computing in Java: Language and Compiler Issues, Proceedings of the 12'th Workshop on Language and Compilers for Parallel Computers, Aug. 4-6, 1999, San Diego, CA.
postscript at CyberDigest
Java for Numerically Intensive Computing: From Flops to Gigaflops
Appeared in: Proceedings of Frontiers '99, IEEE, Computer Society Press, Los Alamitos, CA.
Efficient Support for Complex Numbers in Java, Proceedings of the 1999 ACM Java Grande Conference, June 12-14, 1999, San Francisco, CA.
postscript at CyberDigest
A Standard Java Package for Technical Computing, Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, March 22-24, San Antonio, TX.
postscript at CyberDigest
Optimizing Array Reference Checking in Java Programs IBM Systems Journal, Aug. 1998, Vol. 37, No. 3, pp. 409-453.
postscript at CyberDigest
A Case Study of Fortran 90 in Computational Science and Engineering, IEEE Computational Science and Engineering, April 1998, Vol. 5, No. 2, pp. 29-49.
postscript at CyberDigest
A Comparison of Java, C/C++, and Fortran for Numerical Computing, IEEE Antennas and Propagation Magazine, v40, n5, Oct 1998, p.102-105.

back to publications, or the top

Refereed publication abstracts

Automatic Transformations and Parallization for Java (200K, .ps), submitted, Parallel Processing Letters

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 and parallelization completely automatically. We believe that our compiler is the first to have such capabilities of optimizing numerical Java codes. By exploiting synergies between our compiler and the Array package for Java, we achieve 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. Our compiler technology enables Java to become a serious contender for implementing new numerical applications. postscript at CyberDigest
Automatic Transformations and Parallization for Java (170K, .ps), 2000 International Conference on Supercomputing, May, Santa Fe, NM

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.
Escape Analysis for Java, ACM 1999 Conference on Object-Oriented Programming Systems, Languages and Applications, Nov. 1-5, Denver, CO
Work done with members of the Jalapeño group

Abstract
This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory.
back to Refereed publications, Refereed publication abstracts, or the top
From Flop to MegaFlops: Java for Technical Computing, to appear, ACM TOPLAS

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. In this paper 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 4-processor 332MHz RS/6000 model F50 computer. We also report in this paper 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.
back to Refereed publications, Refereed publication abstracts, or the top
Parallel Data Mining Using the Array Package for Java, Proceedings of SuperComputing '99, Nov. 13-19, 1999, Portland, OR

Abstract
Java is almost universally recognized as a good object-oriented language for writing portable programs. However, it still lags behind Fortran and C in performance, particularly for computationally intensive numerical programs. In this paper we present a true multidimensional Array package, and related compiler support, that can bring Fortran-like performance to Java numerical codes. We discuss the main design principles for our Array package, and illustrate the benefits from its use through several examples.
back to Refereed publications, Refereed publication abstracts, or the top
High Performance Numerical Computing in Java: Language and Compiler Issues, Proceedings of the 12'th Workshop on Language and Compilers for Parallel Computers, Aug. 4-6, 1999, San Diego, CA

Abstract
Poor performance on numerical codes has slowed adoption of Java within the technical computing community. In this paper we describe a prototype array library and a research prototype compiler that support standard Java and deliver near-Fortran performance on numerically intensive codes. We discuss in detail our implementation of: (i) an efficient Java package for true multidimensional arrays; (ii) compiler techniques to generate efficient access to these arrays; and (iii) compiler optimizations that create safe, exception free regions of code that can be aggressively optimized. These techniques work together synergistically to make Java an efficient language for technical computing. In a set of four benchmarks, we achieve between 50 and 90% of the performance of highly optimized Fortran code. This represents a several-fold improvement compared to what can be achieved by the next best Java environment.

back to Refereed publications, Refereed publication abstracts, or the top
Java for Numerically Intensive Computing: From Flops to Gigaflops, Proceedings of Frontiers '99, IEEE, Computer Society Press, Los Alamitos, CA, 1999

Abstract
Java is not thought of as being competitive with Fortran for numerical programming. In this paper, we discuss technologies that can and will deliver Fortran-like performance in Java. These techniques include new and existing compiler technologies, the exploitation of parallelism, and a collection of Java libraries for numerical computing. We also present experimental data to show the effectiveness of our approaches. In particular, we achieve 1~Gflops with a linear algebra kernel on an RS/6000 SMP machine. Most of these techniques require no language changes; a few depend on extensions to Java currently under consideration.
back to Refereed publications, Refereed publication abstracts, or the top
Efficient Support for Complex Numbers in Java, Proceedings of the ACM Java Grande Conference, June 12-14, 1999, San Francisco, CA.

Abstract
One glaring weakness of Java for numerical programming is its lack of support for complex numbers. Simply creating a Complex number class leads to poor performance relative to Fortran. We show in this paper, however, that the combination of such a Complex class and a compiler that understands its semantics does indeed lead to Fortran-like performance. This performance gain is achieved while leaving the Java language completely unchanged and maintaining full compatibility with existing Java Virtual Machines. We quantify the effectiveness of our approach through experiments with linear algebra, electromagnetics, and computational fluid-dynamics kernels.
back to Refereed publications, Refereed publication abstracts, or the top
A Standard Java Package for Technical Computing, Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, March 22-24, San Antonio, TX

Abstract
Java is almost universally recognized as a good object-oriented language for writing portable programs. However, it still lags behind Fortran and C in performance, particularly for computationally intensive numerical programs. In this paper we present a true multidimensional Array package, and related compiler support, that can bring Fortran-like performance to Java numerical codes. We discuss the main design principles for our Array package, and illustrate the benefits from its use through several examples.
back to Refereed publications, Refereed publication abstracts, or the top
Optimizing Array Reference Checking in Java Programs, IBM Systems Journal, Aug. 1998, Vol. 37, No. 3, pp. 409-453
Abstract
The Java language specification requires that all references to pointers and arrays be checked for validity. If a reference is invalid, an exception must be thrown. Furthermore, the environment at the time of the exception must be preserved and made available to whatever code handles the exception. Performing the checks at run-time incurs a large penalty in execution time. In this document we describe a collection of transformations that can dramatically reduce this overhead in the common case (when the access is valid) while preserving the program state at the time of an exception. The transformations allow trade-offs to be made in the efficiency and size of the resulting code, and are fully compliant with the Java language semantics. Preliminary evaluation of the effectiveness of these transformations show that performance improvements of 10 times and more can be achieved for array-intensive Java programs.
back to Refereed publications, Refereed publication abstracts, or the top
A Case Study of Fortran 90 in Computational Science and Engineering, published, IEEE Computational Science and Engineering, April 1998, Vol. 5, No. 2, pp. 29-49.
Abstract
Fortran has been the dominant language in scientific and engineering computing for nearly 40 years. Fortran's latest widely available form, Fortran 90, provides important facilities for developing large CSE applications: array language, abstract data types, modularity, and encapsulation. Object-oriented programming has been successfully accomplished in Fortran 90 by many users. All this has been achieved while maintaining a major design goal throughout the evolution of the language: high performance on numerical-intensive computing. In this paper, we present a case study of Fortran 90 in a CSE application. We show that Fortran 90's features facilitate the development of these types of applications. We also show that a good compiler can generate very efficient code from Fortran 90 source, both in serial and parallel forms. Finally, we discuss some of the issues involved in choosing the right language for an application, and the topic of language inter-operability.
back to Refereed publications, Refereed publication abstracts, or the top
A Comparison of Java, C/C++, and Fortran for Numerical Computing, IEEE Antennas and Propagation Magazine, v40, n5, Oct 1998, p.102-105
Abstract
This paper compares the use of three programming languages, Fortran, C/C++, and Java, in a simple numerical computation of the product of two matrices. The goal is to show that, although similar in expressiveness, the performance of the three languages can be vastly different with current implementations. We analyze the causes of these differences and we discuss how state-of-the-art compilation can be used to deliver excellent performance for all three languages.
back to Refereed publications, Refereed publication abstracts, or the top

Technical reports

Parallel Data Mining in Java
postscript at CyberDigest
Improving Java Performance through Semantic Inlining
postscript at CyberDigest
Back to Technical reports, Technical report abstracts, or the top

Technical report abstracts

Parallel Data Mining in Java

Abstract
This paper discusses several techniques used in developing a parallel, production quality data mining application in Java. Three sequential versions of the data mining application were developed: A sequential Fortran 90 version used as a performance reference, a plain Java implementation that only uses the primitive array structures from the language, and a baseline Java implementation that uses a Java Array package designed by us. When desired, this Array package provides parallelism at the individual Array and BLAS operation level. We have also developed two parallel Java versions: one that relies entirely on the parallelism from the Array package, and another that is explicitly parallel at the application level. We discuss the design of the Array package, as well as the design of the data mining application. We compare the trade-offs between performance and the abstraction level presented to the application programmer with the different Java versions. Our studies show that not only is the Java implementation of this program competitive with the Fortran implementation, but that it parallelizes well, both in the implicit as well as the explicit form. The Java implementation achieves a performance of 109 Mflops, or 91% of Fortran performance, on a 332 MHz PowerPC 604e processor. On an SMP with four of those processors, the implicitly parallel form achieves 290 Mflops with no effort from the application programmer, while the explicitly parallel form achieves 340 Mflops.
Back to Technical reports, Technical report abstracts, or the top
Improving Java Performance through Semantic Inlining

Abstract
This paper describes a new compilation technique called semantic inlining. Unlike traditional lexical inlining, which only incorporates a lexical representation of a method into the calling context, semantic inlining incorporates into the calling context semantic information about the method and its class. This is accomplished by treating selected classes and methods, which are crucial to performance, as primitive data types and primitive operations on those data types. We show that, in our numerical benchmarks which use complex numbers and multidimensional arrays, semantic inlining yields speedups of between 35 and 81, delivering performance between 65% to 90% of Fortran. The speed and effectiveness of semantic inlining make it practical for both static and dynamic compilers, and make it an effective technique for extending the primitive data types and operations of the Java programming language without altering the Java Virtual Machine specification.
Back to Technical reports, Technical report abstracts, or the top

Presentations

Numerical Intensive Computing with Java: Language, Libraries, and Compiler Issues, presented to the American Nuclear Society Annual Meeting, San Diego, CA, June 6th, 2000. (ps 1210K).

Tutorial on High Performance Numerical Computing with Java, presented at the 2000 ACM Java Grande Conference, San Francisco, CA., June 5, 2000 (ps for part one, 652K, ps for part two, 1600K, ps for part three, 215K).
Presentation on the paper High Performance Numerical Computing in Java: Language and Compiler Issues at the 12'th Workshop on Language and Compilers for Parallel Computers on Aug. 4, 1999 in San Diego, CA (ps 924K) , (pdf 210K)
Presentation on the paper Efficient Support for Complex Numbers at the 1999 ACM Java Grande Conference on June 14, 1999 in San Francisco, CA. (pdf (~5M))
Presentation on the paper From Flop to MegaFlops: Java for Technical Computing at the 11'th Workshop on Languages and Compilers for Technical Computing, Chapel Hill, North Carolina, Aug. 1998.
(ps (~300K) , pdf (~590K))
Presentation to the Java Grande Forum on Aug. 6, 1998, (ps (~160K) , pdf (~155K)) and on May 9, 1998 (ps (~185K) , pdf (~245K)).
Presentation at EuroPar 98. (ps (~315K) , pdf (~670K)).
Presentation at the 1998 Workshop on Compilers for Parallel Computers (ps (~290K) , pdf (~520K)).
Presentation at the Center for the Simulation of Advanced Rockets, University of Illinois at Urbana-Champaign, June, 1998 (ps (~315K) , pdf (~800K)).

back to presentations, or the top

Group members

Current members of the group are Manish Gupta, Sam Midkiff and Jose Moreira. We have had the opportunity to work with Pedro Artigas, George A. Almasi and Peng Wu during the course of this project.

back to group members, or the top