From Ranka@top.cis.syr.edu Wed Sep 16 19:51:29 1992
Received: from mime.top.cis.syr.edu by spica.npac.syr.edu (4.1/I-1.98K)
	id AA07249; Wed, 16 Sep 92 19:51:26 EDT
Message-Id: <9209162351.AA07249@spica.npac.syr.edu>
Date:     Wed, 16 Sep 92 19:49:00 BST
From: Sanjay Ranka <ranka@top.cis.syr.edu>
To: zbozkus@nova.npac.syr.EDU
Subject:  paper
Phone:    315-443-4457 Fax: 315-443-1122
Address:  4-116 CST, School of Computer Science, Syracuse University, Syracuse, NY 13244-4100
Status: R

\documentstyle[12pt,titlepage]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}

\date{}



\title{\Large\bf Performance comparison of the CM-5 and Intel Touchstone
delta for simple global operations\thanks{This work was supported in
part by NSF
 under
CCR-9110812 and DARPA under
contract \# DABT63-91-C-0028.  The content of the information does not
necessarily reflect the position or the policy of the Government and no
official endorsement should be inferred.}
}

\author{Zeki Bozkus, Sanjay Ranka, Geoffrey Fox and  Alok Choudhary \\
         School of Computer Science  \\
         4-116, Center for Science and Technology  \\
         Syracuse University  \\
         Syracuse, NY 13244-4100 \\
         zbozkus@npac.syr.edu  \\
         ranka@top.cis.syr.edu \\
         gcf@npac.syr.edu
}
\maketitle

\thispagestyle{empty}

\begin{abstract}
This paper describes the  performance comparison
of the CM-5 multiprocessor and Intel Touchstone Delta.
We describe comparisons for important collective communication routines
and several applications.
\end{abstract}

\section{Introduction}
This paper presents results of a set of benchmark programs run on the
CM-5
machine\footnote{\em Note to the referees: the current version of the
paper is l
imited to the scalar version of the
CM-5. It is expected that within the next few months the CM-5 would be
upgraded
to
the floating point vector units increasing the computational performance
significantly. We expect to add performance results of vector units at
that time.} and the Intel Touchstone Delta.
The current study has two goals.
The first goal is
to
benchmark the CM-5 and Intel Touchstone delta for its performance. The second goal is to model the
primitives in a fashion that it will be useful for estimating the
performance of
applications on these machines. These primitives are modeled
by linear performing regression using SAS, a statistical package widely
available. The parameters for each primitive are chosen appropriately.

The rest of the paper is organized as follows.

\section{Architecture of the CM-5}

The CM-5 is a distributed memory multiprocessor. The processors are
interconnected using three networks: data network, control network and the
diagnostics network. The data network is useful for
processor to processor communication for bulk transfer. The control network, in
general, is useful to perform operations which require the participation of all the
nodes simultaneously, such as broadcasting and synchronization. 
Thus communication between two nodes can be performed by using 
the data network or  the control network.
The diagnostic network is for fault diagnosis/maintenance of the system. This paper
is restricted to the control network and the data network.

\subsection{Processors}
Each node is a SPARC microprocessor with four vector units of a CM-5 system and
32 Mbytes of memory (Figure \ref{sparc}.) 
The Sparc processor has a clock of 33Mhz. A 64Kbyte cache is used for
both instruction and data. It has separate integer and floating point
registers. The Sparc processor is rated at a peak performance of 22
Mips or
5 MFlops. It performs the instruction fetching, controls the processing
engines for vector units ( in the full version of CM-5 ) and manages 
the communication with other system
components via the network interface.
\begin{figure}
\begin{center}
\input{sparc}
\end{center}
\caption{CM-5 processing node with vector units.}
\label{sparc}
\end{figure}
The vector units perform one memory operation and one arithmetic
operation per cycle at 16Mhz (half the rate of the SPARC). It can
perform a multiply and add in one cycle. Thus the peak performance of
each vector unit is 
32 Mflops for multiply-add and 16Mflops for add or multiply.

Thus a processing node with four vector units can give a peak
performance of 128 MFlops (for multiply-adds) and 64 Mflops for 
multiplies or adds alone.

\subsection{Networks}
Every node in the CM-5 is connected to two interprocessor
communications networks, the data network and the control network.
There is a separate network for carrying out diagnostics. 
\subsubsection{Control Network}
The control network provides hardware support for common cooperative
operations. These operation include integer sum, max, min, and, or, xor,
parallel prefix and segmented parallel prefix. Further, it provides
barrier synchronization. The control network has a relatively low latency. This
combined with a high bandwidth provides fast execution of the above
operations.
\subsubsection{Data Network}
The data network is a message passing point to point routing network.
The network topology is a quad tree based structure with a network
interface at all the leaf nodes. 
The CM-5 is  designed to provide a peak bandwidth of 5 MBytes/s for
point to point communication between any two nodes in the system.
However, if the destination is within the same group of 4 or 16, it can
give a peak bandwidth of 20 Mbytes/s and 10 Mbytes/s respectively\cite{12}.

\begin{figure}
\begin{center}
\input{dnet16}
\end{center}
\caption{Data network with 16 nodes.}
\label{dnet16}
\end{figure}

\begin{figure}
\begin{center}
\input{dnet64}
\end{center}
\caption{Data network with 64 nodes.}
\label{dnet64}
\end{figure}

Figure \ref{dnet16} and \ref{dnet64} show the network 
for 16 nodes and 64 nodes respectively.
%Figure .. gives the network for a general case (N $\ge$ 256).
The CM-5 network is redundant in nature and is fault tolerant. 
The routing is deadlock free and the conflict arbitration is fair
\cite{10}.
\subsection{Test System}
Our experiments were performed on 32 node CM-5 at Northeast Parallel
Architecture Center at Syracuse and a 512 node CM-5 at The Army High
Performance Research Center  at University of Minnesota.

All the measurements reported in this paper were done using programs written in C.
The timings were estimated by measuring the time for $m$
repetitions of the experiment and dividing the time by $m$.
The value of $m$ was varied from 1 to 100 as required for the accuracy
of measurement. 
\section{Architecture of the Intel Touchstone Delta}
\subsection{Processors}

The touchstone delta machine consists of 540 i860-based nodes
(Figure 8).  
The i860-based numeric node operates at 40 MHz and is rated at 33
MIPS, 80 (peak) single-precision MFLOPS, and 60 (peak) double-
precision MFLOPS.  
It is capable of
executing more than one integer instruction and one floating point
instruction per clock in its superscalar mode of operation.
There are two internal caches: 4-KByte code and 8-KByte data catches.
The numeric node supports
8 or 16 MBytes of parity-checked 
DRAM and a high-speed FIFO-based interface to the MIM. The on-board
memory is organized in pages. This  provides fast access to
consecutive references in the same page.  References to distant
pages require additional set-up time.
A high-resolution counter provide timing information for
diagnostic and application programs.


\subsection{Network}
Message passing, including message assembly,
transmission, reception, and disassembly is done under program
control by the i860 microprocessor.

The system uses a two-dimensional mesh topology for its
interconnection network. The communication 
over the interconnection network is done in terms of messages. The messages
are divided into fixed length packets. 
These packets are transmitted over the network
interleaved with messages from other nodes.

The routing on the  mesh uses wormhole routing chip.  A sending node
transmits one or several packets that contain a message by moving
the data.  Each packet is examined to determine the routing path of  the
packet through the network.  A packet moves from  a node to another node
along the row of the mesh until it has reached the column of the
receiving node.  It then moves along the column until
it arrives at the destination node. 

\section{Comparison of the  Computational Performance}
\subsection{Scalar operations on the Cm-5 and Touchstone delta}
We implemented a series of tests to measure the arithmetic speed of the
Sparc processor for integer and floating point operation. A comparison
with the timings on the Intel Delta processor i860  is also provided 
at table \ref{table1}.
The current Sparc chip has  performance 2 to 3 times slower than i860 processor
 (running at 40 MHz) .

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c |c ||} \hline
Operation & CM-5 &  DELTA \\
          & ($\mu$s)  &($\mu$s) \\    \hline \hline
short +   & 1.22  &0.54  \\
long  +   & 1.35  &0.62  \\
float +   & 1.57  &0.68  \\
double +  & 1.88  &0.69  \\ \hline

short *   & 1.75  &0.69  \\
long  *   & 1.90  &0.62  \\
float *   & 2.19  &0.62  \\
double *  & 2.05  &0.68  \\ 
\hline
\end{tabular}
\end{center}
\caption{Time for arithmetic operation on CM-5 and Delta}
\label{table1}
\end{table*}

\subsection{Vector operations on the CM-5}
\section{Basic Node to Node Communication on the two architectures}
\label{sec_node_node}
The cost metric for data references on distributed data structures
is quite different from a stored, global physical memory.  The
source of this difference is the communication system that is used
to move data between memory units.  This data motion is the most
critical operation with respect to performance.  The modeling of
this part of the system is imperative for any distributed memory
architecture.

This section describes the results for basic node to node communication.
Message passing routines on CM-5 support two types of messages: standard
messages in which bytes are in normal sequential order and vector
messages in which elements (many bytes) are stored with strides ( a
fixed amount of space). Most of the routines support the same
primitives for both types of messages. We only performed experiments for
standard messages. The performance of these primitives for vector messages
should be similar.
\subsection{Send and Receive for Regular messages}
We wanted to measure the time necessary for sending a message from one
node to another. We measured this time for node 0 to all the other
nodes in the system. Since, one way messages are difficult to measure,
this time is estimated by dividing the round trip time by 2. The
round trip time is calculated using the following algorithm. Node 0  starts the
clock and sends a message to node $i$ ($i \neq 0$). Node $i$ waits for
a message form node $0$ and echoes this message back. Node 0 stops the
clock after receiving the message.
The send and the receive used on the CM-5 are both blocking in nature.
\subsubsection{Neighbour communication}
The best performance communication is between two neighbours in all networks. 
We measured the message passing time between node 0 to node 1 on the CM-5.
If the buffer is improperly (word) aligned the current implementation  
is relatively slower (by a factor of 4 !)  for moving data from node memory into Network
interface. Figure \ref{neighbor_notaligned} shows sending different size of
messages from Node 0 to Node 1. But figure \ref{neighbor_aligned} shows sending
 word aligned messages ( divisible by 16) from Node 0 to Node 1. The time can be modeled by the following equation
\begin{equation}
 T(l) = 73.39 + 0.126*l \hspace{0.5in} microseconds
\end{equation}
For comparison, the corresponding equation for the Delta at \cite{14} is 
 \[ T(l) = 100 + 0.139*l \hspace{0.5in} microseconds \]

The timing of the Delta which we observed is higher than given in
\cite{}.

\begin{figure}
\begin{center}
\input{neighbor_notaligned}
\end{center}
\caption{Neighbour communication between node 0 to node 1 with unaligned 
 message length (not have to be divisible by 16)(time is milliseconds). }
\label{neighbor_notaligned}
\end{figure}


\begin{figure}
\begin{center}
\input{neighbor_aligned}
\end{center}
\caption{Neighbour communication between node 0 to node 1 with  word aligned message length (divisible by 16) (time is milliseconds).}
\label{neighbor_aligned}
\end{figure}

Figure \ref{neighbor_rate} shows that the transfer rate for the aligned buffer is around 
8 Mbytes/sec for CM-5 and .. for the Intel Touchstone Delta.



\begin{figure}
\begin{center}
\input{neighbor_rate}
\end{center}
\caption{Transfer rate for neighbour communication between node 0 to node 1
with  word  aligned messages}
\label{neighbor_rate}
\end{figure}

\subsubsection{Non-neighbor communication}
We measured the communication time from node 0 to every other nodes
using the same strategy as the previous section.
The results for a message of size 16 and 2000 bytes at CM-5 are presented in 
figure \ref{span16} and \ref{span}. It  shows that the difference in time to communicate between neighbour and non-neighbour 
is negligible. 
Again, this could be attributed to the fact that the bandwidth is
limited by how fast the Sparc processor (using the C program) can pump
data into the network interface.

{\sl you need timing figures for large message ! Mega byte}
\begin{figure}
\begin{center}
\input{span16}
\end{center}
\caption{Communication from node 0 to every other node on a 512 nodes CM-5 for a message of 16 bytes (time is milliseconds). }
\label{span16}
\end{figure}


\begin{figure}
\begin{center}
\input{span}
\end{center}
\caption{Communication from node 0 to every other node on a 512 nodes CM-5 for a message of 2000 bytes (time is milliseconds). }
\label{span}
\end{figure}

The results for a message of size 16 and 2000 bytes at DELTA are presented in 
figure \ref{delta_span16} and \ref{delta_span2000}. It  shows that the difference in time to communicate between neighbour and non-neighbour 
is negligible. 

\begin{figure}
\begin{center}
\input{delta_span16}
\end{center}
\caption{Communication from node 0 to every other node on a 512 nodes DELTA
 for a message of 16 bytes (time is milliseconds). }
\label{delta_span16}
\end{figure}

\begin{figure}
\begin{center}
\input{delta_span2000}
\end{center}
\caption{Communication from node 0 to every other node on a 512 nodes DELTA for a message of 2000 bytes (time is milliseconds). }
\label{delta_span2000}
\end{figure}



\section{Global Operations}
Scans, reductions, and concatenation are some of the global operations
provided by the CMMD library. Given a buffer
containing a value  in each node, these global computations operate 
simultaneously on the buffer set to perform such tasks as
\begin{itemize}
\item summing the value across all the nodes
\item finding the largest or smallest value
\item performing a bitwise AND, OR, or XOR
\end{itemize}
\subsection{Scan Operation}
A scan (a parallel prefix operation) creates a running tally of 
results  in each processor in the order of the processor identifier.
Assuming that the $A[j]$ represents the element $A$ in the $j$th
processor and $R[j]$ represents the result $R$ in the $j$th processor.
Then a scan (with an add) performs the following operation

\[ R[i] = \sum_{j=0}^{i-1} A[j] \hspace{0.2in}  0 \leq i < P\]

where $P$ is the number of processors.There are several versions of scan 
with behaver similar to above.

Table \ref{scan1} shows the performance of scan operation for a 32 node CM-5.

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c | c| c |c | c | c | c ||} \hline
Operation & type & add & mult & max & min & ior & xor & and  \\   \hline \hline
scan CM-5& int    & 10.14 & * &10.14 & 9.51 & 10.48 & 10.47 & 9.81 \\
scan CM-5& double & 47.57 & * & 54.16 & 55.91 & * & * & *  \\
\hline \hline
reduce CM-5 &int  & 6.63 & * &6.95 & 6.29 & 6.95 & 6.96 & 6.63 \\
reduce CM-5 &double & 39.48 & * & 42.21 & 46.76 & * & * & *  \\
\hline \hline
reduce DELTA &int & 778.9 & 778.9 & 772.0 & 777.9 & 782.0 & 777.9 & 771.0  \\
reduce DELTA &double & 787.9 & 791.9 & 790.0 & 791.9 & * & * & * \\
\hline
\end{tabular}
\end{center}
\caption{scan, segmented scan and reduction with host ( result on the host and nodes) reduce only host ( result only on the nodes) operation on 32 nodes. Time unit is microseconds.
 * : represents an undefined operation.}
\label{scan1}
\end{table*}


\subsection{Segmented Scans}
In a segmented scan, independent scans are computed simultaneously on different 
subgroups ( or segments) of the nodes. For a detailed description of segmented 
scans, the reader is referred to \cite{8}. The segments are determined at run time
by an argument called the {\em sbit\/} which is a segment bit.  {\em sbit\/} $=$ 1, represents the beginning of a new segment.
Table \ref{scan1} shows the performance of a segmented scan operation on
a 32 node CM-5  assuming {\em sbit\/} is 1 with a probability of 0.1.


\subsection{Reduction Operation}
A reduction operation takes as input a value  in every processor and outputs 
a single value, either in every processor or in the host processor. 
The operation performed can be one of the following  : {\em add}, {\em max}, {\em min}, 
{\em ior}, {\em xor} and {\em and}.

Table \ref{scan1} gives the time required for
the reduction operation assuming that the result is on the host and nodes or 
the result is on the nodes. The host in the reduction operation 
slows down the operation by an order of magnitude.

\subsection{Concatenation Operation}
Concatenation  appends the value from each processor to the values of all
preceding processors (in processor identifier order). CMMD provides two versions of concatenation: one concatenates across the nodes only, and writes the resulting value into a buffer on every node. The other concatenates values from
every node into a buffer on the host. The result of the concatenation 
is always ordered from the lowest to highest node \cite{11}.

Assuming that each processor has $N $ elements,
and there are $P$ processors.
Suppose processor $i$ contains a vector $V_i [ 0 \cdots {N  -1}]$.
The global concatenate operation computes
a concatenation of the local list in each of the processors.
The resultant vector $R [ 0 \cdots NP-1]$ is stored
in 
the host or in every node.

\[ R[j] = V _{ j \;div\; N} [ j \;mod\; N] \]

Figure \ref{cm5_delta_con32} and \ref{cm5_delta_con512} shows the time required for concatenation using 32 and 512 
nodes with the result at the nodes on CM-5 and DELTA.
The length of the resultant vector is proportional to the product of $N$
and $P$. From figure  \ref{con1}, it is clear that the time for concatenation on 512 nodes
is 15.36 ($\approx$ 16) times larger than 32 nodes. 
>From figure \ref{con1} we approximately derive the equation 6 for concatenation
operation at nodes.
\begin{equation}
 T(l,p) = p + 1.2*p*l \hspace{0.5in} microseconds
\end{equation}
$l$ is message length and $p$ is the number of nodes in that partition.
Clearly, concatenation operation is scalable.
  \[ T(l,512)/T(l,32) \approx 16\]
However when the result is to be stored on the host the timings are
irregular and larger  than the case when results are stored on the nodes.
This can be mainly attributed to the reasons described in  section
\ref{sec_host_node}.

\begin{figure}
\begin{center}
\input{cm5_delta_con32}
\end{center}
\caption{Concatenation with result at the  32  nodes on CM-5 and DELTA (time is milliseconds).}
\label{cm5_delta_con32}
\end{figure}


\begin{figure}
\begin{center}
\input{cm5_delta_con512}
\end{center}
\caption{The concatenation with result host and nodes at  512 nodes on 
CM-5 and DELTA (time is milliseconds).}
\label{cm5_delta_con512}
\end{figure}



\subsubsection{Broadcast from one node to  all nodes}
When we write SPMD style programming,
one of the common kind of communication is to broadcast from one node to the rest of node. 
Figure \ref{cm5_delta_bc32} and \ref{cm5_delta_bc512} shows 
performance of this primitive on CM-5 and DELTA at 32 
and 512 nodes respectivelly.
We derive the following Equation 7 and 8 for 32 and 512 nodes CM-5.
\begin{equation}
 T(l) = 19.38  + 1.49*l \hspace{0.5in} microseconds
\end{equation}

\begin{equation}
 T(l) = 5.0  + 1.46*l \hspace{0.5in} microseconds
\end{equation}


\begin{figure}
\begin{center}
\input{cm5_delta_bc32}
\end{center}
\caption{Broadcasting from one node to  all the other nodes on a 32  nodes CM-5 and DELTA(time is milliseconds). }
\label{cm5_delta_bc32}
\end{figure}



\begin{figure}
\begin{center}
\input{cm5_delta_bc512}
\end{center}
\caption{Broadcasting from one node to  all the other nodes on a 512  nodes CM-5 and DELTA(time is milliseconds). }
\label{cm5_delta_bc512}
\end{figure}

We implemented a series of tests to measure the arithmetic speed of the
Sparc processor for integer and floating point operation. A comparison
with the timings on the Intel Delta processor i860  is also provided 
at table \ref{table1}.
The current Sparc chip has  performance 2 to 3 times slower than i860 processor
 (running at 40 MHz) .

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c |c ||} \hline
Operation & CM-5 &  DELTA \\
          & ($\mu$s)  &($\mu$s) \\    \hline \hline
short +   & 1.22  &0.54  \\
long  +   & 1.35  &0.62  \\
float +   & 1.57  &0.68  \\
double +  & 1.88  &0.69  \\ \hline

short *   & 1.75  &0.69  \\
long  *   & 1.90  &0.62  \\
float *   & 2.19  &0.62  \\
double *  & 2.05  &0.68  \\ 
\hline
\end{tabular}
\end{center}
\caption{Time for arithmetic operation on CM-5 and Delta}
\label{table1}
\end{table*}

\section{Summary of Performance Models for Collective Communications}
Table \ref{summary} presents a summary of the performance modeling of all the
global communication primitives for CM-5. This table shows that CM-5 is 
scalable for these operations.

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | l ||} \hline
 Communication Type &  Derived Formula \\    \hline \hline
 Neighbour          & 
 \[T(l) = 73.39 + 0.126*l \hspace{0.5in} microseconds \] \\
 Broadcast from Host (32 nodes) &
 \[T(l) = 527 + 0.83*l \hspace{0.5in} microseconds\]  \\
 Broadcast from Host (512 nodes) &
 \[T(l) = 542 + 0.83*l \hspace{0.5in} microseconds\]  \\
 Broadcast from node  (32 nodes) &
  \[T(l) = 19.38  + 1.49*l \hspace{0.5in} microseconds\]  \\
 Broadcast from node (512 nodes) &
  \[T(l) = 5.0  + 1.46*l \hspace{0.5in} microseconds\]  \\
 Distribute from node (32 nodes) &
 \[T(l) = 360 + 1.15*l \hspace{0.5in} microseconds \] \\
 Distribute from node (512 nodes) &
 \[T(l) = 2600 + 1.13*l \hspace{0.5in} microseconds \] \\
 Concatenation to Host&
 \[T(l,p) = p + 1.2*l \hspace{0.5in} microseconds\] \\
\hline
\end{tabular}
\end{center}
\caption{Summary of all derived equations for communication on CM-5}
\label{summary}
\end{table*}

\section{Comparison of Computation to Communication Ratio}
Computation and Communication

Fox et al. [Fox book] relate computation to communication as the single
most important parameter to characterize a parallel machine.

$t_ calc$: The typical time required to perform a generic
          calculation. For scientific problems, this can be taken
          as a floating point calculation, such as a = b - c.

$t_comm$:   The typical time taken to communicate a single word
          between two nodes connected in the hardware topology.  To
          decrease the efect of start-up.  We get average timing of
          sending N words.

The ratio , $f_c$ = $t_comm \over t_calc$ charecterize typical communication and
computation (calculation) times is crucial to the performance of
parallel machines.

The fractional communication overhead $f_c$ gives a measure of how
well balanced a computer is.  For small $f_c$, computer can be called
well balanced.  For example $f_c$ < 1 shows that it is better to
spread the data to other nodes rather than to calculate all values
on this node itself.  Table x shows the $f_c$ of CMS and Delta.  $f_c$
does not show everything in the parallel machine.  The magnitude of
$t_calc$ depends upon both the nature of the floating point operation
and such thing as the storage location of data.  It depends on whether they
are in memory,
cache or in registers.  $T_comm$ depends upon the number of
word being transfered between nodes.  This is due to the fact that communication
hardware and software incur significant startup times.  We should
note that $t_comm \over t_calc$ is also highly dependent on the floating-
point hardware used.

\section{Benchmarking on Some applications}
\subsection{Performance Comparison for global operations}
At CM-S, the operations of integer summation, finding the
integer maximum, logical OR, and logical exclusive OR are
supported directly in hardware by the Control Network. In
other words, the Control Network contains integer and logical
arithmetic hardware for carrying out reduction operations.
This hardware is distinct from the arithmetic hardware of the
processing nodes; (The arithmetic hardware of the Control
Network can also compute various forms of parallel prefix
operations (scan operation)).  Floating-point reduction
operations are carried out by the nodes with the help of the
control Network and Data Network.  (That's why as seen in
table X, integer reduction 5 times better than floating-point
reduction).

But at Delta, reduction operations fon't have dedicated hardware.
And all implemented  at software.  That is why they are two-fold
slower than CM-S reduction operations.

\subsection{Performance Estimation for Gaussian elimination}
Modeling of the primitives is useful in estimating the performance of a
given program \cite{16}.
We use Gaussian elimination to illustrate how to estimate the performance of a program by using results mentioned in the previous sections.
Figure \ref{code} is the computational intensive segment of a Gaussian elimination program.
The row-column-oriented algorithm with partial pivoting is used here \cite{7} .

\begin{figure}
\begin{center}
\begin{verbatim}
  double a[N/nproc][N+1]
  for(i=0;i<N;i++) {
    find pivoting row 
       by using two reduction operations;
    broadcast pivoting row;
    some vector computation;
  }
\end{verbatim}
\end{center}
\caption{Gaussian Elimination Code for Program Estimation.}
\label{code}
\end{figure}

Table \ref{bench} is a portion of the relevant data derived from our
benchmarking and modeling results presented in the previous sections. 
The execution time of each iteration is multiplied by the number 
of iterations to obtain the estimated time. There are $N$ iteration for matrix size of $N \times (N+1)$.
This code was executed on a 32 node CM-5. The measured results are
compared to the estimated results in Table \ref{esti}.
Such modeling can be useful in performance prediction
 different algorithms.
One can use this information in choosing algorithms and optimizing 
program codes.
One can automate performance estimation at compile time 
by using cost function of each primitives instead of real operations.

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c | c | c | c | c ||} \hline
Operation & Reference & $64 \times 65$ & $128 \times 129$ & $ 256 \times 257$ & $512 \times 513$ \\    \hline \hline

Reduction double with max & Table \ref{scan1} & 0.042 & 0.042 & 0.042 & 0.042 \\
Reduction int with max    & Table \ref{scan1} & 0.006 & 0.006 & 0.006 & 0.006 \\
Broadcast from node       & Equation 7        & 0.917 & 1.680 & 3.206 & 6.252 \\
Computation               & Table \ref{table1}& 0.266 & 1.057 & 4.213 & 16.823 \\ \hline
Time per iteration        &                           & 1.057 & 2.787 & 7.469 & 23.130 \\
\hline
\end{tabular}
\end{center}
\caption{Cost of operations of Gaussian elimination on 32 nodes CM-5 (time is milliseconds).}
\label{bench}
\end{table*}

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c | c | c | c ||} \hline
Matrix Size & $64 \times 65$ & $128 \times 129$ & $ 256 \times 257$ & $512 \times 513$ \\    \hline \hline

Estimated Time & 78.9 & 356.7  &  1912.1 & 11843.0 \\
Measured Time  & 72.5 & 353.45 &  1848.0 & 10948.6 \\
\hline
\end{tabular}
\end{center}
\caption{Estimated and measured time (time is milliseconds).}
\label{esti}
\end{table*}
We now compare CM-5 to the Intel Touchstone Delta Mesh for
Gaussian elimination.
The Delta system is a message-passing multicomputer, consisting of an ensemble of individual and autonomous nodes that communicate across a two-dimensional mesh interconnection network. It has 513 computational i860 nodes, each with 16 Mbytes of memory and each node has peak speed of 60 double-precision Mflops, 80 single-precision Mflops at 40 MHz.
We implemented the Gaussian elimination algorithm in both system 
by C + MP (Message Passing).

Table \ref{ind_delta} show timing of individual operation of Gaussian elimination in the Delta Mesh.
Comparing the results of  Table \ref{bench} and Table \ref{ind_delta}, The Delta 
{\em gopf \footnote{The Delta function which lets user define its own function.
We designed our function to find pivot row and its processor number in 
the Delta Mesh}
 } operation is slower 
than two reduction operations of CM-5. But the Delta is faster for  broadcasting and computation.

\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c | c | c | c | c ||} \hline
Operation & $64 \times 65$ & $128 \times 129$ & $ 256 \times 257$ & $512 \times 513$ \\    \hline \hline

 gopf   
                         & 0.86 & 0.86 & 0.86 & 0.86 \\
Broadcast from node       & 0.43 & 0.72 & 1.36 & 2.50 \\
Computation               & 0.12 & 0.48 & 2.18 & 11.10 \\ \hline
Time per iteration        & 1.41 & 2.06 & 4.40 & 14.46 \\
\hline
\end{tabular}
\end{center}
\caption{Individual operation of Gaussian elimination on 32 nodes The Delta Mesh (time is milliseconds).}
\label{ind_delta}
\end{table*}

 Table \ref{delta} compares the performance
on the two multicomputers. Thus, for Gaussian elimination it can be seen that the 32 nodes CM-5 without vector nodes is comparable to the 
 32 nodes Delta system. This is because the CM-5 (without vector units) has poor performance as compared on computation to Intel Delta Machine. 
 However, it has a faster mechanism for performing reduction. Since large 
 matrixes have more computation as seen on the tables, CM-5 is better for smaller matrixes and worse for large matrixes.


\begin{table*} \footnotesize
\begin{center}
\begin{tabular}{|| c | c | c | c | c | c ||} \hline
                  &  CM-5      & DELTA \\
Matrix Size       &  32 Nodes & 32 Nodes \\ \hline \hline
$64 \times 65$    & 72.5    & 126.0  \\
$128 \times 129$  & 353.4   & 331.0  \\
$ 256 \times 257$ & 1848.0  & 1261.0 \\
$512 \times 513$  & 10948.6 & 6062.0 \\    \hline \hline
\end{tabular}
\end{center}
\caption{Comparison of CM-5 and DELTA (time is milliseconds).}
\label{delta}
\end{table*}

\section{Conclusions}

{\sl Zeki please add the comparison with delta for each of the paras}

In this paper, we studied the performance of the CM-5 multiprocessor and
the Intel Touchstone delta. We provided a
number of benchmarks for their communication and computation performance.
The computation performance of the CM-5  is currently limited because the vector
units are not available.
In the current version the CM-5 Sparc chip has
 performance 2 to 3 times slower than i860.
It is expected that the performance should improve by at least an order
of magnitude with the full configuration (with the vector units).

The maximum node to node transfer rate was found to be 8
Mbytes/sec for unidirectional transfer between two neighbour nodes.

We studied some collective communication patterns required for solving many
interesting scientific problems (such as the mesh and hypercube).
The bandwidth for hypercube type of communications was between 4 and 5
Mbytes per second.

This was also true for  cases when all the communication passed through
the root (pseudo) of the CM-5 interconnection network.

For the mesh type of communication the bandwidth was relatively lower.
For most patterns the transfer rate was between 1.0 and 2.5 Mbytes/sec.
The reasons of hypercube type patterns having higher transfer rate can
be attributed to the following: 1) hypercube patterns require a swap
between two processors; 2) hypercube patterns embed more regularly on the
CM-5 interconnection network.

There are several global operations which use the control network for
communication. Broadcast from the host to nodes achieves a transfer rate
of 12 Mbytes/sec. Concatenation from nodes when the host is not
participating requires time linearly proportional to the size of the resultant
array. The other operations,
like max, min, add, xor, and etc.,
 which use the global
control network 
are extremely fast 
 when the
result is to be stored on the nodes
and can be completed in 6 to 7 microseconds for
integers
and 39 to 47 microseconds for double precisions.
The time are an order of magnitude higher when the result need to be
stored on the host.

Scans and segmented scans are useful primitives for solving many
applications \cite{8}. These operations are quite fast and can be
completed in 10 microseconds for integers   on 32 nodes.
For double precision the times are significantly larger (a factor of 4
for scans and a factor of 13 for segmented scans).
 
For most primitives, the participation  of the host generally degraded the total time for completion. Thus the CM-5 is more suitable for programs which require
minimum participation of the host ( such as the Single Program Multiply Data style 
of programming).

The CM-5 data and control network were found to be highly scalable.
The performance figures remained constant for most operations when we
evaluated similar primitives from 32 to 512 nodes.

A comparative study was performed between Intel Touchstone Delta and CM-5 (without vector units). We found that a 32 node CM-5 had a comparable performance to the Touchstone Delta. Although, the Sparc processor is slower as compared the i860 chip. Reduction operation is faster on CM-5 but its broadcast is slower 
than on the Delta

Once the vector units are added to the current version of CM-5, the
computation performance along with the scalable communication provided
by the data and control network and the global operations (like scans,
synchronization, max etc) provided by the control network should make
the CM-5 a versatile machine for solving many computationally 
intensive, interesting scientific
and engineering problems. 

\subsection*{Acknowledgements}
We would like to thank Steve Swartz of Thinking Machine for many clarifications
regarding the CM-5. We would like to thank Professor Vipim Kumar for 
providing access to the CM-5 at the Army High Performance Computing Center at 
University of Minnesota.We would also like to thank Min-You Wu for his suggestions
on improving the manuscript.

\bibliographystyle{unsrt}
\bibliography{last}
\end{document}
\end{document}



