A well-known approach from past work on accelerating Java programs with heterogeneous accelerators 
is exemplified in the Rootbeer system~\cite{rootbear}. Rootbeer is built on top of CUDA. It uses multiple threads and reflection to rapidly
serialize Java objects to a native format compatible with CUDA's C/C++ API, a translation framework to auto-generate
CUDA kernels from Java bytecode at compile-time, and a runtime to manage 
execution of CUDA kernels and the transfer of input and output data.
Rootbeer supports ``all features of the Java Programming Language except dynamic method invocation, reflection, and native
methods''~\cite{rootbear}. In this section we will study Java, Rootbeer, and HJ-OpenCL 
implementations of an application similar to the Array-Sum example in~\cite{rootbear}.

The Array-Sum example studied in this section takes as input a matrix
of size $N \times M$ ({\tt arrays}), and 
returns a vector of size $N$ ({\tt result}) for which the $i^{\mbox{th}}$ element 
is the sum of the elements contained in row $i$ of the input matrix. This is a 
data-parallel application which we would expect to
perform well on GPUs for large input sizes.
Consider the sequential Java implementation in 
Figure~\ref{fig:java-example}. Nested for-loops are used to sum each input array into
its corresponding output element. While the implementation is simple, it is 
single-threaded and takes $O(N \times M)$ time.
% , where N is the number of
% input arrays and M is the length of each input array.

\begin{figure}
\begin{small}
%\singlespacing
\begin{lstlisting}[xleftmargin=0.35cm, xrightmargin=0.25cm]
public class ArraySum {
  public static void main(String[] args) {
    int[][] arrays = new int[N][M];
    int[] result = new int[N];
    ... arrays initialization ...
    for(int i=0; i < N; i++) {
      result[i] = 0;
      for(int j=0; j < M; j++) {
        result[i] += arrays[i][j];
      }
    }
  }
}
\end{lstlisting}
\end{small}
\caption{Original Array-Sum Java Code. Note that while this code is short and 
simple, it is also O(N*M) where N is the number of arrays to sum and M is the length of each array.}
\label{fig:java-example}
\end{figure}

Now, consider the Rootbeer implementation of Array-Sum in
Figure~\ref{fig:rootbeer-example}. 
In Rootbeer, any computation to be 
executed on a CUDA device must be encapsulated in a class which implements Rootbeer's
\textit{Kernel} interface. This interface contains a method called \textit{gpuMethod}(),
which is used as the entry point for the computation kernel and is executed by each
CUDA thread. The work to be performed by CUDA in a Rootbeer program is specified by 
passing a vector of \textit{Kernel} objects to a \textit{Rootbeer} object's \textit{runAll} 
method. Each of these \textit{Kernel} objects represents a thread of execution to be run on the CUDA device.


While Rootbeer provides 
impressive support for executing Java programs on CUDA devices, the programming model 
significantly decreases programmability relative to the original sequential 
Java implementation.
It is clear that using Rootbeer dramatically increases code length (approximately 2x) and decreases
readability by separating the computational kernels from the application code. 
The parallelism in this program is not readily apparent, hidden by a
sequential loop that adds
\textit{Kernel} objects to the \textit{jobs} list. 
It is also important to note that Rootbeer ignores Java 
exception semantics during GPU execution, and exceptions such as
{\tt IndexOutOfBoundsException} and {\tt NullPointerException} may not be reported.

\begin{figure}
\begin{small}
%\singlespacing
\begin{lstlisting}[xleftmargin=0.35cm, xrightmargin=0.25cm]
public class ArraySum {
  public static void main(String[] args) {
    int[][] arrays = new int[N][M];
    int[] result = new int[N];
    ... arrays initialization ...
    List<Kernel> jobs = 
        new ArrayList<Kernel>();
    for(int i = 0; i < N; i++) {
      jobs.add(new ArraySumKernel(arrays[i], 
          result, i);
    }
    Rootbeer rootbeer = new Rootbeer();
    rootbeer.runAll(jobs);
  }
}

class ArraySumKernel implements Kernel {
  private int[] source;
  private int[] ret;
  private int index;
  public ArraySumKernel(int[] source, 
      int[] ret, int i) {
    this.source = source; 
    this.ret = ret;  this.index = i;
  }
  public void gpuMethod() {
    int sum = 0;
    for(int i = 0; i < source.length; i++) {
      sum += source[i];
    }
    ret[index] = sum;
  }
}
\end{lstlisting}
\end{small}
\caption{Rootbeer Implementation.}
\label{fig:rootbeer-example}
\end{figure}

Finally, we compare the Java and Rootbeer implementations to the HJ-OpenCL implementation in Figure~\ref{fig:hjopencl-example}.
The nested for-loop structure in the Java sequential version is retained in the HJ-OpenCL benchmark, without the added encapsulation and
separation required for Rootbeer. In the HJ-OpenCL implementation, the outer for loop is replaced by a parallel HJ \hjforall{} loop which executes
every iteration in parallel. There are other two modifications from the Java sequential version.
First, an HJ array view object \textit{arrays} is declared at line 6. This 
array view object provides two-dimensional indexing (\eg\ {\tt arrays[i,j]} )
into a one-dimensional ``base'' array ({\tt base}). The use of a
one-dimensional base array
results in more efficient serialization when communicating with OpenCL
devices. 
% Now, the \textit{arrays} 
% is referenced in the parallel \hjforall{} loop in
% place of the \textit{base} object backing it.
The second change, the addition of a \safe{} block in line 8, enables
the programmer to preserve Java exception semantics. 
A \safe{} statement takes a boolean condition, and asserts that no
exception will be thrown inside the
body of that block if that condition is true. The compiler then
generates exception-safe and unsafe versions of the same block that
can be selected for execution based on the evaluation of the condition.
These HJ language constructs will be covered in more detail later in Section~\ref{sec:hj}.

It is important to note that the implementation in Figure~\ref{fig:hjopencl-example} can be executed without modification on the multi-threaded HJ runtime,
in native threads on a multi-core CPU, or in native threads on a many-core GPU.

\begin{figure}[t]
\begin{small}
%\singlespacing
\begin{lstlisting}[xleftmargin=0.35cm, xrightmargin=0.25cm]
public class ArraySum {
  public static void main(String[] args) {
    int[] base = new int[N*M];
    int[] result = new int[N];
    int[.] arrays = new arrayView(base, 0, 
                                     [0:N-1,0:M-1]);
    ... initialization ...
    boolean isSafe = ...;
    safe(isSafe) {
      forall(point [i] : [0:N-1]) {
        result[i] = 0;
        for(int j=0; j<M; j++) {
          result[i] +=  arrays[i,j];
        }
      } 
    }
  }
}
\end{lstlisting}
\end{small}
\caption{HJ-OpenCL Implementation.}
\label{fig:hjopencl-example}
\end{figure}
