%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Fine-Grain Parallel Programs on Stock Hardware}
% ----------------------------------------------------------------------------
\label{sec:id-on-stock}
\label{sec:requirements}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


A natural question to ask dataflow architecture researchers is ``why
not use stock hardware?''  Given the availability of very high
performance microprocessors, it is a very relevant question.  The
problem is that the demands of fine-grain parallel execution are
different than the demands made by sequential code.  Current
microprocessors are optimized for the latter.  It is a challenge to
determine whether processors features for fine-grain codes can coexist
with existing features for sequential codes.

\subsection{What is fine-grain parallel execution?}

Dataflow graphs offer perhaps the most mature model for fine-grain
parallelism.  These graphs are usually generated by a compiler from a
functional language (see \cite{Arvind90} for an example).  We briefly
explain the execution of a dataflow graph.

The nodes of a dataflow graph specify the operations to be performed
on the values that flow on {\em tokens} along arcs between the
nodes.  Each token also carries a {\em continuation} consisting of a
node number, an instruction pointer and a frame pointer.  A
continuation specifies the computation to be done with the value on
the token.  Execution starts with a pool of initial tokens.  When a
token is processed, a waiting/matching store is checked to see if the
token's partner, if any, is already present.  If not, the token is
inserted into the waiting/matching store, and the next token is
processed.  If the synchronization is successful (the correct partner
token is found), the node is fired ({\em executed}) and the
resulting values are put back into the pool.  The order in which
tokens are processed does not affect the result of the computation,
but may greatly affect the running time and the resources required.
To avoid deadlocks, it is essential that a value that fails to
synchronize ({\ie} one or more of its partners has not yet been
processed) should not block the processing of other tokens.

Our dataflow graphs allow global memory in the form of I-structures
which are write-once, read-many-times data structures.  Accessing an
I-structure location is done by splitting the read operation into two
separate phases (see \cite{Arvind90} for details). In the first phase,
the read (fetch) is initiated and the processor is then relinquished
to another thread.  The read request consists of a continuation and
the address to be read.  In the second phase, the read is performed
and the result is returned (actually forwarded) to the waiting node,
specified in the continuation supplied on the request tokens.

In such a {\em split-phase} operation, the actual reading of the
value may occur on some processor other than the one where the read is
initiated.  Depending on the dynamic execution order, a value to be
read may not have been written yet.  If it is unknown whether a value
being read has already been written, the reads and write require some
synchronization.  Synchronizing reads (\eg I-structures) may take an
arbitrary amount of time to complete, since an arbitrary amount of
time may elapse before the value is actually written.  In the case
where a read arrives before the write of a location, the second phase
of the read request is deferred ({\ie} queued up) until the write
occurs.  It is important to note that deadlocks are not possible (as
long as the program does not include any cyclic data dependence)
because the node waiting for a reply does not block any processor or
memory operations.  Once the write is completed, the request is
satisfied in the usual manner.

If every node of the dataflow graph is a simple operation like add or
memory fetch, an inordinate number of synchronizations need to be
performed, because almost every instruction requires synchronization.
It is easy to see, however, that a node could consist of more than one
operation.  Operations within a node could themselves be organized as
a dataflow graph or as a simple linear sequence of instructions.  We
call the latter case, where the nodes in the dataflow graph are
sequences of instructions, {\em multithreading}, and each of the
linear instruction sequences, {\em threads}.  This model of
multithreading is essentially identical to the Threaded Abstract
Machine (TAM) proposed by Culler {\em et. el.}
\cite{jpdc-tam93}.  TAM distinguishes between inlet threads
and computation threads --- the former are threads executed in
response to incoming messages.  A thread scheduling model is also part
of TAM.  There are several other variants of multithreaded models --
depending on whether threads are allowed to be suspended and resumed,
and the types of instructions that can be included in a thread (see,
for example, Traub \cite{traub91c} or Iannucci\cite{hawaii-isca}).
Nikhil\cite{Nikhil93a} is a good introduction to compiling an
implicitly parallel language into multithreaded code.


\subsection{What architectural support does multithreading require?}

Multithreading requires some hardware support to run efficiently.  In
the following, we discuss the categories of hardware support that
would be useful, and how current stock processors fail to provide that
support.  

\subsubsection{Message Passing}  

Messages are used to start threads, to make a request or reply, or to
pass information.  Since every instance of a dataflow graph node could
potentially be executed on a different processor, a huge number of
interprocessor messages could be generated by a multithreaded program.
A good network interface is probably the single largest improvement
that can be made to a processor to support
multithreading\cite{Supercomputing93-start}.  A fast processor/network
interface that requires the fewest number of processor cycles to send
and receive messages would be vital.  The efficiency of the interface
can be measured in terms of the number of processor cycles needed to
send a certain unit of data, say a 64-bit word.  The raw network
latency is somewhat less critical, since multithreading can be used to
tolerate it.

The fastest possible network interface can format and send a message
in a single cycle.  Given a standard RISC processor, formatting and
sending a message in a single cycle would require using registers to
provide the necessary pieces of the message, forcing large hardware
modifications to insert the network interface into the processor
itself.  It is possible, however, to get a reasonable network
interface through a normal memory bus.  The cost of sending a message
could still be low as the processor does not have to wait for the
message to actually get out of the chip.  The latency of receiving a
message, however, cannot be hidden, and may be significant.  Pipelined
memory systems in modern aggressive microprocessor adds many stages
between the processor and the memory bus, and may also introduce the
possibility of out-of-order stores.  These make sense for executing
long sequential threads, but hurt the performance of a bus based
messaging interface.

Most commercial parallel machines take a substantial amount of time to
get to the network, say 50 cycles or more if external hardware support
is available (see CM-5 for example), or 1000's of cycles if software
gets involved (see Paragon, for example).  This level of processor
latency encountered in accessing the network makes communication very
expensive and thus, limits compilation options.

\subsubsection{Thread Creation}  

In order to execute threads, they need to be created.  When a
multithreaded program first starts execution, an initial pool of
threads is produced by the startup system code.  The running program
is then responsible for generating its own threads to get its job
done.  A mechanism for creating threads is a {\em fork}, which allows
the running thread to split itself and execute down two paths.  A
minimal encoding of fork will require an instruction pointer which
indicates one branch of the fork --- the other branch being implicitly
the next instruction.  Thus, forking can be performed by a single
instruction which takes an instruction pointer as an argument.
Clearly, the cost of thread creation determines the rate at which
parallelism can be expanded.  It also determines whether it is worth
spawning parallel threads at all.

Stock processors do not have any special support for thread creation.
Creating a thread requires software conventions and some sort of
thread queue which, on stock hardware, also needs to be managed by
software.

\subsubsection{Synchronization}  

When more than one value used for the same computation arrive on
separate, arbitrarily ordered messages, the values must be {\em
synchronized}.  Synchronization ensures that the necessary values are
available before continuing past the synchronization point.  In a
dataflow graph, each node must synchronize all of the incoming values
before it can be fired.  Though the frequency of synchronization
events vary greatly from program to program, our preliminary compiler
work indicates that synchronization events occur around once per 10
abstract dataflow instructions, which would expand to no more than 40
RISC instructions.  This makes synchronization a very frequent event.

Synchronization required for multithreading can be emulated with
software counters in normal memory locations.  We call these locations
{\em synchronization counters}.  The essence of synchronization is an
atomic read-modify-write to a the memory location, followed by a
branch on the result.  Synchronization is best viewed as a
memory-to-memory operation because it is rare that the same
synchronization counter is accessed more than once in a thread.  Thus,
a typical sequence of instruction to implement a synchronization will
include a load, a decrement, a jump conditional and a store, with the
additional requirement that atomic access to the counter is maintained
between the load and the store.  Such a sequence of instruction is not
very cheap, particularly when this is expected to happen every 50 or
so instructions.  Thus, specialized hardware support in this area is
highly desirable.

Most stock processors have some hardware support for synchronization,
in the form of test-and-set, exchange-reg-with-mem,
load-locked/store-conditional, memory-barrier, etc.  These
instructions essentially enforce some atomicity constraints which
would be hard to emulate otherwise.  They do not, however, provide the
type of synchronization we require.  Also, these multi-cycle
instructions usually disrupt the processor pipeline.  It is probable
that emulating synchronization using the scheme discussed in the
previous paragraph will be easier and more efficient than using these
specialized synchronization instructions.

%Such support can perhaps be in the form of {\em presence bits} on
%memory words and registers with accompanying hardware to operate on
%them.  Since presence bits usually make the word size awkward, some
%implementations designate some special bit patterns in the value space
%to indicate a missing value, and rely on processor traps to detect
%these special bit patterns.


\subsubsection{Context Switching} 

Whenever a synchronization event fails or a thread terminates, a {\em
context switch} must occur.  A context switch conceptually requires
the previous state to be saved and the new state to be installed into
the processor.  Of course, only the state that has been modified and
needs to be preserved for later use needs to be saved.  The cost of
each context switch depends on the size of context to save and
restore.  This is related to the size of the thread, with shorter
threads having smaller states.  However, shorter threads also entail
more frequent context switching.  In general, the lower frequency of
context switching for longer threads tend to outweigh the increased
cost per switch, making it cheaper to run longer threads.
Multithreading with short threads is therefore at a disadvantage.

This disadvantage is aggravated on commercial microprocessors by the
principles behind their design, namely, to run long threads and expect
infrequent context switches.  Accordingly, the processor is optimized
to take advantage of that locality with a sophisticated memory
hierarchy that makes frequent access to the lower hierarchy a costly
event.  In some sense, stock processors are designed to make context
switching {\em expensive} in order to process long threads more
efficiently.

Faster context switching can take on many different flavors.  The
simplest technique is to eliminate the memory hierarchy and allow the
processor to address a monolithic memory directly.  Thus, context
switching amounts to loading a program counter and a frame base
register.  The obvious problem with this is the less competitive speed
and bandwidth of the large memory as compared to registers and cache.
While very long pipelines and multiple banks of memory could
conceivably alleviate this problem, elimination of the local state
will probably slow down sequential threads.  

Another solution is to have multiple register files, each dedicated to
a thread, and to switch between them.  One might interleave threads in
the pipeline and force a context switch every cycle \cite{HEP,Tera},
or one might switch to another thread on encountering a long latency
operation \cite{Agarwal93}.  On the University of Tokyo's UNIRED-II
processor\cite{UNIRED-II} the frequency of thread switching depends on
the number of active threads.  One might also allow one register file
to be swapped while another is in use.  Another possible related
solution is the Named State Register File\cite{Nuth93} which uses a
cache instead of a register file and has multiple pipeline registers
to allow very rapid switching between threads.  Yet another solution
is to permit multiple instruction streams to execute on the same set
of execution units.  If sufficient load-store unit bandwidth is
available, this could allow the overlap of useful computation with
context switching overhead, thus effectively masking the cost of
context switching.

\subsubsection{Thread and Message Scheduling}

The pool of ready threads in our model needs to be scheduled for
execution in some way.  The ordering method could be as simple as LIFO
or FIFO or could be very complicated, such as taking the content of
the threads into account.  As mentioned earlier, a bad schedule could
explode the amount of resources required to run the program.  Since
messages/tokens often contain very small amounts of work, it is
generally too expensive to allow software to do much scheduling.

Automatic hardware scheduling of the ``next'' thread upon thread
completion or suspension takes far fewer cycles than any software
scheduler.  Hardware queues are, however, less flexible in terms of
the ways in which the thread queues can be managed.  No commercial
processor has direct hardware support for thread queues.  

\subsubsection{Global Memory} 


Access to global shared memory is a fundamental issue of parallel
processing.  It is very important for the parallel execution of most
high level languages.  Thus, we discuss the issues in greater detail
in the next section.

%----------------------------------------------------------------------------
\subsection{Accessing Global Memory}
\label{sec:global-memory}
%----------------------------------------------------------------------------

Researchers generally agree that it is important to support the
abstraction of a global shared memory for the programmer even though
reality dictates that the memory has to be physically distributed on
any scalable machine.  There are several ways of supporting the global
shared memory abstraction on machines with physically distributed
memory.  The two basic methods for accessing global memory are (1)
protocols built on top of message passing and (2) global caching.  The
method provided has become the most popular way of differentiating
parallel computers.  In this section, we will discuss the strengths
and weaknesses of these two methods.

% ----------------------------------------------------------------------------
\subsubsection{Global Shared Memory through Message Passing}
% ----------------------------------------------------------------------------

Message passing alone allows us to implement certain forms of global
shared memory.  A processor $a$ which desires the value from a
location in the memory of processor $b$ can send a message to $b$
requesting that value.  After $b$ receives the request, it replies to
$a$ with the desired value.  

What does $a$ do while it is waiting for $b$ to respond?  It could
just wait for the result, not doing anything in the meantime.  Just
waiting, however, is prone to deadlock, since $b$ could be
waiting for $a$ to return a result before it responds to $a$'s
request.  Either an alternative path for other processors to access
$b$'s memory is required, or all processors must periodically satisfy
other processors' requests.  The former solution is used by *T
(discussed in Section~\ref{sec:Start0-1}) and is showing up in
commercial machines such as the Cray T3D\cite{T3D}.  This solution
works as long as the value to be read is available.  The latter
solution, periodic polling, makes code generation more difficult
and degrades sequential thread performance.  Even if the polled
message is just put aside, it can still negatively affect the caching
behavior of thread in the processor pipeline.  

In general, if the value to be read is not yet available, it is
necessary to suspend the current thread and schedule another.  This
requirement stems from the fact that processor $a$ may be required to
execute a thread that creates, directly or indirectly, the value being
read.  If the processor is not relinquished, deadlock is possible.
The request and reply messages must contain some information, a
continuation, to indicate what should be done with the data when it
returns to the requesting processor.  Separating the request for a
global memory location from its actual use is essentially the dataflow
split-phase operation.

Switching threads has another good property; it overlaps computation
and communication, potentially increasing processor efficiency.
Reading a value from another processor potentially takes more than a
hundred cycles in most parallel machines of reasonable size.  It
involves two message launches, two network trips, execution of two
message handlers, a load and perhaps a context switch at the
destination.  Waiting for every global read will clearly destroy any
chances of performance for the vast majority of programs.  Switching
threads, however, requires a context switch, scheduling a new thread,
and other such overhead.  If the aggregate overhead of switching a
thread is longer than the total latency of remotely accessing the
global location, it is not worth switching threads.

It is clear that the performance of global memory through message
passing depends heavily on the performance of context switching and
the processor/network interface (of course, the basic bandwidth of the
network is also important, but is generally not the limiting factor).
The faster the context switch, the greater the overlap of
communication and computation.  If switching cannot be done quickly,
communication cannot be overlapped with computation since the latency
of remote fetches is effectively added to the total computation time,
often negating any advantage of using a parallel machine.  Machines
that do not have some special hardware for handling memory requests
from other processors must context switch twice when doing a
split-phase operation, first when the remote processor switches
contexts to handle the request and second when the requesting
processor switches contexts to accept the response.  For these
reasons, emulating word-level access to global memory on message
passing machines using stock processors is generally inefficient.
These characteristics bias the compilers to generate long threads and
large messages, hallmarks of coarse-grain parallelism, to achieve
acceptable performance.


%----------------------------------------------------------------------------
\subsubsection{Global Shared Memory Through Caching}
%----------------------------------------------------------------------------

The other basic approach to providing global shared memory is through
the use of global caching, {\ie} caching global data in computation
processors' local caches.  The requesting processor $a$ performs a
load on a global location exactly as it would a local location; it
checks the cache first.  If the value is found in the cache, the
computation continues as it would in a sequential machine; the value
is put into a register directly.  If the value is not in the cache,
however, the value is fetched from its remote location through the
standard memory bus interface of $a$.  There must be some device
sitting on the memory bus which recognizes global addresses,
satisfying the requests by communicating with the memory of processor
$b$ that actually owns the desired value.

In the simplest case, when $a$ misses on a global location in the
cache, $a$ waits until the value is returned to it.  If $a$ never hits
in the cache, the situation becomes exactly the same as for message
passing when context switching takes longer than the round-trip
message time.  Clearly, the more $a$ hits in the cache, the fewer
remote fetches of cache data need to be done.  Any miss of global
values in the cache, assuming that $a$ waits for the value, add the
fetch latency to the critical path.  The execution time includes all
the latency from accesses to global memory.


Since current processors have scoreboarding, they can execute past a
load until the loading data is actually needed.  Future
microprocessors will allow multiple outstanding memory operations.
All of these features allow some overlap of communication and
computation.  How much is actually achievable depends on the program
behavior.  The potential for overlap, however, is still far less than
in the split-phase model.

There are several reasons for stalling the processor on a miss rather
than switching threads.  The most important reason is that if the
processor suspends the waiting thread and switches to another thread,
there is no guarantee that the cache line fetched from the remote
location will still be in the cache by the time the suspended thread
is resumed.  Additional mechanisms such as locking a cache line
(analogous to locking a page of physical memory during a page
fault), or placing the fetched line in some buffer that will not be
flushed would be needed.  Such schemes need to be careful not to
introduce deadlocks.  \cite{kubi92} describes how this problem is
dealt with in Alewife.  A second reason is that unless multiple
hardware contexts are provided, thread switching can be expensive,
especially since code compiled for such machines usually keeps as much
valid state in registers as possible.  A third reason is that most
code compiled for such machines is not multithreaded at the
processor level; there is usually only one single thread running on
each physical processor.

The big problem with global caching is keeping the caches coherent.
If two processors each have a copy of a cache line, and one modifies
that line, the other processor must somehow be automatically notified
of the change.  If the notification is not automatic, there is no
point to general purpose global caching since processors must then
always check to see if the cached object is up to date.  Some scheme
for dealing with the coherency of data is needed (see
\DASH\cite{Lenoski&others92,Lenoski90},\KSR\cite{ksr},
SCI\cite{sci92}, and
\Alewife\cite{Alewife-overall} for examples of specific coherency
protocols).  Cache coherency protocols for managing cache coherency in
a distributed memory machine are very complicated.  Also, support for
global coherent cached memory traditionally requires a fairly sizable
investment in hardware.

When there is sufficient locality in the code, global caching works
well (see {\DASH} results for examples).  Prefetches can also be used
to bring data into the cache before they are actually needed.
However, the performance is sensitive to the nature of the code, and
how code and data is distributed.  The same study described examples
like the {\sc Mp3d} code in the {\sc Splash}\cite{splash} benchmarks
where poor locality killed performance.

%----------------------------------------------------------------------------
\subsubsection{Split-Phase verses Global Caching}
%----------------------------------------------------------------------------

It is clear that both split-phase operations and global caching have
their respective advantages and disadvantages.  Split-phase operations
can hide communication latency but demand fast context switching and
network interfaces.  Using proper message handlers, messages of any
size and I-structure synchronized accesses can be supported.  Global
caching may reduce the average latency but does not hide it when a
cache miss occurs.  It is limited to cache-line sized accesses and
requires more hardware support than message passing.

Is there a clear winner between the two methods?  The short answer is
no.  We will discuss that question in greater depth in
Section~\ref{sec:daxpy}.

\subsection{Does Hardware Support for Fine-grain Parallelism help
other Programming Models?} 


It is not difficult to see that all the hardware modifications
proposed above would help execution of programs written under other
paradigms.  The question is by how much.  The relative importance of
these features crucially depends upon the programs to be run.  In
parallel computing, much more so than in sequential computing,
programmers take into account the characteristics of the machine on
which the program is to be run.  Thus, it is difficult to determine
the importance of each feature simply by studying the behavior of
existing parallel applications.  In some sense, the other paradigms
evolved to run on the available parallel hardware, and thus do not
context switch, synchronize or access the network very much.  Thus,
the impact of the described modifications would be modest for most
paradigms other than fine-grain parallel execution.

Context switching and synchronization support only helps if you plan
on switching contexts and synchronizing very often.  Unless the
threads are generated automatically, it is unlikely that a programmer
will write a program with a large number of threads or complex
synchronization.  It is simply not feasible for a user to manage
fine-grain parallel execution.  Context switching and synchronization
support, therefore, are much less important in data parallel and
control parallel models.

A fast network interface, on the other hand could potentially help
other paradigms a great deal.  Every parallel program has to access
the network sometime, and if that access time was reduced, less care
would be required to minimize communication.  Performance would
increase on codes that use the network extensively.

Support for shared memory will also help the compiler writers of
almost all the high-level languages, including HPF.  The global shared
memory abstraction greatly simplifies access to distributed memory.

Even if all the features discussed in the previous sections could be
included in a modern RISC processor without negatively affecting its
performance, it would still be difficult to convince the manufacturer
to include these features in his next generation processor.  There is
never sufficient silicon to include all one wants.  However, if a
feature, such as a better network interface, is useful for most
programming models, its inclusion is more likely to be acceptable.
