\subsection{Routing on a Hypercubes}

Using binary representation, routing on a hypercube is achieved by
comparing the starting and destination node addresses, sending the
message along the dimension of each differing bit. Specifically, an
{\tt XOR} of the starting and destination addresses yields routing
instructions, where a 1 at a particular bit position indicates the
need to route along the dimension associated with that position.

\begin{tabular}{l|l}
Start & 10111010 \\
End & 01101110 \\
XOR & 11010100
\end{tabular}

We note the following properties for a hypercube:
\begin{tabular}{l|l}
Diameter & $\lg N$ \\
Time & $\Omega(\lg N)$ \\
Degree & $\lg N$ \\
BW & $N/2$ \\
\# of wires & $\Theta(N\lg N)$ \\
\end{tabular}

\subsection{Cube-Connected Cycles}

Hypercube networks still have variable node degrees, which can be a
problem for network modularity. \defn{Cube-Connected Cycles} (CCC)
offer a structure with many properties similar to those of hypercubes,
but with a fixed degree.

The construction of a CCC network is shown in Slide 7, which clearly
shows that each node's degree is in fact 3 (even when we move to
higher dimensions). Routing is still performed by {\tt XOR}ing the binary
representations of starting and destination nodes, routing within the
cycle for a 0 bit, and routing out on the cube for a 1 bit.

We note the following properties for a CCC network:

\begin{tabular}{l|l}
Cycles & $N= n\lg n$ nodes \\
Degree & $\Theta(1)$ \\
Diameter & $\Theta(\lg N)$ \\
BW & $\Theta(n) = \Theta(N/\lg N)$ \\
\# of wires & $\Theta(N\lg N)$ \\
\end{tabular}

\section{Butterfly (FFT) Networks}

\subsection{Construction}
A \defn{Butterfly Network}, also called an FFT network, is constructed
as shown in Slide 8, with $n$ input nodes and $n$ output nodes. The
network can be {\bf direct} or {\bf indirect}, depending on whether
the last layer of nodes is in fact same as the first layer. (MORE
DETAILS HERE on this direct vs. indirect --ben).

Given the construction of the network, given $n$ input nodes, the
number of total nodes is $N = n \lg n$. We note the following
properties:

\begin{tabular}{l|l}
Diameter & $\Theta(\lg N)$  \\
Degree & $\Theta(1)$ \\
BW & $\Theta(n) = \Theta(\frac{N}{\lg N})$ \\
\end{tabular}

A butterfly network is, in fact, exactly the same as a CCC network,
a fact overlooked by the original authors.

(SOMETHING HERE ABOUT DECOMPOSING A BUTTERFLY network --Ben)

\subsection{Routing and Congestion}

Routing on a butterfly network is much like on a hypercube, using the
specific order of the dimension. Specifically, if we {\tt XOR} the
starting and destination binary addresses, a bit value of 0
indicates a straight routing, while a bit value of 1 indicates a cross
routing.

(We note, in the construction of a butterfly network, the presence of
binary trees rooted at each input and at each output.)

Packet routing from a specific source $x_{d-1}x_{d-2}...x_0$ to a
specific destination $y_{d-1}y_{d-2}...y_0$ progresses from major to
minor bit, as follows:

\begin{itemize}
\item $x_{d-1}x_{d-2}...x_0$
\item $y_{d-1}x_{d-2}...x_0$
\item $y_{d-1}y_{d-2}...x_0$
\item ...
\item $y_{d-1}y_{d-2}...y_0$
\end{itemize}

Routing takes $d= \lg n$ steps, but there remains a fairly congested
worst-case scenario. The worst-case routing scenario occurs for
packets originating at sources $x_1x_2x_3x_40000$ going to
destinations $0000x_1x_2x_3x_4$. There are $\sqrt(n)$ such packets,
and all must go through the $00000000$ halfway point.

\seclabel{part2}



