Index Transformation Algorithms in a Linear Algebra Framework.
We present a linear algebraic formulation for a class of index transformations such asGray code encoding and decoding, matrix transpose, bit reversal, vector reversal,shuffles, and other index or dimension permutations. This formulation unifies, simplifies,and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.
Introduction
We present a theory for a class of index transformation algorithms that should be properly
thought of as a matrix-vector product, though they rarely are. This class is strictly a superset of
the class known as BCP (bit-permute/complement) [20, 21]. In spirit this theory is linked with the
ideas in Van Loan's new book [26], particularly the notion that matrix factorizations can define
algorithms. The principal idea is not the discussion of matrix factorization algorithms, per se. The
idea is a different way of viewing and generating algorithms.
Loan [26] covers computational frameworks for the Fast Fourier Transform. Despite differences
in our approach, on this quote we firmly agree:
The proper way to discuss a matrix-vector product such as the discrete Fourier
transform is with matrix-vector notation, not with vectors of subscripts and multiple
summations. We should be as repelled by scalar notation as we are by assembly language
coding for both retard algorithmic development.
Although it has always been clear that BCP and larger classes of communications problems can
be formulated as matrix-vector products, they rarely have been. Keohane and Stearns address a
similar class of permutations [19], but do not formulate the problem as a matrix-vector product. A
notable exception is the contemporaneous work of Cormen [2] for permuting data on disk arrays.
Our motivation stems from communications algorithms for real applications on hypercube multiprocessors
such as the Connection Machine model CM-2 multiprocessor, though we believe these
ideas to have wider applicability. Our matrices only contain 0's and 1's: they describe transformations
on a vector of length 2 n indirectly through binary encodings. The most familiar example is
bit reversal, an operation used in conjunction with FFT's. Bit reversal is a permutation of a vector
of length 2 n induced by a permutation on n objects: the n bits of the vector's indices. One can
represent this transformation as a 2 n \Theta 2 n permutation matrix on the components of the vector
[11, 26]. For our purposes it is more convenient to consider the more compact representation of
the n \Theta n matrix describing the index transformation, which in the bit reversal case has 1's on the
northeast-southwest diagonal and is otherwise 0. Also familiar are so-called dimension transformations
or index permutations. These are arbitrary permutations of the n bit indices, which induce
permutations on 2 n elements. Why use matrices of order 2 n when matrices of order n suffice?
We define a linear index transformation by
where i is a bit vector with n components, A is an n \Theta n 0,1 matrix, and the matrix-vector multiply
is performed modulo 2. So long as A is nonsingular, this n \Theta n matrix induces a permutation on the
indices. Dimension permutations are trivial examples of such transformations; other examples
include Gray code encoding and decoding of arbitrary axes. Many real applications on hypercube
multiprocessors require complicated compositions of these transformations.
We show that this is not a matter of notation, but rather that the existence of a certain kind
of convenient algorithm on a hypercube to perform the data movement given by a linear index
transformation is equivalent to the ability to perform Gauss-Jordan elimination on A without
pivoting. This ability, in turn, is related to a familiar condition on the principal submatrices of A.
Thus the complicated combinatorial problem of devising an algorithm is reduced to the algebraic
problem of decomposing a matrix. We believe that this is the first time that the existence of
a hypercube communications algorithm has been related to the ability to perform Gauss-Jordan
elimination.
In Section 2, we fix notation that will be useful throughout the paper, while Section 3 contains
our main results. In Section 4, we apply these results towards the special case of Gray code encoding
and decoding while Section 5 considers dimension permutations. We conclude in Section 6.
Notation
Let F 2 be the field of elements f0; 1g with addition and multiplication defined modulo 2. In
this paper, addition and multiplication are always performed modulo 2.
We denote the vector space of n-vectors with elements in F 2 as F n
. Similarly, the set of m \Theta n
matrices with elements in F 2 is denoted by F m;n
2 . For clarity, we sometimes display such matrices
with empty spaces where the entries are 0. We sometimes consider i or its binary encoding as the
node address of a hypercube in the usual manner.
Any integer i such that 0 - can be identified with an element of F n
2 by the use of
the binary encoding of the number. Thus, if
then we identify i with the vector
Notice that the vector is written with the least significant bit first. Of course F ncan be naturally included as a subset of F n+1
2 by appending an extra zero.
We admit that this vector notation for the binary representation of a number seems to clash with
the usual representation, in that the order appears backwards, but the definition as
presented is appropriate and consistent for matrix-vector notation. We have resisted the temptation
to refer to the first row of a matrix in F mn
2 or the first component of a vector in F n
2 as the 0th, but
rather chose the more familiar index origin of one.
Some useful vectors are e which only the nth component is 1 and j
which only the first n components are 1. These vectors can be thought of as elements of F k
2 for any
using the natural embedding. Also we can avoid difficulties by letting e
If ordered sequence of numbers, then its reversal is the sequence
3 Linear and Affine Index Transformations
We now define the transformations of interest to us which we refer to as affine or linear:
Definition 3.1 An index transformation is defined to be affine if the data in node i is sent to
node f(i), where
Cormen [2] calls this class of transformations BMMC for bit-matrix-multiply/complement.
Definition 3.2 An index transformation is defined to be linear if the data in node i is sent to
node f(i), where
Thus a linear index transformation is an affine transformation that fixes the data in node 0.
The simplest hypercube communication is the unconditional exchange of data across a fixed
dimension. Algebraically this can be described by Another simple hypercube communication
sends data to the opposite corner of the hypercube. This is
vector reversal.
Another example of a linear index transformation is a dimension permutation considered by
such authors as Stone [22], Fraser [6], Nassimi and Sahni [20, 21], Flanders [5], Johnsson and Ho [14],
Stout and Wagar [23, 24], and Swarztrauber [25]. A dimension permutation is defined as the map
permutation matrix. Since permutation matrices are orthogonal (PP
if it is also symmetric, then it is a square root of the identity I). Thus a symmetric
permutation matrix corresponds to a disjoint set of dimension pairs being exchanged. On
the other hand circulant permutation matrices correspond to relabeling dimensions in a way
that preserves the circular order of the indices. The shuffle and unshuffle operations give two
such matrices. Circulant permutation matrices form a subset of the irreducible permutation
matrices. A matrix A is said to be irreducible if it has no nontrivial invariant subspaces. The
irreducible permutation matrices correspond to the dimension exchange represented by a cycle.
In Section 4, we will consider the example of Gray code encoding and decoding.
The basic theorems of algebra tell us that if A is nonsingular, then the
map is one-to-one. Otherwise, if the rank of A is r, then A maps the hypercube to an r-dimensional
subcube. This map sends the data in 2 n\Gammar nodes to one.
Definition 3.3 A conditional exchange across dimension k, denoted E k , is a communication
pattern defined by f(i) = Ai; where A is any matrix whose diagonal consists of 1's, and whose
off-diagonal may possibly be 1 only in the kth row.
An example of a conditional exchange across dimension 3 is represented by the matrix:
The mapping describes a conditional change of the third bit, depending on the first
and fourth bits. We will extend our use of the term "conditional exchange" to also refer to the
associated matrix without loss of clarity.
Lemma 3.1 If E k is a conditional exchange, then E k is nonsingular,
Proof From the form of the matrix, it is clear that the determinant of E k is 1, and that E k e
i, and thus
I .
Notice that if the kth diagonal entry were 0, then the kth column is 0 and the matrix would be
singular. In fact the rank of the matrix would be exactly n \Gamma 1. Such a communication might be
termed a conditional projection.
A conditional exchange can be implemented directly on a hypercube. Each node either sends
all its data across the dimension specified in the exchange, or does nothing. Only one dimension
of the hypercube is traversed in this operation, and this algorithm achieves fifty percent overall
utilization of that dimension.
A hypercube communication operation that uses all the dimensions simultaneously is called
cube swap. In this operation, each node sends one message along each hypercube dimension.
If an n \Theta n matrix A can be decomposed as a sequence of conditional exchange matrices,
describes an algorithm for implementing the linear index
transformation given by A as a sequence of conditional exchange operations across dimensions 1
through n respectively. More generally, if A admits a factorization of the form
is a reordering of the dimensions 1 through n, then the factorization defines an
algorithm for implementing the linear index transformation as a sequence of conditional exchanges
in a different order. Any sequence of exchanges on disjoint dimensions can be implemented in a
pipelined fashion on a hypercube as a sequence of identical cube swap operations, as long as there
is a nontrivial amount of data at the node. The pipeline will have one start-up and one wind-down
step for each dimension traversed. Once the pipe is started the algorithm achieves fifty percent
utilization of the total bandwidth available. Of course, this leaves us short by a factor of two in
total use of cube swap bandwidth, but allows us to consider very general situations.
We now present our main theorem relating hypercube communications algorithms algebraically
to Gauss-Jordan elimination performed columnwise and modulo 2 instead of over the reals:
Theorem 3.1 The following statements are equivalent:
1. A may be decomposed as a product of conditional exchanges:
2. The index transformation defined by A can be accomplished on a hypercube as a pipelined
sequence of cube swaps, accomplishing a sequence of conditional exchanges traversing
dimensions 1 through n consecutively.
3. The columnwise Gauss-Jordan elimination algorithm (modulo 2) on A runs to completion
without the need for pivoting.
4. All n principal submatrices of A are nonsingular.
Proof The equivalence of 1. and 2. is discussed before the theorem. By columnwise Gauss-Jordan
elimination we mean an algorithm whose ith step consists of adding multiples of column i to the
other columns so that the resulting matrix matches the identity in the first i rows. In modulo 2
arithmetic one can verify that the algorithm takes the following simple form:
for i=1,2,.,n
Here E(A; j) denotes a matrix that is the identity except in the jth row, which is defined to
match that of A. It is well-known that the Gauss-Jordan algorithm requires no pivoting at the ith
step if A i\Gamma1
ii 6= 0 which is exactly the condition that E(A nonsingular. If the Gauss-Jordan
algorithm above can run to completion without generating any singular matrices E i then
or
Conversely, suppose A can be decomposed as in 1. Then
For the product on the right side of (3.1) does not change bits 1 through i and thus,
as a matrix it agrees with the identity matrix in its first i rows. This determines E i as the unique
matrix that describes the ith step of column-wise Gauss-Jordan elimination without pivoting. This
establishes the equivalence of 1 and 3.
Finally, since at step i the Gauss-Jordan procedure adds multiples of column i to the other
columns, the determinants of the principal submatrices do not change. Thus, if the Gauss-Jordan
algorithm runs to completion, then the principal submatrices are all nonsingular. Conversely, if the
principal submatrices are all nonsingular, the ith pivot cannot be 0, for the product of the first i
pivots is the determinant of the ith principal submatrix. Having now established the equivalence
of 3 and 4, the proof is complete.
Corollary 3.1 If A = LU where L and U are nonsingular lower and upper triangular matrices,
then A can be decomposed as Thus Gaussian elimination, rather than Gauss-Jordan
elimination, can be used to test whether A has this decomposition, though Gauss-Jordan is needed
to construct the decomposition.
Corollary 3.2 Let d be a reordering of the numbers 1 through n. Then A can be decomposed
as
if and only if all the diagonal submatrices of A given by rows and columns
are nonsingular for Equivalently, if A = PLUP T , where P is a permutation
matrix, then the index transformation corresponding to A can be performed as a sequence of
conditional exchanges in an order specified by P .
Proof The Gauss-Jordan algorithm, when run consecutively on rows d 1 through d n , gives the
desired decomposition if it exists, or breaks down through the need for pivoting if it does not.
Corollary 3.3 If A is a nonsingular upper (or lower) triangular matrix, then an algorithm exists
that traverses the dimensions in any order.
Proof All diagonal minors of A are determinants of upper (or lower) nonsingular triangular matrices

Corollary 3.4 A cycle or any matrix at all that has all diagonal entries equal to 0 cannot be
written as a product of conditional exchanges in any order.
Proof principal submatrix is equal to 1.
Corollary 3.5 No permutation matrix can be written as a product of conditional exchanges in any
order.
Proof All principal submatrices that include exactly one row and column from one of the component
cycles are singular.
Corollary 3.6 Any nonsingular A defines an index transformation that can be performed as a
pipelined sequence of conditional exchanges followed by a dimension permutation algorithm.
Proof Any nonsingular A can be written as PLU by performing Gaussian elimination with partial
pivoting.
Since we have shown how to construct an algorithm corresponding to any LU , and since algorithms
for accomplishing address permutations exist, we can now accomplish any linear transformation

Corollary 3.7 If A has the form U 1 PU 2 where U 1 and U 2 are upper triangular, then
where A 0 has all nonsingular principal submatrices. Therefore A 0 can be implemented as a sequence
of conditional exchanges in standard order.
Proof Let A upper triangular, every diagonal minor of U 1 and hence
nonzero. The kth principal submatrix of A 0 is given by the product of the kth principal
submatrix of P T U 1 PU 2 and that of U 2 and hence is nonsingular.
The triple product U 1 PU 2 arises on the CM-2 multiprocessor when transposing a matrix,
collapsing or separating axes, or changing the layout of an array on the machine. In this case,
U 1 and U 2 denote Gray coding and decoding operations respectively. The Gray code is decoded,
the address bits are permuted, and then the bits are encoded in possibly a new way. This type of
operation is explored in the next section.
Gray Codes and Hypercube Multiprocessors
Gray coding and decoding of arbitrary axes is an important communication pattern on hyper-cube
multiprocessors. The outline of this section is as follows:
1. A brief digression into the history of Gray coding, which is not as well-known as perhaps it
ought to be.
2. Derivation of widely known properties of the Gray code using the linear algebra framework.
3. Applications of the theory from the previous section toward new results about Gray coding.
The binary-reflected Gray code has had a most curious history in that it has appeared in so
many different applications. It was invented by the French engineer Emile Baudot (1845-1903) for
the purpose of sending and receiving telegraphs [10]. In 1872, it appeared in the solution of the
so-called Chinese ring puzzle (see Gardner [7]), and it is also the solution of the famous Tower of
Hanoi puzzle. Frank Gray developed the code that now bears his name during the 1940's, though
it was first published in 1953 in a patent for a so-called pulse code modulation tube. Later, the
Gray code has been used in many ways in analog-to-digital converters.
Though probably obvious to many, we believe that Gilbert [8] in 1958 was the first to point
out explicitly that the consecutive numbers in the Gray code sequence form a Hamiltonian path
on a hypercube. During that time it was fashionable to enumerate other Hamiltonian paths on the
hypercube as well.
With the invention of multiprocessor computers with hypercube networks, it became possible for
the first time to make use of these paths on real physical hypercubes. Many authors independently
observed the utility of this property for embedding rings and higher dimensional meshes. CM-2
system software uses these embeddings to store grids in such a manner that it is invisible to the
programmer. Indeed it would be easy to believe erroneously that the CM-2 has a separate network
for grid communication.
On the CM-2, data is considered to be in "grid" order (also known as "NEWS" order) if the
data labeled i is located in the processor with the label Gi, where G is the gray coding operator.
The data is in "cube" order (also known as "send" order) if the data labeled i is in fact located
in node i. Since certain algorithms run more efficiently if the data is in "grid" order while other
algorithms run faster in "cube" order, there has been need for routines to convert between the two
ordering schemes. The communication pattern that converts a single one-dimensional axis from
"cube" to "grid" order is Gi and from "grid" to "cube" order is given by
G and G \Gamma1 are given below. The key point is that they are linear index transformations.
In numerical linear algebra [9], it is common to embed Householder reflections or Givens rotations
inside a larger identity matrix so as to operate on selected components of a vector. Analo-
gously, one can "Gray code" certain components of a vector. On hypercubes it is usual to associate
blocks of components with various axes, and then one refers to Gray coding an axis.
The Gray code encoding operator G is deceptively simple, defined by the condition that G be
a linear operator on vectors modulo 2 and that
Let G n denote the restriction of the Gray code encoding operator G to the finite dimensional
space F n
2 . We then have that G n is a linear transformation on F n
whose n \Theta n matrix representation
is
The Gray code decoding operator G \Gamma1 is uniquely defined by
The restriction of G \Gamma1 to the finite dimensional space F n
2 has the n \Theta n matrix representation
We now let S n be the sequence of 2 n elements of F n
2 in numerically increasing order. To obtain
the same sequence in reverse order, add j n to each element; hence the name vector reversal. Let
the sequence of Gray codes of elements of S n . Since
we have proved a very important property of the binary-reflected Gray code that is often taken as
part of the standard definition:
Theorem 4.1 (Reversal Property) The reversal of the sequence G(S n ) is equal to the sequence
with the bit in the nth position complemented.
A related observation is
Theorem 4.2 Consecutive members of the sequence G(S n ) differ in exactly one bit.
Proof Two consecutive numbers can always be written as
Gi has a 1 in the k least significant bits. Since Gj the bit in which
the Gray codes differ is the kth.
Following Gilbert [8], the reversal property is readily grasped by the eye from the diagram below
in which 0 is represented by a blank space, and 1 with a black square.
1000 1100
Since G and G \Gamma1 are both upper triangular, by Corollary 3.3 Gray coding and decoding can be
accomplished in any order. For example, when 4, we express the algorithm from Johnsson [12]
in our notation:
and
Notice that the algorithms perform encoding from low-order bits to high-order bits, while decoding
is performed from high-order bits to low-order bits. Algorithms for the reverse order were
first developed by Johnsson [16], and the existence and use of algorithms for any order are discussed
by Johnsson and Ho [15, 17].
One particularly interesting example is decoding starting from the least significant bit. In this
case F p
k has a 1 in row p(k) and column n. It readily follows that if an edge is used in the subcube
defined by v it is not used in the subcube v 1. This is the basis for a new algorithm
given by Johnsson and Ho [15] that takes better advantage of the available bandwidth.
More generally, if A can be decomposed as the product of conditional exchanges E i over distinct
dimensions, then if the element in the ith row and jth column of E i is 1 for every i and if the jth
row of A matches the identity matrix, then the wires along dimension j can be used to take better
advantage of the available bandwidth.
We define a code change operation as any G 1 G \Gamma1
combination. As an example, treating a
two-dimensional matrix as a one-dimensional vector on a hypercube involves a code change.
Corollary 4.1 All code change operations have pipelined algorithms.
Proof Since decode and encode operations are both upper triangular, so is their composition.
Corollary 4.2 All code change operations have pipelined algorithms for each permutation of the
dimensions.
5 Dimension Permutations and Hypercube Multiprocessors
We have seen previously that dimension permutations correspond to permutation matrices.
Why use n 2 elements to describe an object only requiring n? There are two answers. One is
that on a hypercube multiprocessor it is frequently desirable to combine coding, decoding, and
dimension permutation operations [13]. Matrix notation allows us to put all of these operations
into the same setting. The other answer is that we can derive results about these matrices without
actually explicitly writing down the entries of the matrix. In this latter context, we are really only
deriving algebraic results for the symmetric group on n objects.
On hypercube multiprocessors, dimension permutations induce a fairly complicated motion on
the machine. Remember that a dimension permutation is an index transformation on n objects
that induces a more complicated permutation of 2 n objects. Factorizing the permutation matrix
into simpler matrices allows a compact way of thinking about algorithms.
A dimension permutation on all dimensions forming a shuffle is represented by a circulant matrix
as shown below for five dimensions.
An unshuffle is also represented as a circulant matrix,
In our next definition we precisely define shuffle permutations.
Definition 5.1 A shuffle permutation on indices is the transformation whose
matrix S i;j is given as the identity except in columns which are e
in other words, the appropriate columns are shifted left circularly.
On hypercube multiprocessors, it is convenient to implement dimension permutations as sequences
of elementary bit-exchanges:
Definition 5.2 An index transformation is defined to be an elementary bit-exchange if its
matrix representation is a permutation matrix that is the identity except in two rows and columns.
We denote such a matrix E i$j , where i and j are the distinguished rows and columns.
Definition 5.3 An index transformation is defined to be a bit-exchange if its matrix representation
is a symmetric permutation matrix.
Lemma 5.1 A bit-exchange matrix can be expressed as the product of independent elementary bit-
exchange matrices, and, conversely, the product of independent elementary bit-exchange matrices
can be reduced to a bit-exchange matrix.
Lemma 5.2 Any shuffle permutation can be expressed as the product of two bit-exchange matrices.
Proof Renumber the shuffle, if necessary, to be S 1;n . S 1;n is the product of the following two
bit-exchange matrices:
Lemma 5.3 Any permutation matrix can be expressed as the product of two bit-exchange matrices.
Proof The proof is similar to the proof of Lemma 5.2 once the permutation matrix is separated
into disjoint cycles.
These facts can be quite useful in practice. Code written for the CM-2 to accomplish the
bit-reverse operation [4] was easily generalized to the bit-exchange operation. Using Lemma 5.3,
any dimension permutation had an implementation. This was the motivation for a large software
project, known as the "twuffler," to accomplish operations of the form G
.
Notice that if
As is well-known [14], a shuffle or unshuffle can be carried out as a sequence of dimension
exchanges in two convenient ways, as illustrated by the following examples when 5:
Example 1: S
and
Example 2: S
In fact, there are exactly n factorizations of the shuffle matrix into elementary bit-exchanges with
elementary bit-exchanges are their own inverses, factorizations of S \Gamma1
are
obtained by reversing the order of the factors of S 1;5 .
Generalizing the two examples, we see that
and
where the product is in increasing order in Equation (5.6) and in decreasing order in Equation(5.7).
Note how in Example 1, all dimensions but the first and last are used twice, while in Example 2
only dimension 1 is used more than once. With the total use of dimensions must be
so that Example 1 best load balances all of the dimensions, while Example 2 represents the
worst case of load balancing the dimensions. However, the data motion in Example 1 accounting for
the factor-of-two difference between the two approaches is unnecessary and can be eliminated [14].
Furthermore, even though Example 2 appears unfavorable, if the fixed dimension is a dimension
local to a node, then all bit-exchanges are between adjacent nodes in a binary cube, while the
factorization given in Example 1 requires communication between nodes at distance two. The
factorization given by Example 2 is the basis for the algorithms by Swartztrauber [25], and several
of the algorithms by Johnsson and Ho [14, 18].
These algorithms are based on the following observation. From (5.6) we see that E i$i+1 S
S i+1;j . Combining this with (5.7), we obtain that
Y
Thus, a shuffle on dimensions can be expressed as the product of n
exchanges, with the same dimension used in every bit-exchange. If dimension i in fact represents
local memory, the advantages of this approach are clear. Each elementary bit-exchange represents
one-hop communication on the hypercube.
Another approach that has proved convenient is to express a shuffle permutation as a composition
of several shuffle permutations on fewer dimensions. This method can be used to devise
algorithms with optimal concurrency in communication [20, 21, 14, 18].
Again using Equations (5.6) and (5.7),
taking advantage of the fact that S j;k and S i;j \Gamma1 commute. Thus, if there are several elements per
node, some elements can be permuted according to S j;k first, others according to S i;j \Gamma1 first.
6 Conclusion
We have cast index transformation algorithms in a linear algebraic framework with applications
towards hypercube algorithms. Such a framework has multiple purposes. One is to express ideas
that are already commonly known, but in a more concise language. Another more important
purpose is to shed light on the existence of algorithms and to construct them automatically. We
have demonstrated both.

Acknowledgements

We would like to thank Thinking Machines Corporation, and particularly Marshall Isman and
Ted Tabloski, for supporting this work and related projects on the Connection Machine. They
provided financial support and a sense of spirit that makes such a project a pleasure. In addition,
the first author would like to thank Thinking Machines Corporation and the third author for
inviting him to work on this project as it related to the "twuffler" project in the summer of 1990
during which the earliest version of this paper was drafted [3]. Finally, we would like to thank
Emily Stone for her excellent assistance in editing.



--R

Optimal communication algorithms for hypercubes
Fast Permuting on Disk Arrays
The algebra of shuffling and Gray-coding on a hypercube
Optimal matrix transposition and bit reversal on hypercubes: all-to-all personalized communication
A Unified Approach to a Class of Data Movements on an Array Processor
Array permutations by index-digit permutation
The curious properties of the Gray code and how it can be used to solve puzzles
Gray codes and paths on the n-cube
Matrix Computations
Origins of the binary code
A fast algorithm for transposing large multidimensional image data sets
Communication efficient basic linear algebra computations on hypercube archi- tectures
Algorithms for matrix transposition on Boolean N-Cube Configured Ensemble Architectures
Optimal Algorithms for Stable Dimension Permutations on Boolean Cubes
On the conversion between binary code and binary-reflected Gray code on Boolean cubes
Optimal Communication in Distributed and Shared Memory Models of Computation on Network Architectures
The Complexity of Reshaping Arrays on Boolean Cubes
Generalized Shuffle Permutations on Boolean Cubes
Routing linear permutations through the omega network in two passes
An optimal routing algorithm for mesh connected parallel computers
Optimal BPC Permutations on a Cube Connected SIMD Computer
Parallel processing with the perfect shuffle
Passing Messages in Link-Bound Hypercubes
Intensive hypercube communication I: prearranged communication in link-bound machines
Journal of Parallel Computing.
Computational Frameworks for the Fast Fourier Transform
--TR
A unified approach to a class of data movements on an array processor
Communication effect basic linear algebra computations on hypercube architectures
Algorithms for matrix transposition on Boolean <italic>N</>-cube configured ensemble architecture
Optimal algorithms for stable dimension permutations on Boolean cubes
Optimal matrix transposition of bit reversal on hypercubes
Computational frameworks for the fast Fourier transform
Matrix computations (3rd ed.)
Array Permutation by Index-Digit Permutation
An optimal routing algorithm for mesh-connected Parallel computers

--CTR
Mounir Hamdi , Siang W. Song, Embedding Hierarchical Hypercube Networks into the Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.897-902, September 1997
Chris H. Q. Ding, An Optimal Index Reshuffle Algorithm for Multidimensional Arrays and Its Applications for Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, v.12 n.3, p.306-315, March 2001
Leonard F. Wisniewski, Structured permuting in place on parallel disk systems, Proceedings of the fourth  workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.128-139, May 27-27, 1996, Philadelphia, Pennsylvania, United States
Mayez Al-Mouhamed, Array organization in parallel memories, International Journal of Parallel Programming, v.32 n.2, p.123-163, April 2004
gray code encoding;matrix transpose;hypercube communications algorithms;index termslinear algebra;shuffles;bit reversal;encoding;hypercube multiprocessors;linear algebra framework;gray codes;indextransformation algorithms;vector reversal;gauss-jordan elimination;decoding;hypercube networks