\begin{slide}{}
\begin{center}
{\large \bf
Synchronization and Pipeline Design
for a Multithreaded Massively Parallel Computer\vspace{5cm}}

{\large Shuichi Sakai}\vspace{1cm} \\

Computation Structure Group\\
MIT-LCS
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Acknowledgment}
\end{center}
Dr. Sakai would like to thank
\begin{itemize}
\item Prof. Arvind, Prof. Papadopoulos,
and Dr. G. A. Boughton for supporting his research ({\it also his life}),
\item the members of CSG for the fruitful discussions ({\it also for buying
his items and carrying his boxes})
\item Prof. Dennis and Dr. Nikhil for his helpful comments
\item Ms. Maderer for her support.
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Introduction}
\end{center}
This presents the optimization of a synchronization  
and a pipeline in a multithreaded massively parallel
computer.
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Basic Strategies}\\
(please do not be too serious....)
\end{center}
\begin{itemize}
\item study the past and the present
\item use, improve or forget
\item reconsider the proposal
\end{itemize}
Remark: Here, we concentrate on data-driven
sync. and a processor pipeline based on a dynamic
model.
\end{slide}

\begin{slide}{}
\begin{center}
{\large Proposed Data-Driven Synchronizations}
\end{center}
\begin{itemize}
\item Hash in Manchester DFM and SIGMA-1
\item ETS in the Monsoon
\item Direct Matching in the EM-4
\item Direct Match in Sandia Dataflow
\item *T Synchronization
\item Advanced Direct Matching in the EM-5
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\large Matching by Pseudo Associative Mechanisms = Hashing}
\end{center}
\begin{center}
{\bf Advantages}
\end{center}
\begin{itemize}
\item high spatial efficiency
\item flexibility
\end{itemize}
\begin{center}
{\bf Drawbacks}
\end{center}
\begin{itemize}
\item complex
\item pipeline bubbles caused by a hash-miss
\item difficult to understand what is happening
\end{itemize}
\end{slide}

\begin{slide}{}
(ETS in Monsoon)
%\begin{center}
%{\large ETS in Monsoon}
%\end{center}
%\vspace{18cm}
%\begin{fig}{ets}{Explicit Token Store.}
%\illustration{ets}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf Advantages}
\end{center}
\begin{itemize}
\item no associative mechanisms
\item no hash miss
\item EXPLICIT = easy to understand what is/
should be happening
\item matching word is reusable even in the same function instance 
\end{itemize}
\begin{center}
{\bf Drawbacks}
\end{center}
\begin{itemize}
\item instruction fetch is always necessary, even if match fails
\item instruction fetch and matching must be serialized
\end{itemize}
\end{slide}

\begin{slide}{}
(Direct Matching)
%\begin{center}
%{\large Direct Matching in EM-4}
%\end{center}
%\begin{fig}{direct}{Direct Matching.}
%\illustration{direct}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf Advantages}
\end{center}
\vminus
\begin{itemize}
\item no associative mechanisms
\vminus
\item no hash miss
\vminus
\item instruction fetch is not necessary for match
\vminus
\item ins. fetch can be performed in parallel with match.
\vminus
\item easy to understand what is happening
\end{itemize}
\begin{center}
{\bf Drawbacks}
\end{center}
\begin{itemize}
\vminus
\item TSN fetch overhead
\vminus
\item reuse of a frame word is difficult
\vminus
\item TSN write overhead at the function invocation time (small overhead)
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\large *T Synchronization}
\end{center}
= FORK and JOIN instructions
\begin{itemize}
\item flexible for many types of synchronizations
\item longer turnaround
\item using instruction execution cycles: overhead\\
(originally it is a separate part of the processor)
\end{itemize}
\end{slide}

\begin{slide}{}
(Advanced Direct Matching)
%\begin{center}
%{\large Advanced Direct Matching in EM-5}
%\end{center}
%\begin{fig}{advanced}{Advanced Direct Matching.}
%\illustration{advanced}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf Advantages}
\end{center}
\begin{itemize}
\item no associative mechanisms
\item no hash miss
\item instruction fetch and matching are completely independent
and performed in parallel
\item easy to understand what is/should be happening
\item no TSN fetch and no TSN write
\end{itemize}
\begin{center}
{\bf Drawbacks}
\end{center}
\begin{itemize}
\item hardware cost, especially bandwidth
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf \large Requirements for Synchronization in Multithreading}\\
(before showing the optimization... )
\end{center}
\begin{enumerate}
\item multi-way join 
\item may not need as frequent sync. as pure dataflow
\item sync. must be fast enough to follow the localized exec., e.g.
to follow the cache/
register cycle
\end{enumerate}
\end{slide}

\begin{slide}{}
(Optimized Synchronization)
%\begin{center}
%{\bf \large Optimized Synchronization Mechanism}
%\end{center}
%\begin{fig}{optsync}{Optimized Synchronization Method.}
%\illustration{optsync}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\it Opt. Sync. = modified advanced direct matching}
\end{center}
\vminus
\begin{itemize}
\item short pitch pipelining for cache/register architecture
\vminus
\item flag-cache/data-cache separation 
\vminus
\item supporting five types of sync.
\vminus
\begin{itemize}
\item monadic: no sync.
\vminus
\item dyadic: same as advanced direct matching
\vminus
\item multiway: counter join without using instructions
\vminus
\item signal sync.: multiway without data read/
write
\vminus
\item counter overflow: join tree
\end{itemize}
\end{itemize}
\vminus
= SIMPLE, FAST and FLEXIBLE sync.
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Optimizing a Pipeline} \\
\vspace{1cm}
{\bf Proposed Pipelines}
\end{center}
\begin{itemize}
\item Circular Pipe. in Manchester DFM, SIGMA-1
\item Non-blocking Circular Pipeline in Monsoon
\item Layered Pipeline in EM-4 and EM-5
\item *T Pipeline (not published)
\end{itemize}
\end{slide}

\begin{slide}{}
(Monsoon Pipeline)
%\begin{center}
%{\bf \large Monsoon Pipeline}
%\end{center}
%\begin{fig}{monsoonpipe}{Monsoon Pipeline.}
%\illustration{monsoonpipe}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf Advantages of a Circular Pipeline}
\end{center}
\begin{itemize}
\vminus
\item exploiting maximally the parallelism within a single pipeline
\vminus
\item natural and efficient combination of computation and communication
\vminus
\item excellent throughput even without complex interlocking and
branch predictions
\end{itemize}
\begin{center}
{\bf Drawbacks of a Circular Pipeline}
\end{center}
\begin{itemize}
\vminus
\item no advanced control
\vminus
\item lots of bubbles for less parallel execution
\vminus
\item inefficient resource management
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\large \bf Pipeline Fusion in a Multithreaded Computer}
\end{center}
Integration of a Circular Pipeline and a von Neumann (RISC) Pipeline\\
= keep the advantages and remove the drawbacks\\
\vspace{0.8cm}
e.g. EM-4, *T, EM-5
\end{slide}

\begin{slide}{}
(EM-4 pipeline)
%\begin{center}
%{\bf \large EM-4 Layered Pipeline}
%\end{center}
%\begin{fig}{em4pipe}{EM-4 Pipeline.}
%\illustration{em4pipe}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\large \bf Pipeline Optimization}
\end{center}
\begin{center}
{\bf Requirements for a Pipeline in a Multithreaded Computer}
\end{center}
\begin{itemize}
\item high throughput for both multithreaded execution and single-threaded
execution, i.e. 1 (or $s$) result(s) per one RISC clock
\item short turnaround
\begin{itemize}
\item single-thread: as fast as or faster than sequential RISC
\item multi-thread: 4 to 5 clocks between message input and output
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
(Optimzed Pipeline)
%\begin{center}
%{\bg \large Optimized Pipeline}
%\end{center}
%\begin{fig}{optpipe}{Optimized Pipeline.}
%\illustration{optpipe}
%\end{fig}
\end{slide}

\begin{slide}{}
\begin{center}
{\large \bf Features of the Optimized Pipeline}
\end{center}
\begin{itemize}
\item short-pitch: one cache cycle, achieved by multiport caches
\vminus
\item intra-PE parallelism
\begin{itemize}
\vminus
\item instruction fetch-decode and synchronization
\vminus
\item flag handling and data handling
\vminus
\item parallelism among operational units
\vminus
\item message generation and execution
\end{itemize}
\item  Packet Turn around
\vminus
\begin{itemize}
\item 4 clocks for monadic/dyadic\\
\vminus
\item 4 + (s-2) clocks for s-adic 
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Architectural Tuning}
\end{center}
\begin{enumerate}
\vminus
\item Priority Control\\
for short prior thread, for supervisor thread, etc.\\
\begin{itemize}
\vminus
\item independent pipeline: *T
\vminus
\item multiple register set 
\vminus
\item priority queue
\vminus
\end{itemize}
\item Load/Store Overhead Elimination\\
\vminus
bypassing the write/read of multiway-join
\vminus
\item More Flexible Thread Interleaving\\
\begin{itemize}
\vminus
\item multithreaded floating pipeline
\vminus
\item multithreaded superscaler execution
\vminus
\end{itemize}
\end{enumerate}
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Cost-Effectiveness}
\end{center}
Proposed methods are cost-effective since:
\begin{itemize}
\item amount of the logic is not much
\item control is not complex, no interlocking between threads
\item bandwidth
\begin{itemize}
\item caches : OK since they are inside chip
\item network bandwidth: worth spending (one additional field for the header)
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\large \bf Related Issues}
\end{center}
\begin{itemize}
\item I-structure/M-structure Synchronization
\item Global Synchronization
\item Cache Structure Optimization
\item Scheduling Techniques
\item Virtual Memory
\end{itemize}
will be combined with the proposed mechanisms
\end{slide}

\begin{slide}{}
\begin{center}
{\Large \bf Conclusion}
\end{center}
This presents the optimization of a data-driven synchronization and
a pipeline.
\begin{center}
{\large \bf Future Problems}
\end{center}
\begin{itemize}
\item quantitative evaluations by analyses and simulations
\item consideration of the "related issues"
\item feasibility study by implementation and evaluations
by the real machines with practical application programs
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf Future Plan in Japan = NIPT/RWC Project}
\end{center}
\begin{itemize}
\item major fields: Optical, Neural, Theory, {\bf MPP}
\item to establish a truly effective programming model
\item 16K to 64K PE system in 1996 (hopefully, EM-6)\\
= 3 to 10 TFLOPS computer
\item 1 M PE system in 2001\\
= fusion of soft-logic and MPP
\end{itemize}
\begin{center}
{\bf JAPAN is waiting for you to attend it!!}
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
{\bf ETL is also waiting for you.}
\end{center}
\begin{itemize}
\item invited researcher: visit ETL and give a talk\\
e.g. Prof. Dennnis, Prof. Arvind, Dr. Iannucci
\item post-doctor
\item permanent position (It's new!!)
\item MIT Japan Program
\end{itemize}
\end{slide}
