\documentstyle[12pt]{article}

\input fig
\input illustrations
%\input macros
\def\illustrationfileprefix{/tmp_mnt/home/jj/sakai/mit/paper/}

\topmargin = -1.5cm
\oddsidemargin = 0cm
\evensidemargin = 0cm
\textheight = 23.5cm
\textwidth = 16cm
\begin {document}
\title {Synchronization and Pipeline Design for a Multithreaded
Massively Parallel Computer
\thanks{This paper describes research done at the Laboratory
for Computer Science of the Massachusetts Institute of Technology.
Funding for the Laboratory is provided in part by the Advanced
Research Projects Agency of the Department of Defense under
Office of Naval Research contract N00014-89-J-1988.}}
\author {{\bf \Large Shuichi Sakai
\thanks{also belongs to the Computer Architecture Section,
Computer Science Division, Electotechnical Laboratory, 1-1-4, Umezono,
Tsukuba, Ibaraki 305, Japan. Email address: sakai@abp.lcs.mit.edu}}
\vspace{0.5cm}\\
Computation Structure Group\\
Laboratory for Computer Science\\
Massachusetts Institute of Technology}
\maketitle
\begin{abstract}
This paper examines two basic functions in a massively parallel
computer - synchronizations and pipelining - and proposes 
efficient implementations. 
The data-driven synchronization mechanisms which
currently exist are carefully analyzed from the viewpoint of
efficiency and hardware complexity, and the optimized synchronization
mechanism is proposed.
The pipeline structure 
for a massively parallel computer
containing the proposed synchronization is presented.
Performance improvement methods for this pipeline are proposed, 
cost-effectiveness of the proposed method is considered, 
and related issues are listed.
Lastly, future problems including software issues are presented.
\end{abstract}
\section{Introduction}
The main stream of research and development of dataflow architectures
is being shifted from pure dataflow computers toward multithreaded
computers. This tide includes :
(1) the activities at MIT,
from TTDA \cite{arvind80} to the Hybrid Architecture \cite{iannucci88}
and Monsoon \cite{greg90}\cite{greg91},
and from Monsoon to *T \cite{nikhil92};
(2) the activities in ETL, 
from the SIGMA-1 \cite{hiraki87} to the EM-4 \cite{sakai89},
and from the EM-4 to the EM-5 \cite{sakai912};
and the activities in Sandia National Laboratory,
from the Epsilon-1 to the Epsilon-2 \cite{sandia91}.
Clearly these multithreaded architectures still maximally
exploit the advantages of dataflow architectures;
they tolerate long latencies by cheap local synchronization, and
they are suited to the programming model which naturally extracts
maximum parallelism.
In addition, they are also advantageous for local sequential computation,
since they include a von Neumann architecture (typically,
a RISC architecture) which efficiently executes sequential threads
with a set of registers and an advanced-control pipeline.

The concept of multithreading is not exclusive to the extension of
dataflow architectures.
For instance, the Denelcor HEP
\cite{smith78} and the Tera Computing System \cite{thistle88} are
multithreaded computers in the sense that
they execute and control multiple threads in a single pipeline.
Dally's J-machine \cite{dally89} does not interleave multiple threads,
but it can switch between threads very quickly;
thus, we can say that it actually supports the multithreaded computation.
In addition, Dally's new machine, called the M-machine, has a mechanism of
thread-interleaving \cite{keckler92} where many threads can exist
inside a processor chip at the same time.

In all of these machines, the common and central design decisions
are how to design an efficient synchronization mechanism and
how to pipeline the machine?
These two functions seriously influence
the performance of the multithreaded system.

This paper examines the functions of synchronization
and pipelining,
and proposes ultimately efficient mechanisms for them. 
Firstly, the data-driven synchronization mechanisms which
were already proposed are carefully reconsidered from the viewpoint of
efficiency and hardware complexity, and the new synchronization
mechanism is proposed (Section 2).
Secondly, the pipeline structure 
for a processing element of a massively parallel computer
including the proposed synchronization is presented (Section 3).
Thirdly, methods to improve performance proposed this
pipeline are proposed (Section 4).
In Section 4, cost-effectiveness of synchronization and
pipelining are also considered,
and related issues are listed.
Lastly, future problems including software issues are presented.

The mechanisms proposed here can be implemented using
the current VLSI technology.
We can provide an ultra-high performance
massively parallel system  such that the communication/synchronization 
performance is strictly comparable to the computation performance,
and the latency of each processor
(time from packet input to result packet output)
is fairly short, e.g. less than or equal to 5 RISC clocks.
\section{Optimizing Data Driven Synchronization}
\subsection{Data-Driven Synchronizations}
This subsection summarizes the data-driven synchronizations
which have already been proposed
and reexamines their merits and defects.
\footnote{Here, the author concentrates on the data-driven synchronizations
on a dynamic dataflow model. We have another model, {\it a static model}.
Although a modern "static architecture" \cite{dennis91}
is also a challenging architecture,
this paper does not include the architectural optimization of it.}

Earlier version of dynamic dataflow machines used
associative mechanisms, such as hashing mechanisms,
to implement data-driven synchronization (token matching).
For instance,
Manchester Dataflow Machine \cite{gurd85} uses a parallel hash table
to provide a pseudo-associative access for token matching.
Another example is 
the SIGMA-1 \cite{hiraki87} system
whose processor contains a chained hash mechanism.
Matching by hashing has the following advantages.
\begin{itemize}
\item Efficient use of memory.
\item Flexibility to implement different matching schemes;
sticky token matching for example.
\end{itemize}
On the other hand, there are several drawbacks.
\begin{itemize}
\item Complexity.
\item In case of a hash miss, pipeline bubbles are generated or
an exception occurs.
\item Difficulty to understand what is happening.
\end{itemize}
In the next generation dataflow machines,  these defects were eliminated
by introducing a frame-based matching.
The explicit token store (ETS) in Monsoon
\cite{greg90}, the direct matching in the EM-4 \cite{sakai89} and
the direct match in the Epsilon \cite{sandia91} are such mechanisms.

Here the former two are briefly described and criticized
in preparation for proposing a new scheme of a data-driven
synchronization.

\vspace{0.5cm}
\noindent
(1) Explicit Token Store in Monsoon

Figure 1 illustrates how matching is operated in Monsoon.
The method by which tokens find their partners is
called the Explicit Token Store  (ETS) \cite{greg90}.

\begin{fig}{ets}{Explicit Token Store.}
\illustration{ets}
\end{fig}

In Monsoon, an area for matching
is exclusively reserved for a single function instance.
This area is called a frame and a frame is allocated
at the function invocation time.
Matching occurs at a certain word in the frame.

In ETS, every token has a field of IP and FP.
The IP is an instruction pointer which points
the address of the instruction invoked by this packet,
and the FP is a frame pointer which points the top of the frame.
As each instruction has a field which indicates the offset of
matching, the matching address can be calculated
by adding FP and the offset (Figure 1).
Each data word in the frame
is associated with a flag memory word where the synchronization
flag is stored.
In the case of a dyadic matching,
Monsoon test-and-sets this flag in a single cycle.
If the partner has already arrived,
it clears the flag, reads the partner data and executes an instruction.
If the partner has not yet arrived, then
the token data will be stored in the memory word of matching address
and the flag is set.

At the end of the function execution,
the frame is released for a future reuse.

The advantages of ETS are as follows.
\begin{itemize}
\item It does not need any associative mechanisms.
\item It does not generate a pipeline bubble caused by
a hash miss.
\item The location of the matching is written in the instruction,
so debugging and tracing are quite easy.
\item A frame word can be reused even by another instruction
in the same function instance, if there is an ordering between two nodes.
\end{itemize}

However, ETS has a few defects as described below.
\begin{itemize}
\item An instruction fetch is always necessary, even if
the matching fails. 
\item An instruction fetch and matching must be serialized,
and the former always occurs before the latter occurs.
This makes pipeline length longer and thus causes a long
turnaround.
\end{itemize}

These two defects are the result
of storing the frame offset with the instruction;
it is necessary to fetch the instruction offset pair
to find the match location.
\vspace{0.5cm}
\noindent
(2) Direct Matching in EM-4

The direct matching in EM-4 \cite{sakai89} is also a data-driven synchronization
without using associative mechanisms.

Figure 2 shows the direct matching scheme. 

\begin{fig}{direct}{Direct Matching.}
\illustration{direct}
\end{fig}

Similar to ETS, a matching area is exclusively
reserved for a single function instance.
This area is called an operand segment while
the code block corresponding to it is called a
template segment.
Matching occurs at a certain word in the frame.
At the function invocation time, one operand segment is reserved
for the new function instance and the top address of the template
segment is written to the top address word of the operand segment.
The top address of the template segment is called TSN, template
segment number.

In direct matching, every token contains two fields, OSN and DPL.
OSN is an operand segment number (same as a frame pointer in
ETS) which points the top of the operand segment.
The DPL serves both a displacement of the instruction and that
of the matching.
This displacement is common for both matching and an instruction
fetch, i.e. the matching offset in the operand segment
is the same as the instruction offset in the template segment.

Each packet also has a field of SF, a {\it synchronization flag}.
This field indicates the type of the synchronization. In the
EM-4, the SF contains two bits representing four synchronization
types: monadic, dyadic left, dyadic right and immediate. 

The matching address is produced simply by concatenating the OSN and the DPL.
Instruction address is derived by concatenating the TSN, which is fetched
from the top word of the operand segment, and the DPL (Figure 2).

Each data word in an operand segment includes a synchronization
flag.
A dyadic matching in the EM-4 is performed by a test-and-set of
the flag. 
If the flag has already been set, the partner data will be read,
the flag will be cleared, and the instruction will
be executed.
Otherwise the arriving data will be stored there and the flag will be set.

At the end of function execution,
the operand segment is released for a future reuse.

The advantages of the direct matching are as follows.
\begin{itemize}
\item It does not need any associative mechanisms.
\item It does not generate a pipeline bubble caused by
a hash miss.
\item An instruction fetch is not necessary, if
the matching fails. This solves the first defect
of ETS.
\item After a TSN fetch, matching and an instruction fetch
can be performed in parallel.
This partly solves the second defect of
ETS\footnote{In the EM-4, matching and an instruction fetch
are not operated in parallel, because of its narrow
memory bandwidth. However, it has to be
emphasized that, in principle, the direct matching
can provide parallel operations of matching and an instruction
fetch, if the memory bandwidth is sufficiently high or if
the Harvard architecture is adopted.}.
\item The location of the matching is completely written in the packet,
so debugging and tracing are quite easy.
\end{itemize}

However, the direct matching has a few
drawbacks as described below. 
\begin{itemize}
\item A TSN fetch is necessary before an instruction fetch. 
Although these can easily be pipelined, this makes
the turnaround one cycle longer.
\item The reuse of a frame word within the same function instance
is impossible, since it is bound to a single instruction which
has the same offset as the matching word.
\item At the time of a function invocation, a TSN must
be written to the first word of the operand segment.
This overhead is usually negligible, since it happens once per
one function. If the function body is quite small, 
this may be a problem.
\item Each instruction must have exactly one frame slot. This
reduces the memory efficiency.
\end{itemize}

Both in Monsoon and in the EM-4, a dyadic matching is
performed only in a single clock cycle. Memory read-modify-write
is thus carried out in a single clock cycle and the pipeline pitch
of these two machines cannot be shorter than it. 

After the development of these machines,
more innovative computers
are proposed and now being built by the same groups.
One is *T \cite{nikhil92} and the other is the EM-5
\cite{sakai912}.
In these two machines, the data-driven synchronizations
are improved so as to eliminate the defects listed
above.

\vspace{0.5cm}
\noindent
(3) *T message synchronization

The data-driven synchronization in *T is based on
ETS, but is more flexible.
For thread-based computation, cases 
where more than two messages must be synchronized
are the common case.
To perform synchronization of n-messages efficiently
and flexibly,
*T will provide a general join instruction at
the starting/resuming time of each thread.
Each message in *T includes the FP and IP, just like
ETS in Monsoon.
The join instruction reads a flag (or a counter),
updates it, and performs a conditional branch if
the synchronization is completed.
This method makes the turnaround longer,
but gains flexibility.
The details of this instruction and the details of
the *T architecture have not been presented yet,
so this paper will not closely examine the data-driven mechanisms in *T.

\vspace{0.5cm}
\noindent
(4) Advanced Direct Matching in the EM-5

The EM-5 adopts an improved synchronization method, called
an {\it advanced direct matching}.
Unlike the previous mechanisms, the matching and the instruction fetch
are completely independent within the advanced direct matching.

This method is based on the direct matching.
Each token packet contains
the OSN and the displacement in the operand segment (ODPL).
Furthermore, it contains the TSN and the displacement of the template segment
(TDPL).
There are thus two offset fields, so the address of the instruction
is completely independent of the matching. 

The advanced direct matching uses the SF field in each
packet which indicates the type of the synchronization.

Figure 3 illustrates the advanced direct matching in the EM-5.
At a function's invocation time, a frame is allocated for it.
When each token
arrives at a processor, an instruction fetch occurs
using TSN and TDPL.
At the same time, matching occurs using OSN and ODPL.

\begin{fig}{advanced}{Advanced Direct Matching.}
\illustration{advanced}
\end{fig}

As the packet in the advanced direct matching holds
all information which are necessary for an instruction fetch and
matching, it is a superset of both ETS and the direct matching,
i.e. it receives all the advantages which are
listed in (1) and in (2).
In addition, the advanced direct matching has the following advantages.

\begin{itemize}
\item An instruction fetch is not necessary for matching. A token
whose partner has not arrived yet does not fetch an instruction.
\item a matching and a speculative instruction fetch can be
performed completely in parallel, which shortens the turnaround.
\item It is not necessary to write TSN at a function invocation.
\item There are no TSN fetches. 
\end{itemize}

These advantages are derived at the cost of the additional
address field in a packet, i.e. an additional offset and a TSN field.
In each instruction which outputs a packet, there is also an
additional field containing the TDPL. Whether this cost
is reasonable or not will be discussed in Section 4.

\subsection{Optimized Synchronization}
Before proposing a new method, we have to understand
the differences between
the synchronization requirements in
an original dataflow architecture,
and those in a multithreaded architecture. 

The additional requirements (or conditions)
for "multithreaded" synchronization are as follows.
\begin{enumerate}
\item In a multithreaded architecture, multi-way join
occurs more frequently.
This is because a long thread may need a lot of data for all of its operations.
In addition, the size of messages may not be fixed,
i.e. the amount of data included in a message will
vary from one to many, depending on the system's data
distribution method and its operand passing method.
\item Multithreaded architectures may not need as many
data-driven synchronizations as the conventional
dataflow architectures. This is because a node inside
a thread does not need data matching.
\item To exploit locality,
a cache and a register set are introduced for a fast single-thread
execution.
Synchronization should be comparable in the speed to
these local storages.
\end{enumerate}
The first condition may force us to use a counter-type join
logic in addition to (or instead of) the traditional
dyadic matching logic. In addition, we have to prepare
multiple data words for waiting data storage at one
synchronization.
The second condition will make us reconsider
the cost-effectiveness of synchronization.
If a synchronization occurs usually once per
ten thousand cycles, we may not need a special
mechanism for it.
The third condition will force us to make a short-pitch
pipelined implementation of synchronization.
It will also force us to perform the synchronization
in parallel with an instruction fetch and a decode.

In this subsection, an ultimately efficient synchronization
is proposed. Discussions on cost-effectiveness will be
made in Section 4.

Figure 4 shows the optimized data-driven synchronization for massively
parallel multithreaded computers.

\begin{fig}{optsync}{Optimized Data-Driven Synchronization.}
\illustration{optsync}
\end{fig}

Each message (or each packet) contains the (TSN, TDPL) pair
(i.e. instruction address), and the (OSN, ODPL) pair\footnote{
All the addresses are virtualized, so there is an address translation
mechanism for each cache.},
just like the advanced direct matching shown in 2.1. In addition,
the packet has a synchronization flag field (SF) which indicates
the type of the synchronization.
This flag field has typically
three bits, i.e. larger than that in the advanced direct matching,
representing (1)a monadic synchronization, (2)dyadic left data,
(3)dyadic right data, (4)a synchronization for more than two messages,
(5)a signal synchronization, (6)dyadic data with an immediate left or
(7) dyadic data with an immediate right. We may consider a larger
field for this flag for representing a sticky token, representing a
triadic synchronization, etc.

We use an instruction cache
and a data cache respectively, to shorten local memory latency.
These will be separate on-chip-caches just
as in a typical RISC chip. In addition, it is advantageous to
have another independent cache, a {\it flag cache},
to speedup synchronization.

Suppose a single clock cycle means time enough for a cache read
(or write).
When a message comes into the synchronization part in a processor, 
an instruction can immediately be fetched. 
The operational sequence of a instruction fetch and a decode are
completely independent of that of the synchronization until
the execution occurs.
We can thus concentrate on the data-driven synchronization.

Actually there are five types of data-driven synchronizations
according to the SF.
We describe the mechanism for each case.

\begin{enumerate}
\item Monadic Synchronization\\
In case of monadic operations or in case that a single message
contains all data which are necessary for certain thread execution.
Synchronizations are not necessary.

Besides fetching an instruction and decoding it, nothing happens before
the execution.
Note that all the synchronization stages of a pipeline
should be bypassed to reduce latency.
\item Dyadic Synchronization\\
A dyadic synchronization is the same as the dyadic matching in
conventional dataflow machines. Although this can be implemented
by a multiway join described below, this should be distinctively
implemented, since dyadic synchronizations occur
so frequently that its efficiency influences the overall performance
of the machine considerably.

The operations of a dyadic synchronization are (1)read a flag from a
flag cache (if it fails, a cache line is read from the main memory),
(2)check whether the flag shows the existence of the partner or not,
(3)clear the flag if the partner exists or to set the flag if
it does not exist,
(4)read data from the data cache (if it fails, a cache line is
read from the main memory)
whose address is (OSN, ODPL), and (5)write message data to the data
cache whose address is (OSN, ODPL) if the partner does not exist.

These operations can be parallelized, i.e. (1) and (4) are parallelized,
and (3) and (5) are parallelized. So the synchronization sequence is:
\begin{description}
\item clock 1 : (1) and (4)
\item clock 2 : (3) and (5) following (2)
\end{description}
As (2) is simple and the address has been held since (1),
(2) and (3) can be performed in a single cycle.

To make a complete pipeline, it is necessary to have 
a dual port flag cache and a dual port data cache.
\item Multiway Join ($\geq$ 3)\\
There are two ways to synchronize more than two messages.
One is to make a tree of dyadic synchronizations. Each node
of the tree performs a dyadic synchronization and a store of message
data to certain words of the frame.
This methods requires no additional hardware.
However, it needs many instruction execution cycles
and additional packet flow, since there may be many intermediate nodes
dedicated to the synchronization.

To perform the multiway join more efficiently and more flexibly,
it is necessary to use a join-counter logic. In this case, each
flag is used for a counter indicating the number of messages
which have already arrived or the number of messages which
will have to arrive before execution.

The operations of a multiway join with this counter are
(1)read a flag from a flag cache (if it fails, a cache line
is read from the main memory),
(2)increment the counter and compare the result with some
constant (or to decrement the counter and compare the result
with zero),
(3)clear the flag if the partner exists or to set
the flag to the new value derived from (2) if it does not exist, 
(4)read waiting data from the data cache (if it fails,
a cache line is read from the main memory).
(5)write message data to the data cache (if it fails, a cache line
is read from the main memory). 

Here, (4) can be performed by the executor, not by the synchronization
logic. However, the speculative data fetch will be effective, since
(4) can be performed in parallel with the flag memory write.

The operations here can also be parallelized. The synchronization sequence 
is:
\begin{description}
\item clock 1: (1) and (5)
\item clock 2: (2) and (4)
\item clock 3: (3) and (4)
\item clock 4 and after: (4), if necessary 
\end{description}
In case of the multiway join, the counter update and branch are
more time-consuming than the flag-check and branch in the dyadic
synchronization. This is the reason why (2) takes one independent
clock cycle.

If the size of the message data is more than one, (5) will take
more than one cycles. In this case, data write occurs
in clock 2 or after clock 2. This will delay the sequence of (4).
\item Signal Synchronization\\
The operations of a signal synchronization with a lot of tokens
are similar to those of the multiway join.
However, it does not need to access a data memory at all.

What happens in this case is a sequential operation of (1)(2)(3)
of the multiway join.
\item Counter Overflow\\
In a multiway join (also in a signal synchronization), the counter
overflow may occur when the number of messages which should
be synchronized at the same point exceeds the number which
can be represented by the flag.

In this case, a join-tree is constructed
each node of which performs a smaller join. 

One question is the size of the flag. If the flag is too small,
we have to make a high tree which causes overhead.
If the flag is too large, memory efficiency is degraded.
For instance, if the flag is four-bit wide, then it
can perform 16 way join with a single node, 256 way join
with a two-layer tree, etc.
Although four bits seem sufficiently for a multi-way join,
a good size must be experimentally determined.
\end{enumerate}

Note that the synchronization does not use instructions at all.
Instructions such as Post, Start, Join
and Next \cite{nikhil92} do not exist here.
This reduces the execution cycles of a processor.
The synchronization for a certain thread
can totally be pipelined with the other threads.
This highly increases the system throughput.
It also can be parallelized with the instruction fetch and the decode
for the same message. This highly decreases the processing latency.

The synchronization sequence described above
can also be pipelined, which is described in 4.3.

The advantages of this optimized synchronization are as follows.

\begin{enumerate}
\item Efficiency\\
The proposed method is ultimately efficient, because of
the followings:
(1)it provides highly parallel and pipelinable operation mechanisms:
parallel execution of instruction fetch/decode and synchronization,
parallel execution of flag memory accesses and data memory accesses,
and pipelined execution between multiple threads;
(2)it provides five kinds of synchronization mechanisms which
can optimally be adopted for the synchronization type, and
(3)it does not need any instructions which will increase the
latency and a whole cycle time.
\item Flexibility\\
The proposed method provides five kinds of synchronization.
Especially the counter type synchronization makes
it fairly flexible for complex synchronizations.
\item Simplicity\\
As each message has both the address of instruction and the
synchronization, this mechanism
simplifies the synchronization itself and eases the understanding
of what is happening in the synchronization stages.
To design and to debug are both much easier than the
other data-driven methods.
\end{enumerate}

\section{Pipeline Design}
\subsection{Basic Methodologies}
Conventional dataflow machines and the HEP\cite{smith78} have 
a pipeline where multiple threads share its slots at the same time.
The pipeline of this type is called a {\it circular pipeline}\cite{gurd85}.

The circular pipeline has several advantages as follows.
\begin{itemize}
\item It exploits the parallel activities maximally in a single
pipeline.
There is no overhead of a context switching.
\item It achieves the natural and efficient combination of
computation and communication
by providing continuous operations from the network to the
instruction executor and from the instruction executor to
the network. There are no interruptions between a network and
a processor.
\item It can provide an excellent throughput without
preparing complex interlocking mechanisms and
branch prediction mechanisms.
\end{itemize}
Because of these advantages, the circular pipeline has been
regarded as an excellent structure for parallel computation.
Two of the representative dataflow machines, the SIGMA-1\cite{hiraki87}
and Monsoon\cite{greg90} have this type of pipeline.

Figure 5 shows the pipeline structure of Monsoon. It has eight stages
each of which can be occupied by an independent thread in a completely
non-blocking way.

\begin{fig}{monsoonpipe}{Pipeline Organization of Monsoon.}
\illustration{monsoonpipe}
\end{fig}

However, there are several drawbacks in a "pure" circular pipeline
\cite{sakai911}.
\begin{itemize}
\item The circular pipeline does not perform an advanced control.
Advanced control here means a look-ahead control containing
an instruction prefetch.
\item There may be a lot of empty slots in the circular pipeline
if there is not enough parallelism.
\item Throughput of the circular pipeline is limited by the speed
of global data handling such as a packet flow and main memory 
access.
\item Resource management is inefficient with the circular pipeline,
since it has to lock the pipeline resources for a series of
indivisible operations which cannot be interleaved.
\end{itemize}

Briefly, the circular pipeline is not suited to a local sequential
execution nor is it suited to a less parallel execution. 

To overcome these defects is one of the most essential reasons
of proposing multithreaded computers. Multithreaded computers
typically have a RISC-type von Neumann pipeline in addition to the
the packet-based circular pipeline.

For instance, Figure 6 illustrates the pipeline structure of
the EM-4 \cite{sakai89}. The processor of the EM-4 has two-layered
nested pipeline, i.e. the packet-based circular pipeline includes
the RISC-pipeline. The former performs a multithreaded pipelining
as fast as or faster than a conventional dataflow pipeline, 
while the latter performs a register-based advanced-control pipelining
as fast as a conventional RISC pipeline.
In addition, the multithreaded pipeline of the EM-4 has several
bypassing routes which shortens a latency of a packet with a simple
request.

\begin{fig}{em4pipe}{Pipeline Organization of the EM-4.}
\illustration{em4pipe}
\end{fig}

The EM-5\cite{sakai912} will have a faster and
more complex pipeline based on the EM-4 layered-pipeline,
i.e. the matching stage will be faster because of the introduction
of the advanced direct matching,
and the execution part will perform integer operations,
floating operations and load/store in parallel\footnote{ 
The basic concept of the EM-5 pipeline design is the same as
the EM-4, so this paper will not describe its structure more
closely.}.

The *T \cite{nikhil92} will also have a RISC pipeline inside its
processor. Actually, the *T processor is an extension of a
MC88110, a commercial RISC processor which will provide
the peak performance of 100 MFLOPS
for double precision floating point calculations.
The details of the *T pipeline structure have not been presented yet,
so this paper will not examine the *T pipeline closely; however,
we have to note that it performs both the continuous
data-flow between a network and an instruction executor, and the
local RISC execution.
\subsection{Optimized Pipeline}
The previous architectures have shown that the pipeline for a multithreaded
processor should be a combination of two types of pipelines.
One is a multithreaded circular pipeline and the other is a
RISC type single-threaded pipeline with an advanced control.
The former should be fairly fast with the optimized data-driven
synchronization stages proposed in 2.2.

Before proposing an ultimately efficient pipeline for a multithreaded
computer, we have to show the requirements for a pipeline
of multithreaded computers.
\begin{enumerate}
\item High throughput for both multithreaded execution and
single-threaded execution\\
In the normal case, the throughput should be one result
per one RISC clock which indicates the pitch for both pipelines. 
\item Short turnaround from message input to result write 
to message output, and from instruction fetch to result write\\
For single-thread execution, the turnaround of operations
inside a processor must be equal to or less than a normal RISC processor.
For multithread execution, result message should be output as soon as
possible after the input message enters. 
\end{enumerate}
To meet the first requirement, a pipeline
pitch must be as short as possible.

Cache read and write should be pipelined.
There are three independent caches
to implement the optimized synchronization described in 2.2.
Among those,
the flag cache is accessed by the read-flag stage and write-flag stage.
The data cache is accessed by the read-data stages, write-data stages
and, possibly, load/store stages
\footnote{Note that the frame is used as a working area for the
executor as well as a synchronization area.}.
To achieve the short pitch pipeline, 
the former cache must be dual-port and the latter will preferably
be dual- or tri-ported, in order to avoid memory-request contentions 
at the same time.

The executor should also be highly pipelined as is shown
in the current RISC processors, e.g. floating point pipelines
and load/store pipelines.

To meet the latter requirement, intra-processor parallelism
should be pursued as much as possible.

As was already shown in the optimization of synchronizations,
the synchronization and the instruction fetch/decode should
be operated in parallel. In the executor, many operations
should be executed in parallel, e.g. superscaler execution
of integer instructions and parallel execution of floating
point instructions and integer instructions.
In addition, for a multithreaded computer, generating packets
should be carried out in parallel with the instruction
execution.

To meet the latter requirement, bypassing mechanisms
are sometimes necessary.
For instance, remote fetch of the data should not be
performed by a long pipeline.

Figure 7 illustrates the optimized pipeline for an element
of a massively
parallel multithreaded computer.

\begin{fig}{optpipe}{Optimized Pipeline.}
\illustration{optpipe}
\end{fig}

When a message enters, the processor performs the multithreaded
pipeline as follows.
The first stages of the pipeline carry out a synchronization and
an instruction fetch and an instruction decode as was stated in 2.2.
There were several kinds of parallelism in it, i.e. parallelism
among the flag handling, the data read/write and the instruction
fetch/decode. In addition there are some bypassing routes.
Continuously the latter stages execute the instruction invoked
by the message. If the thread contains more than one instruction,
an instruction fetch for the second instruction occurs while
the decode of the first instruction is carried out. Third instruction
fetch occurs while the first one is executed
and the second one is in the decode stage.

The instructions can be issued in parallel in the executor as long as
the operand data exist and the functional unit is available. Intra-processor
Parallelism can be extracted in this way, just as in the current RISC
processor.
In order to fetch instructions for incoming messages in parallel with
the previous thread execution, the instruction cache should also
be dual-ported.

Thread execution proceeds in this way.
The packet turnaround time (the time from packet input to the first packet
output, if the first instruction is a packet output instruction)
is (1)4 clocks for a monadic node, (2)4 clocks for a dyadic node
and (3)4 +($s$ - 2) clocks for a $s$-adic node if the processor
and the network have no other activities.
The typical throughput is $n$ instructions per clock where $n$ is an
average execution parallelism utilized in a processor.

There are three queues illustrated in Figure 7: the Input Message Queue,
the Continuation Queue and
the Output Message Queue.
These queues absorb the speed gap
between the network and the synchronization part,
between the synchronization part and the execution part, and
between the execution part and the network. 
To omit one or two queues is possible, depending on the typical
throughput of each part.
\section{Discussions}
\subsection{Architectural Tuning}
\noindent
(1) Priority Control

Although the proposed pipeline is fairly efficient,
there are cases where a certain thread should be
executed before the current thread execution is finished.
For example, suppose that a certain remote fetch 
is critical for the whole computation time.
If the remote fetch message is blocked at the
entrance of the executor by a long thread, the overall
performance will be degraded.

To solve this situation, two ways can be considered:
independent execution or preemption.
In the former, the processor may have an extra pipeline
(including extra registers and data paths for executing) which
is dedicated to the priority operations. The I-structure handling 
of *T uses this \cite{nikhil92}. In the latter, the processor
should have a fairly fast context switching mechanism. 
To exploit the ultimate pipeline shown in Section 3, the overhead of switching
context must be zero or one clock cycle. 
The instruction insertion mechanism with multiple register sets
\cite{toda91} will be adopted for this.

In either case, efficient priority queues are necessary in a message
waiting section and sometimes in an interconnection network.

\vspace{0.5cm}
\noindent
(2) Load/Store Overhead between Synchronization and Execution

In the pipeline described in 3.3,
all message data must be stored before execution.
However, if the synchronization succeeds, they can be sent directly to
the registers of the execution unit, instead of
store and load after the synchronization.

\vspace{0.5cm}
\noindent
(3) More Flexible Thread-Interleaving

In the previous discussions, the author did not mention 
about more complex situations where we can adopt a much finer control
of threads. This can improve performance with fairly small amount of
control logic.

Here is a simple example. A floating point pipeline can be
shared by more than two threads at the same time.

Another example is to execute parallel activities between threads 
in the multiple execution units (e.g. integer units, a floating point
unit, a load/store unit).
\subsection{Cost-Effectiveness}
If threads are usually long,
then the instruction executions can be pipelined in a single thread in most of
the computation time. In this case, people may say that
the synchronization mechanism and the pipeline proposed here
may be an "overdesign".

However, as for the number of transistors, these mechanisms cost 
fairly small.
The direct matching in the EM-4 only costed 3,610 CMOS
gates \cite{sakai89}, which are relatively small in comparison
with the other units, e.g. integer units. The proposed mechanisms
will need slightly larger amounts of hardware, since the pipeline
pitch is about as half as that of the EM-4 and thus additional
pipeline registers will be necessary; however, it is clearly
not a great deal of a VLSI area.
The logic is quite simple, since there are no
interlocks necessary for coordinating more than one threads.
In addition, no interrupt mechanisms exist
instead of the error handlings and exceptions.

The extra hardware will also be required for implementing a multiport
cache: multiple buses, multi-set decoders and arbitration logic.
However, these are simple circuits and all the buses
are inside the chip.
This part thus does not affect the pin limitation
of VLSI design.

The last question is the bandwidth of an interconnection network and
a memory.
The message needs extra fields for
the proposed synchronization method:
in comparison with ETS,
this needs the frame offset and the SF.
However, in a multithreaded computer, this field can be
fairly small, since synchronizations in a frame
are much less frequent than in a conventional
dataflow computers,
and thus the address space necessary
for a synchronization is small.

An extra field for a TDPL in an instruction memory
is also a small problem for the same reason.

In addition, because of highly extracting intra-processor parallelism,
the thread execution time becomes short in this architecture.
Therefore, to shorten a pipeline is significant for performance,
and we must have synchronization mechanisms with fairly short turnaround.

Therefore, we got the conclusion that the proposed synchronization
and the proposed pipeline are both implementable at
a reasonable cost; they are cost-effective in VLSI design
of a multithreaded computer.
\subsection{Related Issues}
Here we concentrate on a local data-driven synchronization.
However, we have to optimize the I-structure/M-structure type
synchronization for a large data structure handling. In addition,
a multithreaded computer should have a fast global synchronization
mechanism in case of a barrier in a program. These issues are
orthogonal to the issues described in this paper. They can be
independently pursued and added to the pipeline described
in 3.3.

Optimization of the cache structure is another significant issue,
since the pipeline cannot work well if cache misses are frequent.
Scheduling techniques to increase the cache hit ratio without
degrading the parallelism must be considered closely.

In an actual machine, virtual memory mechanisms should be implemented
\footnote{Here, how to implement the virtual memory is not
examined. It must be closely considered,
combined with the implementation of caches.}.
To optimize the physical distribution of data influences
the performance of the pipeline.
\section{Conclusion}
This paper made a proposal about
two fundamental mechanisms for a multithreaded massively parallel computer:
synchronizations and pipelining.
The synchronization proposed here is based on frame and is a
highly parallel and pipelinable.
It provides one synchronization per each RISC clock cycle and
its latency is typically four cycles if the target words are
in caches.

With this synchronization mechanism,
pipelines can be ultimately optimized. This paper showed such
an optimized pipeline in a processor of a multithreaded
massively parallel computer. The operations are
highly parallelized (matching and an instruction fetch/decode are
operated in parallel, instruction execution and packet generation
are in parallel, etc.)
and the pipeline pitch is ultimately shortened to a cache cycle.

Future problems are :
(1) quantitative evaluations of the proposed mechanisms,
by analyses based on a queueing model and by simulations;
(2) close consideration of the related issues, including
virtual memory/cache design,
priority handling mechanisms,
task partitioning and optimization of granularity,
work load balancing,
data distribution,
I/O and other scheduling problems;
and
(3) feasibility study by constructing a prototype
system and examinations of its efficiency and
cost-effectiveness, with state-of-the-art VLSI implementation
and practical application programs.
\vspace{0.5cm}
\section*{Acknowledgement}
\vspace{0.2cm}
The author wishes to thank Professor Arvind, Professor Gregory
M. Papadopoulos and Dr. George A. Boughton
for supporting this research, and the members
of Computation Structure Group in MIT-LCS for the fruitful
discussions. He also would like to express his sincere
appreciations to Professor Dennis and
Dr. Nikhil of DEC for his helpful comments. 
\begin{thebibliography}{99}
\bibitem{smith78}Smith, B.J.: A Pipelined, Shared Resource
MIMD Computer, Proc. of 1978 ICPP, pp.6-8 (1978).
\bibitem{arvind80}Arvind, Kathail, V., Pingali, K.:
A Data-flow Architecture with Tagged Tokens,
Tech. Rep. TR-174, Lab. Computer Science, MIT (1980).
\bibitem{gurd85} Gurd, J., Kirkham, C.C. and Watson, I.:
The Manchester Prototype Dataflow Computer, CACM, Vol.21,
No.1, pp.34-53 (1985).
\bibitem{hiraki87}Hiraki, K., Nishida, K., Sekiguchi, S.,
Shimada, T. and Yuba, T.:
The SIGMA-1 Dataflow Supercomputer: A Challenge for New Generation
Supercomputing Systems, 
Journal of Information Processing, Vol.10, No.4, pp.219-226
(1987).
\bibitem{iannucci88}Iannucci, R.A.: Toward a Dataflow/von Neumann
Hybrid Architecture, Proc. of 15th ISCA, pp.131-140 (1988).
\bibitem{thistle88} Thistle, M.R. and Smith, B.J.:
A Processor Architecture for Horizon, Proc. of IEEE
Supercomputing Conference, pp.35-41 (1988).
\bibitem{sakai89}Sakai, S., Yamaguchi, Y., Hiraki, K., Kodama,
Y. and Yuba, T.: An Architecture of a Single Chip Dataflow
Processor, Proc. of 16th ISCA, pp.46-53 (1989).
\bibitem{greg90}Papadopoulos, G.M. and Culler, D.E.:
Monsoon: An Explicit Token Store Architecture,
Proc. of 17th ISCA, pp.82-91 (1990).
\bibitem{sandia91}Grafe, V.G., Hoch, J.E., Davidson, G.S.,
Holmes, V.P., Davenport, D.M. and Steele, K.M.:
The Epsilon Project,
in Advanced Topics in Data-Flow Computing,
Chapter 6, pp.175-205, Prentice Hall (1991).
\bibitem{dennis91}Dennis, J.B.: The Evolution of "Static"
Data-Flow Architecture, 
in Advanced Topics in Data-Flow Computing,
Chapter 2, pp.35-91, Prentice Hall (1991).
\bibitem{sakai911}Sakai, S., Hiraki, K., Yamaguchi, Y., Kodama,
Y. and Yuba, T.: Pipeline Optimization of a Data-Flow
Machine, in Advanced Topics in Data-Flow Computing,
Chapter 8, pp.225-246, Prentice Hall (1991).
\bibitem{sakai912}Sakai, S., Kodama,Y. and Yamaguchi, Y.:
Architectural Design of a Parallel Supercomputer EM-5, Proc.
of JSPP91, pp.149-156 (1991).
\bibitem{greg91}Papadopoulos, G.M. and Traub, K.R.:
Multithreading: A Revisionist View of Dataflow Architecture,
Proc. of 18th ISCA, pp.342-351 (1991).
\bibitem{sato92}Sato, M., Kodama, Y., Sakai, S., Yamaguchi, Y.
and Koumura, Y.: Thread-based Programming for the EM-4 Hybrid
Dataflow Machine, to appear in the 19th ISCA (1992).
\bibitem{nikhil92}Nikhil, R.S., Papadopoulos, G.M. and Arvind:
*T: A Multithreaded Massively Parallel Architecture,
to appear in the 19th ISCA (1992).
\bibitem{dally89}Dally, W., Chien, A., Fiske, S., Horwat, W.,
Keen, J., Larivee, M., Lethin, R., Nuth, P. and Wills, S.:
The J-Machine: A Fine-Grain Concurrent Computer, Proc. of
IFIP 89, pp.1147-1153 (1989).
\bibitem{keckler92}Kechler, S.W. and Dally, W.J.:
Processor Coupling: Integrating Compile Time and Runtime Parallelism,
to appear in the 19th ISCA (1992).
\bibitem{toda91} Toda, K., Nishida, K., Uchibori, Y., Sakai, S. and
Shimada, T.: Parallel Multi-Context Architecture with High-Speed
Synchronization Mechanism, Proc. of 5th IPPS, pp.336-343 (1991).
\end{thebibliography}
\end{document}
