%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
% ----------------------------------------------------------------------------
\label{sec:intro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The dataflow approach to parallel computing has been very successful
in at least two important aspects: (i) exposing parallelism and (ii)
using fine-grain parallelism to tolerate long latency operations and
synchronization waits.  These features have been demonstrated in
several studies on real machines\cite{monsoon-perf93,jpdc-tam93}.
There are, however, still several obstacles in making the dataflow
approach a truly viable solution to parallel computing.

The biggest challenge is to find a way of executing dataflow style
code efficiently on a wide variety of platforms.  One approach is to
improve the compilation of dataflow style languages to reduce
synchronization requirements, instruction counts, non-local
communication, and so on. Research efforts are underway to try to
achieve this goal without affecting the ability to expose parallelism
and tolerate latency.  Another approach is to identify the basic
architectural mechanisms that will efficiently support the dataflow
style of fine-grain parallel execution.  For pragmatic reasons the
resulting architecture should be as close to conventional
architectures as possible to take advantage of the decades of
experience in building and programming conventional processors, as
well as to make maximum use of existing hardware and software
subsystems.

This paper will concentrate on architectural features that are needed
to support fine-grain parallel execution.  We discuss the lessons we
have learned from the Monsoon
project\cite{Greg-monsoon,monsoon-perf93} and the early phases of
implementing the *T Multithreaded architecture\cite{StarT92}. Drawing
on these experiences, and the basic requirements of any parallel
computation, we suggest a desirable set of features to be incorporated
in our current machine called {\archname} (StarT, the Next
Generation). Essentially {\archname} has better provision for global
shared memory than either Monsoon or 88110MP
\cite{Supercomputing93-start}, a Motorola 88110 based implementation
of the abstract *T model presented in \cite{StarT92}. Our proposal
adds caching of global memory in a way that allows it to coexist with
the split-phase transactions and the multithreaded approach used in
Monsoon and the 88110MP.

The rapid improvements in stock microprocessors and the high cost and
complexity of developing a modern microprocessor imposes practical
constraints on what can be built in any experimental project that
wishes to have competitive performance.  {\archname} has to work
within these constraints, and thus represents many compromises.
Nevertheless, it incorporates many of the desired features. We hope
that the importance of the missing features can be investigated
through the effects of their absence.  The machine will also provide
the platform to continue research into compilation technology.

The rest of the paper is organized as follows:
Section~\ref{sec:parallel-programming} describes some of the models
for parallel programming. Section~\ref{sec:requirements} describes the
architectural concerns of running fine-grain parallel programs,
especially on stock hardware.  It also describes architectural
modifications that would allow dataflow programs to run much more
efficiently and how those modifications may help other programming
paradigms as well.  Section~\ref{sec:monsoon} examines Monsoon, an
implementation of a processor designed to be able to exploit
fine-grain parallelism, and how it performed.  That section ends with
a discussion of the deficiencies of Monsoon, and how they may be
fixed.  Section~\ref{sec:Start0-1} describes *T, an architecture that
addresses some of Monsoon's weaknesses while moving towards a
conventional microprocessor based machine.  The initial plan was to
build *T around Motorola's MC88110 microprocessor.  However, for
reasons beyond the control of the project, these plans had to be
abandoned in late 1993. While drawing up new implementation plans
centered around the Power PC architecture family, we took the
opportunity to explore incorporating global caches into our new
machine.  Section~\ref{sec:realizable-machine} gives a high-level view
of this machine.  {\archname} is an on-going project; thus, the
discussed implementation should not be assumed to be final.
Finally, we conclude this paper with a brief look at related work.

