
%=====================================================================
\section{Protection and Multiuser Concerns}
\label{sec: multitasking}
%=====================================================================
% multiuser software view of communication

\start/ was designed to support a multiuser, multitasking, loosely
gang-scheduled environment.  To achieve this goal, \start/ employs a
combination of protection and translation mechanisms and
provides multiple message queues at each site.

% multiple queues / site 
%virtual queue address -- provides protection, migration, fault
%tolerance

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.}.  No
queue is assigned to two independent processes simultaneously.  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. Furthermore, a process is allowed to send
messages to other processes (i.e., enqueue messages in remote receive
queues) only if it is so specified in a predetermined {\em Destination
Table}.

A message packet header must specify both the destination site and
destination queue at the site.  Rather than addressing physical sites
and queues, the application code uses a logical destination specifier,
which identifies an entry in the Destination Table (see
Figure~\ref{fig: logical destination mappings}).  The NES translates
logical destination specifiers to the appropriate site/queue pair.
Since the translation is also a function of the local transmit queue,
only specific transmit queues can send messages to specific receive
queues%
%%% 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 NES also attaches a source identifier to each outgoing message.
The destination process can reply to a message using the source
identifier. For symmetry in translation the source identifier must
look like a logical destination specifier at the destination.  Such a
specifier is also kept in the Destination Table to facilitate
attaching of the source identifier (see Figure~\ref{fig: logical
destination mappings}).  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.  The Destination Table is configured through a separate NES
address space and should be accessible only to system software.  Thus
an application must be granted permission to access remote queues
prior to initiating any communication.

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

% actual multitasking

With this support, efficient protected multitasking can be implemented
easily.  A running parallel job can be suspended and ``swapped out''
by suspending and swapping out each of its constituent processes
independently.  Since each receive queue is assigned to at most one
process, messages can arrive for a process that is swapped out;
swapping out a parallel process requires no global coordination,
though it may impact performance.  Such freedom dramatically reduces
the parallel job swapping time needed by traditional MPP's.
Traditional MPP's such as the CM-5\cite{Leiserson92} support 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.


Logical destination translation also enables
processes to migrate from one site to another and from one set
of receive queues to another.  Moving processes to other sites and
receive queues is useful if a parallel job must be moved to
a smaller space partition, say to adapt to the failure of a site.
Several processes of the same job can be
mapped to the same site, each with its own set of message passing queues.


Other machines use a Parallel Job Identifier (PJID) which is added
automatically to every outgoing message and verified at the
destination\cite{Papadopoulos93}.  Such schemes define 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 logical destination
mechanism supports such non-uniform communication patterns in a
protected fashion.


% implementation

The large number of queues at each 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}.  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.  There are several ways to implement non-resident
queues.  One method is to map the buffer space into the aP's DRAM and
the producer-consumer pointers into sP service space.  Messages can
continue to be received into and sent from non-resident queues with
the sP's assistance.  The sP implements the transition of a queue
between resident and nonresident status when directed by the OS.


%All user-level messages are sent with logical destinations.  Those
%logical destinations are used as an address into a translation table
%which produces a physical site number and a receive queue
%number\footnote{The receive queue number is produced by combining bits
%from the translation table with bits associated with the transmit
%queue.}.  That information is spliced into the message before it is
%sent.  




