%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

% ----> was this -----> \documentstyle[auffil,rotate,epsf,art12]{article}
\documentstyle[auffil,twocolumn,rotate,epsf,art10]{article}

%\documentstyle[auffil,twocolumn,rotate,epsfig,epsf,art12]{article}
\pagestyle{empty}

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

\input{BoxedEPS} % replaces epsf.sty -- much better!
\input{psfig}
\SetRokickiEPSFSpecial % turn this on for Unix dvips
%\SetTexturesEPSFSpecial
\HideDisplacementBoxes

\pagestyle{empty}

\newcommand{\qed}{\vspace*{-2\baselineskip}\hfill$\Box$}

%\input{BoxedEPS} % replaces epsf.sty -- much better!
%\SetRokickiEPSFSpecial % turn this on for Unix dvips
%\SetTexturesEPSFSpecial
%\HideDisplacementBoxes
%\input{psfig}


\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}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{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}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{
\vspace*{-.4in}
%{\normalsize 
%Appeared in ``Proceedings of the 28th Hawaii International 
%Conference on System Sciences January, 1995'} \\
%\vspace*{.25in}
\Large\bf 
DOGMA: Distributed Object Group Metacomputing Architecture
$^{\small \dag}$
}

\widowpenalty=10000
\clubpenalty=10000


\author{
Glenn Judd, Mark Clement, Quinn Snell\\
Computer Science Department \\
Brigham Young University \\
Provo, Utah 84602-6576 \\
(801) 378-7608 \\
\{glenn, clement, snell\}@cs.byu.edu
}

\bibliographystyle{abbrv}

\maketitle

\thispagestyle{empty}

\auffil{
$^{\tiny \dag}$ This research was
supported by Sprint. 
}

\vspace*{-.2in}
\subsection*{\centering Abstract}
%IEEE allows italicized abstract
{\em


The performance of Java just-in-time compilers currently approaches 
native C++, making Java a 
serious contender for supercomputing application development.
This paper presents DOGMA--a new Java based system which
enables parallel computing on heterogeneous computers.  
DOGMA supports parallel programming in both a traditional
message passing form
and a novel object-oriented approach.
DOGMA provides support for dedicated clusters as well as 
idle workstations through the use of a web based browse-in
feature or the DOGMA screen saver.
This research provides a unified environment for 
developing high performance supercomputing applications on 
heterogeneous systems.
  

\rm
{
%\baselineskip 24pt


\section{Introduction}

Researchers have long sought to integrate the
computational power of heterogeneous clusters of computers in order to achieve
fault tolerance, utilization of idle computers and resource sharing. 
Unfortunately,
the complexity of heterogeneous computing has made these goals elusive.  
The Java programming language has eliminated some of the problems by making
high performance applications portable across nearly all architectures.
However, the Java environment does not directly support supercomputing.
The Distributed Object Group Metacomputing Architecture (DOGMA) provides
system management, data distribution and messaging facilities for Java
based supercomputing applications.

Harnessing the computational power of clusters of heterogeneous computers
requires both a hardware system capable of fast, reliable 
communication as well as a software system capable of allowing applications to
make use of large numbers of computers.
Recently the creation of distributed/parallel 
programs has been eased somewhat
by developments such as MPI\cite{mpi}, PVM\cite{geist1994tr}, and
CORBA\cite{corba}. These standards
have allowed parallel/distributed programs to be written that will function on several
different platforms in both tightly and loosely coupled environments.

Nevertheless, despite the advances in source code level compatibility,
traditional distributed programming environments require machine specific 
compilation and operating system customization.
This makes the inclusion
of a new architecture into an existing distributed computing platform
non-trivial.  With the advent of Java, code distribution is 
now relatively simple.
Several significant obstacles still remain for heterogeneous parallel computing.
The rest of this paper describes the DOGMA system and how it addresses 
these problems.

\subsection{Distributed Computing with Java}

Java's platform independent/internet-centric nature make it natural for use
in distributed computing, and
this has lead several groups to begin research on distributed/parallel programming
with Java. The following section differentiates DOGMA from these existing
systems.

The JavaPVM\cite{javapvm}, JPVM\cite{jpvm} and  IceT\cite{icet} message 
passing schemes do not provide automatic data distribution nor do they
provide
the object group method invocation found in DOGMA.
DOGMA supports traditional message passing via an MPI implementation,
but features object-group
oriented programming as its preferred paradigm. 
Linda derivatives such as Jada\cite{jada}, JavaSpaces\cite{javaspaces} and 
Javelin\cite{javelin} have not been able to achieve comparable performance.
Java/DSM\cite{javadsm}, Spar\cite{spar}, JavaParty\cite{javaparty}
and Charlotte\cite{charlotte} provide a shared address space, while
DOGMA seeks to make
the developer aware of the distributed nature of the program
in order to increase performance.  


JAVADC\cite{javadc}, Lilith\cite{lilith}, 
WebFlow\cite{webflow}, and WWVM\cite{wwvm} provide
frameworks for controlling 
natively coded
parallel programming systems.  They are functionally orthogonal to DOGMA
which seeks to provide a Java-based system that is completely 
platform independent.
The Parallel Java with Global Object
Space\cite{javagos} sytem is object-group based as is DOGMA, but
it does not provide for volunteer computing or
dynamic class loading.
Systems such as 
JET\cite{jet}, 
SuperWeb\cite{superweb}/Javelin\cite{javelin} and Charlotte are similar to
DOGMA in that they incorporate Web browser functionality;  however, DOGMA
also adds cluster based computing in order to utilize groups of nodes
for which a user has login privilege.  Additionally, DOGMA adds
screen saver based browsing.

DOGMA seeks to do more than simply provide a Java version of a message
passing standard. Rather, DOGMA has two main goals: 
\begin{itemize}
\item The creation of a distributed computing platform which can 
harness the power of clusters of computers as well as anonymous idle computers
in both Internet and intranet settings.
\item Providing a mechanism for easily writing programs capable of 
harnessing the power of such a system.
\end{itemize}

\section{DOGMA}

DOGMA is built using Java Remote Method Invocation (RMI) as a foundation.
RMI allows Java objects to interact with Java objects residing in
separate Java Virtual Machines (JVM's); however, the programmer is required
to handle issues such
as object location at a low level.

DOGMA's runtime system is known as the Distributed Java Machine (DJM) layer.  
It allows several JVM's to act
as one distributed machine while freeing the programmer from needing to
worry about the location of objects, the names of nodes, the location of
nodes, etc. This layer also allows application binary code to be served via
an arbitrary number of http servers, 
and eliminates the need for applications to 
be installed on local file systems.

The programming API is known as the Distributed Object Group (DOG) layer.  It
allows method invocation, data partitioning, communication,
etc. on large groups of objects without the programmer needing to worry
about issues such as the exact number of nodes used.

Also, DOGMA includes a partial MPI implementation written entirely in Java. 
Although it will probably usually be used in conjunction with Distributed 
Object Groups, its design is orthogonal to them and only requires 
the DJM layer in order to function. 


Currently, DJM is a centralized system managed by a central entity, DJMManager,
which coordinates the actions of all system entities. Each node (JVM) in
the system has a NodeManager which coordinates the node's interaction with
DJMManager.
As in Mentat\cite{mentat}, nodes are organized into families and clusters. 
Families of nodes are nodes that have a similar configuration and architecture.
Clusters of nodes are nodes that are located near each other physically.
Unlike Mentat, there is not a single static system configuration database.
Rather, the system is configured dynamically.

%\begin{figure}[tbh]
%%\centering
%\setlength{\epsfysize}{0.35\textheight}
%\centerline{\rotate[r]{\epsfbox{SampleConfig.eps}}}
%\caption{}
%\label{SampleConfig}
%\end{figure}

\begin{figure}[tbh]
%\centering
\setlength{\epsfysize}{0.30\textheight}
\centerline{\epsfbox{overview.eps}}
\caption{Sample System Configuration}
\label{BigOverview}
\end{figure}


System topology is configured dynamically in several ways.
1) Nodes may be made active or inactive at any time (by an administrator)
on an individual node basis, or by cluster.
2) The system topology database may be updated at runtime. 
%(see Figure~\ref{SampleConfig}). 
This is done by grouping families and 
clusters into groups known as "configurations"
each managed by a ConfigurationManager. When a ConfigurationManager
is made active, it contacts DJMManager and informs it of all families,
clusters, and nodes that are in the ConfigurationManager's configuration.
When a ConfigurationManager is shutdown it removes all knowledge of its
configuration from DJMManager.
In this way, ConfigManagers provide modularity. They free the DJMManager
from needing to know the configuration of the system when it is started.
Also, by handling all architecture specific issues,
ConfigManagers free DJMManager 
from any system specific functions. In this way arbitrary clusters of
nodes can be added to and removed from the system dynamically.
3) Web browsers can effectively become nodes in the system.
This allows users to run applications by simply browsing
into the system and running the desired application, or to donate computational
power by browsing into the system simply to help.
4) The DOGMA screen saver can be used to add nodes to the system
when they become idle.


Distributed object groups allow programs to work with large groups of 
objects easily and efficiently.
A master instantiates a DOG made up of a number of objects which
is distributed across the DJM.
A DOG is organized according to a data configuration scheme. The scheme
defines how data will be partitioned, group elements will communicate, and
what type of coordinates are used to define group element position.
Through asynchronous group method invocation, the master can invoke
methods on the entire group.  The master will only
block when a return value is requested and unavailable.

Arguments to methods can be partitioned
automatically by the system according to a group's data configuration scheme.
The speed and load of nodes on which group elements
reside can also be considered.  DOGMA currently supports 
partitioning of object data along a single dimension.
Data returned by a group method invocation can
also be reassembled automatically by the system. Alternatively, an
array of results can be returned.

Distributed Object Groups free the programmer from the traditional
tasks of computing partition sizes, partition overlaps, element
position, etc., and add the power of dynamic partitioning according
to system topology and load.

DOGMA also supports group element peer communication. 
Standard functions include point
to point, multi-point, synchronous, and asynchronous send and 
receive methods.

\section{Results}

DOGMA has proven to be an
effective, easy-to-use parallel programming environment.  
Performance has been hindered somewhat by just-in-time compilers which
either functioned poorly or crashed (i.e. had to be disabled).  These
problems should disappear as Java matures.

As Java  
implementations capable of supporting DOGMA have become available
(JDK 1.1.3 and greater), DOGMA has easily run on them.
We have successfully run applications on large groups of 
heterogeneous nodes 
with no source code
modification. 
The applications include: 
matrix multiplication, image FFT, image histogram equalization, and
ray tracing to name a few.  The number of nodes included in the system
has ranged from 1 to 40 (including several dual-processor machines) with the 
nodes residing in 4 different domains.  The system has also incorporated
both browser-based nodes, which were able to execute applications and
donate CPU power, as well as nodes running the DOGMA screen saver
to donate idle CPU time to DOGMA.  In addition, DOGMA has proven capable of
seamlessly harnessing the power of multiprocessor machines by assigning
multiple objects to them, and allowing local objects to communicate
via direct method invocation.

DOGMA applications typically make use of dynamic data partitioning
in order to ease programming and increase power.  The increased
performance from dynamic data partitioning is application dependent, but
as an example of the benefits of dynamic data partitioning consider
speedups obtained executing a matrix multiplication of 2 400x400 matrices:

\begin{itemize}
\item{Effect with different speed machines}-
Configuration: 2 Pentium Pros 200Mhz, 1 Pentium 133 Mhz, 1 Pentium 90Mhz.
Result: 33 percent speedup when dynamic data partitioning is used.

\item{Effect with different loads}-
Configuration: cluster of HP 9000/778's with one node heavily loaded, one
node lightly loaded, and 2 not loaded. 
Result: 48 percent speedup when dynamic data partitioning is used.
\end{itemize}

\subsection{Application Results}

First some cautions: Java is relatively new. Performance is increasing drastically. 
Consequently,
the actual performance obtained is frequently more dependent on the 
implementation
of Java than the power of the machine on which it runs.

The result of this is that while in many instances the actual time required
for algorithm completion is quite instructive, it can also be quite misleading.
With this in mind some of the results obtained with DOGMA are listed
below:

\begin{figure}[htb]
\centerline{\psfig{file=matrix_1.eps,width=3.3in}}
\caption{Matrix Multiplication Performance DOGMA vs. Native MPI}
\label{speedup}
\end{figure}

Figure~\ref{speedup} shows time required to complete a matrix multiplication
of two square matrices on a cluster of Pentium II 266Mhz workstations runnning
Windows NT and connected by Gigabit Ethernet.  In all cases, the performance
of DOGMA is never less than 75\% that of native MPI, and is within  
95\% for smaller numbers of nodes.  Also
note that both DOGMA and MPI exhibit superlinear speedup as the application
working
set fits into cache.

Figure~\ref{h_speedup} shows performance obtained executing a ray tracing
application on a hetergeneous set of nodes.  Performance predictions for 
multiple nodes are obtained simply by adding the speed in lines per second of
the individual nodes.  Note that the predicted times match the actual
times observed almost exactly.  This indicates that the speedup
obtained from using these 10 nodes is almost perfectly linear.

\begin{figure}[htb]
\centerline{\psfig{file=speedup.eps,width=3.5in}}
\caption{Ray Tracer Performance on Heterogeneous Nodes}
\label{h_speedup}
\end{figure}

\section{Conclusions}
DOGMA is a new but promising system for practical distributed programming
with Java. DOGMA provides both an effective object-group-oriented
programming capability and powerful system configuration
abilities such as dynamic code loading, cluster management, web browser
participation, and screen saver donation of idle CPU cycles.

Preliminary results obtained with DOGMA show that while Java is still an immature language, it is nonetheless a very promising language for 
distributed/parallel computing on a large scale. Improvements to the 
Java virtual machine to allow class reloading, better memory management,
and native threading will improve the performance and usability of DOGMA.

Though there is much future research to be done, DOGMA has proven to be 
very capable of enabling clusters of computers and
individual anonymous computers to act as a single powerful networked computing
entity.

\section{Future Work}
Parallel programming with Java is still in its infancy. Tools such
as DOGMA open many avenues for research, and below are listed a few that
will be focused on in the near term. 

There is much research to be done in the area of object placement for
an application. DOGMA currently places objects on nodes which appear to
have the most computational power (where power = speed*(1-load)) available.
However, there are many factors such as network bandwidth, network latency,
and an application's data configuration scheme that are not captured by
this model. This work is closely 
related to designing an efficient object placement algorithm. 
Future work will investigate more sophisticated dynamic data partitioning
algorithms.

Object migration is currently being incorporated to allow for 
increased performance,
and useful inclusion of transitory nodes in a large number of
applications. Other issues such as security and
fault tolerance enhancements are also being worked on.

See the DOGMA homepage at http://ccc.cs.byu.edu/DOGMA/ for more current 
information.
}

\small
\bibliography{java}
\end{document}
