\documentclass{llncs}
%\usepackage{german}
\sloppy
\begin{document}
\mainmatter
%
%============================================================
 
\input epsf
\epsfverbosetrue
\input{psfig}

\title{\Large\bf Locality optimization in JavaParty by means of static
type analysis}

\author{Michael Philippsen and Bernhard Haumacher}

\institute{
Computer Science Department, University of Karlsruhe\\
Am Fasanengarten 5, 76128 Karlsruhe, Germany\\
{\tt [phlipp$|$hauma]@ira.uka.de}\\
\texttt{http://wwwipd.ira.uka.de/JavaParty/}
}

\maketitle

%\vspace*{-6cm} \noindent \begin{minipage}[t]{\textwidth} \begin{sc}
%To appear in: Concurrency: Practice \& Experience, Vol. 11, 1999.\\
%~\\~\\
%\end{sc} \end{minipage} \vspace*{4cm}

\pagestyle{empty} % regular page numbering at the bottom on pages 2 and up
\pagenumbering{arabic}
%\setcounter{page}{22}

\begin{abstract}
On clusters and DMPs, locality of objects and threads and hence
avoidance of network communication, are crucial for the application
performance. We show that -- in certain situations -- an extension of
known type inference mechanisms can be used to compute placement
decisions that improve locality of threads and objects and hence
reduce the application execution times.

In addition to this general contribution, the paper specifically
addresses the problems that are caused by the distributed Java
environment. Since the JVM and the bytecode format are assumed to be
fixed, the optimization is done as source-to-source transformation.
\end{abstract}

\section{Introduction}

\noindent For programming languages that target distributed memory
parallel computers (DMPs), locality is crucial for performance. Data
structures that are used together should be stored on the same node,
processes/threads should be executed where the data is located that
they access. If either form of locality is not achieved, network
access (high latency and low bandwidth) is likely to become a
bottleneck for the application's performance.

For imperative programming languages, the literature is full of
techniques that enhance locality. Various parallel Fortran dialects
have compiler pragmas to express layout constraints for array data
\cite{Chap93,HPF}. Some work has been done to determine distributed
array layout through the analysis of index expressions
\cite{Knobe92,Sheffler95}. Loop restructuring techniques have been
studied extensively in parallelizing compilers and for cache
optimization purposes \cite{Banerjee,Wolfe96}. The owner-computes-rule
and the inspector-executor \cite{Koelbel90} are used to determine the
scheduling of expression evaluation in distributed environments.

However, these techniques can rarely be applied to object-oriented
code since, in general, it is not array-based. Moreover parallelism
does not stem from forall-loops, doacross-loops, or doall-loops but is
instead expressed by means of thread objects.  Little work has been
done specifically for parallel object-oriented languages.  From over a
hundred existing imperative concurrent object-oriented languages
(COOL) surveyed in \cite{Phlipp95e} more than half do not consider the
locality problem at all. The reasons are different: Some languages
have only been implemented in a prototypical way on a single
workstation, where network latencies do not occur; their developers
have mainly been interested in the design of coordination mechanisms
and a proof of concept. Other languages are restricted to shared
memory multiprocessors, they rely on the cache systems provided by
those machines. Most of the other languages are used to do research in
concurrency coordination constructs. Threads and explicit
synchronization as used in Java are not optimal for object-oriented
languages because this approach suffers from various types of
inheritance anomalies \cite{MatsuokaYonezawa93}.\footnote{A very basic
introduction to inheritance anomalies: The problem is that the lines
of code that implement the synchronization requirements may be spread
across all methods of a class. If a subclass has slightly different
synchronization needs, inheritance anomaly is likely to occur: then
instead of inheriting methods from the parent, nearly all methods must
be re-coded in the subclass. However, in the re-implementations, the
algorithms remain unchanged, just the synchronization code lines are
modified. Code duplication results in higher maintenance efforts.}

There are at least three orthogonal approaches to deal with locality
in parallel object-oriented languages. 

\begin{itemize}

\item The basic approach is to let the programmer {\it specify
placement and migration explicitly}. Since locality does not affect
the semantics of a program, the programmer in general is required to
express locality information by means of annotations. Several
suggestions have been made; only the most influential of which are
mentioned. In the Emerald system \cite{Hutch87}, objects can fixed to
other objects which advises the system to store them together;
un-fixed objects can be migrated by the system. 
Similarly, the COOL
\cite{Chandra93} programmer can provide locality hints by expressing
affinity between objects and threads. In addition there are
hierarchical schemes, e.g.\ zones \cite{Stoutamire97}, that avoid
point-to-point relationships.  In Jade \cite{Jade98}, the programmer
declaratively provides information about how the program access data
(read-only, write, etc.). 

Although user-provided placement information is likely to result in
the best performance the main problem is that annotation based
mechanisms are prone to inheritance anomalies.

%In contrast to explicit locality information in the code, both the
%runtime system and the compiler might help.

\item {\it Dynamic object distribution} is based on a runtime system
that keeps track of the call graph and the invocation
frequencies. Clever graph distribution techniques are used to (re-)
distribute objects and threads by migration.

Dynamic object distribution has two disadvantages. First, since there
is no knowledge about future call graphs and invocation frequencies,
in general object placement decisions for newly created objects are
far from optimal. Second, creation of objects that cannot migrate
because they are only meaningful on a certain node (e.g.\ file
handles, GUI-windows, etc.)  often results in a broad re-distribution
of other objects.

\item {\it Static object distribution} is the compile time
alternative. Whereas dynamic object distribution is predominantly
aimed at the improvement of locality in running programs, static
object distribution kicks in at the time of object creation. Based on
a thorough program understanding developed during compile time, the
compiler tries to predict the best node for a new object, i.e.\ the
compiler predicts the node that will result in best locality during
runtime. Static object distribution does not consider object migration.
Not a lot has been done in the area of static object distribution for
object-oriented parallel languages.

\end{itemize}

\noindent In the context of JavaParty -- a transparent extension of
Java for parallel programming of DMPs, \cite{Phlipp97b} -- we follow
all three basic approaches to improve locality; this paper focuses on
the static object distribution alone. Object migration and annotation
to increase locality are discussed elsewhere \cite{JavaParty}.

Our general idea to compute a static object distribution is to use
careful type analysis to identify groups of threads and objects that
should be co-located.  Object-oriented type analysis for purposes of
dispatch optimization
\cite{Agesen95,Chambers92,Chambers90,Palsberg91,Plevyak96} has a long
tradition. Locality optimization however, is more difficult since the
identities of threads and objects -- or at least groups thereof --
must be considered. 

In section~\ref{JavaParty} we present the details of JavaParty that
are relevant for this paper. It also provides the motivation for our
idea that instance level type analysis might help improve locality.
Section~\ref{TypeInference} discusses the basics of type inference,
section~\ref{TypeThreads} presents the extensions that are needed for
threads and locality optimization. In this section we extend classic
type inference mechanism to look beyond the level of classes and types
to extract locality information if possible.  The transformations that
result from the analysis are discussed in section~\ref{Trafo}. The
paper is concluded after a brief discussion of the results in
section~\ref{Benchmarks}.

\section{Parallelism and Distribution in JavaParty}
\label{JavaParty}

\noindent JavaParty is an extension of Java for programming DMPs; the
details can be found in
\cite{JavaParty,Phlipp97b,Phlipp98a}. JavaParty provides the illusion
of a shared address space, i.e., although objects can reside on
different hosts, their methods can be invoked as in regular
Java. JavaParty programs use thread objects as their sole means to
introduce parallelism.

The JavaParty compiler and runtime system map this model to a system
of Java virtual machines, one per node, where communication is handled
by RMI or KaRMI \cite{Phlipp99f}. JavaParty threads are mapped to
regular Java threads.

\subsection{Activity-Centered Approach}

\noindent It is necessary to understand JavaParty's execution model
before reasoning about thread and object distribution.

The physical representation of a thread object created by the
programmer must be distinguished from the control flow of a running
thread.  Although a Java thread object cannot migrate, the control
flow -- that will be called {\it activity} in the remainder of the
text -- can: whenever a method of a remote object is invoked, the
activity conceptually leaves the JVM of the caller object while the
thread object stays behind. The activity is continued at the callee
object's JVM by means of another thread object, transparently created
by the underlying RMI or KaRMI system. An activity always belongs to a
specific thread object and starts on the JVM where this thread object
has been created. A thread's activity can be determined by tracing the
execution of its {\tt run()} method.

\begin{figure}[htb]
\begin{minipage}{6cm}
\psfig{figure=fig1.ps,scale=90,clip=}
\end{minipage}\hfill
\begin{minipage}{6cm}
\psfig{figure=fig2.ps,scale=90,clip=}
\end{minipage}\\
(a) local invocation, concurrent activities \hfill
(b) remote invocation, time-sliced activities\\
\caption{JavaParty's execution model}
\label{activity}
\end{figure}

Figure~\ref{activity}(a) shows two activities, indicated by the fat
lines, in two JVMs (A and B). Time advances from top to bottom of the
graph. The activity in JVM A first executes a method of object O1,
then calls one of O2's methods on the same JVM.  The other activity
works on object O3. For simplicity, assume that both O1 and O3 are
thread objects.

Figure~\ref{activity}(b) shows the situation, when object O2 is placed
on JVM B. In contrast to a local invocation, the time needed for a
remote method call is higher than for a local invocation. Moreover,
during the execution of O2's method, the two activities face a
time-sliced execution in JVM B while JVM A is idle. The total
execution time increases.

In general, the following holds. 

\begin{itemize}

\item Whenever an activity leaves its JVM, it competes with other
activities that are concurrently executed on the target JVM. Since
method invocation is synchronous in Java, the original JVM may be idle
during the remote method invocation.  Due to time-slicing and
blocking, competing activities on one JVM decrease the total
parallelism.

\item Additional costs are introduced by the remote method invocation
itself since communication latency and bandwidth must be taken into
account.

\end{itemize}

\noindent The general distribution strategy therefore must be
activity-centered: it is preferable to place different activities onto
different JVMs. Objects are co-located to activities so that most
often and as long as possible, method invocation is local. Local
method invocation avoids costly network traffic and avoids competing
activities.

\subsection{Co-location with Activities}
\label{coloc}

\noindent Assume a hypothetical situation where the compiler has
knowledge about the concrete types of all the objects and especially
thread objects that are created at runtime.  In this situation no
dynamic dispatch is needed, i.e., for each method invocation the code
that must be executed can be selected statically.

In addition, assume
two heuristic approximations: an estimate of runtime cost for each
method (including branches and loops) and an estimate of the
probability that a specific method is invoked.

With all that information at hand, the compiler can build and trace
the weighted call graph and can derive estimates for two values:
$work(t,a)$ indicates the time an activity $t$ would spend on methods
of an object $a$ if $t$ and $a$ are located on the same node. Remember
that objects do not migrate, only activities do.

Similarly, we can determine $cost(t,a)$ for the communication time
that would be necessary if $t$ and $a$ are {\it not} stored on the
same node. The cost information takes into account that in the assumed
hypothetical situation the concrete types of parameters and return
values are known by the compiler. The compiler hence can estimate the
communication costs caused by the sizes of the messages that must
cross the network to ship the marshaled arguments.

When large data sets are passed as arguments, the necessary
communication time is considered. Otherwise (if the large data sets
are themselves objects that do not migrate but instead are touched by
activities) the cost of an activity accessing the data is considered
as well.

If $work(t,a) > \sum_{t_i \neq t} cost(t_i,a)$ it is wise to co-locate
object $a$ with activity $t$ (or with $t$'s thread object), since
activity $t$ spends more time working on $a$ than all other activities
$t_i$ together need to call methods of $a$ remotely. Hence,
parallelism is increased.

For every single object $a$, the optimal activity $\tau = activity(a)$
is derived as the one that maximizes $work(\tau,a) - \sum_{t_i \neq
\tau} cost(t_i,a)$.

\subsection{Placement of Activities}
\label{group}

\noindent In general, more activities are used than there are CPUs 
available. An activity increases parallel execution when working on a
co-located object (first sum below); the overall parallel execution is
decreased if the activity faces remote method invocations (second
sum). Therefore, we define the parallelization win of $t$ as $win(t) =
\sum_{activity(a)=t} work(t,a) - \sum_{activity(b) \neq t} cost(t,b)$.

Activities are assigned in a round-robin fashion to the available JVMs
in decreasing order of their parallelization wins until on every JVM a
single activity has been scheduled, i.e, one thread object has been
created per JVM. For each of the remaining activities, a new value of
its parallelization win is computed. The new value takes into account
the potential co-location with other activities and objects. With
these new values derived, the next set of activities (thread objects)
is scheduled to the JVMs. This is repeated until all activities are
scheduled.

\subsection{Reality Check}

\noindent In sections~\ref{coloc} and~\ref{group} we motivated a
perfect placement methodology for JavaParty objects and
threads. Unfortunately, the presented techniques relied on severe
assumptions.

First of all, the technique needed knowledge about concrete types of
all objects that will be created at runtime. Although such precision
cannot be available during compile time analysis, we show in
sections~\ref{TypeInference} and~\ref{TypeThreads} that -- in certain
situations -- less precise (but sufficient) information can be
derived, categorizing objects and threads into equivalence classes
with known concrete type information.

Second, heuristics have been used in optimizing compilers for the cost
estimates and the invocation frequencies before, see for example
\cite{Fah92}. We use similar heuristics in our prototype.

\section{Type Inference}
\label{TypeInference}

\noindent Consider a method invocation {\tt a.foo(arg)} in Java. Due
to Java's static type system, it can be determined at runtime which of
several methods {\tt foo(param)} is used if the concrete type of {\tt
a} is known. The types of {\tt arg} and {\tt param} are irrelevant for
dispatch at runtime. Hence, the goal of the type inference mechanism
is to determine the concrete type of {\tt a} since the computation of
$work(t,a)$ needs to know exactly which version of {\tt foo} is used.

Since there are different control flow paths that can lead to the
invocation, in general {\tt a} can hold one of a set of possible
concrete types. Thus, there is only {\it imprecise type information}
for {\tt a} available. Especially if {\tt a} is declared to be of an
{\tt interface} type the set of possible concrete types can get quite
diverse.  The type inference algorithm uses constraint propagation and
traverses the control flow and data flow graphs to determine such
sets. Depending on the nature of {\tt a}, there are known strategies
to resolve the imprecise information: if {\tt a} is the parameter of
the surrounding procedure, conceptual method cloning can be used
\cite{Agesen95,Chambers90,Chambers92,Palsberg91}.  If {\tt a} is an
instance variable, conceptual class cloning can improve precision
\cite{Plevyak96}. We will now explain both techniques.

\subsection{Method Cloning}
\label{MethodCloning}

\noindent If {\tt a} is a method parameter, say of method 
{\tt bar}, and if there is imprecise information about {\tt a}'s
concrete type, the imprecision is usually caused at the points where
{\tt bar} is called.  Assume that there are two paths to two
invocations of {\tt bar}, as shown in Figure~\ref{call1}. Both
invocations use a different concrete argument type (precise
information, {\tt C} or {\tt D}). After the invocations, the concrete
type of {\tt a} can be either of these.

\begin{figure}[htb]
\centerline{\psfig{figure=call1.ps,scale=90}}
\caption{Reason for method cloning. The variables are annotated with
the inferred type information, i.e., with the set of possible concrete
tzpes.}
\label{call1}
\end{figure}

Now, the type inference algorithm conceptually duplicates the called
method. The invocation of {\tt bar} that has been processed first
remains unchanged. For processing the second invocation, {\tt bar} is
cloned and instead of {\tt bar}, the copy {\tt bar'} is called.
Therefore, the analysis has precise concrete type information for the
parameter {\tt a} in {\tt bar} and as well for the parameter {\tt a}
of {\tt bar'}.\footnote{The presentation is simplified.  Special care
must be taken to avoid endless code duplications in recursive
methods.} Thus, type inference can determine which version of {\tt
foo(param)} will be called in both {\tt bar} and {\tt bar'}.

\subsection{Conceptual Class Cloning}
\label{ClassCloning}
 
\noindent If {\tt a} is an instance variable, local method cloning is
insufficient. Conceptually, whole classes must
be cloned instead. That in turn causes the type inference mechanism 
to start over again -- at least for a significant part of the code.
The reason is that while for parameters there is only a single reaching
definition (namely at the very beginning of the method) for instance
variables there might be arbitrarily many reaching
definitions all over the code.

Assume a situation (see Figure~\ref{class1}) where two assignments in
the code assign objects of two different concrete types to {\tt a},
namely {\tt C} and {\tt D}. Let {\tt a} be an instance variable of
class {\tt A}. From each of these reaching definitions the type
inference algorithms uses data flow information to track back to the
points where a {\tt new A(.)}  statement is used to create the
object. (The paths to the reaching definitions might have common
segments whose nodes have imprecise type information. Separation of
common path segments may require cloning even during inverse tree
traversal.)

\begin{figure}[htb]
\centerline{\psfig{figure=class1.ps,scale=90}}
\caption{Reason for class cloning}
\label{class1}
\end{figure}

At the {\tt new A(.)}
statements, class {\tt A} is conceptually cloned, one of the {\tt new}
statements is modified to create an object of class {\tt A'}
instead.\footnote{Actual cloning would break the type system: Neither
is there a well-defined relationship between {\tt A} and {\tt A'} in
Java, nor can objects of type {\tt A'} be used instead of {\tt A}, and
vice versa. Section~\ref{Trafo} briefly explains how conceptually
cloned classes are transformed back into regular Java.}  Due to this
cloning, there are suddenly two different instance variables: {\tt a}
of class {\tt A} and {\tt a} of class {\tt A'}. Let us rename the
latter to {\tt a'} for clarity. Both instance variables keep their
concrete types, they are not combined by the two assignment statements
that now affect different instance variables. Thus, type inference can
determine which version of {\tt foo(param)} will be called at runtime
in both {\tt a.foo(arg)} and {\tt a'.foo(arg)}.

\subsection{Reality Check}

\noindent Of course, type inference cannot determine the concrete classes for
every method invocation. Especially, method and class cloning cannot
handle imprecise type information for local variables. Similarly, for
arrays or polymorphically used recursive data structures, no precise
type inference can be done.

\section{Type Inference for Thread Locality}
\label{TypeThreads}

\noindent Although after type inference 
the target method of each invocation is known, still no placement
decision can be derived, the analysis might not be able to tell thread
objects apart.  Consider the following example where, unfortunately,
standard type inference will neither clone methods nor classes.

\begin{verbatim}
   class MyThread extends Thread {
     public void run() {
       A x = new A();
       x.foo();
     }
   }
   class A {
     void foo() { }
   }
   ... 
   new MyThread().start();
   new MyThread().start();
\end{verbatim}

\noindent The analysis does not realize that each of the
threads\footnote{In Java a thread object has a {\tt run()} method that
is invoked by calling {\tt start()}. {\tt start()} returns immediately
to the caller; {\tt run()} is executed concurrently.}  uses a private
object of type {\tt A} since everything is monomorphic. We will extend
the mechanism, so that both the classes {\tt MyThread} and {\tt A}
will be cloned. Then {\tt MyThread} uses {\tt A} whereas {\tt
MyThread'} uses {\tt A'}. This fact can be used to guide placement
decisions so that the activity {\tt MyThread} and the object of type
{\tt A} end up in the same JVM whereas the primed versions end up in
another JVM.

\subsection{Introduction of Helper Polymorphism}

\noindent We now present how enough polymorphism can be introduced to
force the necessary cloning.  This is done in two steps: First,
wherever a thread is created, the corresponding thread class is
cloned.  Objects that implement the {\tt Runnable} interface are
treated analogously.  Second, the original source code is
(conceptually) transformed so that it carries and keeps thread IDs as
additional parameters through all method invocations.

In the above example, we first use different classes {\tt MyThread}
and {\tt MyThread'}.

\begin{verbatim}
   new MyThread().start();
   new MyThread()'.start();
\end{verbatim}

\noindent Second, the source-to-source transformation carries and
keeps thread IDs.  The idea is to pass the current thread as an
additional parameter {\tt \$thread} to each method invocation. Each
non-static method stores this thread parameter as a supplementary
instance variable of its class (called {\tt \$thread}). The {\tt
run()} method is the only exception of this rule.  This is the only
method which is never called from within another method. The {\tt
run()} method is invoked in a new thread and as its first action
stores the {\tt this} variable in its {\tt \$thread} variable. For the
example, the transformed code is shown below.

\begin{verbatim}
   class MyThread extends Thread {
     Thread $thread;               //new instance var
     public void run() {
       Thread $thread = this;      //keep thread ID
       this.$thread = $thread;     //keep thread ID
       A x = new A();
       x.foo($thread);             //new argument
     }
   }
   class A {
     Thread $thread;               //new instance var
     void foo(Thread $thread) {    //new parameter
       this.$thread = $thread;     //keep thread ID
     }
   }
\end{verbatim}

\subsection{Helper Polymorphism is Sufficient}

\noindent We now explain why the above two-step modification is
sufficient to cause the desired cloning.

\begin{figure}[htb]
\centerline{\psfig{figure=thread1.ps,scale=90}}
\caption{Type imprecision after introduction of helper
polymorphism and cloning of thread creations. Two {\tt run()} methods
invoke the same method {\tt foo(.)}, causing an imprecision in the
{\tt \$thread} parameter.}
\label{thread1}
\end{figure}

All the activities of a given program commence at the {\tt run()}
methods of the thread classes. As shown in Figure~\ref{thread1} there
are two paths in the example program that reach {\tt
foo(\$thread)}. Along the two paths, thread objects of different
conceptual types are used: One path carries a thread object of type {\tt
MyThread}, the other carries a thread object of type {\tt MyThread'}.
The type inference algorithm therefore faces an imprecision in the
parameter of {\tt foo}, since the set of possible concrete types has
more than one element. This causes {\tt foo} to be cloned so that {\tt
foo} is called with {\tt MyThread} whereas {\tt foo'} is called with
{\tt MyThread'}; see section~\ref{MethodCloning}.

Since both {\tt foo} and {\tt foo'} belong to the same class {\tt A},
they refer to the same instance variable {\tt this.\$thread}.  When
{\tt foo} and {\tt foo'} assign the thread ID to that instance
variable, the same imprecision re-appears. The instance variable {\tt
\$thread} can either contain a thread object of type {\tt MyThread} or
of type {\tt MyThread'}.  At that point, the type inference algorithm
uses conceptual class cloning to resolve that imprecision; see
section~\ref{ClassCloning}.  For that purpose, the type inference
algorithm must find the point where the object is created to which the
instance variable {\tt \$thread} belongs. Due to the cloning of {\tt
MyThread} there are two {\tt run} methods, each of which calls {\tt
new A()}. Conceptual cloning of {\tt A} solves the problem: The {\tt
run} method of {\tt MyThread'} creates an object of type {\tt A'}
instead; there is no longer an imprecision at the assignment to
{\tt this.\$thread}. The resulting types are illustrated by
Figure~\ref{thread2}.

\begin{figure}[htb]
\centerline{\psfig{figure=thread2.ps,scale=90}}
\caption{Resulting type information. Method {\tt foo} is cloned. The
imprecision in {\tt this.\$thread} has been resolved by cloning class
{\tt A}.}
\label{thread2}
\end{figure}

Therefore, the added polymorphism is sufficient to clearly separate
the activities and objects into two disjoint groups according to their
locality requirements. 
More details can be found in \cite{Haumacher98}.

\section{Transformation}
\label{Trafo}

\noindent Instead of actual cloning of methods and classes, the
JavaParty system modifies a ``cloned'' method to accept a new
parameter. This parameter carries a version number into the
method. Inside of the method, this version number is used to decide
which versions of other methods are to be called. Similarly, ``cloned''
classes are mapped to classes that carry an additional version number.

The JavaParty system includes a ByteCode disassembler that is used to
analyze existing Java programs that are not translated/optimized. To
allow for seamless integration with existing code, in addition to the
``cloned'' method with its extended signature, there is a method with
the original signature.

\subsection{Transformation of cloned Methods}

\noindent The method {\tt bar(a)} of
section~\ref{MethodCloning} is roughly modified as follows:

\begin{verbatim}
void bar$clone(A a, int method$version) 
   ...
   a.foo$clone(arg, 
               bar$apply[method$version][42]);
   ...
}
void bar(A a) {
   bar(a, default$version);
}
\end{verbatim}

There are two versions of {\tt bar}; the second invokes a default
version of the first. Since the two clones of {\tt bar} introduced in
section~\ref{MethodCloning} invoke different versions of {\tt foo}, a
lookup table {\tt bar\$apply} is used. The lookup table is a static
final array that is computed by the optimizer. There is one such
lookup table per cloned method. It has entries for every single method
invocation that appears textually within the method. In the above code, the
invocation of {\tt foo} is assumed to be the 42nd method that is
called inside {\tt bar}. The optimizer avoids the table
lookup if a constant value will be returned for all versions.

%In addition, type case operations on {\tt a} might be necessary. In
%this case, the optimizer introduces another lookup table for switching
%between replicated invocations of {\tt foo}, each of which is guarded
%with the correct type case.  

\subsection{Transformation of cloned Classes} 

\noindent Each ``cloned'' class is augmented with a new instance variable {\tt
class\$version}. Two new parameters are added to constructor
routines. In addition to the {\tt method\$version}, a {\tt
class\$version} is passed into the constructor.

Let us study a {\tt new A()} statement that appears inside of method
{\tt gee} and the (simplified) result of its transformation.

\begin{verbatim}
seq{ 
  RuntimeSystem.setTarget(
               gee$newAt[method$version][17]);
  return new A(gee$apply[method$version][29],
               gee$new[method$version][17]);
}  
\end{verbatim}

First of all, the runtime system is ordered to create the next object
at a node whose number comes from the lookup table {\tt
gee\$newAt}. This table has two dimensions: As before, the first
dimension refers to the version of the method. The second dimension
gives the number of the {\tt new} statement within {\tt gee} (17 in the
example).  The constructor's first parameter refers to the version of
{\tt gee}, indexed by the number of method invocations inside {\tt
gee}, say 29. The second parameter selects the particular ``clone'' of
{\tt A} that is to be created. The {\tt seq}-block is a shorthand
notation that allows for a block of statements where Java
expects an expression.

Again, the optimizer generates the
necessary lookup tables.
The details of the transformation can be found in \cite{Haumacher98}.

\section{Results and Future Work} \label{Benchmarks}

\noindent As part of the JavaParty project, we have implemented the type
inference algorithm, a ByteCode disassembler that allows for the
analysis of existing Java code, the transformation extending the type
inference algorithm to handle threads and to deliver locality
information. Finally, the ``cloned'' methods and ``classes'' are
transformed back into regular Java that can compiled by 
{\tt javac}.

The optimizer works fine for some JavaParty programs and performs
badly for others. 

We have studies a synthetic benchmark program of about 100 lines of
code with 7 classes and a total of 15 methods thoroughly.  The program
is constructed in a way so that every method invocation and every
declaration of an instance variable requires work and potentially
cloning by the inference algorithm. On the other hand, all the methods
are effectively empty, so that all size comparisons give an idea of a
worst case scenario.

\begin{itemize}

\item {\bf Static comparison.}  For that example program, the type
inference created 17 clones of classes and 41 clones of methods. The
generated Java code needs about 300 lines of code.  The byte code of
the compiled program increases by a factor of three as well.

Compared to the original version of the program, the optimized version
creates 96 additional static final objects that are stored in 49
static variables and 42 instance variables. A total of 174 static ints
are necessary to implement the arrays that are needed for cloning by
means of an additional method parameter. The initialization of these
objects and variables is executed only once at program start.

For one of the classes of the benchmark program, its code and the
generated code is shown in figures~\ref{examplecode1}
and~\ref{examplecode2}.  With more realistic programs the relative
growths is smaller since less cloning will add less code lines and
will require smaller amounts of helper data.

\begin{figure}[htb]
\begin{verbatim}
                    remote class A implements Runnable {
                      public void run() {
                        System.out.println("A.run");
                        for (int n = 0; n < 5; n++) {
                          D d = new D();
                          d.foo();
                        }
                      }
                    }
\end{verbatim}
\caption{Source code for one class of the synthetic example.}
\label{examplecode1}
\end{figure}

\begin{figure}[htb]
\begin{verbatim}
remote class A implements Runnable {
   protected int this$contour;
   private static final int[]   A$$code  = {0};
   private static final int[][] A$$apply = {{-1}};
   private static final int[][] A$$new   = {{}};
   private static final int[][] A$$newAt = {{}};
   public  A(int method$contour, int object$contour){
      super();
      this$contour = object$contour;
      final int[] this$apply = A$$apply[method$contour];
      final int[] this$new   = A$$new[method$contour];
      final int[] this$newAt = A$$newAt[method$contour];
      switch (A$$code[method$contour]) {
      case 0:  break;
      default: throw new RuntimeException("wrong code selector");
      };
   };
   private static final int[]   run$$code  = {0};
   private static final int[][] run$$apply = {{-1, 0, 2}};
   private static final int[][] run$$new   = {{0, 0}};
   private static final int[][] run$$newAt = {{-1, 0}};
   public void run$contour(int method$contour){
      if (method$contour < 0) 
         method$contour = run$$dispatch(- (method$contour + 1));
      final int[] this$apply = run$$apply[method$contour];
      final int[] this$new   = run$$new[method$contour];
      final int[] this$newAt = run$$newAt[method$contour];
      switch (run$$code[method$contour]) {
      case 0: {
            System.out.println("A.run");
            for (int n = 0; n < 5; ++ n) {
               D d = seq {
                  ObjDistr.setPriority(this$newAt[1]);
                  return new D(this$apply[1], this$new[1]);
               };
               d.foo$contour(this$apply[2]);
            };
         };
         break;
      default: throw new RuntimeException("wrong code selector");
      };
   };
   public void run(){
      run$contour(-1);
   };
   private static final int[][] run$$vct = {{0}};
   protected int run$$dispatch(int name){
      return run$$vct[name][this$contour];
   };
}
\end{verbatim}
\caption{Generated code for the class of figure~\ref{examplecode1}.}
\label{examplecode2}
\end{figure}


\item {\bf Dynamic comparison.}  With Java 1.2.1., the remote
invocation of an empty method takes about 1.02~ms when RMI is used
between two Sun Ultra 10 workstations. Since a cloned method requires
some table lookups and since it takes another argument of type int,
some slowdown can be expected. We have timed that slowdown: it is
about 20 $\mu$s, i.e., the overhead of calling a cloned versus a
regular method is about 2\% with regular Java. 

%(Although the call is much faster when KaRMI is used on a
%Myrinet-connected cluster of DEC Alpha workstations (120 $\mu$), we
%notice a slowdown of 50 $\mu$s :-(.)

However, the slowdown of a remote call is not the only relevant
aspect.  It is more important that local method invocations can be
performed in the nano second range, i.e., they are much faster than
any remote invocation. When the locality optimization can co-locate
threads and objects so that local invocations can be used where slow
remote invocations were necessary in an un-optimized version, the
table lookups and the extra int argument can easily be afforded.

On three JVMs the performance of the synthetic benchmark program was
improved by more than a factor of 2. We have seen similar results
for other programs.

\end{itemize}

\noindent For some JavaParty programs, however, the approach did not
improve the runtimes. We have identified two reasons for it. First,
the analysis can handle separate creations of thread objects in the
code. However, if threads are created in a loop (and stored in an
array), there is no way to clone the corresponding thread classes and
to introduce enough polymorphism so that the type inference can be
used to derive useful placement decisions. On the contrary, without
further processing, all these threads fall into the same activity
class and are instantiated on exactly the same JVM. The second reason
for weak performance showed up in other JavaParty programs where the
programmer used the design pattern ``workpile''. Objects that
describe/contain work to be done are stored into an internal data
structure of the workpile that often is a list or an array. In either
case, the type inference algorithm cannot handle the
imprecision. Again, the problem is that all work objects are combined
into one single equivalence class. Hence there is no way to distribute
certain work objects to certain activities.

In the future, we will attack these two problems. Since the static
analysis can identify areas of the code where additional information
would be beneficial, we will generate additional code that performs
dynamic object distribution at runtime. Hence, additional runtime
information is used to further split equivalence classes determined by
the type inference algorithm. In contrast to a pure dynamic object
distribution, smaller call graphs are needed. Moreover, by selecting a
certain clone number, the dynamic distribution can capitalize on
results of the static analysis when creating new objects. We are
convinced that a combination of static and dynamic object distribution
will yield better results whenever one of the approaches alone fails.

\section{Conclusion} 

\noindent We have shown that standard type inference techniques for
object-oriented languages can -- in certain situation -- be applied to
guide object and thread creation in a distributed environment towards
improved locality. The necessary extensions of the type inference
mechanisms have been discussed in general. Their shortcomings in
cases that require true polymorphism have been identified.

The optimizer has been implemented as part of the JavaParty
project. Depending on the nature of the optimized program, the
optimizer can improve performance significantly. 

\section*{Acknowledgements}
\noindent We would like to thank the JavaParty group, especially Matthias
Zenger, for their support of the JavaParty environment.

%\bibliographystyle{plain}
%\bibliography{../../Literatur/literat} 

\begin{thebibliography}{10}

\bibitem{Agesen95}
Ole Agesen.
\newblock The cartesian product algorithm, simple and precise type inference of
  parametric polymorphism.
\newblock In {\em Proc. of. ECOOP'95, European Conf. on Object-Oriented
  Programming}, pages 2--26, Arhus, Danmark, 1995.

\bibitem{Banerjee}
Utpal Banerjee.
\newblock {\em Dependence Analysis for Supercomputing}.
\newblock Kluwer Academic Publishers, Boston, Dordrecht, London, 1988.

\bibitem{Chambers92}
Craig Chambers.
\newblock {\em The Design and Implementation of the Self Compiler, an
  Optimizing Compiler for Object-Oriented Programming Languages}.
\newblock PhD thesis, Stanford University, Department of Computer Science,
  March 1992.

\bibitem{Chambers90}
Craig Chambers and David Ungar.
\newblock Iterative type analysis and extended message splitting: Optimizing
  dynamically-typed object-oriented programs.
\newblock In {\em Proc. of the SIGPLAN '90 Conf. on Programming Language Design
  and Implementation}, pages 150--164, White Plains, NY, June 1990.

\bibitem{Chandra93}
Rohit Chandra, Anoop Gupta, and John~L. Hennessy.
\newblock Data locality and load balancing in {COOL}.
\newblock In {\em ACM Sigplan Symp. on Principles and Practice of Parallel
  Programming}, pages 249--259. ACM Press, New York, September 7--8, 1993.

\bibitem{Chap93}
Barbara Chapman, Piyush Mehrotra, and Hans Zima.
\newblock User defined mappings in {V}ienna {F}ortran.
\newblock In {\em Proc. of the 1993 Workshop on Languages, Compilers, and
  Run-Time Environments for Distributed Memory Multiprocessors}, pages 72--75,
  Boulder, CO, September 30 -- October 2, 1992, January 1993. ACM SIGPLAN
  Notices 28(1).

\bibitem{Fah92}
T.~Fahringer, R.~Blasko, and H.~Zima.
\newblock Static performance prediction to support parallelization of {F}ortran
  programs for massively parallel systems.
\newblock In {\em Int. Conf. on Supercomputing}, pages 347--356, Washington,
  D.C., July 1992.

\bibitem{Haumacher98}
Bernhard Haumacher.
\newblock Lokalit{\"a}tsoptimierung durch statische {T}ypanalyse in
  {J}ava{P}arty.
\newblock Master's thesis, University of Karlsruhe, Department of Informatics,
  January 1998.

\bibitem{Hutch87}
Norman~C. Hutchinson, Rajeandra~K. Raj, Andrew~P. Black, Henry~M. Levy, and
  Eric Jul.
\newblock The {E}merald programming language report.
\newblock Technical Report 87-10-07, Department of Computer Science, University
  of Washington, Seattle, October 1987.

\bibitem{Phlipp98a}
Matthias Jacob, Michael Philippsen, and Martin Karrenbach.
\newblock Large-scale parallel geophysical algorithms in {J}ava: A feasibility
  study.
\newblock {\em Concurrency: Practice and Experience}, 10(11--13):1143--1154,
  September--November 1998.

\bibitem{JavaParty}
{J}ava{P}arty.
\newblock http://wwwipd.ira.uka.de/JavaParty/.

\bibitem{Knobe92}
Kathleen Knobe, Joan~D. Lukas, and William~J. Dally.
\newblock Dynamic alignment on distributed memory systems.
\newblock In {\em 3rd Workshop on Compilers for Parallel Computers}, pages
  394--404, Vienna, Austria, July 6--9, 1992.

\bibitem{Koelbel90}
Charles Koelbel and Piyush Mehrotra.
\newblock Supporting shared data structures on distributed memory
  architectures.
\newblock In {\em Proc. of the 2nd ACM SIGPLAN Symp. on Principles and Practice
  of Parallel Programming, PPoPP}, pages 177--186, March 1990.

\bibitem{HPF}
Charles~H. Koelbel, David~B. Loveman, Robert~S. Schreiber, Guy~L. Steele, and
  Mary~E. Zosel.
\newblock {\em The High Performance Fortran Handbook}.
\newblock MIT Press Cambridge, Massachusetts, London, England, 1994.

\bibitem{MatsuokaYonezawa93}
Satoshi Matsuoka and Akinori Yonezawa.
\newblock Analysis of inheritance anomaly in object-oriented concurrent
  programming languages.
\newblock In Gul Agha, Peter Wegner, and Akinori Yonezawa, editors, {\em
  Research Directions in Concurrent Object-Oriented Programming}, pages
  107--150. MIT Press Cambridge, Massachusetts, London, England, 1993.

\bibitem{Phlipp99f}
Christian Nester, Michael Philippsen, and Bernhard Haumacher.
\newblock A more efficient {RMI}.
\newblock In {\em ACM 1999 Java Grande Conference}, pages 152--159, San
  Francisco, 1999.

\bibitem{Palsberg91}
Jens Palsberg and Michael~I. Schwartzbach.
\newblock Object oriented type inference.
\newblock In {\em Proc. of OOPSLA'91, Conf. on Object-Oriented Programming
  Systems, Languages, and Applications}, pages 146--161, Phoenix, Arizona,
  November 1991.

\bibitem{Phlipp95e}
Michael Philippsen.
\newblock Imperative concurrent object-oriented languages.
\newblock Technical Report TR-95-050, International Computer Science Institute,
  Berkeley, August 1995.

\bibitem{Phlipp97b}
Michael Philippsen and Matthias Zenger.
\newblock Java{P}arty: Transparent remote objects in {J}ava.
\newblock {\em Concurrency: Practice and Experience}, 9(11):1225--1242,
  November 1997.

\bibitem{Plevyak96}
John Plevyak.
\newblock {\em Optimization of Object-Oriented and Concurrent Programs}.
\newblock PhD thesis, University of Illinois at Urbana-Champaign, Urbana, IL,
  1996.

\bibitem{Jade98}
Martin~C. Rinard and Monica~S. Lam.
\newblock The design, implementation, and evaluation of {J}ade.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  20(3):483--545, May.

\bibitem{Sheffler95}
Thomas~J. Sheffler, Robert Schreiber, John~R. Gilbert, and Siddhartha
  Chatterjee.
\newblock Aligning parallel arrays to reduce communication.
\newblock In {\em Frontiers '95: The 5th Symp. on the Frontiers of Massively
  Parallel Computation}, pages 324--331, McLean, VA, February 6--9, 1995.

\bibitem{Stoutamire97}
David Stoutamire.
\newblock {\em Portable, Modular Expression of Locality}.
\newblock PhD thesis, University of California at Berkeley, Department of
  Computer Science, December 1997.
\newblock Available as ICSI technical report 97-056.

\bibitem{Wolfe96}
Michael Wolfe.
\newblock {\em High Performance Compilers for Parallel Computing}.
\newblock Addison-Wesley, Reading, Mass., 1996.

\end{thebibliography}

\end{document}
