% Introduction section for ISCA paper

\section{Introduction}

There appears to be widespread consensus that general purpose
supercomputers of the future will be Massively Parallel Architectures
(MPA's) consisting of a number of nodes in a high speed, regular
interconnection network.  This view has been eloquently summarized in
the slogan ``attack of the killer micros'' by Eugene Brooks of
Lawrence Livermore Laboratories \cite{Brooks89a}.  In this paper, we
focus on the organization of each node in such an MPA.

In an MPA, inter-node communication latency is expected to be high and
caching global locations is difficult.  In Section \ref{sec-analysis}
we present this issue in concrete terms by describing two specific
latency-related problems that must be performed well by MPA nodes.  In
Section \ref{sec-solutions} we systematically develop the logical node
organization of {\archname}, that addresses these problems.
Pronounced {\em Start}, it is named after the principal communication
instruction in the machine.  It can also be read as an acronym for
``multi- (*) Threaded'', a principal feature of the machine.  In
Section \ref{sec-abstract-model} we present some instruction set
details of the logical organization of {\archname}, and in Section
\ref{sec-daxpy} we discuss the coding of DAXPY.
In Section \ref{sec-implementation} we discuss possibilities for
physical implementation of {\archname}, and we conclude in Section
\ref{sec-compiling} with some discussion of compilation issues.

{\archname} is the latest step in the evolution of dynamic dataflow
architectures, starting with the MIT Tagged-Token Dataflow
Architecture (TTDA,~\cite{Arvind83a,Arvind90a}), the Manchester
dataflow machine~\cite{Gurd85} and the ETL SIGMA-1~\cite{Hiraki87b}.
In 1987-88, the associative waiting-matching store of these machines
was replaced by an explicitly managed, directly addressed token store,
by Papadopoulos and Culler in the Monsoon
architecture~\cite{Papadopoulos88a,Culler91a}.  Nikhil and Arvind's
P-RISC architecture~\cite{Nikhil88d} then split the ``complex''
dataflow instructions into separate synchronization, arithmetic and
fork/control instructions, eliminating the necessity of presence bits
on the token store (also known as ``frame memory'').  P-RISC also
permitted the compiler to assemble instructions into longer threads,
replacing some of the dataflow synchronization with conventional
program counter-based synchronization (in retrospect, Monsoon could
also be viewed in this light~\cite{Papadopoulos91a}).  {\archname} is
the latest step in this direction, eliminating the prior distinction
between processor and I-structure nodes, and attempting also to be
compatible with conventional MPA's based on von Neumann processors.

Throughout this evolution, our {\em system view\/} of an MPA (\ie\
viewing each node of an MPA as a black box) has remained constant, and
is in fact quite unique to dataflow architectures.  Inter-node traffic
consists of tokens (\ie\ messages) which contain a {\em tag\/} (or
{\em continuation}, a pair comprising a context and instruction
pointer) and one or more values.  All inter-node communications are
performed with {\em split-phase\/} transactions (request and response
messages); processors never block when issuing a remote request, and
the network interface for message handling is well integrated into the
processor pipeline.  Thus, TTDA, Monsoon, P-RISC and {\archname} are
properly viewed as steps in the evolution of the {\em node
architecture\/} of dataflow MPA's.

Important architectural influences in our thinking have been the
seminal Denelcor HEP~\cite{Smith78} and Iannucci's Dataflow/von
Neumann Hybrid architecture~\cite{Iannucci88a}, which incorporated
some dataflow ideas into von Neumann processors for MPA's (similar
ideas were also expressed by Buehrer and Ekanadham
~\cite{Buehrer87a}).  ETL's EM-4~\cite{Sakai89a}, Sandia's
Epsilon~\cite{Grafe88a}, Dennis and Gao's Argument-Fetching Dataflow
machine~\cite{Dennis88a}, and Dennis' multithreaded
architecture~\cite{Dennis91a} are also dataflow machines supporting
threads.  Finally, the Network Interface Chip by Henry and
Joerg~\cite{Henry91a} has had a direct influence on our implementation
of {\archname}.

Software considerations, \ie\ compiling, have played an equally
important role in the design of {\archname}.  Compilation of the
high-level parallel programming language Id has been central to our
research since the beginning~\cite{Arvind90a}.  Nikhil,
in~\cite{Nikhil90e}, and Culler {\em et al\/} in~\cite{Culler90a}
proposed P-RISC-like compilation models extended to allow additional
instruction sequencing constraints, making explicit the notion of a
thread.  Culler's model, the Threaded Abstract Machine (TAM) has been
implemented by his group and has been in use for almost two years,
providing a wealth of data on the nature of threads, locality and
synchronization~\cite{Schauser91}.  This experience has directly
influenced the {\archname} design.

Many researchers have arrived at similar mechanisms starting from
other vantage points (\eg\ Halstead and Fujita's
MASA~\cite{Halstead88a} and Maurer's SAM \cite{Maurer88}).  There are
very interesting comparisons to be made between {\archname} and recent
multithreaded architectures, notably the Tera Computer
System~\cite{Alverson90a} (a descendant of the HEP),
Alewife~\cite{Agarwal90a} and the J-Machine with Message Driven
Processors (MDPs)~\cite{Dally87a}.  Undoubtedly, aspects of these
machines will influence concrete {\archname} designs.
