\documentstyle[lcscover,oneinchmargins,11pt]{article}

\def\start/{{{\sc StarT-ng}}}
\def\startjr/{{{\sc StarT-jr}}}
\def\funi/{{{\sc FUNi}}}
\def\jam/{{{\sc Jam}}}

%\def\funi/{{{\sc {FUNi}{\large 2}}}}

%\input laktex
%\input fixqmsfonts
\input psadobe


%\setlength{\parindent}{2em}
%\setlength{\parskip}{0pt}

%\setlength{\oddsidemargin}{0.45cm}
%\setlength{\evensidemargin}{0.45cm}
%\setlength{\textheight}{25cm}
%\setlength{\textwidth}{15.6cm}
%\setlength{\topmargin}{-1.8cm}
%\setlength{\baselineskip}{12pt}


% define path for floating figure
\def\figurefileprefix{/home/prj/jhoe/publications/1394/figures/}
\def\illustrationfileprefix{/home/prj/jhoe/publications/1394/figures/}

\def\illustration#1{\begin{center}
{\psadobe{\illustrationfileprefix#1.eps}}
\end{center}}

\def\illustrationpercent#1#2{\begin{center}
{\psadobepercent{#2}{\illustrationfileprefix#1.eps}}
\end{center}}

\input epsf
\def\psfigure#1#2{\epsfxsize=#2\epsffile{\figurefileprefix#1.eps}}

\begin{document}

\trnumber{Computation Structures Group Memo 384} 

\researchcredit{This paper describes reserach done at the Laboratory
for Computer Science of the Massachusetts Institute of Technology.
Funding for this work is provided in part by the Advanced Research
Projects Agency of the Department of Defense under the Office of Naval
Research contract N00014-92-J-1310 and Ft Huachuca contract
DABT63-95-C-0150.  Paper to appear in the Proceedings of the 7th
Transputer/Occam International Conference, Tokyo, Japan, November
1996.}

\bibliographystyle{plain}

%\pagestyle{myheadings}
\markright{DRAFT\hspace{2.0in}\today}

\pagestyle{plain}

\title{{\sc StarT-Jr}: A Parallel System from Commodity Technology}
\author{James C. Hoe, Mike Ehrlich}

\maketitle

\begin{abstract}

\startjr/
is an experimental parallel system composed of a network of personal
computers (PCs).  The system leverages the momentum of the
microprocessor and PC industries to achieve excellent single node
performance at a low cost.  For parallel processing, \startjr/ uses
the Flexible User-level Network Interface (\funi/) to provide
low-overhead, user-level interprocessor communication over two IEEE
1394 High Performance Serial Busses.  This efficient message-passing
mechanism enables \startjr/ to exploit fine-grained parallelism for
good parallel performance.\\

\funi/ is based on an embedded processing system on a PCI card.
Custom network hardware assembled from a commercial IEEE 1394 chip set
provides \funi/ with access to the IEEE 1394 network.  In message
passing, \funi/'s embedded processor serves as a network coprocessor
and manages an user-accessible message-passing interface in the host
memory.  User-level applications directly manipulate the interface
location in host memory using cached reads and writes.  Costly
physical I/O accesses to device registers on the PCI bus are avoided.
Currently, \funi/ can efficiently support both fine-grain message
passing and direct memory-to-memory transfers of large data blocks.
\funi/ can also support globally coherent shared memory by capturing
and responding to memory accesses within a designated global address
range.  \funi/ maintains a globally coherent shared memory cache to
minimize global memory access latency.  The necessary coherence
protocol processing and communication is performed by the \funi/
coprocessor.\\

We have demonstrated a two-node prototype of \startjr/ and are
awaiting fabrication of additional interface cards in order to
assemble an eight-node system.  \startjr/ currently supports an active
message-based light-weight communication library for the C programming
language.  Preliminary measurements of the communication library
demonstrated overheads of 1$\sim$4 $\mu$sec for sending or receiving
small ($\leq$ 40 bytes) messages, and an user-to-user latency of 85
$\mu$sec.  Direct memory-to-memory transfers can sustain 3.4 MByte/sec
on an unloaded network. With regard to the shared memory operation,
reading a shared-memory location cached in \funi/ takes approximately
2 $\mu$sec.\\

{\em Keywords:} \startjr/, \funi/, network of workstations, parallel
processing, network interface, user-level, interprocessor
communication

\end{abstract}
\newpage


\section{Introduction}
\label{sec:intro}

\startjr/ is an experimental parallel system based on a network of
workstations (NOW). The goal is to demonstrate that an efficient and
powerful parallel system can be inexpensively constructed from
commodity technology.  Thus, the first-order design directive of the
system is to make maximal use of existing and proven commercial
technology.  Commodity-like Intel Pentium-based personal computers
(PCs), in stock configuration, currently serve as the processing nodes
to offer state-of-the-art single-node performance at a consumer-level
price.  In addition to a standard local area network (LAN) providing
normal network services, two IEEE 1394 High Performance Serial
Busses\cite{IEEE1394} provide the necessary interconnect for scalable
parallel performance.  Stock Linux operating system, a PC freeware
version of Unix, controls the operation of the PCs.

As a corollary from the first directive, the detail design of
\startjr/ must not only use the most suitable technology available,
but it must also adopt to more suitable technologies as they emerge.
Given this objective, the Flexible User-level Network Interface
(\funi/) for \startjr/ is designed for the industry-standard
PCI\cite{PCI95} bus, as opposed to a specific processor-memory bus.
Although some aspects of performance is sacrificed, by maintaining
this generality, \startjr/ systems can also be ``scalable'' through
time by continually adopting more effective PC or workstation
platforms with minimal loss in non-transferable software and hardware
investment.  On the other hand, \funi/ itself also incorporates a
modular design to facilitate upgrade in network performance.  The
on-board embedded processor, which controls the functions of \funi/,
is packaged as an upgradable module.  The lowest-level network adaptor
module is also contained within an interchangeable daughter card to
allow for different interconnection technologies.  

To support a highly scalable parallel system, \funi/ is targeted for
fine-grain parallel processing where interprocessor communication is
short but frequent.  Any inefficiency in communication overhead
(computation cycles lost to communication) will be magnified under
such usage.  This seems to counter \funi/'s PCI-based design since
physical I/O accesses to a PCI device -- typically many tens of cycles
per access -- can add up to a very large overhead during communication.
To overcome this obstacle, \funi/ uses a decoupled interface paradigm
to avoid direct interaction between the host processor and the \funi/
hardware.  \funi/ itself is based on a commercial Intel i960 embedded
processing system with direct read and write accesses to the host
memory.  Thus, \funi/ can act as a network coprocessor to implement a
message-passing interface (e.g.  send and receive message queues) in
the host memory.  User processes only have to manipulate these message
interface locations using normal memory reads and writes.
Figure~\ref{fig:dmabased} illustrates this idea.

\begin{figure}
%\centerline{\psfigure{dmabased}{12.6cm}}
\centerline{\psfigure{dmabased}{11.5cm}}
\caption{
\label{fig:dmabased}A Message Interface based on Software Queues in User's Virtual Memory}
\end{figure}

The \funi/ coprocessor firmware can be reprogrammed to support many
flavors of message passing interfaces and functions.  In general, the
\funi/ interfaces are designed such that communication overhead is
transferred from the host processor to the \funi/ coprocessor.
Currently, \funi/ efficiently supports both fine-grain message passing
($\leq$ 80 bytes of payload per message) and direct memory-to-memory
transfers of large data blocks (up to 2560 bytes per initiation).  To
further reduce the communication overhead, \funi/, with the
general-purpose processing power of i960, can be programmed to
off-load some of the simpler message processing from the host
processor.  For example, memory access requests from a remote node
could be satisfied by \funi/ directly without ever disrupting the host
processor.  Active messages\cite{ECG92} processing can also be
off-loaded from the host processor.

In addition to message passing, \funi/'s hardware can also support
globally coherent shared memory by capturing and responding to memory
accesses within a designated global address range.  After an address
capture, the hardware first tries to satisfy the request by consulting
a globally coherent shared memory cache.  If the request cannot be
satisfied directly, the \funi/ coprocessor is interrupted to perform
the necessary coherence processing and communication to complete the
memory request.  The programmability and processing power of the
\funi/ coprocessor allow for experimentation with memory coherence
protocols.  Unfortunately, in the current implementation, host
processors are unable to cache the shared memory regions, thus
limiting the performance of shared memory applications.

To obtain a meaningful performance estimate, a light-weight
communication library (for the C programming language) based on active
messages has been developed for \startjr/.  The library efficiently
exposes \funi/'s message-passing and DMA features to user-level
applications.  Preliminary measurements of the communication library
demonstrated overheads of 1$\sim$4 $\mu$sec for sending or receiving
small ($\leq$ 40 bytes) messages, and an user-to-user latency of 85
$\mu$sec.  Direct memory-to-memory transfers can sustain 3.4 MByte/sec
on an unloaded network.  The low overhead is attributed to the fact
that the host processor only has to access the host memory for message
passing.  The latency and bandwidth is below the capability of the raw
hardware since the coprocessor firmware is designed to minimize
overhead. By reprogramming the \funi/ firmware for an alternative
interface style, the low overhead can be traded for lower latency and
better bandwidth.  Currently, no software has been developed for
shared memory.  However, based on low-level experiments, a single-word
read of a locally-cached shared-memory location takes approximately 2
$\mu$sec.

In this section, we have given an introductory overview of \startjr/
and \funi/.  The remainder of this paper presents the details of the
\startjr/ system and pays particular attention to the interprocessor
communication mechanism that \funi/ provides.  The next section
describes the current implementation of \startjr/ using stock PCs and
IEEE 1394 interconnections.  Section~\ref{sec:operation} discusses
\funi/, the interprocessor communication mechanism in \startjr/.
Section~\ref{sec:results} presents the results acquired from the
prototype system.  Section~\ref{sec:related} briefly relates \startjr/
to other projects in the area of NOW and network interface design.
This paper concludes with a summary and a brief discussion in
Section~\ref{sec:conclusion}.

\section{A \startjr/ Implementation}

\label{sec:hardware}

The \startjr/ system is not fixed to any one specific implementation.
Following our objective to construct the most efficient parallel
system from the best suited commercial technology, we have left the
design open to adopt new implementation technologies.  In this
section, we outline the implementation of our current IEEE 1394-based
\startjr/.  We first describe the commodity components (i.e.  stock,
commercial portion) of our system and how each is selected.  In the
current \startjr/ implementation, a portion of \funi/ does contain
semi-custom hardware because no adequate substitute existed.  The end
of this section is devoted to the design and implementation of this
semi-custom IEEE 1394 adaptor module.

\subsection{Commodity Components of \startjr/}

The \startjr/ system can be broken into three components: the
processing nodes, the interconnect substrate, and the network
interface.  Each of the components are specified or designed for
trade-offs between cost and performance, together with the added
constraint of flexibility and upgradability.  The goal is to achieve
the widest range of commercial options for implementation.

\subsubsection{Processing nodes}

The current \startjr/ system is composed of eight stock PCs with
120~MHz Pentium processors.  These commodity-like PCs, with 256~KBytes
of cache and 32~MBytes of main memory, is estimated at 172.2 SPECint92
and 108.4 SPECfp92.  Even when fully configured with disk drives and
I/O peripherals, the system costs under US\$2000.  This level of
price-performance ratio, made possible by the market volume of the PC
industry, is precisely what \startjr/ wants to exploit.

\startjr/ currently employs Linux, a PC version of the Unix operating
system.  \startjr/ only requires the addition of a \funi/ device
driver to provide mapping and protection for the interface memory
region in the user's virtual address space.  The standard OS offers
the familiar suite of software development tools (compilers,
debuggers, windowing systems, etc.) to reduce software development
overhead.  Equally importantly, pre-exiting sequential applications
make \startjr/ immediately useful as a cluster of powerful stand-alone
workstations.

With PCI-compliant \funi/ hardware, \startjr/ can adopt any
PCI-equipped platform running a selection of operating systems.  This
option ranges from entry-level PCs to high-end SMP servers, and allows
for a heterogeneous \startjr/ system.  Furthermore, \startjr/ can
automatically track the technology curve by adopting to faster, and
even cheaper, base platforms as they emerge.

\subsubsection{Interconnect Substrate}

The IEEE 1394 High Performance Serial Bus standard \cite{IEEE1394} is
intended for multimedia applications with real-time and bandwidth
requirements.  This high performance technology is available as a
ready-to-integrate chip set at a negligible cost.  Chip sets for 100
and 200~Mbit/sec networks are already available, and 400~Mbit/sec and
1~Gbit/sec are being developed.  IEEE 1394 has already found
applications in consumer electronics such as disk drivers, printers,
VCRs and video cameras.

Currently, two 100 Mbit/sec IEEE 1394 High Performance Serial
Busses constitute the interconnect substrate for its
price-performance ratio and its ease of implementation.  However, the
multimedia lineage of IEEE 1394 presents a problem in the case of
network buffer overflow.  Whereas it is of little concern to discard
overflowing packets in most multimedia applications, parallel
processing systems have traditionally relied on a reliable, loss-less
network.  In Section~\ref{sec:lossless} we will explain how \funi/
maintains the loss-less abstraction on top of the lossy underlying
IEEE 1394 substrate.

A number of interconnect technologies can be incorporated into
\startjr/ with minimal modifications to the remainder of the system.
For example, a network module for the Arctic Switch Fabric (160~MBytes
per link)\cite{Bou94} has been developed concurrently with the IEEE
1394 adaptor module.  The Arctic module will allow us to construct a
larger, higher performing \startjr/ using mostly the same hardware and
software.

\subsubsection{\funi/ Hardware}

Although \funi/ contains semi-custom hardware, it is mostly based on a
commercial embedded system.  The custom hardware development is
limited to the IEEE 1394 adaptor module that plugs into an existing
interface.  The details of this custom module is presented at the end
of this section.  The following paragraphs describe the commercial
embedded system.

\funi/ is based on Cyclone Microsystem's PCI80960 {\em Intelligent
Communication Controller}\cite{Cyc95}.  Packaged as a plug-in PCI
card, PCI80960 is a general-purpose embedded system, complete with a
33 MHz Intel i960CF (a 32-bit superscalar RISC processor) and 2~MBytes
(upgradable to 32~MBytes) of local DRAM.  A bus bridge provides i960
with direct load/store access and a DMA engine to the host memory.
Eight 32-bit mailbox registers, visible to both the host and i960 by
memory-mapped reads and writes, are also available to implement
handshakes and synchronizations.

\begin{figure}
%\centerline{\psfigure{funi2}{13.6cm}}
\centerline{\psfigure{funi2}{11.5cm}}
\caption{{\sc FUNi} PCI Card}
\label{fig:funi2}
\end{figure}

PCI80960 is engineered with an open-standard, Squall I/O adaptor
interface on the i960 local bus. A variety of network adaptors, such
as Ethernet, ATM, etc., are commercially available.  \funi/ employs a
custom IEEE 1394 adaptor module for the Squall interface to provide
i960 with access to the interconnect.  Figure~\ref{fig:funi2}
illustrates the datapath of the \funi/ PCI card.  In \startjr/, i960
serves as the intelligent network coprocessor.
Section~\ref{sec:operation} describes how \funi/ makes use of this
embedded processing to implement an efficient low-overhead user-level
message-passing interface despite being physically located on the
peripheral PCI bus.

To help track the microprocessor performance curve, PCI80960's modular
design packages the i960 processor in an interchangeable module. The
binary compatibility and standardized bus interface within the i960
family allow transparent upgrades to upcoming generations of i960.  By
upgrading the host system and network coprocessor accordingly, we will
be able to maintain the balance between computation and communication
performance.

\subsection{Custom IEEE 1394 Interface Module for \funi/}

The Squall IEEE 1394 adaptor module for \funi/ provides the \funi/
coprocessor with access to two separate IEEE 1394 High Performance
Serial Busses.  All components on the adaptor can be purchased
``off-the-shelf''; only the PCB layout and the logics inside two
Xilinx 4005 FPGAs are custom to our system.  The IEEE 1394 adaptor
module for \funi/ is made up of two separate printed circuit boards,
joined by a connector.  The IEEE 1394 Physical Link Module (1394PLM)
PCB is specific to IEEE 1394 and utilizes commercial 1394 chip sets.
The other PCB, Squall Interface Module (SIM), provides a generalized
interface between the \funi/ i960 coprocessor and PLMs.

\subsubsection{Squall Interface Module}

SIM presents a simple generic 32-bit FIFO-based transmission and
reception interface to the \funi/ coprocessor.  The same SIM interface
can be fitted with different specifically designed PLMs to support
different network technologies.  To support two physically prioritized
networks, four hardware FIFOs are built from TI723631 synchronous
FIFOs.  A high and a low priority transmit FIFO pass commands and
out-going packets from the \funi/ coprocessor to PLM.  A high and a
low priority receive FIFO provide \funi/ with access to hardware
responses and in-bound packets from PLM.  The SIM interface supports
both single-word and four-word-burst accesses from the i960 \funi/
coprocessor to the FIFOs.  The optimized burst transactions allow more
than double the bandwidth of single-word reads and writes.

SIM also includes the hardware for implementing globally coherent
shared memory on \startjr/.  During shared memory operations, the
shared memory region of the user's virtual address space is mapped to
an Address Capture Device (ACD) on SIM.  ACD is backed by a two-way
set-associative Global Shared Memory Cache (GSMC) that is managed by a
combination of hardware and \funi/ firmware.  GSMC is based on a 16KB
Dual Ported Synchronous SRAM (DPSRAM) where one half of the DPSRAM is
used for the data store, and one quarter is used for the tag store.
The remaining 4KB of DPSRAM is available to \funi/ as fast scratch
memory.

When an access to a shared memory location occurs, ACD checks the two
tag/control words in the GSMC tag store that correspond to the memory
reference.  If ACD determines that the memory requested can be
completed according to the tag/control words, it will allow the bus
transaction to access the corresponding GSMC data location to complete
the transaction.  If the transaction cannot be satisfied in hardware,
ACD will force the memory transaction to retry indefinitely and
interrupt the \funi/ coprocessor for assistance.  Once interrupted,
the \funi/ coprocessor queries ACD for the cause and performs the
necessary coherence protocol to satisfy the memory request.  This may
require communication with \funi/s on other nodes over the IEEE 1394
interconnect.  The \funi/ coprocessor can also maintain a large
software cache in its local memory to reduce network traffic.  Once
the \funi/ coprocessor is ready to complete the memory transaction,
the \funi/ coprocessor updates the corresponding data and tag location
in GSMC.  ACD is re-enabled to complete the retried memory
transaction.

\subsubsection{1394 High Performance Serial Bus Physical Link Module}

1394PLM is built from a ready-to-integrate IEEE 1394 Physical Layer
and Link Layer chip sets from Texas Instruments.  Connections to two
independent IEEE 1394 busses are provided; one is given a higher
priority.  A custom FPGA-based controller interfaces with the SIM
FIFOs and carries out the corresponding low-level handshakes with the
IEEE 1394 chip set.  The specifics of the network implementation is
contained within PLM.  This modular design allows \startjr/ to adopt a
variety of different interconnect technologies with only limited
modifications.

\section{{\bf \funi/}}
\label{sec:operation}

\begin{sloppypar}
The basic \funi/ message-passing interface was first proposed for
SBus-equipped workstations\cite{Hoe94}.  The design proposed a way to
implement a fine-grain message-passing interface on a peripheral bus
without a penalty in communication overhead from the long access
latency.  The design required more intelligence in the interface
hardware to manage a message-passing interface in the host memory.
Interaction between the host processor and the network interface is
achieved indirectly through these shared memory locations.  The
original proposal asked for implementation of custom logics in FPGAs.
Due to the limited logic density of FPGAs, only the very basic
message-passing mechanisms were supported.
\end{sloppypar}

This initial study has led to the current embedded processing-based
\funi/ implementation.  The new design still retains the same
low-overhead since the memory-based interface paradigm is unaffected.
Embedded processing does slightly increase communication latency over
the FPGA-based design.  However, newly available processing power and
programmability enable richer features and open opportunities for
experimentation.  Furthermore, by eliminating much of the custom
logics, embedded processing has also significantly reduced the design
and implementation complexity.  Logic designs are replaced by firmware
development using a standard C compiler and interactive debugger.

In the following paragraph, we describe the communication mechanism
currently supported by \funi/.  \funi/ is composed of two parts: an
user-visible part that implements the user-level message interface,
and an internal part that processes network events such as
transmission and reception, and the necessary network protocols.  We
first describe the basic interaction between the \funi/ firmware and host
software at the message passing interface.  Next, we will examine the
internal part of \funi/. Finally, possibilities to extend the
\funi/ feature set is briefly explored.

\subsection{Memory-based User-level Message-Passing Interface}

\label{sec:userinterface}

\funi/ externally presents an abstract network interface to the user.
Due to the \funi/ coprocessor, the user interface can include more
complicated services not directly supported by the underlying network
hardware.  The interface abstraction off-loads the tasks of dealing
with the particularity of the network implementation to the \funi/
coprocessor.  This does not only streamline the host processor's
communication task, but the generalized abstraction also allows the
same user software to be carried over among different network
implementations.

\begin{figure}
\centerline{\psfigure{message}{12.5cm}}
%\centerline{\psfigure{message}{15.0cm}}
\caption{\label{fig:message}\mbox{FUNi} User Message Interface}
\end{figure}

\begin{sloppypar}
The basic message sending and receiving interface currently
implemented for \startjr/ is based on a set of message queues for
transmission (Tx) and reception (Rx).  Figure~\ref{fig:message}
logically depicts this message interface in the user's virtual address
space.  The message queues are jointly maintained by the host
processor and \funi/ as circular buffers in the host memory.  Two sets
of Tx and Rx queue pairs are implemented to support two message
priorities.  Each queue is logically divided into fix-sized message
slots, each large enough to hold the largest message.  A set of
memory-mapped registers (the PCI80960 mailbox registers) holds the
head and tail indices associated with each circular buffer.  During
the initialization call to the device driver, the user application
supplies a region of virtual address space to be mapped to the Tx and
Rx queues pinned in the host physical memory.  The index registers are
also mapped into the user's virtual address space.
\end{sloppypar}

The circular buffers use the standard convention of head and tail
indices to implement FIFO queues.  The head index points to the next
free slot, whereas the tail index points to the next valid slot.  A
queue is empty when the head and tail indices both point to the same
slot, and full when the head is immediately before the tail.  The
producer of a queue increments the corresponding head index register
to inform the consumer about new slots containing messages.  The
consumer increments the tail index to indicate which slots are ready
for reclaim.  Each index register is only incremented by either the
user or \funi/, and therefore does not require atomic operations to
modify.

\subsubsection{User-level Message Passing: Sending}

As the consumer, the \funi/ firmware compares the head and tail index
registers to poll the Tx queues for pending out-going message.  To
send a message, the user process directly composes the message in the
next free slot in the Tx queue.  The user-level interface uses very
simple message formats (simpler than an actual network packet).  For
normal message passing, the message header, containing the logical
destination address, message length and message type, is written to
the first word of the message slot.  The message payload is written to
successive addresses following the message header.  These writes to
cacheable memory locations incur minimum overhead.  Afterwards, the
user process increments the content of the head index register to make
the current message slot visible to \funi/.  Once notified, \funi/
issues cache-coherent read requests on the PCI bus to retrieve the
user message, presumably still in the data cache, and composes the
corresponding network packet for transmission.  After each successful
retrieval from a slot, \funi/ will increment the tail index to release
the slot.

\subsubsection{User-level Message Passing: Receiving}

When a packet arrives, \funi/, acting as the producer, enqueues the
message to one of the two Rx queues depending on the message's
priority.  Then, \funi/ increments the corresponding head index
register to indicate the arrival of a new message.  Prior to
enqueuing, the contents of the tail and the head index registers are
compared to detect queue overflow.  Section~\ref{sec:overflow}
explains how an overflow is handled by \funi/.

The user process detects the presence of an incoming message by
comparing the head and tail indices of the Rx queue.  However, reading
the head index register involves costly physical I/O accesses to the
\funi/ device.  Therefore, the same information is redundantly
represented as a {\tt message-valid} bit in the header word of each Rx
message slot.  When \funi/ enqueues a message, aside from incrementing
the head index, it also sets the {\tt message-valid} bit in the
message slot.  Thus, to poll for new messages, the user process should
check the {\tt message-valid} bit of the next message slot using a
cached memory read.  As long as the Rx queue remains empty, the header
word is unchanged, and each failed poll only incurs the overhead of a
cache hit. This continues until \funi/ flushes and updates the header
word to reflect a new message arrival.\footnote{The {\tt
message-valid} scheme is not used to eliminate the need to increment
the Tx head index by the host processor.  For \funi/'s coprocessor,
reading from the Tx queue in the host memory is a much more costly
operation than reading the index registers.  Since the \funi/
coprocessor is time-shared among many tasks, better overall
performance is achieved when the index registers are used for the Tx
queues.  The host overhead of writing to the index registers can be
partially hidden by the write-buffer of the host processor.
Furthermore, the head and tail index registers do not need to be
updated immediately after each message for correct operations.  Thus,
the overhead of updating the index registers can be amortized over
many messages.}


When the user process locates an unreceived message, the user process
first extracts the message type and length from the message header.
Then, the message payload is read from successive addresses.  After
the message is received, the user process releases the message slots
by incrementing the tail index register.  According to the \funi/ Rx
handshake, the user also needs to clear the {\tt message-valid} bit
afterwards.

\subsubsection{Remote DMA Transfers}

With a passive network interface, a block memory transfer requires the
sending process to explicitly copy, in verbatim, each byte of transfer
from the source to the interface.  Similarly, the receiving process
must later copy each byte from the interface to the destination
location.  To eliminate the data copying overhead, the active \funi/
network interface is extended with two types of remote DMA transfer
mechanisms.  In either DMA modes, the user process only needs to
enqueue a header that specifies the source and target virtual
addresses and the length of the data block; \funi/ will automatically
move the data block across the nodes.

The first DMA mode, intended for medium sized blocks (a few hundred
bytes), is only a zero-copy variant of message passing where \funi/
operates on the source and target location directly instead of the
message queues.  The second type of DMA can transfer up to 2560 bytes
of data per initiation.  In this case, payload is moved to and from
\funi/ using a DMA engine.  \funi/ automatically packetizes the data
block for transfer over the network.  The trade-off between the two
DMA modes is bandwidth versus latency and granularity of control.  The
overhead of initiating a DMA transfer, regardless of size, is
comparable to normal message passing.

\subsection{Internal \funi/ Functions}
\label{sec:internal}

In addition to providing the user interface, the \funi/ coprocessor is
responsible for interfacing with the network adaptor hardware as
dictated by the user application.  At the highest level, this simply
involves translating between the abstract user-level messages and the
appropriate network packets, according to a fixed rule.  However,
\funi/ presents an abstraction of a secured, multi-prioritized,
loss-less and deadlock-free network to simplify the work of the host
processor.  If these characteristics are not directly supported by the
physical network substrate, \funi/ must enforce these characteristics
through network protocols. In the paragraphs below, we describe the
light-weight protocols for enforcing these assumptions and how they
apply to the IEEE 1394 implementation in particular.

\subsubsection{Protection and Security}

\startjr/ is designed to allow multiple parallel applications to
time-share the network and processor resources while providing each
application the illusion of a private and reliable network.  \funi/
maintains this abstraction by automatically tagging network packets
with Group Identifiers (GIDs).

Each parallel application on \startjr/ is assign an unique GID.  When
the process of a parallel application is active on a workstation, the
operating system makes the corresponding GID available to \funi/.
Every out-going packet is automatically tagged with the GID.  When the
packet arrives at the destination, the receiving \funi/ compares the
GID tag of the in-bound packet against the local GID.  The in-bound
packet is delivered to the current process only if a match is made.  A
mismatched GID indicates the correct process is not presently
executing, and the in-bound packet is not delivered.  (Under the flow
control protocol of \startjr/, \funi/ will discard the undeliverable
packet and return a negative acknowledgment to the packet's
originator.)  Thus, a process is only able to communicate with its
cooperating peer processes of the same application whom all share the
same application GID.

\subsubsection{Network Flow Control for Performance Guarantee}
\label{sec:overflow}

When a parallel system is shared among different users, another
concern is gross performance degradation, or even deadlock, of the
network due to misuse by a user.  This issue is addressed in \startjr/
by the Acknowledgment/Retry End-to-End Flow Control Protocol carried
out by the \funi/ coprocessor.

The Acknowledgment/Retry Protocol in \startjr/ is a simplification of
the Selective Repeat Protocol\cite{Tan89}.  In this sender-buffering
protocol, \funi/ is responsible for buffering its out-going packets
until the packet is accepted and positively acknowledged by the
receiver.  When \funi/ absorbs an in-bound packet from the network, a
positive acknowledgment is sent if the packet is accepted.  If \funi/
cannot accept the packet, a negative acknowledgment is returned to the
originating \funi/ to request for a retry.

With the ability to discard incoming packets, \funi/ at each node can
continuously absorb packets from the network even with only finite
local storage.  Since network packets are continuously absorbed, the
network will not deadlock regardless of the individual behavior at
each node.  Thus, \funi/ can never be indirectly blocked from
communication by other misbehaving nodes.  Thus, the protocol can
guarantee the worst-case performance of the network.  \funi/ is
stopped from transmitting only when its own receivers cannot absorb
and acknowledge the packets fast enough.  Thus, this protocol also
serves as an automatic rate control for throttling network activities
of over-active sender nodes.

The Acknowledgment/Retry Protocol needs to be implemented on top of
two physically separate or prioritized network where the higher
priority network traffic cannot be blocked by lower priority traffic.
In IEEE 1394-based \startjr/, this is accomplished by using two
separate IEEE 1394 busses.  In the protocol, the payload packets are
sent on the low priority network, and the acknowledgments are sent on
the high priority network to avoid deadlock within the protocol
itself.

\subsubsection{Virtually Prioritized Networks}

On top of the Acknowledgment/Retry Protocol, any number of virtual
network priorities can be extended to the user. Currently, \funi/ has
chosen to implement two levels of priority to support the popular
request-reply based user protocols.  Two sets of Tx and Rx message
queues as described in Section~\ref{sec:userinterface} are provided to
handle the two priorities of messages independently.  \funi/
preferentially services the higher priority queue first.  Parts of the
buffering resources at each \funi/ are also reserved for exclusive use
by high priority message traffic.  This is sufficient to guarantee the
flow of high priority messages in the system regardless of lower
priority traffic since the Acknowledgment/Retry Protocol already
guarantees that the network itself will not block.

\subsubsection{Packet Loss Recovery}
\label{sec:lossless}

Although the Acknowledgment/Retry Protocol allows \funi/ to
continuously absorb packets from the network, under an extreme
many-to-one communication pattern, \funi/'s hardware buffer can become
full because the \funi/ coprocessor cannot keep up with the influx of
packets.  In a traditional loss-less MPP network, this condition would
temporarily block the network, but eventually it will become freed
again without extra handling.

The Acknowledgment/Retry Protocol on a loss-less network can expect
every payload packet transmitted to be matched with a returning
acknowledgment, whether positive or negative.  However, on IEEE 1394,
when the hardware buffer overflows, the partially transferred message
is discarded.  In this case, a discarded payload packet would never be
acknowledged.  (Due to the small size of acknowledgment packets, the
acknowledgment receive buffer is guaranteed not to overflow.)  Thus,
for IEEE 1394-based \startjr/, the Acknowledgment/Retry Protocol is
augmented with an additional {\em round} counting scheme to restart
packets with lost acknowledgments.  All packets destined for a
particular node is tagged with a round identifier associated with that
node.  When \funi/ detects a situation where packets are lost on the
network, it broadcasts a new round identifier for itself and discards
any future in-bound packets tagged with the old round identifier.
After receiving a restart broadcast, the other \funi/s will treat
unacknowledged packets as if they were negatively acknowledged and
retry them with the new round identifier.

\subsection{Coprocessing-based Extension to \funi/}

Higher-level communication features can be developed to further
off-load network processing tasks from the host processor to the
firmware programmable \funi/.  We are currently working on a version
of the \funi/ firmware with integrated MPI\cite{MPI95} functions to
reduce host processing overhead during communication.  Processing of
light-weight active messages and remote fetches are also candidates
for transfer into the \funi/ coprocessor.  Other possibilities include
scheduled prefetches, conditional prefetches and advanced
synchronization services.  Additional performance for mission-critical
applications can be obtained through fine-tuning the firmware to the
specific traffic pattern and communication needs.

\funi/'s embedded processor-based implementation also encourages
research in network flow control protocols.  Even non-trivial
protocols can be quickly tested by recoding the firmware.  Performance
monitors can also be included during system development.  Future work in
protocols can extend to address fault tolerance and network load
balancing issues.

\section{Current Status and Results} \label{sec:results}

A two-node \startjr/ prototype has been completed as a prelude to the
eight-node final system.  A light-weight communication library, \jam/,
has been developed to assist the software development for SPMD
message-passing programming.  The library is based on University of
California at Berkeley's version of the Connection Machine Active
Message (CMAM) library\cite{ECG92}.  The CMAM library is ported to
\startjr/ by rewriting the low-level primitives that deal directly
with the network interface\footnote{Currently, all software and
firmware additions are coded in C and compiled with GCC with
optimization options.}.  New primitives are added to take advantage of
the features of \startjr/ and \funi/.  A new set of primitives to
support larger messages, up to twenty arguments, is added.  A 
set of data transfer primitives is also added to take advantage of
\funi/'s low-overhead remote DMA transfer.  Examples of the \jam/
primitives and a brief description are given in
Table~\ref{tab:primitive}. As in CMAM, each \jam/ primitive is
supported in two priorities; high priority primitives have the
additional suffix {\tt \_{reply}}.


\begin{table}
\caption{Examples of \jam/ Primitives}\label{tab:primitive}
\footnotesize
\begin{center}
\begin{tabular}{|p{1.2in}|p{1.0in}|p{3.2in}|}
\hline
\multicolumn{3}{|c|}{Message-passing Primitives}\\\hline
\multicolumn{1}{|c|}{primitive}&\multicolumn{1}{|c|}{argument}&\multicolumn{1}{|c|}{description}\\\hline
{\tt JAM\_4()} {\tt JAM\_reply\_4()}&{\tt dest, *func, arg1, arg2,
arg3, arg4}&
Sends an active
message containing the pointer {\tt func} and the 4 integer arguments
to {\tt dest}. \linebreak {\tt *func(arg1,arg2,arg3,arg4)} is invoked
at {\tt dest} upon arrival.\\\hline
{\tt JAM\_n()} {\tt JAM\_reply\_n()}&{\tt dest, *func, arg[], size}&
Sends an
active message containing the pointer {\tt func} and up to 20 integer
arguments from arg[] to {\tt dest}.  {\tt *func(arg[0],arg[1],...,arg[n-1])} is invoked at {\tt dest} upon arrival.\\\hline
\multicolumn{3}{c}{}\\\hline
\multicolumn{3}{|c|}{Block Data Transfer Primitives}\\\hline
\multicolumn{1}{|c|}{primitive}&\multicolumn{1}{|c|}{argument}&\multicolumn{1}{|c|}{description}\\\hline
{\tt JAM\_xfer\_4()} {\tt JAM\_reply\_xfer\_4()}& {\tt dest, seg\_addr, word0, word1, word2, word3}&
Transfers 4 integer data to {\tt dest}.
The transfer segment ID and address at the destination are encoded in
{\tt seg\_addr}.  This primitive uses \funi/'s standard message passing
mechanism.\\\hline

{\tt JAM\_mfer\_n()} {\tt JAM\_reply\_mfer\_n()} & {\tt dest, seg,
*source, *target, nword}& Transfers up to 16 4-byte data to {\tt
dest}.  The payload is moved from local {\tt source} to remote {\tt
target} using \funi/'s 0-copy message passing mechanism.\\\hline

{\tt JAM\_DMA\_n()} {\tt JAM\_reply\_DMA\_n()} & {\tt dest, seg, *source, *target, nword}&
Transfers up to 640 4-byte data to {\tt dest}.  The payload
is moved from local {\tt source} to remote {\tt target} using \funi/'s
direct memory-to-memory transfer.\\\hline
\multicolumn{2}{|c|}{}&{\bf NOTE:} Like CMAM, data transfers first involve
registering a transfer segment and a handler at the destination node.  Subsequent transfers
decrement a transfer counter.  When the transfer is completed,
the registered handler is invoked. \\\hline
\end{tabular}
\end{center}
\end{table}



A benchmark suite to assess the performance of \funi/ in conjunction
with \jam/ is executed on the two-node \startjr/ prototype.
Communication overhead, one-way user-to-user latency and sustained
throughput of the basic \jam/ primitives are measured.  The send and
receive overheads measure the average execution time of the
corresponding primitives on the sending and receiving host processors
respectively. User-to-user latency includes all the processing by the
host and \funi/ on both the sending and receiving ends, plus the
one-hop network transit latency.  In addition to MByte/sec,
sustainable throughput is also given in terms of $\mu$sec, which
roughly corresponds to the occupancy of each \jam/ primitive on the
\funi/ coprocessor.  Table~\ref{tab:summary} gives a summary of the
measured results.

\begin{table}
\caption{Benchmark Summary of \jam/ on \startjr/} \label{tab:summary}
\footnotesize
\begin{center}
\begin{tabular}{|l|p{0.6in}|p{0.6in}|p{0.4in}p{0.4in}|p{0.4in}p{0.4in}|p{0.6in}}
\hline
\multicolumn{8}{|c|}{Message-passing Primitives}\\\hline

&\multicolumn{1}{c|}{send}&\multicolumn{1}{c|}{receive}&\multicolumn{2}{c|}{send}&\multicolumn{2}{c|}{receive}&\multicolumn{1}{c|}{latency}\\

&\multicolumn{1}{c|}{overhead}&\multicolumn{1}{c|}{overhead}&\multicolumn{2}{c|}{throughput}&\multicolumn{2}{c|}{throughput}&\multicolumn{1}{c|}{}\\\cline{2-8}

&\multicolumn{1}{|c|}{$\mu$sec}&\multicolumn{1}{|c|}{$\mu$sec}&\multicolumn{1}{|c}{MB/sec}&\multicolumn{1}{c|}{$\mu$sec}&\multicolumn{1}{|c}{MB/sec}&\multicolumn{1}{c|}{$\mu$sec}&\multicolumn{1}{|c|}{$\mu$sec}\\\hline

{\tt JAM\_4}&\multicolumn{1}{c}{2.2}&\multicolumn{1}{c}{1.1}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{29}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{29}&\multicolumn{1}{c|}{85}\\

{\tt JAM\_reply\_4}&\multicolumn{1}{c}{1.6}&\multicolumn{1}{c}{1.1}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{29}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{29}&\multicolumn{1}{c|}{85}\\\hline

{\tt JAM\_n=1}&\multicolumn{1}{c}{2.0}&\multicolumn{1}{c}{1.3}&\multicolumn{1}{c}{0.1}&\multicolumn{1}{c}{27}&\multicolumn{1}{c}{0.1}&\multicolumn{1}{c}{26}&\multicolumn{1}{c|}{ }\\

{\tt JAM\_n=20}&\multicolumn{1}{c}{5.4}&\multicolumn{1}{c}{3.5}&\multicolumn{1}{c}{1.9}&\multicolumn{1}{c}{42}&\multicolumn{1}{c}{1.9}&\multicolumn{1}{c}{42}&\multicolumn{1}{c|}{ }\\\hline

{\tt JAM\_reply\_n=1}&\multicolumn{1}{c}{1.5}&\multicolumn{1}{c}{1.3}&\multicolumn{1}{c}{0.1}&\multicolumn{1}{c}{27}&\multicolumn{1}{c}{0.1}&\multicolumn{1}{c}{27}&\multicolumn{1}{c|}{ }\\

{\tt JAM\_reply\_n=20}&\multicolumn{1}{c}{4.0}&\multicolumn{1}{c}{3.6}&\multicolumn{1}{c}{1.9}&\multicolumn{1}{c}{43}&\multicolumn{1}{c}{1.9}&\multicolumn{1}{c}{42}&\multicolumn{1}{c|}{ }\\\hline
\multicolumn{8}{c}{}\\\hline
\multicolumn{8}{|c|}{Block Data Transfer Primitives}\\\hline

&\multicolumn{1}{c|}{send}&\multicolumn{1}{c|}{receive}&\multicolumn{2}{c|}{send}&\multicolumn{2}{c|}{receive}&\multicolumn{1}{c|}{latency}\\

&\multicolumn{1}{c|}{overhead}&\multicolumn{1}{c|}{overhead}&\multicolumn{2}{c|}{throughput}&\multicolumn{2}{c|}{throughput}&\multicolumn{1}{c|}{}\\\cline{2-8}

&\multicolumn{1}{|c|}{$\mu$sec}&\multicolumn{1}{|c|}{$\mu$sec}&\multicolumn{1}{|c}{MB/sec}&\multicolumn{1}{c|}{$\mu$sec}&\multicolumn{1}{|c}{MB/sec}&\multicolumn{1}{c|}{$\mu$sec}&\multicolumn{1}{|c|}{$\mu$sec}\\\hline

{\tt JAM\_xfer\_4}&\multicolumn{1}{c}{2.7}&\multicolumn{1}{c}{1.5}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{48}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{48}&\multicolumn{1}{c|}{ }\\
{\tt JAM\_reply\_xfer\_4}&\multicolumn{1}{c}{1.8}&\multicolumn{1}{c}{1.4}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{49}&\multicolumn{1}{c}{0.5}&\multicolumn{1}{c}{50}&\multicolumn{1}{c|}{ }\\\hline

{\tt JAM\_mfer\_n=16}&\multicolumn{1}{c}{1.9}&\multicolumn{1}{c}{1.2}&\multicolumn{1}{c}{1.5}&\multicolumn{1}{c}{17}&\multicolumn{1}{c}{0.4}&\multicolumn{1}{c}{69}&\multicolumn{1}{c|}{ }\\

{\tt JAM\_reply\_mfer\_n=16}&\multicolumn{1}{c}{2.0}&\multicolumn{1}{c}{1.1}&\multicolumn{1}{c}{1.5}&\multicolumn{1}{c}{17}&\multicolumn{1}{c}{0.4}&\multicolumn{1}{c}{69}&\multicolumn{1}{c|}{ }\\\hline

{\tt JAM\_dma\_n=640}&\multicolumn{1}{c}{2.1}&\multicolumn{1}{c}{1.1}&\multicolumn{1}{c}{3.4}&\multicolumn{1}{c}{ }&\multicolumn{1}{c}{3.4}&\multicolumn{1}{c}{ }&\multicolumn{1}{c|}{ }\\
{\tt JAM\_reply\_dma\_n=640}&\multicolumn{1}{c}{2.1}&\multicolumn{1}{c}{1.1}&\multicolumn{1}{c}{3.4}&\multicolumn{1}{c}{ }&\multicolumn{1}{c}{3.4}&\multicolumn{1}{c}{ }&\multicolumn{1}{c|}{ }\\\hline
\end{tabular}
\end{center}
\end{table}

Table~\ref{tab:comparison} compares the performance of \funi/ against
other message passing systems.  The first column lists the typical
performance of TCP/IP on a Linux PC with a 120MHz Pentium processor
and 10~Mbit/sec Ethernet.  The second column shows the performance of
the original CMAM library on a 32-node CM-5 with 32~MHz SPARC
processors.  The performance of \startjr/ connected by IEEE 1394 is
given in column three.  For comparison, the performance of \startjr/
connected with MIT's Arctic Switch Fabric\cite{Bou94} is given in
column four.  Finally, a comparison is made against a pair of
Myrinet-equipped 75~MHz SPARCstation20s running UIUC's FM
library\cite{PKC96}.  The overhead and latency are measured using
minimum size packets in each system.  The overhead shown includes both
the send and receive overheads, and the latency is for one-way
user-to-user.  In Table~\ref{tab:comparison}, overhead and latency are
also given in terms of native processor cycles to give an
approximation of the communication cost in terms of number of
instructions.

\begin{table}
\caption{Communication Performance Comparison}\label{tab:comparison}
\footnotesize
\begin{center}
\begin{tabular}{|lr|p{1.2in}|p{1.2in}|p{1.2in}|p{1.2in}|p{1.2in}|}
\hline
\multicolumn{2}{|c}{}&\multicolumn{1}{|c}{TCP/IP and}&\multicolumn{1}{|c}{CMAM
and}&\multicolumn{1}{|c}{\jam/ and}&\multicolumn{1}{|c}{\jam/ and}&\multicolumn{1}{|c|}{FM and}\\
\multicolumn{2}{|c}{}&\multicolumn{1}{|c}{Ethernet}&\multicolumn{1}{|c}{CM\-5}&\multicolumn{1}{|c}{\startjr/}&\multicolumn{1}{|c}{\startjr/}&\multicolumn{1}{|c|}{Myrinet}\\
\multicolumn{2}{|c}{}&\multicolumn{1}{|c}{}&\multicolumn{1}{|c}{}&\multicolumn{1}{|c}{(IEEE
1394)}&\multicolumn{1}{|c|}{(MIT
Arctic)}&\multicolumn{1}{|c|}{}\\\hline



overhead&($\mu$sec)&\multicolumn{1}{c}{27}&\multicolumn{1}{c}{2.9}&\multicolumn{1}{c}{3.3}&\multicolumn{1}{c}{3.6}&\multicolumn{1}{c|}{4.4}\\
&(cyc)&\multicolumn{1}{c}{3240}&\multicolumn{1}{c}{92.8}&\multicolumn{1}{c}{396}&\multicolumn{1}{c}{432}&\multicolumn{1}{c|}{330}\\\hline

latency&($\mu$sec)&\multicolumn{1}{c}{1289}&\multicolumn{1}{c}{12.5}&\multicolumn{1}{c}{85}
&\multicolumn{1}{c}{18.0}&\multicolumn{1}{c|}{13.1}\\
&(cyc)&\multicolumn{1}{c}{154K}&\multicolumn{1}{c}{414}&\multicolumn{1}{c}{10200}
&\multicolumn{1}{c}{2160}&\multicolumn{1}{c|}{982}\\\hline

bandwidth&(MB/sec)&\multicolumn{1}{c}{0.8}&\multicolumn{1}{c}{10.0}&\multicolumn{1}{c}{3.4}
&\multicolumn{1}{c}{9.1}&\multicolumn{1}{c|}{17.5}\\\hline
\end{tabular}
\end{center}
\end{table}

The comparison shows that \funi/ can give nearly an order-of-magnitude
improvement in performance relative to normal Unix IPC mechanisms over
conventional Ethernet.  \funi/'s memory-based, decoupled user-level
interface achieves lower communication overhead in comparison with the
contemporary Myrinet-based system.  However, Myrinet-based systems
achieved nearly five-times the bandwidth and one-sixth the minimum
latency as compared to \funi/.  Section~\ref{sec:related} further
discusses the comparison against Myrinet-based systems.

\funi/'s performance, in terms of bandwidth and latency, is restricted
by our design choices to exchange latency and throughput for lowered
overhead. The user-visible latency and bandwidth of \funi/ is well
below the capability of the raw hardware.  An alternate \funi/
firmware can be used to improve the bandwidth and latency of the
system, but with a penalty in overhead and overall system
performance.

\funi/'s performance is also limited by the processing rate of the
i960 \funi/ coprocessor.  As described in Section~\ref{sec:internal},
additional protocols have to be layered on top of the IEEE 1394 High
Performance Serial Bus to present a network abstraction more suitable
for parallel computing.  The amount of protocol required directly
affects each message's occupancy on the network coprocessor, which
translates to lower bandwidth and longer latency in the
processing-bound \funi/.  For example, by switching to the Arctic
Switch Fabric which is designed from the ground-up for parallel
processing, \funi/, using more minimal protocol, can gain a factor of
two to three improvement in bandwidth and latency.  We hope \funi/'s
performance will increase with the availability of new generations of
i960 processors.  Meanwhile, \funi/ has to make use of its
general-purpose processing power to assist the host processor in more
sophisticated message processing to compensate for its shortcomings.

Lastly, one should also notice that both \startjr/ and the Myrinet
system perform poorly against CM-5 in terms of native processor
cycles.  This exemplifies the two-fold problem that hinders the
communication performance of NOW systems.  First, unlike the
two-generation-old SPARC processor in CM-5, modern microprocessors
have greater bias for number crunching rather than I/O performance.
Secondly, unlike CM-5's proprietary hardware, the NOWs do not have the
luxury of a customized network interface tightly coupled to the
microprocessor on the memory bus.



\section{Related Research}
\label{sec:related}

The parallel processing community has long recognized the importance
of low communication latency and overhead for good parallel
performance.  The {\sc StarT} project\cite{NPA92} integrated an
user-level network interface directly into ISA and the datapath of a
RISC microprocessor.  However, the time and effort required for such a
hardware-intensive project not only introduces great risks but also
often results in out-dated hardware. To close this technology gap,
later projects such as \start/\cite{CAA95} and Flash\cite{KOH94} rely
on stock mainstream commercial microprocessors but with tightly
coupled external hardware (using a direct connection to the
processor).  In the near term, these projects may still be less
practical because their overall message-passing performance remains
hindered by the internal design of the microprocessor, despite
extensive efforts in optimizing the external hardware and its
interaction with the microprocessor.  Nevertheless, this
tight-integration of computation and communication will become
essential as the performance between the microprocessor and the
remainder of the computer system continues to widen.

Meanwhile, the network interface design for a practical NOW
system must work within the limitations of existing system
constraints, such as the bias for normal memory accesses versus I/O
accesses.  The SHRIMP multicomputer project\cite{BDF94,BLA94}
specifies another memory-based interface to achieve low communication
overhead in a stock workstation environment.  The SHRIMP network
interface is designed for a network of Pentium PCs with Xpress Bus and
EISA Bus.  Communication between any two PCs is logically an
uni-directional mapping of a source virtual memory region on one PC to
the target memory region on another.  The network interface on the
source PC snoops the bus for writes into the mapped area of memory and
automatically transmits a message to the target PC.  The target
network interface then writes the data to the corresponding location
using DMA.  To support this communication paradigm, SHRIMP's hardware
needs to support specialized functions such as bus snooping and
memory-management.  SHRIMP's hardware implementation overhead is
higher than \funi/'s, and SHRIMP's association with a specific
processor-memory bus limits its upgrade path.  SHRIMP also does not
have the benefit of a network coprocessor.

Several academic and industry NOW
projects\cite{BDF94,HLW95,KAP95,PKC96,PLC95,SwS96} have based their
research on a cluster of workstations interconnected by
Myrinet\cite{BCF95}.  Derived from Caltech's ATOMIC
project\cite{FDC94}, Myrinet is available commercially as a
ready-to-go high-performance NOW interconnection package.  The Myrinet
package comes complete with network routers, end-point adaptors for
SBus and PCI, standard IP layers, and a custom low-level interface
layer.

Myrinet's network adaptors are controlled by Myricom's custom LANai
embedded processor.  Much of the current research has involved taking
advantage of the programmability of the LANai processor to implement
fast user-level message-passing on NOW.  Both LANai and the host
processor can access the LANai local memory on the adaptor.  However,
unlike the \funi/ coprocessor, the LANai processor does not have
access to the host memory except using a DMA engine.  Thus, in
fine-grain messaging, either the host processor has to pay the
overhead for writing messages all the way out to the adaptor, or to
pay the latency penalty for data movement by the DMA engine.  This
could possibly explain the higher communication overhead compared with
\funi/.  However, Myrinet's integrated custom implementation yields
far better latency and bandwidth (less than 10~$\mu$sec latency and
greater than 30~MByte/sec are reported\footnote{Latest performance
figures for Myrinet are posted on {\bf
http://www.myri.com/myrinet/performance/}.}).

\section{Discussion} \label{sec:conclusion}

The goal of \startjr/ is to achieve usable performance comparable to
hardware-intensive designs while maintaining the price-performance
advantage through the use of low-cost commodity components.  The
system incorporates standard hardware and software subsystems to
achieve state-of-the-art performance with minimal cost and effort.  By
designing for commodity technology, \startjr/ is general enough to
adopt to emerging technologies.  This flexibility will enable
\startjr/ to maintain up-to-date performance despite the rapid
turn-over of technology.

\startjr/ employs \funi/'s memory-based network interface paradigm to
overcome the two disadvantages facing NOW development:

\newcounter{opbean1}
\begin{list}{\arabic{opbean1}.}{\usecounter{opbean1}}

\item Stock microprocessors and workstations are optimized with a bias
for processing rather than non-cached, non-burst I/O operations, and

\item Stock workstations lack a generic/standard interface that is
more tightly-coupled to the processor than the peripheral bus slots.

\end{list}

\funi/ overcomes these problems by decoupling the network interface
hardware from the host processor during communication. The \funi/
coprocessor also off-loads much of the communication overhead from the
host processor.  By relying on latency-hiding software techniques and
concentrating on minimizing communication overhead, \startjr/ can
provide good support for fine-grain message passing.

This paper describes the system design and development of the
\startjr/ project.  Continuing \startjr/ research will focus on
developing additional memory-based interface paradigms.  The research
will take full advantage of the programmable \funi/ coprocessor to
compensate for \funi/'s hardware tradeoffs.  Although \funi/ is able
to reduce the overhead of message passing, its latency is not optimal.
The success of \funi/ and \startjr/ must rely on latency-hiding
techniques such as split-phased transactions and software pipelining.
Future research will involve analyzing existing programs/algorithms'
communication pattern and transforming them into more latency tolerant
ones. The analysis of communication patterns will also help in
designing more suitable message interface services.  Given the
programmable \funi/, it is possible to fine-tune the \funi/ firmware
on a program-by-program basis for maximum performance.

Relying on standard technologies from the PC and the workstation
industries, the bus-based symmetric multiprocessing workstations
(SMPs) have solved the chicken-and-egg problem of large market volume
versus lowered production cost.  By providing good performance for
both existing sequential binaries as well as new parallel programming
paradigms, SMPs have also resolved the paradox of creating a software
base without a user base, and vice versa.  By touching off this
seamless transition, SMPs have finally given parallel processing a
solid foothold in mainstream computing.  Nevertheless, the scalability
of these bus-based parallel systems will inevitably be challenged.
Sharing the same two traits that made SMPs successful, NOW systems
such as \startjr/ will play a crucial role in resolving the
scalability bottleneck and further extending this seamless transition
into parallel computing.

\section{Acknowledgments}
\label{sec:acknowledgments}

This research is supervised by Professor Arvind and is supported by
the Advanced Research Projects Agency of the Department of Defense
under Office of Naval Research contract N00014-92-J-1310 and Ft.
Huachuca contract DABT63-95-C-0150.  Special thanks to Intel for their
donation of the Pentium PCs and to Texas Instruments for their
assistance in manufacturing the 1394 interface cards.  Many thanks to
our colleagues, B. S. Ang, M. J. Beckerle, A. Boughton, D. Chiou,
R. Greiner, J. E.  Hicks, L. Rudolph, and X.  Shen on the {\sc
StarT-ng} and {\sc StarT-voyager} sister projects.

\bibliography{/home/prj/jhoe/publications/tex/short-abbrevs,/home/prj/jhoe/publications/tex/total}

\end{document}










