A Note on Native Level 1 BLAS in Java

Aart J.C. Bik ^{∗}  Dennis B. Gannon

1 Introduction

Portability of the Java programming language [13] is obtained by compiling Java programs into architectural neutral instructions (bytecode) of the JVM (Java Virtual Machine) [16], rather than into native machine code. Bytecode runs on any platform that supports an implementation of the JVM. Although the interpretation of bytecode is substantially faster than the interpretation of most high level languages, still a performance penalty must be paid for this portability. Clearly, for Java applications that are computational intensive, it would be desirable to reduce this performance penalty without sacrificing the portability of the language. One approach, for example, is to optimize the Java bytecode [3, 5], either at compile-time (where a machine independent bytecode to bytecode optimization is added as additional phase to the Java compiler), or at run-time (where optimizations that require knowledge of the target machine are applied before execution). Some implementations of the JVM further improve performance by means of JITC (just-in-time compilation), where, at run-time, bytecode is compiled into native machine code.

In this note, we explore a way to speedup certain operations in Java programs using ideas from the mathematical software community. Here, it has been widely accepted that adopting a set of basic routines for problems in linear algebra can help in improving the clarity, portability, modularity, maintenance, robustness, and even the efficiency of mathematical software. The most well-known example of such a set of routines is formed by the Basic Linear Algebra Subprograms [10, ch5]. The original set of vector-vector operations is now commonly referred to as Level 1 BLAS [14, 15]. The set has been extended to Level 2 BLAS [8, 9] and Level 3 BLAS [6, 7] to provide more opportunities to exploit vector processing facilities for matrix-vector operations and memory hierarchies or parallelism for matrix-matrix operations, respectively. Once an efficient implementation of BLAS is available, new mathematical software can be easily build on top of the primitives.

Obviously, a similar approach can be taken for Java by extending the Java API (Application Programming Interface) with an appropriate set of mathematical primitives. In first instance, a Java implementation can be provided for all these primitives to preserve the portability of all Java programs in which the mathematical primitives are used. On a particular machine, however, the performance of all Java software that uses these primitives is simply improved by providing native implementations of the mathematical primitives. Although providing a broad range of highly optimized mathematical primitives would offer the best potential to exploit all characteristic of a particular target machine, this approach would also require the most programming efforts to port the mathematical primitives in the API to different machines. Therefore, in this research note, we explore the potential of extending the API with straightforward native implementations of Level 1 BLAS only. We will see that this extension alone already can improve performance substantially, while combining these native Level 1 BLAS with multi-threading in Java may even provide a simple and portable way to outperform compiled serial C code on multi-processors.

∗Computer Science Department, Indiana University, Lindley Hall 215, Bloomington, Indiana 47405-4101, USA (ajcbik@cs.indiana.edu).

2 Native BLAS

In Java, if the keyword native appears as part of a method definition (without an implementation), then this implies that the method is implemented in another language. A set of primitives from BLAS, for instance, can be defined using the following class that provides a shared library loader that will load the actual implementation when required as well as definitions of all primitives in the set:

   class Blas {
     // Shared Library Loader
     static {
       System.loadLibrary("blas");
     }
     // Level 1 BLAS
     native static double ddot(int n, double[] x, int xoff, int incx,
                                                    double[] y, int yoff, int incy);
     native static void daxpy(int n, double alpha, double[] x, int xoff, int incx,
                                                    double[] y, int yoff, int incy);
     ...
   }

Here, method definitions of DDOT (d ← x⃗^{T} y⃗ in double precision) and DAXPY (y⃗ ← αx⃗+y⃗ in double precision) are shown.^{1} Alternatively, as stated earlier, Java implementations of the primitives could be given in first instance.

Figure 1: Integration of Native Methods

In figure 1, the integration of native methods in Java is illustrated [17]. Using JDK1.0.2, first the source file Blas.java is compiled into Blas.class using the Java compiler javac. Subsequently, the tool javah is used to generate a stubs file Blas.c and a header file Blas.h. The latter file contains C prototypes for all native methods in the class. The actual implementation of these methods is given in a file BlasImp.c. Method ddot(), for example, can be implemented in a straightforward manner in C as follows, where the macro unhand() is used to dereference an object handle:

1Because Java does not support passing of arbitrary sub-arrays, offsets into arrays are added as additional parameters (cf. the Java implementation of BLAS in [11]).

   #include <StubPreamble.h>
   #include "Blas.h"
   double Blas_ddot(struct HBlas *this, long n,
                    HArrayOfDouble *x_, long xoff, long incx,
                    HArrayOfDouble *y_, long yoff, long incy) {
     double *x = unhand(x_)->body;
     double *y = unhand(y_)->body;
     double  d = 0;
     if (n > 0) {
       if ((incx == 1) && (incy == 1)) { /* Unit strides */
         int i;
         for (i=0;i < n; i++)
            d += x[xoff+i]*y[yoff+i];
       }
       else {                        /* Non-Unit strides */
        ...
       }
     }
     return d;
   }

Eventually, the files Blas.c and BlasImp.c are compiled into a shared library. The way in which this is done and the naming convention of shared libraries depends on the target architecture. Under Solaris, for instance, the shared library is created as follows:

  cc -G -O  -I $JAVA_HOME/include -I $JAVA_HOME/include/solaris Blas.c BlasImp.c -o libblas.so

As illustrated in the second picture in figure 1, integrating native methods in JDK1.1 is slightly different. Only a header file Blas.h which contains the appropriate prototypes is generated using javah -jni. The actual implementation of methods is, again, given in a file BlasImp.c. Method ddot(), for example, can be implemented in C as follows, where func-

tions GetDoubleArrayElements() and ReleaseDoubleArrayElements() are used to obtain

and release a double array that cannot be moved by the garbage collector. Eventually, the whole file is compiled into a shared library:

   #include "Blas.h"
   JNIEXPORT jdouble JNICALL Java_Blas_ddot
       (JNIEnv *env, jclass class, jint n, jdoubleArray x_, jint xoff, jint incx,
                                            jdoubleArray y_, jint yoff, jint incy) {
     jdouble *x = (*env)->GetDoubleArrayElements(env, x_, 0);
     jdouble *y = (*env)->GetDoubleArrayElements(env, y_, 0);
     jdouble  d = 0;
     if (n > 0) {
       if ((incx == 1) && (incy == 1)) { /* Unit strides */
         int i;
         for (i=0;i < n; i++)
           d += x[xoff+i]*y[yoff+i];
       }
       else {                         /* Non-Unit strides */
         ...
       }
     }
     (*env)->ReleaseDoubleArrayElements(env, x_, x, 0);
     (*env)->ReleaseDoubleArrayElements(env, y_, y, 0);
     return d;
   }

If native methods are used, care must be taken with respect to the precision of the computed result, because Java data types are mapped to the nearest matching data types on the native language side.

3 Experiments

In this section, we present the results of a series of experiments that have been conducted on an IBM RS/6000 G30 with four PowerPC 604 processors using the AIX4.2 JDK1.0.2B (with JITC) and the AIX4.2 JDK1.1beta (without JITC), a Sun with two 175MHz. ultra SPARC processors using the Solaris 2.5 JDK1.0.2dp (with JITC), and an SGI Indy 4600 with one 133 MHZ IP22 Processor using the IRIX6.2 JDK1.0.2 (without JITC).

All Java and C programs are compiled using the flag ‘-O’. Bytecode is interpreted using the flag ‘-noasyncgc’ and, if available, with JITC enabled. We compare the performance of a pure Java implementation, a Java implementation that uses native Level 1 BLAS (and possibly parallelism by means of Java multi-threading), and a compiled C implementation of an Θ(N) DAXPY-operation, an Θ(N^{2}) matrix times vector operation, and an Θ(N^{3}) matrix times matrix operation.

Below we show the pure Java implementation of the DAXPY operation (y⃗ ← αx⃗ + y⃗), and the Java implementation that uses a primitive from Level 1 BLAS:

pure Java:

   for (int i = 0; i < N; i++)
     y[i] += alpha * x[i];

Java + Level 1 BLAS:

                                   Blas.daxpy(N, alpha, x, 0, 1, y, 0, 1);

The inner product Java implementation of matrix times vector and a Java implementation that uses a call to Level 1 BLAS DDOT (d ← x⃗^{T} y⃗) are shown below:

pure Java:

   for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
       b[i] += a[i][j] * x[j];

Java + Level 1 BLAS:

                                     for (int i = 0; i < N; i++)
                                       b[i] = Blas.ddot(N, a[i], 0, 1, x, 0, 1);

Finally, the product of two matrices can be computed using either the pure Java fragment shown below, or a similar Java fragment that uses a call to DAXPY:

pure Java:

   for (int i = 0; i < N; i++)
     for (int k = 0; k < N; k++)
       for (int j = 0; j < N; j++)
         c[i][j] += a[i][k] * b[k][j];

Java + Level 1 BLAS:

                                           for (int i = 0; i < N; i++)
                                             for (int k = 0; k < N; k++)
                                               Blas.daxpy(N, a[i][k], b[k], 0, 1, c[i], 0, 1);

The performance of the fragments for matrix times vector and matrix times matrix with Level 1 BLAS may be further improved by parallelization of the outermost i-loop. In earlier work [1, 2], we have shown how parallel loops can be expressed in Java by means of multi-threading. In this manner the transformed Java program remains portable (i.e. the parallelized version still runs on uni-processors with only a slight overhead), while the programming efforts of the parallelization are reduced substantially with respect to exploiting parallelism in a native language. The versions with a parallel outermost loop are labeled as ‘parallel’ in subsequent figures. The C versions of the three mathematical operations are similar to the pure Java implementations.

In figures 2–13, we present the results of all experiments. On the IBM, we see that with JITC, providing Level 1 BLAS primitives only suffices to obtain performance that is close to the performance of native C code. Moreover, because IBM’s implementation of the JVM supports the actual parallel execution of threads, the parallel versions with native Level 1 BLAS even outperform serial C code. Without JITC, however, the Θ(N^{3}) operation still suffers from much overhead, and here it would probably be desirable to provide primitives from Level 2 BLAS as well. On the Sun, the performance of Java with native methods is frequently even slightly better than the performance of straightforward native C code. Obviously, Sun’s implementation of the JVM does not support the actual parallel execution of threads. Finally, on the SGI without JITC, the Java performance of Θ(N^{3}) matrix times matrix operations is substantially less than the performance of compiled C code. Obviously, on this uni-processor, no speedup can be expected from loop parallelization.

4 Conclusions

In this research note, we have explored the potential of extending the Java Application Programming Interface (API) with a native implementation of Level 1 BLAS to improve the performance of certain mathematical operations in Java programs. Because, in first instance, a Java implementation of the primitives can be provided, the portability of Java is maintained.

We have shown that for implementations of the JVM that support JITC, providing straightforward native Level 1 BLAS already suffices to obtain performance that is close to the performance of straightforward implementations in native C code for Θ(N), Θ(N^{2}), and Θ(N^{3}) mathematical operations. In case JITC is not supported, the performance difference of the latter operations is more profound, and here it would be desirable to provide higher level primitives as well. In addition, we have shown that, on multi-processors, combining native Level 1 BLAS with the multi-threading mechanism of Java may provide a simple and portable way to obtain a Java program that runs faster than compiled serial C code.

In conclusion, although it is obvious that more speedup can be expected by providing highly optimized native implementations of a broad range of mathematical primitives in which characteristics of the target machine (such as multiple processors, memory hierarchies or vector processing facilities) are fully exploited at native level, providing straightforward native implementations of Level 1 BLAS alone already can help in improving the performance of mathematical operations in Java. In all cases where native methods are used, however, care must be taken with respect to the precision of the computed result, because Java data types are mapped to the nearest matching data types on the native language side.

Acknowledgments This project is supported by DARPA under contract ARPA F19628-94-C-0057 through a subcontract from Syracuse University.

References

[1] Aart J.C. Bik and Dennis B. Gannon. Automatically exploiting implicit parallelism in Java. Concurrency, Practice and Experience, 9(6):579–619, 1997.

[2] Aart J.C. Bik, Juan E. Villacis, and Dennis B. Gannon. javar manual. Computer Science Department, Indiana University, 1997. This manual and the complete source of javar is made available at

http://www.extreme.indiana.edu/hpjava/.

[3] Zoran Budimlic and Ken Kennedy. Optimizing Java – theory and practice. Concurrency, Practice and Experience, 9(6):445–463, 1997.

[4] Bryan Carpenter, Yuh-Jye Chang, Geoffrey C. Fox, Donald Leskiw, and Xiaoming Li. Experiments with HP Java. To Appear in a Special Issue of Concurrency, Practice and Experience, 1997.

[5] Michal Cierniak and Wei Li. Optimizing Java bytecodes. Concurrency, Practice and Experience, 9(6):427–444, 1997.

[6] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Iain Duff. A set of level 3 basic linear algebra subprograms. ACM Transactions on Mathematical Software, 16:1–17, 1990.

[7] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Iain Duff. A set of level 3 basic linear algebra subprograms: Model implementation and test programs. ACM Transactions on Mathematical Software, 16:18–28, 1990.

[8] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Richard J. Hanson. An extended set of FORTRAN basic linear algebra subprograms. ACM Transactions on Mathematical Software, 14:1–17, 1988.

[9] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Richard J. Hanson. An extended set of FOR-TRAN basic linear algebra subprograms: Model implementation and test programs. ACM Transactions on Mathematical Software, 14:18–32, 1988.

[10] Jack J. Dongarra, Iain S. Duff, Danny C. Sorensen, and Henk A. van der Vorst. Solving Linear Systems on Vector and Shared Memory Computers. Society for Industrial and Applied Mathematics, 1991.

[11] Jack J. Dongarra et al. Java Linpack Benchmark. This benchmark is made available at

http://www.netlib.org/benchmark/linpackjava/.

[12] Geoffrey C. Fox and Wojtek Furmanski. Java for parallel computing and as a general language for scientific and engineering simulation and modelling. Concurrency, Practice and Experience, 9(6):415– 425, 1997.

[13] James Gosling, Bill Joy, and Guy Steele. Java Programming Language. Addison-Wesley, Reading, Massachusetts, 1996.

[14] C.L. Lawson, R.J. Hanson, D.R. Kincaid, and F.T. Krogh. Algorithm 539: Basic linear algebra subprograms for FORTRAN usage. ACM Transactions on Mathematical Software, 5:324–325, 1979.

[15] C.L. Lawson, R.J. Hanson, D.R. Kincaid, and F.T. Krogh. Basic linear algebra subprograms for FOR-TRAN usage. ACM Transactions on Mathematical Software, 5:308–323, 1979.

[16] Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, Reading, Massachusetts, 1996.

[17] Beth Stearns. Integrating Native Code and Java Programs. This document is made available at

http://java.sun.com/nav/read/Tutorial/native1.1/.

Figure 2: DAXPY on the IBM Figure 3: Matrix x Vector on the IBM Figure 4: Matrix x Matrix on the IBM

Figure 5: DAXPY on the IBM Figure 6: Matrix x Vector on the IBM Figure 7: Matrix x Matrix on the IBM

Figure 8: DAXPY on the Sun Figure 9: Matrix x Vector on the Sun Figure 10: Matrix x Matrix on the Sun

Figure 11: DAXPY on the SGI Figure 12: Matrix x Vector on the SGI Figure 13: Matrix x Matrix on the SGI