%---------------------------------------------------------------------
\subsection{Destination Translation Mechanism}
\label{sec:trans}
%---------------------------------------------------------------------

All user-level messages in \start/ are directed towards destination
queues in a virtual queue name space that is private to the sending
job, and subjected to translation into physical queue name by the NES
hardware.  Sharing many similarities with traditional virtual memory
systems, the queue name translation offers protection by restricting
the destination queues addressable by a job.  As in a virtual memory
system, such a mechanism not only offers protection, but allows
transparent, dynamic swapping of a virtual queue between different
hardware resources.  System code on \start/ uses this capability to
transparently switch message queues between fast Resident queue
resources and slower but cheaper and more numerous Non-resident queue
resources (see below).  The virtual queue name space also facilitates
dynamically adjusting the number of processors devoted to a parallel
job, allowing several virtual queue names to map to the same physical
queue.

The NES hardware consults a hardware {\em Destination Table},
analogous to a page table, to translate a virtual queue name into a
physical destination site number required by a network packet for
routing, and a received queue name used at the destination site to
identifier the destination queue.  Figure~\ref{fig: logical
destination mappings} illustrates the entries of the Destination Table
%%% begin footnote
\footnote{An inverse table could  be associated with
each receive queue so that only messages from a specified set of
sources will be accepted.  Such additional hardware would protect
against untrusted OS or sP code at a source.
\start/ does not implement this additional hardware.}%
%%% end footnote
.  The Destination Table is configured by software through an NES address
space which should only be accessible to system software.  

The NES also attaches a source identifier to each outgoing message,
which the destination process can use to reply to a message. For
symmetry in translation the source identifier must look like a logical
destination specifier at the destination.  In \start/, it is
convenient to keep the source identifier in the Destination Table to
facilitate attaching of the source identifier to an out-going message.
The logical destination specifiers should have the same meaning across
all of the processes in a single parallel job, allowing the passing of
logical destination specifiers to other processes.

\begin{figure}
\begin{center}
\begin{tabular}{c||l|l|l|l|}
TxQ	& \multicolumn{1}{|c|}{Logical Dest 0}	
	& \multicolumn{1}{|c|}{Logical Dest 1}
	& ...	
	& \multicolumn{1}{|c|}{Logical Dest $n$} \\\hline
0	& $\langle$site$_A$, RxQ$_\beta$, source$_i$$\rangle$
	& $\langle$site$_B$, RxQ$_\delta$, source$_j$$\rangle$ 
	& ...	
	& $\langle$site$_C$, RxQ$_\zeta$, source$_k$$\rangle$ \\
\hline
1	& $\langle$site$_A$, RxQ$_\theta$, source$_l$$\rangle$ 
	& $\langle$site$_E$, RxQ$_\iota$, source$_m$$\rangle$ 
	& ...	
	& $\langle$site$_F$, RxQ$_\lambda$, source$_n$$\rangle$ \\
\hline
$\vdots$& $\vdots$
	& \multicolumn{1}{|c|}{$\vdots$}
	& \multicolumn{1}{|c|}{$\vdots$}
	& \multicolumn{1}{|c|}{$\vdots$}
\\
\hline
$n$	& $\langle$site$_G$, RxQ$_\nu$, source$_o$$\rangle$ 
	& $\langle$site$_H$, RxQ$_\pi$, source$_p$$\rangle$ 
	& ...	
	& $\langle$site$_I$, RxQ$_\sigma$, source$_q$$\rangle$ \\\hline
\end{tabular}
\end{center}
\caption{Destination Table: each row contains the 
logical destination to $\langle$site, RxQ, source$\rangle$ mapping for
a transmit queue.}
\label{fig: logical destination mappings}
\end{figure}

Fast context switching is made possible by multiple messages queues.
Specifically, each \start/ site has 512 pairs of transmit/receive
queues. In a standard allocation scheme each process of a parallel job
is assigned its own unique set of message passing queues\footnote{The
smallest allocation unit is two transmit and two receive queues.}.
Access to a local queue is controlled by the virtual memory mapping of
the processor, \ie/, only specific queues are mapped to a process's
virtual memory space.  A running parallel job can be suspended and
``swapped out'' by suspending and swapping out each of its constituent
processes independently.  Though the process is no longer running on
the processor, its message queues are still active and messages can
continue to arrive and be queued into them.  Swapping out a parallel
process requires no global coordination to ensure correctness.  This
is in contrast to traditional MPP's such as the CM-5\cite{Leiserson92}
which supports only a single set of network queues, forcing the queues
as well as the network to be entirely swapped out at the same time a
parallel job is being swapped out.  The liberation of job scheduling
from globally synchronous gang scheduling opens up the possibility for
novel coscheduling approaches\cite{Sobalvarro95}.

% actual multitasking

The virtual destination queue name space approach is more general than
other machines' approach of using a Parallel Job Identifier (PJID)
which is added automatically to every outgoing message and verified at
the destination\cite{Papadopoulos93}.  The latter scheme defines
monolithic protection domains in which every process can communicate
with every other process in the domain.  While suitable for parallel
applications, it does not offer enough flexibility in a distributed
environment, where a server application may want to communicate with a
number of client applications without allowing a client to communicate
directly with every other client.  \start/'s virtual destination
naming scheme supports such non-uniform communication patterns.  

%----------------------------------------------------------------------
\subsection{ Message Queue Hierarchy }
\label{sec: multitasking}
%----------------------------------------------------------------------

% implementation

The large number of queues at each \start/ site are far too many to be
supported directly in hardware.  Each NES supports 16 pairs of
transmit and receive queues (8 Express/\tagon/ and 8 Basic) directly
in hardware.  The hardware queues act as a software-managed cache for
the 512 pairs of transmit and receive queues.  The queues mapped to
hardware queues are called {\em Resident} while the others are called
{\em Non-resident}.  Because both Resident and Non-resident queues are
accessed via memory-mapped interface, application code is not directly
aware of whether its queue is mapped to Resident or Non-resident
resource.  This mapping can thus be changed dynamically and
transparently by the system software.

When a message packet arrives at an NES, the NESCtrl determines if the
destination queue specified in the message header is resident and if
it has enough room for the message.  If both conditions are true, the
NESCtrl enqueues the message accordingly.  Otherwise, the NES
enqueues the message in the {\em miss queue} serviced by the sP.
Non-resident queues in \start/ are implemented by mapping the message
buffer space into the aP's DRAM and the control/status state into sP
Serviced address space.  Messages can continue to be received into and
sent from non-resident queues with the sP's assistance.  Mapping of
the control/status state into sP Serviced address space allows the sP
to support the non-resident queues without actively polling on the
state of each queue.  Instead, access to control/status state results
in bus transactions which trigger sP processing in an event driven
fashion.


%----------------------------------------------------------------------
\subsection{ The OnePoll Mechanism }
%----------------------------------------------------------------------

With an application potentially having a large number of receive
queues, it becomes expensive to continually poll each one.  Response
time and processor overhead for any receive is increased.  To address
this overhead, \start/ provides the ability to poll from multiple
queues {\em simultaneously}.  Application code specifies to the NES
which queues to poll using the usual single-queue polling mechanism
but to a phantom queue.  Either a special empty message is returned,
indicating that all the queues are empty, or the message from the
highest priority queue is returned.  For ease of implementation, there
is a fixed priority between queues.  Since the polling mechanism
depends on an understanding of the \start/ message passing types, the
implementation details are postponed to the end of the next section.


