
\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{An Algebraic Framework for Gray Code Related Algorithms}
\author{Alan Edelman\thanks
{Department of Mathematics, University
of California, Berkeley, CA 94720, edelman@math.berkeley.edu}
\\
Steve Heller\thanks{
Thinking Machines Corporation \\
245 First Street, Cambridge, MA 02142, heller@think.com, johnsson@think.com
}
\date{(October 17, 1991 version)}

\maketitle

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

Shuffling, Gray code encoding, and Gray code decoding, are all linear
operators upon the address bits of memory, and are thus naturally
viewed as zero-one matrices with matrix
multiplication and addition performed
modulo 2. 
Here we explore this view, showing how it can 
be a useful way of thinking in the context of
the {\it twuffler} project at TMC.  
Many if not all  of the ideas in this note are abstractions of Steve Heller's
ideas. 

Sorry, this was written in a bit of a hurry and I didn't get a chance
to explain everything and clean up the writing.

  
\newpage


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

We begin with a definition of Gray code encoding  that is equivalent to
the more traditional recursive sequence definition, but turns out to be
more practical for our purposes.  The Gray code encoding of 
$i=(i_{d-1} i_{d-2} \ldots i_2 i_1 i_0)$ is 
$g=(g_{d-1} g_{d-2} \ldots g_2 g_1 g_0)$, where
$$
\left(\begin{array}{c}
    g_0\\ g_1\\ g_2 \\ \vdots\\ g_{d-2} \\ g_{d-1} 
\end{array}\right)
=
\left( \begin{array}{cccccc}
1 & 1 & 0 & \cdots & 0 & 0  \\
0 & 1 & 1 & \cdots & 0 & 0  \\
0 & 0 & 1 & \cdots & 0 & 0  \\
0 & 0 & 0 & \ddots & 0 & 0  \\
0 & 0 & 0 & \cdots & 1 & 1  \\
0 & 0 & 0 & \cdots & 0 & 1 
\end{array} \right)
\left(\begin{array}{c}
    i_0\\ i_1\\ i_2 \\  \vdots\\ i_{d-2} \\  i_{d-1}
\end{array}\right),
$$
i.e., $g=Gi$, where $G$ is an upper triangular matrix with ones on
the diagonal and superdiagonal, 
and {\bf all arithmetic is modulo 2}. 

It immediately follows that for decoding, we have
$i=G^{-1}g$:  
$$
G^{-1}=
\left(\begin{array}{cccccc}
1 & 1 & 1 & \cdots & 1 & 1  \\
0 & 1 & 1 & \cdots & 1 & 1  \\
0 & 0 & 1 & \cdots & 1 & 1  \\
0 & 0 & 0 & \ddots & 1 & 1  \\
0 & 0 & 0 & \cdots & 1 & 1 \\
0 & 0 & 0 & \cdots & 0 & 1 
\end{array} \right),
$$
i.e, $G^{-1}$ is  the 
upper triangular matrix of all ones.

We remark that there are reasons to have used the notation with the least
significant bits on the bottom, to correspond to the rows having the
least significant bits on the right.  The matrices would have then been 
lower triangular.  I chose the upper triangular definition instead to
more closely match linear algebra rather than binary notation.  

We further remark that any shuffle is a permutation matrix. 
Since these matrices are upper triangular, it immediately follows
that the information for changing a bit is found in the bits of higher
order.   

\sect{Elementary matrices and hypercube communication}

We say that  a matrix is an elementary matrix if it is the identity
except on row $k$.  On row $k$, it is arbitrary except that the diagonal
element must be $1$ (so the matrix is non-singular). 
We ambiguously
refer to such a matrix as $E_k$.
In different contexts the $E_k$ will be different, depending on
the choice that is made for row $k$.
Notice that $E_k=E_k^{-1}$ for such matrices.

If $M$ is any matrix, notice that $E_kM$ is the same as $M$, except for
in row $k$. The $k$th row of $E_kM$ is the linear combination of the rows
of $M$ determined by the elements in row
$k$ of $E_k$.  For example, if $E_k$ has all ones in row $k$, then
the $k$th row of $E_kM$ is the sum (don't forget everything is binary)  
of the rows of $M$.

Now if $i$ is the binary address of a node of a hypercube, then
unless $i=E_ki$,  $i$ differs from $E_ki$ in only the $k$th bit.
Thus the communication defined by taking all the data in node
$i$ and sending it over to $E_ki$ is a conditionalized communication
over dimension $k$ in the hypercube.  The conditionalization is
based on the inner product of the $k$th row of $I-E_k$ with
$i$.  Since each node always knows its address $i$, this conditionalization
is readily computed.

Let $M$ be any non-singular matrix.  Then we can define a communication
by saying all data in each node $i$ is send to node $Mi$.
Certainly, not all communications fit this model, but 
shuffling and Gray coding do, and that is what we care about most
for now.
If we can factor $M$ as
elementary matrices  $E_{d-1}E_{d-2}\ldots E_1E_0$,
then we have an easily implemented algorithm for the communication
described by $M$:  Conditionally send the first word over wire 0,
next the first word over wire 1 and the second over wire 0, etc.
Once the pipe is going, you are conditionally sending $d$ words
over $d$ wires.
Notice this is not the best wire utilization, but it is  easily
coded.
  


\sect{Matrix interpretation of Gray encoding and decoding algorithms
on hypercubes}

This section describes the matrix interpretation of Gray encodings and
decodings on hypercubes.  This is referred to at Thinking Machines as 
converting from news to send order.  Older codes used sends, more recent
codes use the hypercube wires as in Kimberly's code. 

We start with encoding: Let $E_k$ be the matrix 
that is the identity with an extra one to the right
of the diagonal in row $k$. 

Here are $E_0, E_1, E_2,$ and $E_3$ when $d=4$:
$$
E_0=
\left(\begin{array}{cccc}
1 & 1 & 0 & 0  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_1=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 1 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_2=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 1  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_3=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
$$

We then have the important result that
$$G=E_0 E_1 E_2 \ldots E_{d-2}E_{d-1}.$$
Thus, encoding is naturally performed from higher order bits
to lower order, but as we shall see, the order can be reversed. 
Note the elementary matrices change at most one bit, and thus
they correspond to a conditional move across a hypercube wire. 
$E_k$ can be interpreted as sending data over wire $k$ conditionalized
on bit $k+1$ of the node address.
We now interpret the matrix factorization of $G$ above as,
the algorithm: pass the data over wire $k-1$ conditionalized
on bit $k$ of the address, then over wire $k-2$ conditionalized
on bit $k-1$, etc., as described above.

Notice that if instead we define $E_k$ to be the matrix that
is the identity except we have all ones to the right of the
diagonal in the $k$th row, we now have
$$G=E_{d-1}E_{d-2} \ldots E_2 E_1 E_0.$$
This allows for a change in order.
When $d=4$ we have,
$$
E_3=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_2=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 1  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_1=
\left(\begin{array}{cccc}
1 & 0 & 0 & 0  \\
0 & 1 & 1 & 1  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
E_0=
\left(\begin{array}{cccc}
1 & 1 & 1 & 1  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1 
\end{array} \right),
$$
We can now pass the data
over wire 0, conditioned by the sum mod 2 of the address bits
1 through $d-1$, then over wire 1, conditioned by the sum mod 2
of bits $2$ through $d-1$, etc.

When you have a large data set to move, both of these amount
to setting the condition bits for each node at the beginning of the
algorithm and then passing a window over the data for the conversion.

We conclude our statements regarding encoding by showing how this
can be done in any order.  (Steve Heller was the first to mention
to me that this was possible, and he defined the equivalent algorithm
without the matrix notation.) 
Let $p$ be some permutation of $0, 1, \ldots, d-1.$
Define $E_{p(k)}$ to be the identity matrix modified so that
the elements in row $k$ and columns $k+1, k+2, \ldots, l$
are all one, where $l$ is the smallest number bigger than
$k$ such that $p^{-1}(l)<k$.  Otherwise $l=d-1$. 
In this case, we have
$$
G=E_{p(d-1)}E_{p(d-2)}\ldots E_{p(1)}E_{p(0)}.
$$
We call this decoding in any wire order.

For decoding, all the comments above remain except now $l$ is
the smallest number bigger than $k$ such that $p^{-1}(l)>k$
or $d-1$. An interesting relationship between decoding and encoding is
that if
$$
G=E_{p(d-1)}E_{p(d-2)}\ldots E_{p(1)}E_{p(0)}
$$
then
$$
G^{-1}=E_{p(0)}E_{p(1)}\ldots E_{p(d-2)}E_{p(d-1)}.
$$
The same matrices when multiplied in the other order gives you decoding rather
than encoding.

 

\sect{What if we have global and local bits?}



If we now have global and local bits specifying a word of memory,
then it is convenient to draw a line separating the low order bits
which will be local and the high order bits which will be global.
For any matrix $M$ we now have four parts corresponding to
a vertical and horizontal line.
Assume we have a matrix that is the identity except for 
some modification in one of the four quadrants.  Here we
interpret such a communication:

\begin{center}
\begin{tabular}{|c|c|}
\hline & \\
Parallel Local & Node Dependent Local \\
& \\
\hline & \\
Address Dependent Global & Parallel Global \\
& \\
\hline
\end{tabular}
\end{center}

In other words, if we modify the identity in the upper left,
that corresponds to a parallel local communication: all nodes
are doing the dame local communication.
An example is Phase III bit reversal, or local Gray encoding, decoding,
or local shuffle.
If we modify the
zeros in the upper right, then the local communication becomes
node dependent.    
If we modify the identity in the lower right, we have a global 
communication that is identical in every node.  A phase II bit
reversal would be one example, another is encoding the global
bits using Kimberly's code for the Gray code. 
If we modify the lower left, we  have an address dependent
global communication where the local address does not change.
Phase I bit reversal is almost like this, when written in the
coordinate system of the relative address.

\sect{Decoding global bits locally}

To put in my two cents for the twuffler project, I was asked
by Steve Heller to determine under which ``twuffle'' cases
all Gray code encoding and decoding can be performed on local
bits. Secondly, under which cases will one global communication suffice?

For the moment, I will assume that we are dealing with slices of
memory so that memory is described by two kinds of bits, local and
global.  In general, there are also sprint bits which may complicate
the story a little, but I'm ignoring that for the moment.   
One thing at a time.

The movements allowed consist of decoding global bits of select
axes, shuffling, and encoding the global bits of select new axes.
Decoding is a matrix that has blocks of $G^{-1}$ in the lower right
part, one block for each axis being decoded.  Shuffling is an
arbitrary permutation matrix, and encoding consists of blockwise 
$G$'s corresponding to the new axes to be encoded. 






I now wish to attack the following question posed to me by Heller: 
assuming we are most generally doing a global decoding step,
followed by a shuffle, followed by a global encoding step,
when can we avoid all the global decoding and encoding steps. 
We can write this as $M=G_1PG_0^{-1}$.  Here $G_0$ and $G_1$
are some global block Gray encoding matrices.
We think it is of value to study $M_1=P^{-1}M$.  This matrix
describes what happens to the bits in terms of the Gray code,
but not in terms of the shuffling. It decouples the shuffling and
Gray code problem in a very nice way as we hope to explain..  

This is a bit tricky.  Let me illustrate with an example:
Assume we have 11 bits and we decode two axes one on bits
5 through 7 and one on 8 through 10.
Let us form the shuffle: $(  5 6 7 8 9 10)$, and then encode
again bits 5 through 7 and 8 through 10.
We then have:
$$
P^{-1}M=
\left( \begin{array}{c}
1.......... \\
.1......... \\
..1........ \\
...1....... \\
....1...... \\
.....111... \\
......1.... \\
.......1111 \\
........111 \\
.........1. \\
.....111..1 \\
\end{array}\right)
=
P^{-1}
\left( \begin{array}{c}
1.......... \\
.1......... \\
..1........ \\
...1....... \\
....1...... \\
.....11.... \\
......11... \\
.......1... \\
........11. \\
.........11 \\
..........1 \\
\end{array}\right)
P
\left( \begin{array}{c}
1.......... \\
.1......... \\
..1........ \\
...1....... \\
....1...... \\
.....111... \\
......11... \\
.......1... \\
........111 \\
.........11 \\
..........1 \\
\end{array}\right).
$$
This matrix captures the data dependency.
 

Let me mention some interesting cases.  First assume that we only
decode the bits and then perform a shuffle.  We have essentially
already observed that we can decode bits $j_1,\ldots,j_2$ of
an axis with parallel local moves, only if bits $j_1,\ldots,j_3$
are local,
where $j_3$ is the largest bit, bigger than $j_2$ that has not already
been decoded.  (For encoding just remove the word ``not" from the
previous sentence.)

Notice, however, that if the highest order bits in each axis are global,
and all
the rest are local, than we can perform the decoding locally on
all the other bits, followed by a conditionalized vector reversal.
Or lets assume a situation that is a bit more general:
Assume that some of the highest order bits were already decoded locally
at some point, but now they are global.  If the remaining bits are
local, they can be decoded themselves, followed by a conditionalized
vector reversal.

Now imagine that one bit that is not a highest order bit of an axis 
never makes it local, then there is a global communication involved,
but it can be done using the one wire code which is faster than
the multiwire.  In particular, no transposers need to be loaded
and I think conditionalizing is easy.

If however, there are two global bits
that never become local
neither one of which is the
highest order bit of an axis, then the cube swap primitive will have
to be used. 

I should probably write down two matrix factorizations that
make it clear how to break axes in half:
$$
\left(\begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 1 \\ 
\end{array}\right)
=
\left(\begin{array}{cccccc}
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 0 & 0 & 1 \\ 
\end{array}\right)
\left(\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\ 
0 & 0 & 0 & 0 & 0 & 1 \\ 
\end{array}\right)
$$
and
$$
\left(\begin{array}{cccccc}
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}\right)
=
\left(\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}\right)
\left(\begin{array}{cccccc}
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}\right).
$$
In other words, if you wish to decode bits 0 through 5, you can first
decode bits 2 through 5 and then 0 through 2.  If you wish to encode 
0 through 5, you first encode bits 0 through 2 and then 2 through 5.
During this process, only bits 0 through 2 or 2 through 5 have to
be local at the same time.

\sect{Factored Maps}

For this section, assume all bits are local.  Let me give one example
of a factor map:
$$ 
\left( \begin{array}{c|c}
A & 0 \\ \hline  0 & B\\
\end{array}\right)
\left( \begin{array}{c}
i \\ \hline k \\
\end{array}\right)
$$ 
If $i$ is five bits long, then $ai$ can be stored in CMIS as
a map, and $Bk$ gives you the offsets.  In microcode it is possible
to compute $Bk$ for any $k$, though it might not be fast.  On the
front end, of course, it is trivial but you get the cost of FIFO
pushes.  Thus, unfortunately, only special $B$'s are convenient for
our machine.  The ones used so far are the encoding and decoding 
matrix. 


Let me go into a bit of detail for multiple axis encoding.  For multiple
axis encoding, you might factor the map as follows:
$$
\left( \begin{array}{ccccc|ccc}
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & {\bf  0} & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 1 & {\bf 1} & 0 & 0 \\ \hline
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & {\bf 0 } \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}\right)
$$
It may be hard to see, but there are two zeros and a one in bold
face on the super diagonal.  The two zeros indicate breaks in the
axis, and the one indicates a rank one coupling between the 
bits of $i$ and the bits of $k$.  Two maps need to be stored,
the map corresponding to the upper left matrix, call this
$A$.  The actual map is the set of numbers $\{Aj:j=0,1,\ldots,31\}$.
The other map is $\{Aj+b:j=0,1,\ldots,31\}$ where $b$ is the unit
vector with a $1$ in the highest bit.  Don't forget the plus is
an exclusive or. Since the ordinary Gray code has the property that
flipping the high order bit is equivalent to reading the map backwards,
one map sufficed.  In general, this will not be true.

The three high order bits correspond to the offset to the map.
So far as I can tell, this is most appropriately done with exclusive
ors rather than adding. Consider the sequence of offsets
$$
\begin{array}{ccc}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
1 & 1 & 0 \\
\end{array}
$$
Notice if we can exclusive or 6 when going from the fourth line to the
fifth, then we can generate the correct offset.  For CMIS reasons
based on Debbie's code as it currently exists, I think this is a good
idea, but I won't go into the details here.

\sect{Elementary matrices and the flippers}

The 16 bits of a slice per processor can be addressed by four
bits.  These bits and one more (the Sprint bit), are called the
slice bits by the twuffler  project.  It turns out that any
communication on these four bits that can be factored into
elementary matrices as
$$E_3E_2E_1E_0$$
can be done with the flippers.  (The converse is not true,
what the flippers can do is more general.)

Note this means that these bits can be Gray coded or decoded or
partially coded.  If the matrices also depend on global bits (and
the Sprint bit), you can set up different flipper values in each
node and things will still work.

\sect{One more matrix factorization}

Just for good luck, I include one more matrix multiplication 
based on 11 bits.  Here we will first 
decode bits 6 through 8 and 9 through 10.  Then we encode bits
2 through 6 and 7 through 10.  The answer is
\begin{verbatim}
(1..........)   (1..........) (1..........)
(.1.........)   (.1.........) (.1.........)
(..11.......)   (..11.......) (..1........)
(...11......)   (...11......) (...1.......)
(....1111...)   (....11.....) (....1......)
(.....1.....) = (.....11....) (.....111...)
(......11...)   (......1....) (......11...)
(.......1111)   (.......11..) (.......1...)
(........1..)   (........11.) (........111)
(.........1.)   (.........11) (.........11)
(..........1)   (..........1) (..........1)
\end{verbatim}





\end{document}











    
















 










 

























































































































































































































































