%\documentstyle{csart}

%\begin{document}

%\newenvironment{linear}{\\ \begin{minipage}[t]{\textwidth}}{\end{minipage}}

\section{\label{introduction}Introduction}

     This article discusses efficient spawning of process networks
on a parallel computer.
It starts from the premise that communication between remote processes
will go through ``virtual channels''.  A virtual channel is
a CSP-style \cite{csp} communication channel implemented on
some packet routing network
\footnote{Sometimes distinguished from a ``hard channel'', implemented
across a direct physical link, or a ``soft channel'' implemented
within a single processor's memory and connecting two processes
running on the same processor.}.
It also assumes that
a process running anywhere on the machine can start up another
process somewhere else on the machine at any time.  The parent process
should be able to supply a child with some set of channels
for its communication purposes.

     These services are provided in our case by the Virtual Channel
Router (VCR) developed by Debbage, Hill and Nicole \cite{vcrref1}
under Esprit project 2701 (PUMA).  VCR is, in part, an emulation of
features which will be supported in hardware by the T9000 generation
of Inmos transputer components \cite{t9000} (though it may be that not all the
dynamic features of VCR exploited during this work will be particularly
strongly supported by the T9000).

     The CSP or {\em occam} \cite{ocref} concurrent programming models rely
on the medium of synchronous point-to-point
logical channels for communication between processes.  One advantage
of this mechanism is that channels map
straightforwardly onto the physical wires of simple hardware (for example,
first generation transputers \cite{transputer}).
This particular motivation has become less compelling as MIMD
systems have moved away from providing restricted
local communication, towards
hardware-supported routing of messages between arbitrary processors.
Strong arguments for the channel model remain, however.
For one, a channel can be efficiently implemented on top
of packet routers with a single buffer per channel;
the channel discipline ensures that errant user programs can't infect the
packet delivery system with deadlocks.  For another, the clearly
defined semantics
of channel communication simplify production of reliable code.  Further
aesthetic and formal arguments in favour of the channel
are given, for example, in \cite{csp}.

     The discussion will be mainly in terms of the {\em occam} language.
Obviously similar things can be done in any language provided with
a library of functions for the kinds of service outlined
above---VCR entry-points are available for FORTRAN and C programs,
as well as {\em occam}.
In a number of ways {\em occam} as currently defined is
less than ideal for describing dynamic algorithms, and a slightly extended
form of {\em occam} notation will be introduced in section \ref{dynamic}
as a vehicle for presentation of algorithms.

     The original implementations of {\em occam} only
provided static placement of top-level user processes on processors.
Although {\em occam} allows any process to fork into several processes
at any time through the \verb$PAR$ construct,
early implementations have forced processes
spawned in this way to run on the same processor as their parent.
The dynamic procedures of the VCR library can be viewed as a run-time system
for an enhanced {\em occam} in which this constraint is
relaxed 
\footnote{At the time of writing not all these features have been fully
integrated with the compiler.}.  These VCR facilities allow a process
running on one processor to start a process with which the parent may
communicate unrestrictedly on another processor.  They
are reviewed more fully in section \ref{vcr}.

     The remaining sections describe an application of these basic
capabilites---namely to run-time spawning of fully connected networks
of processes on some available set of processors.

     The work presented here was originally motivated by the configuration
requirements of a distributed-data communication library developed in the
applications workpackage of the PUMA project \cite{acl}.
Some aspects of those requirements show through in details of section
\ref{implement}, although, by and large, I have tried to make the
presentation here self-contained.

%\end{document}


