%template for producing IEEE-format articles using LaTeX.
%written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
%use at your own risk.  Complaints to /dev/null.
%make two column with no page numbering, default is 10 point
%\documentstyle[twocolumn,oldlfont]{article}
\documentstyle[twocolumn]{article}
\input epsf
\epsfverbosetrue
\input{psfig}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI}

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%MP: need an 10 pt font size for subsection and abstract headings
\def\subsubsize{\@setsize\subsubsize{11pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}
{15pt plus 2pt minus 2pt}
{9pt plus 2pt minus 2pt}{\large\bf}}
%=EH=16/10
%{24pt plus 2pt minus 2pt}
%{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{7pt plus 2pt minus 2pt}{\subsize\bf}}
% \makeatother % put in comment by MP

% The following is added by MP:
%make subsubsection titles bold and 10 point, 1 blank line before, 1 after
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}
{7pt plus 2pt minus 2pt} {10pt plus 2pt minus 2pt}{\subsubsize\bf}}
\makeatother

\begin{document}

%Vorspann, damit es zu der Deckseite des TR passt

% \pagenumbering{roman}
% \setcounter{page}{2}
% \onecolumn
% \tableofcontents
% \twocolumn
% \pagenumbering{arabic}
% \setcounter{page}{1}

\newcommand{\nt}{{\noindent}}
\def\N{I \kern-3pt N}                % natuerliche Zahlen
\def\Z{Z \kern-5pt Z}                % ganze Zahlen

\newenvironment{code}{\pagebreak[2]\nt\rule[2mm]{\columnwidth}{1pt}\vspace*{-3mm}}%
{\nt\rule[2mm]{\columnwidth}{1pt}\vspace*{-2mm}}
\newcommand{\abs}[1]{\vspace{2mm}\nt{\it #1}}

%don't want date printed
\date{}
%\date{\today}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf Locality optimization in JavaParty by means of static
type analysis}

\author{
Michael Philippsen and Bernhard Haumacher\\
University of Karlsruhe, Germany\\
phlipp@ira.uka.de and hauma@ira.uka.de
}

\maketitle

%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
% \footnotetext[1]{Much of this work has been done during the authors'
% stay at ICSI, International Computer Science Institute,
% Berkeley.}
%\footnotetext[1]{Removed for anonymity.\\~}
%\renewcommand{\thefootnote}{\arabic{footnote}}
%\setcounter{footnote}{0}

\vspace*{-6cm} \nt\begin{minipage}[t]{6.8in} \begin{sc}
In Proc.\ Workshop on Java for High Performance Network Computing at 
EuroPar'98, Southampton, September 2--3, 1998. Earlier version:
Proc.\ 7th Int. Workshop on Compilers for Parallel
Computers CPC'98, pages 34--41, Link{\"o}ping, Sweden, June 29 -- July
1, 1998.
\end{sc} \end{minipage} \vspace*{3.4cm}

%\vspace*{-6cm} \nt\begin{minipage}[t]{6.8in} \begin{sc}
%~\\~\\~\\
%\end{sc} \end{minipage} \vspace*{3.4cm}

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract} \nt {\em On clusters and DMPs,
locality of objects and threads and hence avoidance of network
communication, are crucial for performance. We show that an extension
of known type inference mechanisms can be used to compute placement
decisions that improve locality.

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

\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 imperative programming languages, literature is full of techniques
that enhance locality. Various parallel Fortran dialects have compiler
pragmas to express distributed layout of 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-, doacross, 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 anomaly\cite{MatsuokaYonezawa93}.\footnote{A very basic
introduction to inheritance anomaly: 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. 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, e.g.\
\cite{Stoutamire97}.  In contrast to explicit locality information in
the code, both the runtime system and the compiler might help.  {\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 
%\cite{} 
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. {\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.

In the context of JavaParty -- a transparent extension of Java for
parallel programming of DMPs, \cite{JavaParty,Phlipp97b} -- we follow
all three basic approaches to improve locality; this paper focuses on
the static object distribution through careful type analysis. Static
type analysis of Java is more difficult than in imperative languages because
of the dynamic dispatch. Object-oriented type analysis for improving
locality is more difficult than type analysis for purposes of dispatch
optimization
\cite{Agesen95,Chambers92,Chambers90,Palsberg91,Plevyak96}, since
concurrently executing threads must be taken into account.

In section~\ref{JavaParty} we present the details of JavaParty that
are relevant for this paper. Section~\ref{TypeInference} discusses the
basics of type inference, section~\ref{TypeThreads} presents the
extensions that are needed for threads and locality optimization. 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. 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.

Although a Java thread 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 and is continued at the callee object's
JVM. 

\begin{figure}[htb]
\begin{small}
\centerline{\psfig{figure=fig1.ps,scale=90}}
\centerline{(a) local invocation, concurrent activities}
\centerline{\psfig{figure=fig2.ps,scale=90}}
\centerline{b) remote invocation, time-sliced activities}
\caption{JavaParty's execution model}
\label{activity}
\end{small}
\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.


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. 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 might run idle during the remote method invocation.  Due
to time-slicing and blocking, competing activities on one JVM decrease
the total parallelism. Additional costs are introduced by the remote
method invocation itself since communication latency and bandwidth
must be taken into account.

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
total knowledge about objects and activities that are created at
runtime. Since for every single object its concrete type is known, 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. Note, that in
the weighted call graph, for a specific thread object the execution of
the {\tt run()} method must be traced.

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.

If $work(t,a) > \sum_{t_i \neq t} cost(t_i,a)$ it is wise to co-locate
object $a$ with activity $t$, 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. 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 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 complete 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 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 heuristice 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 used at
compile-time and are irrelevant 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, called {\it imprecise type information}. 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]
\begin{small}
\centerline{\psfig{figure=call1.ps,scale=72}}
\caption{Reason for method cloning}
\label{call1}
\end{small}
\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}. Let {\tt a} be an instance variable of class {\tt A}. From
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 objects. (Since the paths to the
reaching definitions might have common segments, the graph can have
nodes with imprecise type information. Separation of common path
segments may require cloning even during inverse tree
traversal.)

\begin{figure}[htb]
\begin{small}
\centerline{\psfig{figure=class1.ps,scale=72}}
\caption{Reason for class cloning}
\label{class1}
\end{small}
\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{small}
\begin{verbatim}
class MyThread extends Thread {
  public void run() {
    A x = new A();
    x.foo();
  }
}
 
class A {
  void foo() {
  }
}
 
- - - - - - - - - - - - - - - - - -

  new MyThreaad().start();
  new MyThreaad().start();
\end{verbatim}
\end{small}

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{small}
\begin{verbatim}
  new MyThreaad().start();
  new MyThreaad()'.start();
\end{verbatim}
\end{small}

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{small}
\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}
\end{small}

\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]
\begin{small}
\centerline{\psfig{figure=thread1.ps,scale=72}}
\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{small}
\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]
\begin{small}
\centerline{\psfig{figure=thread2.ps,scale=72}}
\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{small}
\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{small}
\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}
\end{small}

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{small}
\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}
\end{small}

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 numer 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 implented 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. For a synthetic benchmark program with 7 classes and
a total of 15 methods the type inference created 17 clones of classes and
41 clones of methods. On three JVMs the program
performance was improved by more than a factor of 2.

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 by using
additional runtime information to further split equivalence classes
determined by the type inference algorithm.

\section{Conclusion} 

\noindent We have shown that standard type inference techiques for
object-oriented languages can be applied to guide object and thread
creation in a distibuted environment towards improved locality. The
necessary extensions of the type inference mechanisms have been
discussed in general.

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. Cases where
the optimizer fails have been identified and will be attacked in
future.

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

\small
%\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{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{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{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{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}
