An Algebraic Framework for Gray Code Related Algorithms

February 11, 1995

Abstract

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 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.

1 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} … i_{2}i_{1}i_{0}) is g = (g_{d−1}g_{d−2} … g_{2}g_{1}g_{0}), where

( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{d−2} ; g_{d−1} ) = ( \begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & 1 & ⋯ & 0 & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 \\ 0 & 0 & 0 & ... & 0 & 0 \\ 0 & 0 & 0 & ⋯ & 1 & 1 \\ 0 & 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) ( i_{0} ; i_{1} ; i_{2} ; ⋮ ; i_{d−2} ; i_{d−1} ) ,

i.e., g = Gi, where G is an upper triangular matrix with ones on the diagonal and superdiagonal, and all arithmetic is modulo 2.

It immediately follows that for decoding, we have i = G^{−1}g:

G^{−1} = ( \begin{matrix}1 & 1 & 1 & ⋯ & 1 & 1 \\ 0 & 1 & 1 & ⋯ & 1 & 1 \\ 0 & 0 & 1 & ⋯ & 1 & 1 \\ 0 & 0 & 0 & ... & 1 & 1 \\ 0 & 0 & 0 & ⋯ & 1 & 1 \\ 0 & 0 & 0 & ⋯ & 0 & 1 \end{matrix} ) ,

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.

2 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_{k}M is the same as M, except for in row k. The kth row of E_{k}M 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 kth row of E_{k}M 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_{k}i, i differs from E_{k}i in only the kth bit. Thus the communication defined by taking all the data in node i and sending it over to E_{k}i is a conditionalized communication over dimension k in the hypercube. The conditionalization is based on the inner product of the kth 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} … E_{1}E_{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.

3 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} = ( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{1} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{2} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{3} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) ,

We then have the important result that

G = E_{0}E_{1}E_{2} … 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 kth row, we now have

G = E_{d−1}E_{d−2} … E_{2}E_{1}E_{0}.

This allows for a change in order. When d = 4 we have,

E_{3} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{2} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{1} = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) , E_{0} = ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ) ,

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, …, 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, …, 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)} … 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)} … E_{p(1)}E_{p(0)}

then

G^{−1} = E_{p(0)}E_{p(1)} … E_{p(d−2)}E_{p(d−1)}.

The same matrices when multiplied in the other order gives you decoding rather than encoding.

4 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:

Parallel Local  Node Dependent Local
Address Dependent Global  Parallel Global

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.

5 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_{1}P G_{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: (5678910), and then encode again bits 5 through 7 and 8 through 10. We then have:

P^{−1}M = ( \begin{matrix}1.......... \\ .1......... \\ ..1........ \\ ...1....... \\ ....1...... \\ .....111... \\ ......1.... \\ .......1111 \\ ........111 \\ .........1. \\ .....111..1 \end{matrix} ) = P^{−1} ( \begin{matrix}1.......... \\ .1......... \\ ..1........ \\ ...1....... \\ ....1...... \\ .....11.... \\ ......11... \\ .......1... \\ ........11. \\ .........11 \\ ..........1 \end{matrix} ) P ( \begin{matrix}1.......... \\ .1......... \\ ..1........ \\ ...1....... \\ ....1...... \\ .....111... \\ ......11... \\ .......1... \\ ........111 \\ .........11 \\ ..........1 \end{matrix} ) .

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}, …, j_{2} of an axis with parallel local moves, only if bits j_{1}, …, 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:

( \begin{matrix}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{matrix} ) = ( \begin{matrix}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{matrix} ) ( \begin{matrix}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{matrix} )

and

( \begin{matrix}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{matrix} ) = ( \begin{matrix}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{matrix} ) ( \begin{matrix}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{matrix} ) .

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.

6 Factored Maps

For this section, assume all bits are local. Let me give one example of a factor map:

( \begin{matrix}A & 0 \\ 0 & B \end{matrix} ) ( \frac{i}{k} )

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:

( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 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 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

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, …, 31}. The other map is {Aj + b : j = 0, 1, …, 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

0 0 0
0 0 1
0 1 1
0 1 0
1 0 0
1 0 1
1 1 1
1 1 0

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.

7 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_{3}E_{2}E_{1}E_{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.

8 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

(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)