\begin{slide}{}
{\large
\begin{center}
{\dg \bf \Large
Prototype Implementation of a\\
Highly Parallel Dataflow Machine \emfour\vspace{8cm}}

Shuichi Sakai, Yuetsu Kodama\\
and Yoshinori Yamaguchi \vspace{1cm} \\

Electrotechnical Laboratory, JAPAN\\
\end{center}
}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Introduction}
\end{center}
\emfour: a feasible parallel supercomputer\\
\vminus
\begin{itemize}
\item 1,024 PEs
\vminus
\item processing: 12.8 GIPS
\vminus
\item network: totally 187.2 GB/s
\vminus
\item synchronization: 2.6 GSYPS
\vminus
\item targets
\vminus
\begin{itemize}
\item numerical computation
\vminus
\item symbolic computation
\vminus
\item large scale simulation
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf This Presentation\\ =
prototype implementation of the \emfour}
\end{center}
\vminus
\begin{itemize}
\item \emfour: a first step
\vminus
\begin{itemize}
\item design principles
\vminus
\item design and implementation
\vminus
\item performance evaluation
\end{itemize}
\vminus
\item \emfive$\,$ architecture
\vminus
\begin{itemize}
\item design principles
\vminus
\item architectural design 
\end{itemize}
\vminus
\item software issues
\vminus
\begin{itemize}
\item languages under development
\vminus
\item object oriented programming
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf \emfour: a feasible parallel supercomputer}
\end{center}
\vminus
\begin{itemize}
\item advanced dataflow machine
\vminus
\item 1,024 PEs, 12 GIPS
\vminus
\item targets
\vminus
\begin{itemize}
\item numerical computation
\vminus
\item symbolic computation
\vminus
\item large scale simulation
\end{itemize}
\vminus
\item \emfour$\,$ prototype
\vminus
\begin{itemize}
\item 80 PEs
\vminus
\item processing: 1 GIPS
\vminus
\item newtork: 14.63 GB/s
\vminus
\item synchronization: 200 MSYPS
\vminus
\item fully operational since April 1990
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
(photograph of the EM-4 prototype)
\end{slide}

\begin{slide}{}
(performance data)
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Design Principles of the \emfour}
\end{center}
\begin{itemize}
\item strongly connected arc dataflow model
\item direct matching scheme
\item pipeline fusion
\item multiple-RISC concept
\item circular omega network
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Strongly Connected Arc Dataflow Model}
\end{center}
\begin{itemize}
\item definition\\
a certain dataflow subgraph $\to$ critical section\\
= strongly connected block (SCB)
\item realization\\
SCB $\to$ register architecture\\
others $\to$ packet architecture
\item advantages
\begin{itemize}
\item fast local execution
\item flexible resource management
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\vspace*{14cm}
\begin{center}
Strongly Connected Arc Dataflow Model
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Direct Matching Scheme}
\end{center}
\vspace{-1cm}
\begin{itemize}
\item frame-based absolute address matching
\vspace{-1cm}
\item no associative memory, no hashing
\vspace{-1cm}
\item one clock synchronization
\vspace{-1cm}
\end{itemize}
\vspace{14cm}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Pipeline Fusion}
\end{center}
{\it Two pipelines are naturally and efficiently fused.}
\begin{itemize}
\item packet-based circular pipeline : multi-context
\item register-based advanced control pipeline: single context
\end{itemize}
\vspace{10cm}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Multiple-RISC Concept}
\end{center}
\vminus
{\it performance improvement by simplified architecture}
\begin{itemize}
\vminus
\item sequential-RISC features
\begin{itemize}
\vminus
\item small instruction set (26)
\vminus
\item few instruction format (4)
\vminus
\item few addressing modes (2)
\vminus
\item no microprograms
\vminus
\item 1 clock instruction execution
\vminus
\item register file and RISC pipeline
\vminus
\end{itemize}
\vminus
\item multi-RISC features
\begin{itemize}
\vminus
\item few packet formats (1) and few packet types (32)
\vminus
\item light synchronization embedded in a PE chip,
which works independently of the instruction execution
\vminus
\item small and effective interconnection network
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Circular Omega Network}
\end{center}
\begin{itemize}
\item O(N) hardware
\item O(logN) delay
\item SFD prevention facilities
\item automatic load balancing facilities
\end{itemize}
\vspace{12cm}
\end{slide}


\begin{slide}{}
\begin{center}
{\dg \bf \emcr: an \emfour$\,$ single chip processor}
\end{center}
\vminus
{\it 12.5 MIPS processor with a network switch, fully operational
since Oct. 1989}
\vspace{17cm}
\end{slide}

\begin{slide}{}
(\emcr$\,$ photograph)
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf \emfour$\,$ Prototype}
\end{center}
80 \emcr s, 1 GIPS, 14.63 GB/s, 200 MSYPS
\vspace{15cm}
\end{slide}

\begin{slide}{}
(photograph of EM-4 prototype)
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Design Principles of the \emfive}
\end{center}
\begin{itemize}
\item object-oriented data-driven model
\item super direct matching scheme
\item highly fused pipeline
\item multiple-RISC concept
\item functional interconnection network
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Object-Oriented Data-Driven Model}
\end{center}
strongly connected arc model \vspace{5mm}\\
+ side-effect within a block \vspace{5mm}\\
+ sequencing by non-data-dependencies within a block \vspace{1.5cm}\\
critical section: indivisible code block (ICB)
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Super Direct Matching Scheme}
\vminus
\end{center}
direct matching \\
+ TS held by a packet \\
+ different dpl. between matching and instruction \\
- linking overhead between TS and OS  \\
= much more flexible and fast data matching \vspace{14cm}\\
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Highly Fused Pipeline}
\end{center}
\vminus
{\it Pipelines are naturally and more efficiently fused.}
\vminus
\begin{itemize}
\vminus
\item packet-based circular pipeline : multi-context
\vminus
\item register-based advanced control pipeline: single context
\vminus
\item (interlock) floating pipeline
\vminus
\end{itemize}
\vspace{11cm}
pipeline pitch: logically 1/2 of \emfour (25ns)
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf \emcg: an \emfive$\,$ single chip processor\\}
{\it 40 MIPS processor; off-chip FPU: 80 MFLOPS}
\end{center}
\begin{itemize}
\item independent off-chip packet buffer
\item network switch excluded
\end{itemize}
\vspace{13cm}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf \emfive: a feasible parallel supercomputer}
\end{center}
\vminus
\begin{itemize}
\item 16,384 PEs
\vminus
\item processing: 1.3 TFLOPS, 655 MIPS
\vminus
\item network: 5.49 TB/s
\vminus
\item synchronization: 131 GSYPS
\vminus
\item targets
\vminus
\begin{itemize}
\item numerical computation
\vminus
\item symbolic computation
\vminus
\item large scale simulation
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf High Level Language Systems}
\end{center}
\vspace{20cm}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Object Oriented Programming}
\end{center}
\emfive$\,$ is fairly advantageous, because:
\begin{itemize}
\item fast synchronization: 125 ns, pipelined
\item network performance : 25 ns delay between nodes
\item no pipeline break, no context switching overhead 
\item ICB for local side-effect operations
\end{itemize}
\end{slide}

\begin{slide}{}
\vspace*{18cm}
\begin{center}
Object Implementation (Example)
\end{center}
\end{slide}

\begin{slide}{}
\begin{center}
{\dg \bf Conclusion}
\end{center}
\emfour$\,$ and \emfive$\,$ 
\vspace{-7mm}
\begin{itemize}
\item design principles 
\vspace{-7mm}
\item architecture
\vspace{-7mm}
\item implementation
\vspace{-7mm}
\item language systems
\vspace{-7mm}
\item object oriented scheme
\vspace{-7mm}
\end{itemize}
{\dg \bf schedule}
\vspace{-7mm}
\begin{itemize}
\item \emfive$\,$ logical design: 1991
\vspace{-7mm}
\item \emcg$\,$ gate design: 1992
\vspace{-7mm}
\item \emfive$\,$ final design: 1993
\vspace{-7mm}
\item \emfive$\,$ prototype : March 1994
\end{itemize}
\end{slide}{}

\begin{slide}{}
\begin{center}
{\dg \bf Future Problems}
\end{center}
\begin{itemize}
\item language systems
\item further examination of a computational model
\item scheduling methods
\item test and evaluations
\item actual application programs
\end{itemize}
\end{slide}
