\documentstyle[11pt]{article}
\newcommand{\r}[1]{(\ref{#1})}
\setlength{\textwidth}{7in}
\setlength{\baselineskip}{0.2in}
\setlength{\oddsidemargin}{-.3in}

\renewcommand{\thefootnote}{\alph{footnote}}
\begin{document}
\setcounter{footnote}{0}


\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\newcommand{\sect}[1]{\vspace{0.1in}{\section{#1}}
{\setcounter{table}{0}}{\setcounter{figure}{0}}}
\vspace{0.1in}

\title{The ``Guess what? We have a hypercube" document}
\author{\sl{Alan Edelman}
\\ Thinking Machines Corporation \\
Internal Note}

\maketitle

\begin{center}{\bf Abstract}\end{center}

Here I try my best to explain how to use the hypercube wires
on the Connection Machine.  At one time, direct use of the
wires was considered beyond the reach of reasonable programming,
but this is no longer true.  We now have the primitives
and expertise
that make self routing reasonable and actually quite fun.  
No previous experience is assumed, all you have to do is
be willing to learn about the capabilities now
available in CMIS. 
In this document I emphasize less what algorithms can be implemented
using the  
hypercube wires, and more the mechanics of how to use them.
It might be nice to have another document that shows off
how the hypercube can be used in non-trivial ways.


The CM-2's power is being terribly under-utilized.
It is my hope that several people will use this
document as a departure point for implementing fast
communications routines.
There is no doubt that fixed communications patterns
can be much faster.
This document is not at the level of a textbook yet,
but I have tried my best to explain as much as possible.
I strongly encourage people using the wires to send 
questions to the ``wires" mailing list and work with
me (while I am still around) , Mark Bromley, or Steve Heller
to take advantage of the expertise that we have gained.

Just lately I have been hearing talk about implementing
stencils as a program product.  Another product that
would run beautifully fast on the machine is an n-body
package.  Other primitives that can and should be written
are fast power of 2 news, spread row and column simultaneously
(perfect for LU), spread from diagonal accross row and column
simultaneously (perfect for Jacobi eigenvalues and SVD),
scans etc.   There is plenty of work to go around, all of
which we have the know-how to solve.  

There have been many changes in the use of the wires in the
past months.  It went from impossible (the days of Steve
Vavasis) to requiring microcode trickery
and speed hacking (this is where
I started working) to being more or less straightforward and
convenient (Mark Bromley deserves tons of credit for this).  
Benchmarks based on news being fast and everything else
being slow should be thrown away.  AE's hearing about
code being communication bound should be asking probing questions
about why. 




  
\newpage

\tableofcontents

\setlength{\baselineskip}{20pt}
\sect{Introduction}

Everybody talks about how slow communication is on the Connection
Machine, but now you too can do something about it.
Perhaps a good start is to mention a few statements that you
might consider surprising:

\begin{enumerate}
\item The full bandwidth of the hypercube is available, though it is
rarely used in current software.
\item It is a myth that only local applications can run at high speeds
on this machine. 
\item With the full bandwidth, the systolic part of a
single precision full bandwidth real matrix multiply
at VP ratio 128 was timed to run at 1.6 gigaflops on an 8k machine.  That's almost
13 gigaflops scaled up, folks!  
\item News is one of the {\bf worst} communications patterns on the CM2
as it currently uses only one wire, due to our gray code embedding.
\item Butterflies that are not pipelined are also as bad.
\item Some researchers would actually enjoy thinking about ``true" hypercube
algorithms, i.e., algorithms that fully exploit the bandwidth of the machine.
\end{enumerate}

Let me recount the history of multiwire communication as I know it.
I apologize in advance for errors and omisions.  Please inform me
of these errors. 
Cube swaps probably began with Guy's memory to memory cube swap,
which is used in the current implementations of scans and spreads.
I am sure Alan Ruttenberg also used direct memory to memory cube swaps in the
FFT. 
The point of departure of multiwire communications from
my point of view is Steve Vavasis who implemented
a spread using Johnsson-Ho trees in microcode.  It is nothing less than
remarkable that he did this during a summer.  
The first conception and experimentation 
of a cube swap from transposer to transposer 
was Alex Vasilevsky's as it became clear that this was appropriate for the FFT.
I believe that I wrote the first working version of this primitive,
and designed a sped up version (the 
``it can't be done in a four microcode instruction pipe"
Brewster--Edelman beer bet).
Mark Bromley got this faster version
working and into CMIS, and created many 
clever primitives which make the actual task of communications easy
for the first time. 
Mark and I had at first worked
independently realizing that a cube swap from transposer
to transposer would be just the right primitive.
Mark further implemented the stencil code using these and other
primitives that are now available in CMIS.  
In fact, thanks to his efforts, there is no reason not to use the wires
anymore. 
One of the more recent innovative uses of these primitives is a routing
compiler written by Denny Dahl.

One communication pattern whose potential
remains to be further explored is the n-rotated Gray codes hidden 
in one of Lennart Johnsson and Ching-Tien Ho's papers.  
I've written a version with Jean-Philippe Brunet for the n-body problem.
A variant where you do an n-body problem along each of two axes is just
right for matrix multiply. (This became obvious to me after I realized
that the n-rotated Gray codes was just right for the n-body problem after
which I learned that
Johnsson  \& Ho had already written this down.)
Though not sufficiently publicized,
this particular communication is very simple, hence very fast.
It is currently the {\bf fastest} communication pattern that I can think of 
for the CM2 because it both uses the full bandwidth of the machine, and
when coded properly is very simple.

Other recent uses of the cube-wires include a routing pattern for
bit-reversal written by Steve Heller and myself with lots of assistance 
from Mark.
I won't explain what this pattern is here, but I will mention that
the router implementation of this communication pattern slowed down the FFT
immensely.  The new version is much faster.
Not only are these
techniques useful for the FFT, but the same code
improves Marshall's
IO twiddling by a factor of 4 as compared with the use of the router. 
Hopefully, this can be used for the framebuffer as well.
Mark, Steve Heller, and I reimplemented the Vavasis
spreads, obtaining a factor of 2 to 3 speedup over his pioneering work.
Bigger factor over the paris code.
Steve Heller is now placing these spreads into the fieldwise code.
Kimberly is the newest member of the wire team.  She is currently
implementing a send-address to news-address converter.


With the exception of the phase 1 bit reversal (my own algorithm), 
all of the multiwire
algorithms that have so far been implemented  
were either the straightforward algorithm or
the creations of Lennart and his students
who have published several papers on exploiting the bandwidth
of the hypercube.
These papers are chock full of nice ideas, though be warned that
one has to
sometimes penetrate deeply to find the ideas.

\sect{Answers to frequently asked questions}

Before I get into the specifics, let me clarify some basic issues. 

\noindent
Q: What's a hypercube? \\
A: A $d$-dimensional hypercube refers to $2^d$ nodes labeled as a $d$ bit
binary string.  Two nodes are adjacent, if their labels differ by exactly
one bit.  Since there are $d$ bits to change, each node has exactly
$d$ neighbors, one for each dimension (hence $d$-dimensional).
\vspace{0.1in}

\noindent
Q: How are grids embedded in hypercubes? \\
A: By throwing away some of the wires, grids can be found embedded
in hypercubes. The technique is known as Gray coding, and has
been well understood for decades.   
When a two dimensional grid is embedded in a hypercube, the rows (and
the columns) are subcubes.  Thus a spread from column amounts to
independent parallel broadcasts in 
smaller hypercubes. 
It is also true that the row wires and column wires are
disjoint allowing for simultaneous uses of these wires.
(Spread a row and column simultaneously,
spread from diagonal across row and column simultaneously,
(news!! (a 0 1)( b 1 0)), i.e., shift a along the 0th dimension and
b along the 1st,
you get the idea.) 
(Steve Heller suggested I mention something about the above points.)
\vspace{0.1in}

\noindent
Q:  I now  believe that for a two dimensional grid, I can use the
four news wires simultaneously.  I also believe that spreads along
rows and columns can use other less obvious wires as well.  Any
other possibilities? \\
A: The limits are only that of the imagination.  As I mentioned there
is a matrix multiply algorithm that uses all the bandwidth.  All that
is required is to throw away your preconceptions.  I admit that 
it is sometimes  difficult to figure out how to rethink two dimensions
onto higher cubes, but the payoff can be great.  
\vspace{0.1in}

\noindent
Q: I heard a rumor that floating point operations are faster slicewise.
What about communication? \\ 
A: Communication is more convenient slicewise.  In fact, this paper assumes
that your data in memory is indeed slicewise. 
\vspace{0.1in}

\noindent
Q:  Does that mean that if my data is fieldwise, I simply can not use the wires? \\
A: Not always.  If the axis on which you wish to communicate is conveniently
located, it may not matter whether your data is fieldwise or slicewise.
(The most convenient situation is an axis that is completely off-sprint.)
\vspace{0.1in}


\noindent
Q: On the CM, can you move data both ways across a wire at the same time? \\
A: For purposes of the programming model that you are about to hear, the
answer is an emphatic YES.  In fact, as a mode of thinking it is helpful
to focus on one node and consider which data is outgoing
over which dimensions at that node. 
Usually one finds that other nodes are performing similar operations.
By conceptually separating outgoing from incoming usually one finds 
a greater simplicity in thinking. 
\vspace{0.1in}

\noindent
Q: Do I have to own a $\mu$-code workshirt to even consider the idea
of programming the wires? \\
A: Not at all, all you need to know follows. 
\vspace{0.1in}

\noindent
Q: Who should be using the wires? \\
A: Anybody who wants their code to run faster. 
Specifically, if one is using the same routing pattern many times
overshadowing the cost of any set up.
People should get on the  ``wires" mailing list, and take the initiative
to find out what is not clear or not mentioned in this document.
\vspace{0.1in}

\noindent
Q: Do I have to rewrite all my code to make use of these primitives? \\
A: If your code is already slicewise, you probably need not do anything.
If your code is fieldwise, with a certain amount of thought you
might still be able to use these primitives. Contact
Mark Bromley, Steve Heller, or myself (email to CERFACS is okay starting in
January 1990). 


\noindent
Author's note: other questions (or gaps in what you need to know) will
be filled in later based on reader's questions.

\sect{Basic Mechanics }

If you've already programmed in CMIS, you are in an excellent position 
to explore the wires.
If not, let me say a few words about CMIS and the CM2.

CMIS has evolved into a reasonably convenient language for performing
low-level operations on the Connection Machine without resorting to microcode.
Though at first the names of the instructions may look intimidating
(consider CMIS-FPU[-M\{R,W\}T\{A\}-\%P\{1-4\}]-FRT\{B\}\{C\}-DYN2-DELAY-\%C3-STATUS-L3)
actually, once you get into the CMIS philosophy, you see that it's not so bad.
Do get yourself all the nice documentation on the third floor.
In Appendix 1, we list the most relevant CMIS instructions for using
the cube wires.

The basic hardware unit on the CM is the Sprint Node.  (CMIS calls it
the Sprint Section, which hides its chief propery of being the 
basic processing node.)  There are 2048 Sprint Nodes on a full machine;
there are 16 on a board.  The concept of our machine having 64k processors
is essentially a lie when it comes to floating point operations. 
Just note that there are 2048 nodes on a full machine and 16 nodes on
one board.

Each  sprint node has memory for 64k or 256k 32 bit (slicewise) words known
as slices.
The sprint nodes are connected as a d-dimensional hypercube.
Here are the values of $d$ for various machines:
\vspace{0.1in}

\begin{center}
\begin{tabular}{|l|r|}
\hline
& d \\ \hline
full machine & 11 \\
half machine & 10 \\
eighth machine & 8 \\
board machine & 4 \\ \hline
\end{tabular}
\end{center} 

The hypercube allows for communication of {\bf two} slices out of each
node along each dimension.  This communication has lovingly become
known as a {\bf cube-swap}.  Thus on a full machine, as many as
22 slices can depart from (and of course, simultaneously arrive into) a sprint node
during a cube swap.  The word {\it swap} takes the point of view of the edge.
For each edge in the hypercube, four slices,  two on each side of the edge,
swap places during a cube swap. 

Each sprint node contains devices for arranging data to depart from and arrive
into the node.  These devices are known as transposers because of an
archaic purpose (something about turning fieldwise to slicewise). 
As long as your data is slicewise, you need not worry about this function
of the transposers.  All your data will come out just right. 

\begin{center}
\begin{tabular}{|c|}\hline
If your data starts out slicewise, there is  \\ \hline
no need to worry about it ever becoming fieldwise \\ \hline
\end{tabular}
\end{center}

There are three transposers on current machines: TA, TB, and TC.
The basic mechanics of cube-swapping is to 1) load TA from memory with departing
data 2)perform a cube-swap (say from TA to TB) and then 3)read the just
arrived data from TB back to memory.  There are other options of which 
transposer to use (TA-to-TB,TA-to-TC,TB-to-TA) though one should suffice.

For easy reference, all communication takes the following form: 

\begin{center}
\begin{tabular}{|c|}\hline
Memory is written into TA \\ \hline
Cube-Swap TA-to-TB \\ \hline
Memory is read from TB \\ \hline
\end{tabular}
\end{center}

The hard parts are the loading and unloading of the transposers.
The communication is trivial.

This is probably the hardest paragraph.  
I am going to say the same thing in two slightly different ways
in the following two paragraphs to hopefully make it easier.
The transposers each have 32 slots for loading and unloading data,
though you will at most use slots 1-11 and slots 17-26 for
the communication.  
(This would be for a full machine, in general slots 1-$d$ apply.)
The slots are specified by transposer pointers.  We will give examples
of setting the pointers later.
The data loaded into slots 1-11 of TA in any one sprint node say farewell
to each other and arrive in TB at 11 distinct sprint nodes corresponding
to the 11 distinct neighbors of the sending node. 
Data loaded into slot 1 travels along the edge corresponding to the least
significant dimension; data in 11 travels along the most significant dimension
in a full machine. 
At its new location, the data ends up in TB at the same slot it was in
when it left TA. 
Slots 17-26 duplicate slots 1-11 entirely, thus allowing for two
slices to leave along each dimension.

I like to talk about which wire data travels on.  Data can travel
on any of wires 1 through $d$ where $d$ is the dimension of the
hypercube (11 on a full machine.)  The reason the wires aren't
numbered from 0 through $d-1$ is that wire $0$ refers to a wire connecting
the two processor chips on a sprint-node.  This wire is useless in this
context and should be ignored.  Conceptually, I like to say that two
slices can depart from a node along each of the $d$ wires during a cube swap. 
Specifically the data in TA slots $i$ and $i+16$ travel along wire
$i$ arriving at the sprint node corresponding to a change in the $ith$
least significant bit.  These items end up in slots $i$ and $i+16$
in TB of the new transposer.  Note that this is happening in every sprint
node, so each node has loaded data into TA and then later reads data from
TB.

The following example shows how data would appear in TA before cube 
swapping using all four wires on a one board machine:

\newpage
\begin{center}
{\bf Transposer A}
\end{center}

\begin{center}
\begin{tabular}{|r|l|}\hline
0: & \\ \hline 
1: & data for wire 1 \\ \hline
2: & data for wire 2 \\ \hline
3: & data for wire 3 \\ \hline
4: & data for wire 4 \\ \hline
5: & \\ \hline
6: & \\ \hline
7: & \\ \hline
8: & \\ \hline
9: & \\ \hline
10: & \\ \hline
11: & \\ \hline
12: & \\ \hline
13: & \\ \hline
14: & \\ \hline
15: & \\ \hline
16: & \\ \hline
17: & more data for wire 1 \\ \hline
18: & more data for wire 2 \\ \hline
19: & more data for wire 3 \\ \hline
20: & more data for wire 4 \\ \hline
21: & \\ \hline
22: & \\ \hline
23: & \\ \hline
24: & \\ \hline
25: & \\ \hline
26: & \\ \hline
27: & \\ \hline
28: & \\ \hline
29: & \\ \hline
30: & \\ \hline
31: & \\ \hline
\end{tabular}
\end{center}

I strongly urge the reader to turn to the LISP code, and to
look at simple-cube-swap example.  Notice how pointer 1
gets loaded, then we write four slices of transposer A,
then pointer 17 and another four slices.  We then do the
cube swap, and do the read transposer B analogously.


{\bf Important Point:  During a cube swap, two slices leave
a sprint node along each dimension.  Also two new slices arrive
into each sprint node along each dimension.  That's two, not three,
and not one.  This allows for a bandwidth of 2d at each sprint-node,
not 1d nor 3d.} (Sorry for overemphasizing this, but I really
wanted to quickly avoid any misconceptions.) 


It is often not necessary to send data along all of the wires.  For example,
in a two dimensional stencil code, the sprint nodes are thought of as
a two-dimensional grid and the wires perform a get from north, south, east,
and west.  Thus four wires are used in each node.  The mechanism here
is to load TA with only eight slices (two in each direction)
instead of the 2$d$ that are possible.
Then  TB is read into memory from only 8 of its slots.  Thus you see,
the cube swap occurs in all available wires, but all but the relevant
slots are ignored. 
 

Now all you need to know is how to load and unload the transposers and
you can write your own communications code.


There is a certain amount of flexibility in loading and unloading the
transposers and this allows for some pretty powerful communications
possibilities:

\begin{enumerate}
\item All sprint nodes send memory from the same address over the same wire.
\item All sprint nodes send memory from the same  address over different wires.
\item All sprint nodes send memory from independent addresses over the same wire. 
\item All sprint nodes send different addresses over different wires. 
\end{enumerate}

Clearly (1.) is the simplest.  The n-body communication pattern is of this
form.  The stencil code and off-sprint bit-reversal is performed with
method (2.).  Spreads and another phase of bit-reversal is performed with
method  (3.).  The last method is never necessary. 


\sect{Transposer Pointers}

The transposer pointers specify which slots in a transposer are being
written or read.  In each sprint node, the transposer pointers
are set up in a slightly complicated way.  
Each transposer pointer is a five bit  word corresponding to the 
32 locations which the pointer can point to.  On our machine,
the pointers for TA, TB, and TC all get specified at once.
The method is to create a 32 bit number, where the least significant
fives bits are TA's pointer, the next five, are TB's pointer, and the
next five are TC's pointer.  The other 17 bits are ignored  on current
machines.
This 32 bit number needs to get to the bypass register and then
the pointers can be loaded using a CMIS instruction. 
One approach would be
\vspace{0.2in}
\begin{center}
\begin{tabular}{|l|} \hline
\verb^(CMIS-FPU-LOAD-BYPASS-CONSTANT	(+ TA-POINTER (* 32 TB-POINTER)))^ \\
\verb+(CMIS-FPU-WRITE-POINTERS)+ \\
\verb+(CMIS-FPU-MWTA-%P1 count)+ \\ \hline
\end{tabular}
\end{center}
\vspace{0.2in}

This method sets the pointer to be the same in each sprint node and
then writes the transposer with count slices.  Note that the pointers
increment by one after each slice.
The funny symbol \%P1 is a CMIS register which contains the address
of the data to write.

More commonly one writes the pointers into CM memory and then calls
the combined instruction\\
\hspace*{1in} \verb+CMIS-TP-MWTA-%P1-TABLE-%A9+ \\  with count arguments.
This instruction writes transposer A with data from \%P1 using
a pointer table that can be found in \%A9.
Here TP denotes {\it transposer pointer}.
Another method is to store one of the CMIS registers into the
bypass.  An instruction to do this is\\
\hspace*{1in} \verb+CMIS-FPU-LOAD-BYPASS-%A1+. \\


More comprehensive information is in the reference manual.
Meanwhile look at the attached examples and
start playing by yourself.

\sect{Indirect Addressing}

Indirect addressing is a natural idea, yet it is not very well
documented around here.  Quite simply, it is sometimes desirable
that the slice of memory to be loaded into the Sprint chip be
different at each Sprint node.  Thus, let's say we want to
send memory location 205 over wire 1 in Sprint node 0, while
memory location 347 should go over wire 1 in Sprint node 1.
Somehow we have to get these different locations in memory into
TA slot 1. 

The ingredients for doing this are
\begin{enumerate}
\item Always/Conditional
\item The Base Register
\item The Bounds Register
\item Offsets
\item The Scratch Register
\end{enumerate}

In the next paragraph I will mention the commands to set everything,
but first let me describe what everything does.
Setting the Sprint condition bits to always is completely different
from turning on any context in the processors.  For indirect addressing,
all you need to know is that it should usually be set to always.  
The way indirect addressing works is that in each sprint node,
the {\bf base} plus the {\bf offset} is the memory location written into
(or read from) the transposer,
so long as the {\bf offset} is less than the {\bf bound}. 
Otherwise, the memory location in the scratch register gets read or written.
This system sounds a little complicated, but it is often convenient to
simply update the base and keep the offsets constant.


The CMIS Instructions are
\vspace{0.1in}
\begin{center}
\begin{tabular}{l} \\
\verb+CMIS-FPU-ALWAYS+ \\
\verb+CMIS-IA-LOAD-BASE+ \\
\verb+CMIS-IA-LOAD-BOUND+ \\
\verb+CMIS-IA-MWTA-INDIRECT-%P1+ \\
\verb+CMIS-IA-LOAD-SCRATCH+ \\
\end{tabular}
\end{center}

\begin{enumerate}
\item CMIS-FPU-ALWAYS:  Word of advice -- do this at the top of any
code that does indirect addressing, and you won't regret it.
\item CMIS-IA-LOAD-xxxx:  All of these instructions are similar
to the instruction for load pointers.  First you have to
get your data into the bypass register.  This can be done
with CMIS-FPU-LOAD-BYPASS-CONSTANT or with CMIS-FPU-MWB-\%P1,
depending on whether you want the number to be the same or different in
each Sprint node.
You can also use CMIS-FPU-LOAD-BYPASS-%A1 to load the bypass from
a CMIS register.
\item CMIS-IA-MWTA-INDIRECT-\%P1: This is probably the most convenient
method for writing transposer A based on the offsets.  The offsets
are stored slicewise in the memory location starting at \%P1.
Notice that the data to be written into the transposer is not
in any way specified as an argument to this function as they
are the base + offset.  The base has already been loaded and
the offset is in \%P1.
\end{enumerate}

In the attached example file is a simple instance of indirect addressing
that actually works. Please see the reference manual for further
information.   



\sect{What else?}

I didn't cover everything in here as well as I might have liked.
Please look at the reference manual (cheat sheet) for
more information.


\end{document}

    






 
 

