\section{Introduction}

As the performance of local area networks grows, it is increasingly 
tempting to use a cluster of workstations as a parallel computer.  
At the same time, presentation layer APIs such as PVM~\cite{PVM} and
MPI~\cite{MP-STANDARD}, parallel languages such as HPF~\cite{HPF}, and
support utilities are being standardized, greatly enhancing
the portability of parallel programs to workstation clusters.  

Many high speed LANs typically provide at least the promise of quality
of service guarantees to applications.  Parallel programs may be able
to benefit from such guarantees.  In order guarantee a connection and
achieve high utilization, the network must be supplied with
characterization of the traffic the connection will carry.  In
addition to a traffic characterization, the application must also
specify the guarantee it wants for the connection.  Much of the work
in this area has concentrated on media streams.  This paper attempts
to characterize the traffic of parallel programs and provide some
insight as to the kind of guarantees a parallel program might want.

We measured the network behavior of seven message-passing parallel
programs on an Ethernet.  Five of these programs are kernels which
exhibit global communication patterns common to SPMD programs. The
remaining two are an air quality modeling application and a
distributed fault diagnosis (DSD) system.  Except for this last
program, all the programs are written in Fx~\cite{fx-pdt}, a variant
of High Performance Fortran~\cite{HPF}.  DSD was written in gnu C++.

The outgrowth of these measurements is the observation that both the
traffic of SPMD parallel programs, and the guarantees they require are
fundamentally different from those of media streams.  Specifically,
parallel programs exhibit
\begin{enumerate}
\item Global, collective communication patterns,
\item Correlated, even in-phase traffic along many connections, and
\item Periodic burstiness, with constant burst sizes, but periodicity
      which is dependent on bandwidth.
\end{enumerate}
The goal of a SPMD parallel program is to minimize its burst interval,
which depends on the bandwidth it is allocated, its communication
pattern, and the number of processors it runs on.  We suggest a three
parameter traffic characterization which allows the network to
modulate the number of processors the program runs on to achieve the
lowest possible burst interval given the current network state.

\section{Motivation}

Local area computer networks are starting to be used as communication
systems for parallel computing.  As the link and aggregate bandwidths
of LANs approach those of commercial parallel supercomputers, porting
communication intensive parallel programs to run on clusters of
workstations is becoming increasingly attractive.  Overwhelmingly, the
performance of a parallel program on a distributed memory system is
limited by the performance of message passing.  In commercial parallel
supercomputers, the message passing system provides a send/receive
interface to communicate data between nodes over a special purpose
interconnection network.  In a workstation cluster, a send/receive
interface such as PVM~\cite{PVM} is layered on top of the general
purpose protocol stack which communicates via a general purpose
network.  Unlike a parallel computer, a workstation cluster's LAN
is not private, and other traffic may perturb a parallel application.
This makes it tempting to use quality of service guarantees for
parallel applications.

DSD is a distributed program that has been designed to support
parallel programs running on workstation clusters.  It differs from
most parallel applications in that its goal is low overhead - both in
CPU cycles and network bandwidth.  DSD has been running successfully
in various forms on workstations in the Electrical and Computer
Engineering department of Carnegie Mellon
University~\cite{DSD-THESIS,DSM-TR}.

LANs and TCP/IP have been designed using network traffic studies that
emphasize single node interactive and bulk transfer applications.
Since parallel application traffic will grow as LANs become faster, it
is important for LAN and protocol designers to understand the
characteristics of this traffic so that it can be supported with high
performance and minimal impact on other traffic.


% Really need to say something about DSD and distributed apps like
% it here

% I think enough has been said in this section