\renewcommand{\editdate}{Nov 21 15:27 1997}
\renewcommand{\mytitle}{requirements.tex}
\renewcommand{\useredit}{rudolph}
%\markboth{Draft File: \mytitle \ \ \ \  Last Edit: \editdate(\useredit)}{Draft File: \mytitle \ \ \ \ Last Edit: \editdate (\useredit) }


\section{Requirements}
\label{sec:requirements}
%~~~~~~~~~~~~~~~~~~~~


The basic requirement is to form a scalable and open parallel
processing system from a hardware platform consisting of commercial
SMP's and a high speed interconnection network.  It is envisioned that
the system will be used for a wide range of high performance
applications, including both technical and commercial computing.
Thus, the main system requirement is to support multiuser,
multithreaded, parallel jobs in a time-sharing mode that permits
flexible scheduling.  The main communication requirement is to support
a wide range of distributed shared memory and user-level
message-passing models.  The following requirements for these flexible
communication mechanisms implicitly include low development cost as
well.

\subsection{Shared Memory}
%~~~~~~~~~~~

The basic requirement is to support a large cache-coherent shared
memory space.  Because applications exhibit a range of shared memory
data usage patterns and the efficiency of any particular coherence
protocol depends on the usage pattern, an efficient shared memory
implementation should allow for multiple protocols.  In addition, in
order to provide very large caches to minimize conflict and capacity
cache misses, it makes sense to use local DRAM as a cache for global
state when there is locality of reference, as done with S-COMA
\cite{stenstrom92}.  When shared memory is used in a sparsely accessed
mode, it makes sense to support a NUMA \cite{Numa-q} style of shared
memory.

Shared memory models are still evolving because of both programming
and performance concerns. It is likely that there will be several
different models for shared memory and within each there may be
several adaptive coherence protocols to exploit particular access
patterns.  Hence, flexibility is of critical importance.  The system
should provide support so that cache coherence protocols are
programmable and multiple protocols can operate at the same time,
although on different addresses.

\subsection{Message Passing}
%~~~~~~~~~

Different parallel programs have different message passing
requirements.  Consequently, flexible mechanisms for managing, sharing
and polling message buffers are required to build an efficient message
passing substrate. Some programs have very static message passing
patterns; it is possible to determine at compile time which processor
will send messages to which other processors, and at what time.
Others have more dynamic message passing patterns, which can only be
determined during runtime and may even vary from run to run.

Different programs, or different phases of the same program, tend to
send messages of very different sizes, which come from very different
levels in the memory hierarchy.  In order to support a wide range of
message passing codes efficiently, the following spectrum of message
types needs to be supported:

\noindent
{\bf Short:}
Data for short messages consists of a word or two that generally
resides in registers and is to be sent as soon as possible.  Short
messages are generally received in registers as well to permit their
immediate processing.

\noindent
{\bf Medium:} Data for medium messages is generally several words in
length.  As such, they are likely to reside in the cache when ready to
be sent.  Similarly, their reception should be into the cache.  Such
messages are required for cache coherence protocols.

\noindent
{\bf Long:}
Data for long messages is mostly if not entirely found in memory.
Thus, a long message communication involves a memory-to-memory
transmission often accompanied by shorter message transmissions
indicating when the whole message body is ready for transmission and
when it has been successfully received.

Efficiency concerns dictate that message latency, \ie/, end-to-end
transmission time as well as processor overhead time, should be
proportional to the message size.  Thus, short messages should have
very low latency while long messages may suffer longer latencies.
Finally, a protection mechanism is required to prevent unauthorized
transmission and reception of messages.

\subsection{System Requirements}
%~~~~~~~~~~~

There are few ``cluster'' operating systems in use today. Both to keep
the development costs down and for greater fault tolerance, we require
each SMP in the cluster to run its own copy of the operating system.
Parallel or cluster wide services should be layered as extensions to
the standard OS. By limiting the interaction of OS's on different
sites to a well defined and protected interface, it is easier to
isolate faults to individual SMP.

A multi-user environment in an open S\&M system must provide
protection mechanism that ensures the logical independence of
communication belonging to non-interacting jobs.  This means not only
the ability to control the sending and receiving of messages, but also
confining message traffic blockage to the perpetrating job.  Most
parallel machines today enforce protection via job scheduling. The
processors are assigned to a parallel job as a {\em gang} and the job
is not scheduled until the system has been drained of all messages
belonging to the previous job. 

Using gang scheduling as the means of enforcing protection prevents
concurrent use of the network by user applications and system support
facilities, such as a parallel file system.  The need for more
sophisticated protection mechanisms is especially acute in an S\&M
system, due to the presence of both system generated shared memory and
user generated message passing traffic in the network.

No current distributed parallel systems adequately addresses job
scheduling in the presence of page faults and temporal variations in
program parallelism.  For many, the protection model requires gang
scheduling and leaves no other options.  When a page fault occurs,
such a scheduling regime either allows the page faulting processor to
idle or to run a sequential job.  Ideally, the scheduler should allow
a parallel application's processor utilization to expand and contract
over time, with other parallel jobs scheduled on unused processors.

Finally, parallel programs may employ shared memory and message
passing to interact both with its constituent processes and threads
and with the processes and threads of other concurrently executing
parallel programs.  For example, a server application may want to
communicate with a number of client applications without allowing a
client to communicate directly with other clients.  This requires the
protection scheme to enforce non-monolithic, and possibly asymmetric
communication domains.

%%%%%%%%%%%%%%%%%%%
%  End of Section %
%%%%%%%%%%%%%%%%%%%

