\section{Basic Interconnection Networks}
\seclabel{part1}

\subsection{``Ideal'' Parallel Computer and Definitions}
\figref{fig:ideal} (left panel) depicts an ideal parallel computer.  It's ideal in the sense
that every processor, $P$, can communicate directly with every memory
module, $M$.  If the processors and memory modules are combined as in a
distributed shared memory computer, the graph looks like the right panel
of Figure 1.  



A \defn{diameter} of a network is the longest shortest-path between two
nodes. 
% WHY DON'T WE JUST SAY ``shortest-path''
 The diameter of the ideal parallel computer is $\Theta(1)$, but building such a computer would prove difficult for several
reasons.  First, there are $\Theta(n^2)$ wires in the system since 
each node must communicate to $\Theta(n)$ other nodes and a given node has
degree $\Theta(n)$.  Not only is the total number of wires large, but
the number of wires at a particular node (its degree) is large as well.  Furthermore,
 the fact that the degree depends on $N$ makes it difficult
to build uniform, modular nodes.  

\vspace{1em}

\begin{figure}[bthp]
\centering
\includegraphics[width=2in, angle=-90]{16/slide2.epsi}
\hspace{1in}
\includegraphics[width=2in, angle=-90]{16/slide3.epsi}
\vspace{.5in}
\caption{Ideal Parallel Computers}
\figlabel{fig:ideal}

\end{figure}

Figure \ref{fig:networks} shows several low/constant degree networks and their diameters
are listed in Table \ref{tab:diameters}.

\begin{table}[h]
\centering
\begin{tabular}{|l|l|l|}\hline
Network & Diameter & Comment \\ \hline
Linear array & $\Theta(n)$ & Simplicity is nice, but only feasible for
small networks \\
2D-Mesh & $\Theta(\sqrt{n})$ & $\Theta(\sqrt{n})$ is an improvement over
the linear arary, but can still be large\\
Tree & $\Theta(\lg{n})$ &  \\ \hline
\end{tabular}
\caption{Diameters of common networks}
\label{tab:diameters}

\end{table}

\begin{theorem}
If a network has $\bigO(1)$ degree, it has $\Omega(\lg N)$ diameter.
\end{theorem}
\begin{proof}
Begin by listing the number of nodes at a given distance from a
particular node (in terms of degree, $d$):
\begin{table}[h]
\centering
\begin{tabular}{|l|l|l|l|l|l|} \hline
Dist & 0 & 1 & 2 & 3 & k \\ 
Number of nodes & $1$ & $d$ & $d(d-1)$ & $d(d-1)^2$ & $\Theta(d^k)$ \\ \hline
\end{tabular}

\label{tab:nodes}
\end{table}

If there are $N$ nodes, $\Theta(d^k) \ge N$ which implies $k =
\Omega(\lg_d N)$.
\end{proof}

\begin{figure}[bthp]
\centering
\includegraphics[width=2.5in, angle=-90]{16/slide4.epsi}
\caption{Common Networks}
\label{fig:networks}

\end{figure}

Of the networks we've looked at so far, the tree and ideal network have
the lowest diameters, but are they good routing networks?
Unfortunately, these metrics of \textit{wires}, \textit{degree}, and \textit{diameter} do not take
into account network congestion or hotspots.  It's easy to see how
congestion might be a problem in the tree: if all nodes on the left want
to communicate with nodes on the right, all messages must go through the
root where they are serialized.  Another problem (which will be
addressed in a different lecture) occurs when many processors want to
access the same node.  If nodes can handle $\approx 1$ message at a
time, a ``hotspot'' is created.

To start thinking about congestion, we
must first define \defn{minimum bisection width}. Minimum bisection
width (or simply bisection width) refers to the minimum number of edges that must be removed to
partition a network into halves (or within one, for networks with an odd
number of nodes).  Bisection width for various networks are shown in
Table \ref{tab:bw}.

\begin{table}[h]
\centering
\begin{tabular}{|l|l|l|}\hline
Network & BW & comment \\ \hline 
Tree & $1$ & this is by severing a link at the root.  Of course \\ 
& & you could chop off all leaves, but that would be \textit{maximum}
number of edges.\\ 
Linear array & $1$ & \\ 
2D-Mesh & $\sqrt{n}$ & \\ 
3D-Mesh & $n^{2/3}$ & edge of cube is $N^{1/3}$ nodes long.  \\ 
& & A slice through middle of cube would sever ${N^{1/3}}^2$ connections. \\ \hline
\end{tabular}
\caption{Bisection Widths}
\label{tab:bw}
\end{table}

Knowing the bisection width (BW), we can prove a result on the expected
routing time.
\begin{theorem}
Consider an $N$ node network with diameter $d$.  If $N$ messages are
sent to random destinations from $N$ processors, $E[{routing\ time}] = \Omega(N/{BW} + d)$.  
\end{theorem}

\begin{proof}
We expect $\Theta(N)$ messages to cross BW wires.  If each wire ships
$\le 1$ message in unit time, ${time} \ge \Theta(N)/{BW}$.  We also note
that $E[{Time}] = \Omega(diameter)$ (proved in the next lecture).  Note
that $(x+y)/2 \le max(x,y) \le x+y$.  The lower bound on expected time is
$max(N/{BW}, d)$ which we can express $\Omega(N/{BW} + d)$.  
\end{proof}

\section{Hypercubes}
The next network we will examine is the hypercube.  Hypercubes have a
large bisection width and short diameter.  It is simple to figure out
routing on a hypercube.  Unfortunately, they do not have constant degree
as we will see in the following construction.  
\subsection{Hypercubes explained}
A hypercube's recursive
construction is shown in Slide 5, but it may be more convenient to
define the hypercube based on the binary representation of its nodes.
Each of the $n$ nodes is represented by $\lg n$ bits: $\ang{b_{d-1},
b_{d-2}, ... , b_0}$.  To form the network, node $\ang{b_{d-1}, b_{d-2},
... , b_0}$ is connected to the nodes:\\
$\ang{\overline{b_{d-1}}, b_{d-2}, ... , b_0}$ \\
$\ang{b_{d-1}, \overline{b_{d-2}}, ... , b_0}$  \\
$\ang{b_{d-1}, b_{d-2}, ... , \overline{b_0}}$.  \\

\noindent That is, two nodes are connected if their Hamming Distance (number of
bit positions in which they differ) is 1.

