
\section{Introduction}

{\em Grand Challenge} applications require multiple computers, or even
multiple supercomputers, to achieve acceptable performance.  Some
researchers are taking advantage of heterogeneous computing
environments to achieve levels of performance that to date have not been
possible.  A climate simulation model described in ~\cite{mechoso}
uses both SIMD and MIMD style parallel computers to achieve superlinear
speedup.  As applications that require multiple supercomputers
and clusters of high performance workstations become more common, the
need for systems to ease their development and automate their execution
becomes clear.  The Virtual Computing Environment {\em (VCE)} is a
research effort which is investigating new techniques for developing and
managing the execution of large scale applications which exploit high 
performance
heterogeneous computing resources dispersed across a wide area network.

Previous attempts to harness the capacity of distributed resources and
make them available to large applications are not suitable for managing
the current generation of Grand Challenge applications.
Utopia~\cite{zhou} allows a widely dispersed group of heterogeneous
workstations to be used for remote task execution. However, Utopia is
geared towards managing a network of privately owned Unix
workstations.  Tasks are placed on lightly loaded machines and remain
there until they have completed. Users whose machines are used to host
remote tasks may have to execute their own tasks remotely on other
machines to realize good performance.  Condor~\cite{litzkow} also uses
idle workstations to host long running applications and provides
preemptive process migration. The process migration facilities in
Condor require a high degree of homogeneity among the participants.
Durra~\cite{barbacci} provides many facilities which are useful for
constructing large distributed applications.  Durra is also oriented
to a workstation environment and places more emphasis on fault
tolerance than high performance computing.

New scheduling protocols must be devised to manage task execution
in distributed supercomputing environments. 
Recent research has
shown that for some tasks a cluster of DEC Alphas will provide comparable
performance to an IBM SP2~\cite{hariri}. If both these architectures are
available at run time, the least loaded machine is preferable.
Load measurement on
supercomputers is more complex than for workstations. Workstations
contain a single ready queue which can be sampled to gauge the system
activity level~\cite{kunz}. In a supercomputer the load of each computing
element must be sampled in order to compute an aggregate load. Comparing
the loads of geographically dispersed supercomputers is complicated by
communication delays and may be costly. 
Further, large tasks may have
very long running times, so systems which emphasize precise load
measurements in order to optimize initial task placement have no way
to react to load changes during task execution. 
Conversely, the cost of migrating
running tasks between supercomputers might be prohibitively
expensive. 
Because load conditions
are hard to measure and prone to fluctuate, and process migration
between high performance machines is problematic,
redundant scheduling of performance
critical tasks represents an interesting approach to guaranteeing
good performance
over a heterogeneous distributed computing environment.
Several approaches to task scheduling are being investigated in
the Virtual Computing Environment. Two that will be discussed in
this paper are redundant task scheduling and selective initial
task placement. 

The Virtual Computing Environment has two principle components.
The first is an application description framework which is used to describe
the attributes of computing tasks and how these tasks can be arranged
to construct large applications. The second is an execution 
environment which interprets application descriptions and executes them
on a set of computers selected at runtime from machines available 
across a wide area network. 

A prototype VCE has been constructed. It is being used to develop and run
applications which exploit a variety of high performance architectures
including an IBM SP2, and DEC Alpha, Sun and Silicon
Graphics workstations connected to FDDI and ATM networks
to investigate a variety of distributed systems issues
including development methodologies and scheduling protocols.

The remainder of the paper is organized as follows. Section 2 gives
an overview of the VCE execution environment. Section 3 discusses
how applications are constructed from tasks using the application
description framework. Section 4 details 
the scheduling and execution techniques
used in the VCE. Section 5 describes the hardware configuration of 
a VCE prototype system, the applications running on it, and the performance
results observed.
Future work is proposed in Section 6. 

\section{The VCE Execution Environment}

\begin{figure}
\centerline{\psfig{figure=busypic.eps,height=8in,width=7in}}
\caption{The VCE Execution Environment}
\label{fig:busy}
\end{figure}

A VCE execution environment is a group of heterogeneous machines
connected by a high performance network~\cite{rousselle} 
(Figure~\ref{fig:busy}). A portion of the computing
resources on each machine is allotted to execution of VCE applications.
Each machine participating in the VCE hosts a VCE daemon to perform
scheduling and dispatching of VCE work. A dispatchable unit in the
VCE is a {\em task}. Each task corresponds to an executable file
for one or more of the participating machines. The attributes of
each task are defined in a {\em task description}. An application consists
of one or more tasks. Each task is a step in the computation. Applications
are described by files in an {\em application description} library.

To run an application, a user starts an {\em execution process} on their
workstation and gives the name of an application in the application
description library. The execution process reads the application description
and any task descriptions it refers to. It then communicates with the
VCE daemons on the machines that could be used to host application tasks
to determine which machines are available. The execution process 
collaborates with the VCE daemons to arrange execution of tasks as needed.

Some machines are organized into {\em groups} to reduce
communication overhead and improve scalability. Specifically, whenever two
or more machines are architecturally and binary compatible,
they are organized as a group. One machine in each group acts as a group
leader and communicates with the VCE execution process to manage and
control the execution of an application. The group structure of the VCE allows
an execution process to exchange scheduling information with group leaders
only, rather than interfacing with every participating supercomputer and
workstation. Machines within groups exchange load information with their
group leaders so that when an execution process needs a machine to host an
instance of a task, the group leader supplies the address of a lightly
loaded machine. The relationship between VCE daemons and the execution
process is illustrated in Figure~\ref{fig:bids}. 

\begin{figure}
\centerline{\psfig{figure=april_bids.eps,height=3.5in,width=3.25in}}
\caption{Organization of the VCE}
\label{fig:bids}
\end{figure}

Dispatching is accomplished when a VCE daemon on a host machine, under
the supervision of an execution process, fetches an executable file
and begins execution.

\section{Application Description Framework}
\label{sec:descript}

An application description language is presented in~\cite{barbacci} which
is used to construct fault tolerant Ada applications on a heterogeneous
workstation network. The VCE application description framework uses a
similar syntax to describe applications constructed for the
heterogeneous VCE environment. 

The VCE application description framework allows a user to specify the
structure of a distributed application and give the VCE enough information
about its characteristics to efficiently dispatch it on available
hardware.

The two central constructs of the application description framework
are {\em tasks} and {\em applications}. {\em Task descriptions} 
are the building blocks
of VCE applications. {\em Application descriptions} completely 
specify how
a set of tasks can be dispatched in a heterogeneous computing
environment to perform useful work. 

\begin{figure}
\centerline{\psfig{figure=tasksyn.eps,height=3in}}
\caption{VCE Task Description Syntax}
\label{fig:tasksyn}
\end{figure}

\begin{figure}
\centerline{\psfig{figure=task.ps,height=3.5in}}
\caption{Task Descriptions of Linear Algebra Operations}
\label{fig:tasks}
\end{figure}

The complete syntax for task descriptions are given in
Figures~\ref{fig:tasksyn}.

Figure~\ref{fig:tasks} shows task descriptions for some common linear
algebra operations. Each task is implemented on three different platforms.
The {\em Nodes} specification gives a default value for how many nodes
of each architecture are to be assigned to the task. The number of nodes
is chosen by the task implementor to produce efficient granularity in
common applications.

\begin{figure}
\centerline{\psfig{figure=app.eps,height=5in}}
\caption{Application Description of a Linear Equation Solver}
\label{fig:appl}
\end{figure}

Figure~\ref{fig:appl} shows how the tasks of Figure~\ref{fig:tasks} can
be used to construct a linear equation solver application.  

The default {\em nodes} 
specification given in the task description can be overridden in the
application description. The application designer may have more information
about the problem size and can tailor the number of nodes to achieve
better granularity. The {\em input} and {\em output} keywords specify the
data objects produced and consumed by each task. The {\em command} keyword
is used to pass command line arguments to the task. The {\em hints} keyword
is used to alert the execution process to attributes of the task which
should be considered for scheduling purposes.

An application description consists of a number of {\em subtask} 
specifications. Each subtask refers to a task description which
implements the desired function.
The {\em nodes, command, input, output} and {\em hints} keywords in the subtask
specification override the values given in the task description. The
task implementor can place common default values in the task description
which can be altered as needed in particular application descriptions.

The {\bf synchronization} directive of an application 
subtask provides a mechanism for
describing a variety of control sequences. For instance, tasks can be
initiated after other specified 
tasks have begun or after other tasks have completed.
Specifying that one task is to start only after others has started allows
for server tasks to be initiated before their clients proceed.

%\begin{figure}
%\centerline{\psfig{figure=min.eps,height=6in}}
%\caption{VCE Application Description Syntax}
%\label{fig:appsyn}
%\end{figure}

The application description framework allows application structure to be
expressed in application and task description files rather than in the
application source code. Intertwining these operations
with the application's computations and I/O can lead to excessive code
complexity and hamper code reusability.

\section{Scheduling Considerations}
\label{sec:sched}

Scheduling methodologies for the the VCE
are an area of active research. Two protocols being investigated are:
1) {\em Redundant Execution} where each task is run on several available
computers (up to a certain maximum) and the result produced by the
fastest instance of the task is returned to the user or made available
for subsequent computations; and 
2) {\em Selective Initial Placement} where the load on each machine is
monitored and one instance of each task is placed on the least loaded
machine.

\subsection{Redundant Task Scheduling}
\label{sec:redun}

Two different
approaches to redundancy are used in the VCE:
1) {\em Explicit Redundancy} where the user supplies executable files for the
same task to run on multiple platforms which can be dispatched
simultaneously; and
2) {\em Transparent Redundancy} where one of the executable files supplied
by the user is dispatched
on two or more members of a single group.

Transparent redundancy is used when two or more members of a group are
lightly loaded. Under such conditions transparent redundancy further
improves the fault tolerance and performance of the application and allows
better hardware utilization. Transparent redundancy is also used extensively
in workstation groups where each machine is intended primarily for the
use of a single user (ie. its ``owner''). Such machines are frequently idle or
under utilized for long periods of time~\cite{mutka2}.
A VCE task will only dispatched on privately owned machine if the machine's
average ready queue length is below 1.0. This indicates that the workstation
has some idle capacity.
The tasks are dispatched with the lowest possible priority
so that if the locally originated load of the machine increases, interference
from the VCE task will be negligible. By redundantly executing a single
task on several workstations, the probability that at least one will
deliver good performance is high. 
%Details of the VCE's redundant scheduling
%algorithms are discussed in Section~\ref{sec:scheduling}.

Redundant task scheduling has several benefits. Fault tolerance is achieved
because the failure of a single machine does not lead to failure of the
entire application. In fact, redundancy eliminates the need for
checkpointing and error recovery schemes which can complicate task
implementation and reduce performance. Redundancy also improves performance
by allowing the application to proceed at the rate of the fastest machine
participating.  These benefits are realized without the overhead of precise
load measurement routines or process migration techniques.

\subsection{Selective Initial Task Placement}

\begin{figure}
\centerline{\psfig{figure=nuisance.eps,height=3in,width=3in}}
\caption{VCE Load Thresholds}
\label{fig:nuisance}
\end{figure}

\input{SCalgo}

A coarse grain load measurement algorithm has been implemented in the
VCE. For supercomputers, the run queue length of each computing
node is sampled periodically and the average run queue length is
computed. Experiments are performed on each supercomputer
to determine how high this number can get before users begin to
notice degradations in performance. This load level is considered the
machine's {\em nuisance threshold}. When the average run queue length
is below one, indicating idle computing capacity in the machine, the
machine is considered to be under the {\em adequate utilization threshold}.
At any instant, a machine's load relative to these thresholds can be
used to determine if the load is {\em low, medium} or {\em high}
(Figure~\ref{fig:nuisance}).

Experience in the VCE has shown that taking a single instantaneous
reading of the load measure when a placement decision is to be made
is problematic. Task initiation is delayed while the nodes of all
candidate machines are polled, and transient spikes and dips in
load condition can lead to poor placement decisions. To eleviate both
these problems, one process on each supercomputer or workstation
cluster periodically polls the nodes and computes a {smoothed load
average}. This value can be queried by an execution process when
a task placement decision needs to be made. 
 
Figure~\ref{fig:measure} shows the algorithm used to calculate a
machine's smoothed load measurement. An instantaneous load measure is computed
periodically. If this instantaneous load measure is below or above the
smoothed load measure for several consecutive intervals, the smoothed
load measure is changed accordingly. The sampling interval, and the
constants $N$ and $M$, which determine how quickly the smoothed
load measure reacts to changing load conditions, can be customized for
each machine. Currently, the Unix {\em rstat()} function is used to
gather load statistics. Because the {\em rstat()} values are updated by
Unix every five seconds, six second sampling intervals are used. The
constants $N$ and $M$ are set to 2 and 10, respectively. This causes the
smoothed load measure to be increased quickly when load conditions
are raised but to decrease slowly as the load falls. This bias is
used to maximize the probability that machines reporting low load
conditions are actually underutilized.

\begin{figure}
\centerline{\psfig{figure=example.eps,height=5in,width=3in}}
\caption{Load Measurement Algorithm Example}
\label{fig:example}
\end{figure}

An example of how the algorithm behaves is shown in Figure~\ref{fig:example}.
At time 0 both the instantaneous and smoothed load measures indicate
the load on the machine is medium. The changes in the instantaneous
load measure that occur between time 12 and time 30 are considered noise
and are not reflected in the smoothed load measure. The ten consecutive
low instantaneous readings beginning at time 36 cause the smoothed load
measure to become high at time 90. The two consecutive instantaneous
readings of medium at time 120 and 126 cause the smoothed load measure
to return to medium. 

When a task is eligible to be dispatched, the execution process obtains
the current smoothed load measure of each candidate system. The task
is dispatched on the least loaded platform. The order in which machines are
listed in the task description is used to indicate the task implementors
preference of execution platforms. If the lowest load measure is reported by
two or more machines (that is, there is a tie), the precedence expressed
in the task description is observed. 

\section{Validation}
\label{ssec:expenv}

\begin{figure}[htb]
\centerline{\psfig{figure=Network.b.w.eps,width=5.5in}}
\caption{Computing Environment at NPAC}
\label{fig:npac_env}
\end{figure}

Several supercomputers and high performance workstation clusters at
the Northeast Parallel Architectures Center have been included in
a VCE prototype system. 
The NPAC environment consists of
a wide set of 
{\em state-of-the-art } multi-computer systems  
(see Figure~\ref{fig:npac_env}). 
The platforms used are briefly described below:

\paragraph{IBM SP-2:}
The SP-2 consists of a cluster of 16 RISC/6000 370 nodes interconnected 
by a crossbar switch (Allnode). Each node 
runs at a clock rate of 62.5 MHz. 
%The results presented in this section is performed on the Allnode switch.

\paragraph{ALPHA/FDDI:} The ALPHA/FDDI configurations consists of
8 DEC ALPHA workstations interconnected by a high performance (100 Mbps)
backbone composed of dedicated, switched FDDI segments. 
The ALPHA nodes have a clock rate of 150 MHz.

\paragraph{ATM LAN:} This configuration consists of 
2 SUN  SPARCstation IPXs  and 3 SGI workstation communicating over an ATM Local Area Network using ATM FORE  ASX-100 switch.
SUN IPX nodes operate on an approximately 40 MHz clock.
Host computers are connected to the ATM switch
through Fore's 200 series adaptors. Each adaptor has a
dedicated Intel i960 processor (running at 25 MHz) to
support
segmentation and reassemble functions and to manage data
transfer between the adaptor and the host computer. The
200 series adaptors  also have special hardware for AAL CRC and
special-purpose DMA hardware.

\subsection{Applications}
\label{sec:apps}

Three distributed applications have been implemented with the VCE
prototype and are being used to test the runtime support. 

\subsubsection{Linear Equation Solver}

A linear equation solver constructed from a set of general purpose
linear algebra tasks (shown in Figure~\ref{fig:appl}) 
was discussed in Section~\ref{sec:descript}.

\subsubsection{Multi-target Tracking System}

The Multi-target tracking system demonstrates the multi target tracking capabilities that
is
required by a Battle Management Command Control and Communication System~\cite{Tracker}. 
The multi target tracker,
shown in Figure~\ref{fig:fig1}, 
is designed to provide an estimation of launch
vehicle parameters  for individual targets/missiles in multi-target
scenarios. 
The tracker receives input 
in terms of launch sites for missiles or targets. 
The 
launch sites are specified in terms of latitudes and longitudes.  
This information 
is fed to two focal plane
tracking (FPT) modules (2 dimensional tracking) at 5 second intervals. The 
focal plane tracking modules process this data using kinematic filtering 
algorithms and track
pruning and prediction algorithms. The output of this module is an initial
prediction of trajectories of launched missiles. This data is then fed to a 
three dimensional tracking system which uses the data from
the two focal plane tracking modules to prune duplicate tracks (if any), 
extend existing tracks,
prune bad tracks and initiate new tracks. The output of the system is a list 
of target trajectories. 

\begin{figure}
\centerline{\psfig{figure=mtt_scene.ps,height=2in,width=3.1in}}
\caption{Multi-Target Tracker System}
\label{fig:fig1}
\end{figure}

\subsubsection{JPEG Compression/Decompression}

JPEG (Joint Photographic Experts Group) is an emerging
standard for image compression. 
%This is a standard image compression method which enables interoperability of equipments
JPEG standard aims to be
generic and can  support a wide variety of applications for
continuous-tone images. 
%JPEG standard includes two basic
%compression methods, each with various modes of operation.
%A DCT (Discrete Cosine Transform) based method is
%specified for {\em lossy} compression, and a predictive method
%for {\em lossless} compression. JPEG features a simple lossy
%technique known as the {\em Baseline} method,  subset of the
%other DCT-based modes of operation. 
%In multi-media applications like video-on-demand,
%the speed at which compression and decompression are performed is
%very critical. Hence, sequential compression algorithms may
%not be suitable for such real-time applications. 
%Efficient parallel compression/decompression algorithms are needed for
%these types of applications.
%We have implemented a parallel JPEG image compression/decompression
%method in a distributed computing environment. 
%\subsubsection{Implementation Description}
%This implementation of JPEG compression/decompression uses
%DCT-based {\em lossy} compression method. The user can trade off
%output image quality against compressed file size by
%adjusting a compression parameter. 
%Since JPEG sequential algorithm performs the image compression
%line by line where compression of each line is independent
%of any other line, we could take advantage of the inherent data
%parallelism in JPEG compression/decompression algorithm.  
We have used data parallel programming  model to implement a
distributed JPEG algorithm  on a
cluster of workstations. In this implementation half of the computers participate in compression of an image file while the
second half reconstruct the compressed image.
The image to be  compressed is divided into N/2 equal parts
(where N denotes the  number of processors)
by the master process and then shipped to one half of the processors.
Each processor
performs the sequential JPEG compression algorithm on its portion of
the image. 
After compression the processors  send the compressed
image to another set of N/2 processors which perform the
decompression. Once decompression is done, the results are sent back
to the master process which combines them into one image. 
Consequently, this algorithm 
involves five stages {\em viz.} distribution of uncompressed image
, compression of the image,
transmission of compressed image,
decompression of the image, and finally
combining the decompressed images. 

\subsection{Performance}

Of the three VCE applications described in in Section~\ref{sec:apps}
the linear equation solver is most representitive of the kind of
application that will benefit from development and excution in
the VCE. It is constructed from tasks which could be reused in
other applications and for large data sets it has a long running time.
So the developer benefits from the application description framework and
the user benefits from the automatic runtime 
scheduling and dispatching capabilities.

A series of performance tests using the linear equation solver application
were performed to determine under what
conditions running an application in the VCE with the scheduling
protocols described in Section~\ref{sec:sched} would be better than
running it in a single computer. The IBM SP2 and the DEC ALPHA
workstation cluster have similar performance characteristics~\cite{hariri},
so often a user who has an application that could run on either platform
would simply choose one at random. Observations in~\cite{hariri} suggest
that even a moderate difference in load conditions at runtime can
effect performance enough to impose a considerable penalty for choosing
the wrong machine. Performance experiments done with the VCE support
these findings and show that both the scheduling protocols described
in Section~\ref{sec:sched} will reduce turnaround times in many
situations. 

In order to obtain controlled testing conditions, testing was performed
on the DEC ALPHA cluster and the IBM SP2 when transient load conditions
were low. A load generating utility was used to slightly elevate the
load on one or the other as the tests were performed. The load
generator allows load conditions to be varied between {\em low} and 
{\em moderate}. It places two dummy processes on each node in the configuration
for a randomly determined period to simulate an interval of high activity. 
These {\em busy} periods are alternated with randomly determined {\em idle}
periods where no artificial load is placed on the machine. When {\em low}
load is specified, the busy periods vary from four to eight minutes while
the idle periods are between 20 and 30 minutes. To simulate {\em moderate}
load, idle periods are between four and eight minutes and busy periods are
from 20 to 30 minutes.

The results of performance tests run using the linear equation solver
application to solve a system of 1024 equations
are shown in Table~\ref{table:solver}. The table shows the degradation
which results when just two other processes per node are competing
for computing resources. 
Neither
redundant nor selective scheduling will have a significant impact on
performance when the loads on all the candidate machines are roughly
equivalent. That is, if all machines are heavily loaded, or all machines
are lightly loaded, there is little a scheduling system can do to
improve performance.
However, when some candidate machines are less active than others, both
the scheduling approaches studied tend to prevent the performance loss that
could be encountered with a random placement.


\begin{table}
\centering
\caption{Performance of the Linear Equation Solver Application}
\label{table:solver}
\begin{tabular}{||l|l|c||} \hline \hline
&&{Execution time } \\
&{\hspace{1cm} Load}&{in seconds}\\\hline
SP2 & Moderate & 1153  \\\cline{2-3}
 & Low & 849  \\\hline
ALPHA & Moderate & 1440  \\\cline{2-3}
 & Low & 732 \\\hline
& SP2-Moderate &   \\
Reduntant & ALPHA-Low & 741  \\\cline{2-3}
Scheduling&SP2-Low &\\
& ALPHA-Moderate & 868 \\\hline
& SP2-Moderate &  \\
Selective & ALPHA-Low & 744 \\\cline{2-3}
Scheduling&SP2-Low &\\
& ALPHA-Moderate & 886 \\\hline
\hline\hline
\end{tabular}
\end{table}

Redundant scheduling yields slightly better performance than selective
scheduling. If there is a significant load change after a task is placed
with selective scheduling performance will degrade. Redundant scheduling
insures that the best possible performance will be obtained because all
candidate machines run the tasks and the result produced by the fastest
machine is returned to the user or made available for subsequent
computations. Of course, redundant scheduling incurs higher costs for the
application because the computations performed by some machines are discarded.
These costs are somewhat offset by eliminating the overhead required for 
gathering load measurements. 

Both of the scheduling protocols insulate the user from the effects of
poor random placements without imposing the considerable overheads associated
with process migration or checkpointing techniques.

In production Virtual Computing Environments it is expected that
the choice between redundant and selective task scheduling would be  
based on the nature and frequency
of VCE jobs to be executed. If VCE applications are submitted only
occasionally, or tend to be of short duration then the use of redundant
scheduling would be preferred. If many large VCE jobs are to be executed
then selective scheduling would provide lower costs and preserve improved
performance.

\section{Future Work}

The VCE will provide a
testbed for investigating many issues relating to the efficient use
of heterogeneous distributed supercomputing environments. Facilities
to allow several geographically remote supercomputers connected
to an ATM wide area network to participate
in the VCE are already in place. 
Extensions to the scheduling and
dispatching capabilites of the VCE execution environment to exploit
these machines are being implemented.

%Unique opportunities for experimenting with scheduling protocols are
%provided by the VCE. Further experiments with a wide variety of
%scheduling approaches will be performed. Among these approaches

Further research on scheduling protocols is underway. Methods for
effectively determining when lightly loaded remote machines should be
used rather than heavily loaded local ones are being developed. Issues
of load measurement and redundant scheduling across a wide area
network are being explored.
 
Design of an intertask communication system which will facilitate
communication among redundantly scheduled components of an application
has begun. Current applications use the P4 system~\cite{p4} for
ommunication. A more robust system, which will allow communication
requirements to be specified in task and application descriptions, will
ease application design and implementation. 

Other aspects of the application description framework will also undergo 
further development. The syntax will be expanded to permit conditional and
iterative task execution. A graphical user interface which will insulate
the user from the details of the application description syntax will
be developed.




