\documentstyle[12pt]{article}
\addtolength{\footskip}{0.5in}
\newcommand{\r}[1]{(\ref{#1})}
\setlength{\textwidth}{6.5in}
\setlength{\baselineskip}{0.2in}
\setlength{\oddsidemargin}{-.1in}
\begin{document}
\renewcommand{\thefootnote}{\alph{footnote}}

\setcounter{footnote}{0}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{defn}{Definition}[section]
\newcommand{\proof}{\noindent{\bf Proof }}

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}

\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hfill\hfill\vbox{\hrule\hbox{\vrule\squarebox
   {.667em}\vrule}\hrule}\smallskip}

\newcommand{\xt}{\tilde{x}}
\newcommand{\K}{\tilde{K}}
\newcommand{\Ka}{{\tilde{\kappa}}}
\newcommand{\ha}{\frac{1}{2}}
\newcommand{\h}{\hbox{\hspace{0.5in}  }}
\newcommand{\ap}{\stackrel{p}{\rightarrow}}

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

\vspace{0.1in}

\title{Optimal Matrix Transposition and Bit Reversal on Hypercubes:
All--to--All Personalized Communication}
\author{\sl{Alan Edelman}
\footnotemark[0]
\\ Department of Mathematics \\
University of California \\
Berkeley, CA 94720} 
\date{}

\maketitle
\footnotetext{\\ Key words and phrases: 
bit reversal, communication, Connection Machine, hypercube, matrix transpose,
parallel computing 
}

\newpage


\setcounter{footnote}{0}
\renewcommand{\thefootnote}{\arabic{footnote}}

\begin{center}Running head:
All--to--all personalized communication.
\end{center}

\begin{center}
Alan Edelman \\
Department of Mathematics \\
University of California \\
Berkeley, CA 94720 \\
(510) 643-5695
\end{center}


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

In a hypercube multiprocessor with distributed memory,
messages have a street address and an apartment number,
i.e., a hypercube node address and a local memory address.  
Here we describe an optimal algorithm for performing the 
communication described by exchanging the bits of 
the node address with that of the local address. These exchanges
occur typically in both matrix
transposition and bit reversal for the fast
Fourier transform.
  
\newpage

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

Imagine the residents of $N=2^d$ cities 
creating zoos each with $N$ 
distinguishable specimens of some native animal.
The Sydney zoo might have $N$ very different looking koalas,
the New Delhi zoo might have $N$ identifiable elephants,
while the Boston
zoo might have $N$ automobile drivers.
Assume these $N$ cities are serviced by an airplane network forming
a $d$ dimensional hypercube.
What would be the most efficient way to
use the air routes to  reorganize the zoo specimens
so that now each zoo has one 
of every animal?


Consider the example of an
$N \times N$ matrix $A$ stored on a $d$-dimensional
hypercube with $N=2^d$ nodes.  A natural data structure
stores $a_{ij}$ in node $i$ and at local memory location
$j$.  Denote this address by $i|j$. 
Matrix transpose requires 
that the $N$ messages at node $i$ 
($\{i|j:j=0,1,\ldots,N-1\}$)
be divided across the machine into the $N$ memory locations
with local address $i$
($\{j|i:j=0,1,\ldots,N-1\}$).

As another example, let us calculate the FFT of 
a vector of length $N^2=2^{2d}$.  A natural data structure
splits the $2d$ address bits 
into a $d$ bit node address and a $d$-bit  local
address.  As is well known (see \cite{NR}, for example),
the result of an FFT is in bit-reversed order, and a separate 
communication is needed to reorganize the data.
This simply  means that
the real number located at (binary) address
$i_{2d}\ldots i_d | i_{d-1} \ldots i_0$
is swapped  with the number at address $i_0 \ldots i_{d-1} | i_d \ldots i_{2d}$.
Thus bit reversal is similar to the matrix transpose:
the $N$ messages at
node $i$ need to be divided across the machine into the  the $N$  memory
locations with local address $i$.


These two examples illustrate a communication pattern in which
$d$ node address bits are interchanged with $d$ local address bits.
In this situation, each node wants to send a different message
to each other node,  and thus this pattern is denoted all--to--all
personalized communication by the authors of  \cite{J1,J3,J2}
who noticed that these examples and others merit implementing
this type of communication as a programming primitive. 
The pattern is given a different name,
``total exchange" in \cite{BOSTT}, because
all pairs of nodes
trade (unique) data. 
This is different from
``all--to--all (non--personalized) broadcasting" in which every message is
replicated and sent to
every node (\cite{J3}).
We  consider only  the personalized case.


The total exchange  algorithm presented in \cite{BOSTT}
optimally
solves the problem presented. 
Optimal algorithms for the case
when the number of messages for each pair of nodes
is a multiple of the cube dimension
can be
found in \cite{J3} and \cite{S}; these algorithms
are not  optimal for our situation.
More recently, Johnsson and Ho  have devised optimal
algorithms for the single packet case as well \cite{J4}.





We have independently 
derived an optimal algorithm that 
takes advantage of the symmetry of the hypercube. 
We do this by computing a schedule whose computation
time is negligible compared to the communication time.

Our algorithm is based on performing
one--to--all personalized communication (\cite{J3}) from node 0. 
In ``one--to--all personalized
communication," one node has a unique message 
for each of the other nodes (see Figure 1).
We construct an optimal algorithm for routing the data from node 0
in such a way that if every other node performs the same sequence
of actions in its own relativized coordinate system, 
there will be no contention for communications channels.

\begin{figure}

\label{otap}
\begin{picture}(200,450)(-45,-250)
\put(60,40){\framebox(100,100){}}
\put(60,140){\circle*{7}}
\put(170,90){\vector(1,0){70}}
\put(240,89.5){\vector(1,0){0}}
\put(240,89){\vector(1,0){0}}
\put(250,40){\framebox(100,100){}}
\put(50,150){\circle{12}}
\put(50,150){\makebox(0,0){3}}
\put(50,165){\circle{12}}
\put(50,165){\makebox(0,0){1}}

\put(35,150){\circle{12}}
\put(35,150){\makebox(0,0){2}}
\put(35,165){\circle{12}}
\put(35,165){\makebox(0,0){0}}


\put(240,150){\circle{12}}
\put(240,150){\makebox(0,0){0}}
\put(360,150){\circle{12}}
\put(360,150){\makebox(0,0){1}}
\put(240,30){\circle{12}}
\put(240,30){\makebox(0,0){2}}
\put(360,30){\circle{12}}
\put(360,30){\makebox(0,0){3}}


\put(60,-170){\framebox(100,100){}}
\put(60,-170){\line(-1,1){50}}
\put(160,-170){\line(-1,1){50}}
\put(160,-70){\line(-1,1){50}}
\put(60,-70){\line(-1,1){50}}
\put(10,-120){\framebox(100,100){}}

\put(-10,-10){\circle{12}}
\put(-10,-10){\makebox(0,0){4}}
\put(-10,5){\circle{12}}
\put(-10,5){\makebox(0,0){0}}
\put(35,-10){\circle{12}}
\put(35,-10){\makebox(0,0){7}}
\put(35,5){\circle{12}}
\put(35,5){\makebox(0,0){3}}
\put(5,-10){\circle{12}}
\put(5,-10){\makebox(0,0){5}}
\put(5,5){\circle{12}}
\put(5,5){\makebox(0,0){1}}
\put(20,-10){\circle{12}}
\put(20,-10){\makebox(0,0){6}}
\put(20,5){\circle{12}}
\put(20,5){\makebox(0,0){2}}
\put(10,-20){\circle*{7}}

\put(170,-95){\vector(1,0){70}}
\put(240,-94.5){\vector(1,0){0}}
\put(240,-94.5){\vector(1,0){0}}

\put(240,-10){\circle{12}}
\put(240,-10){\makebox(0,0){0}}
\put(360,-10){\circle{12}}
\put(360,-10){\makebox(0,0){1}}
\put(240,-120){\circle{12}}
\put(240,-120){\makebox(0,0){4}}
\put(360,-120){\circle{12}}
\put(360,-120){\makebox(0,0){5}}
\put(290,-70){\circle{12}}
\put(290,-70){\makebox(0,0){2}}
\put(410,-60){\circle{12}}
\put(410,-60){\makebox(0,0){3}}
\put(288,-170){\circle{12}}
\put(288,-170){\makebox(0,0){6}}
\put(410,-170){\circle{12}}
\put(410,-170){\makebox(0,0){7}}


\put(300,-170){\framebox(100,100){}}
\put(250,-120){\framebox(100,100){}}
\put(300,-170){\line(-1,1){50}}
\put(400,-170){\line(-1,1){50}}
\put(400,-70){\line(-1,1){50}}
\put(300,-70){\line(-1,1){50}}
\end{picture}
\caption{
One--to--all personalized communication on a 2-cube and a 3-cube: 
Unique messages are sent from the leader to every other node.}
\end{figure}

For uses of this algorithm in FFTs and for index digit
permutations, see \cite{F1}, \cite{F2}, and \cite{S}.  
Our implementation on the Connection Machine is
used in the bit reversal for the FFT and
other IO reorderings, but we do not discuss this
in detail here.
We take the view that the problem on the hypercube
is interesting, even if no machine exists on which
to implement it.



\sect{Hypercubes}

As is well known,
a $d$ dimensional hypercube (sometimes known as a Boolean
$d$-cube) consists of $2^d$ nodes.  Nodes $j$ and
$k$ are nearest neighbors if the $d$-bit binary representations of
$j$ and $k$ differ in exactly one bit.  
Let $j \oplus k$ be the bitwise exclusive OR of the binary
representations of $j$ and $k$, and let Sum($j$)
denote the number of ones in the bitwise representation of $j$.
The minimum path between nodes $j$ and $k$ has length
Sum($j \oplus k$).  It is then obvious that the
average distance between two random nodes is $d/2$ links. 


There are $d2^{d-1}$ non-directed
edges or links in a $d$ dimensional cube.
In this paper, we typically assume that 
each non-directed edge is replaced by two directed edges,
so that there are exactly  $d2^d$ directed edges.
At each node, there are $d$ links for outgoing data
and $d$ links for incoming data.  Let outgoing
or incoming
link $k$ be the link that changes bit $k$.  


\sect{Basic Algorithm}

In this section, we describe our optimal algorithm for
performing the matrix transpose described as our
first example.  Thus, we assume that we have a $d$-dimensional
hypercube with $2^d$ local storage locations at each node,
and that we have 
an $N \times N$ matrix, where $N=2^d$, that we wish to transpose.
We begin by assuming that the message (32-bit word)
$a_{ij}$ is located at the address
$i|j$, i.e., node $i$ memory location $j$.


We also make use of a relative address of $i|j$:
\begin{defn}
The {\bf relative address} of $i|j= 
i\oplus j$.\footnote{The difference between
matrix transpose and bit reversal is in this definition.
For bit reversal, the relative address is
Reverse($i$) $\oplus j.$ 
For arbitrary  all--to--all personalized communication,
the data in node $i$ destined for node $j$ needs to be loaded into local 
memory
location $j$.}    
\end{defn}

We immediately observe that the relative address of
$i|j$ and that of $j|i$ are the same; i.e., the relative address
of a message is preserved under transposition.  Our
method is to use the links effectively to move
the message from $i|j$ to $j|i$ while preserving the
relative address:

\begin{defn}
A {\bf relative address preserving data movement} is
a communication where at each intermediate step,
the data preserve their relative addresses.
\end{defn}

The relative address is a powerful tool
as it captures the underlying symmetry of the communication.  With it, 
we can focus on one particular node, say node 0,
with the assurance that all the other nodes are performing
the appropriate operations relative to their address.
Furthermore, a relative address preserving data movement
allows the motion of data to occur without storing any
information regarding where the data was coming from or going
to. 
Thus no address bits need to be sent and the information is tied
to the memory location.

We make some simple observations. 
\begin{lemma}
\label{link-lemma}
The minimum number of links that
the word at $i|j$ needs to cross to reach
$j|i$ is exactly ${\rm Sum(}i \oplus j \mbox{\rm)}$. 
Let $L$ be the set of bits of $i \oplus j$
that are 1.  If the word at $i|j$  
traverses all the dimensions in $L$ in any order,
it will reach its destination.  Moreover,
if in each node the word at 
relative address
$i \oplus j$  marches through the
same numbered dimensions simultaneously, after   
{\rm Sum(}$i \oplus j${\rm )} steps, the words will
all reach their destination.
\end{lemma}

As an example, let $d$=3, and consider the words in each
node with relative address $5$.   
In all eight nodes,
the word with relative address 5 needs to travel over links 0 and 2. 
If we send all these words simultaneously first over link 0 and then
over link 2, they will all arrive at their destination in two communication
steps.

\begin{theorem}
The transpose requires at least
$2^{d-1}$ communications steps.
\end{theorem}

\proof
A lower bound is given by 
$$\frac{\mbox{total number of links that must be crossed}}
{\mbox{total number of links available}}$$
or
$$\frac{ \sum_{i,j} \mbox{Sum}(i \oplus j)}{d2^d}
= \frac{(d/2)(2^{2d})}{d2^d} = 2^{d-1},$$
since the average value for Sum($i \oplus j$) is $d/2$. 
(Other proofs of this result can be found in \cite{BOSTT,J3}.)
\qed

\begin{theorem}
\label{array-theorem}
An optimal schedule is given by a $2^{d-1}$ by $d$ array
of numbers $w_{ij}$, $i=0,1,\ldots,2^{d-1}-1$,
$j=0,1,\dots,d-1$
whose $k$th binary bit is denoted
by $w_{ij}^k$ satisfying
\end{theorem}
\begin{enumerate}
\item Wire appropriateness: $w_{ik}^{k}=1$ for all $i,k$.
\item Row uniqueness: $w_{ij_1} \ne w_{ij_2}$, if $j_1 \ne j_2$
for all $i$.
\item Column uniqueness: $w_{i_1j} \ne w_{i_2j}$, if $i_1 \ne i_2$.
\end{enumerate}
\vspace{0.1in}
{\it Given such an array, the optimal algorithm is}\\
{\bf For} $i=0,1,\ldots,2^{d-1}-1$ \\
\hspace*{.3in}
In each node, the expression 
$w_{ij}\oplus$ 
{\bf (node-address)}
specifies the local \\
\hspace*{.3in} memory location for the word sent over link $j$,
($j=0,1,\ldots,d-1$). \\ 
\hspace*{.3in} The word arriving over link $j$ takes its place. 
\vspace{0.1in}

\proof
In Lemma \ref{link-lemma}, we observed that the relative 
address must have a $1$ in the $k$th bit
for it to be appropriate to send the data over link $k$. 
Row uniqueness guarantees that we do not move the same
message over two different links at the same time step;
column uniqueness guarantees that we do not move
any message twice over the same link (which would be backtracking). 
These conditions guarantee that the relative address $w$
appears exactly Sum($w$) times in the array, once in
each column $j$ for which $w^j$ = 1.  Thus, the data 
at each relative address crosses all the appropriate links
exactly once.
\qed

We now propose an inexpensive 
algorithm for computing 
an array with the three conditions described in
Theorem \ref{array-theorem}.  


\vspace{0.1in}
{\bf Direct algorithm:} 
Let $n_i=2i+1$ and $n_i^k$ be the $k$th bit in its binary
representation. 
Compute $w_{ij}$ by performing the following operations
on $n_i$:  1) complement bit $j+1$ and 2) interchange bit
0 and bit $j$.
When $j=d-1$, complementing bit $j+1$ should be considered a
vacuous operation.
\vspace{0.2in}


\proof
The wire appropriateness condition is satisfied since 
$w_{ik}^k=n^i_0=1$.
Row uniqueness for $w_{ik}$, where $k\ne d-1$
follows from the complementing.  For $k=d-1$ a separate trivial
argument confirms row uniqueness once again.  Column uniqueness
follows from the clear fact that column $j$ is some permutation of
the  $2^{d-1}$ numbers with bit $j$ equal to 1. 
\qed

Figure 2 explicitly shows the data movement when $d=3$.
The data starting at node $i$ at location $j$ is indicated
by $i^j$.  The data starting at node 0 is denoted with a
$\spadesuit$ to facilitate tracking the data from one
particular node.  Though it is satisfying to see all the
data arriving at their destinations explicitly, we do not
recommend this diagram as a means for understanding our
algorithm.  Rather Table i contains the same information
as Figure 2, in a more compact manner.


Tables I,  II, and III illustrate the schedule for $d=3, 4$, and $5$.
Note that the schedules list the relative address of the 
data that is moved out of each node on a particular wire at a particular
time.
The three conditions: wire appropriateness, row uniqueness, and 
column uniqueness are readily observed in these tables.
Also observe that each binary number $w$ appears exactly
Sum($w$) times in the array, once in each column $k$ for which
$w^k$=1.

\clearpage

\begin{figure}[h]

\begin{picture}(200,450)(-20, -160)
\newsavebox{\cze}
\newsavebox{\con}
\newsavebox{\ctw}
\newsavebox{\cth}
\newsavebox{\cfo}
\newsavebox{\cfi}
\newsavebox{\csi}
\newsavebox{\cse}
\savebox{\cze}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^0$}}
            \put(2,11){\makebox(0,0){$\spadesuit^1$}}
            \put(20,11){\makebox(0,0){$\spadesuit^2$}}
            \put(38,11){\makebox(0,0){$\spadesuit^3$}}
            \put(-16,-7 ){\makebox(0,0){$\spadesuit^4$}}
            \put(2,-7 ){\makebox(0,0){$\spadesuit^5$}}
            \put(20,-7 ){\makebox(0,0){$\spadesuit^6$}}
            \put(38,-7 ){\makebox(0,0){$\spadesuit^7$}}
            \end{picture}
            }
\savebox{\con}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$1^0$}}
            \put(2,11){\makebox(0,0){$1^1$}}
            \put(20,11){\makebox(0,0){$1^2$}}
            \put(38,11){\makebox(0,0){$1^3$}}
            \put(-16,-7 ){\makebox(0,0){$1^4$}}
            \put(2,-7 ){\makebox(0,0){$1^5$}}
            \put(20,-7 ){\makebox(0,0){$1^6$}}
            \put(38,-7 ){\makebox(0,0){$1^7$}}
            \end{picture}
            }
\savebox{\ctw}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^0$}}
            \put(2,11){\makebox(0,0){$2^1$}}
            \put(20,11){\makebox(0,0){$2^2$}}
            \put(38,11){\makebox(0,0){$2^3$}}
            \put(-16,-7 ){\makebox(0,0){$2^4$}}
            \put(2,-7 ){\makebox(0,0){$2^5$}}
            \put(20,-7 ){\makebox(0,0){$2^6$}}
            \put(38,-7 ){\makebox(0,0){$2^7$}}
            \end{picture}
            }
\savebox{\cth}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$3^0$}}
            \put(2,11){\makebox(0,0){$3^1$}}
            \put(20,11){\makebox(0,0){$3^2$}}
            \put(38,11){\makebox(0,0){$3^3$}}
            \put(-16,-7 ){\makebox(0,0){$3^4$}}
            \put(2,-7 ){\makebox(0,0){$3^5$}}
            \put(20,-7 ){\makebox(0,0){$3^6$}}
            \put(38,-7 ){\makebox(0,0){$3^7$}}
            \end{picture}
            }
\savebox{\cfo}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$4^0$}}
            \put(2,11){\makebox(0,0){$4^1$}}
            \put(20,11){\makebox(0,0){$4^2$}}
            \put(38,11){\makebox(0,0){$4^3$}}
            \put(-16,-7 ){\makebox(0,0){$4^4$}}
            \put(2,-7 ){\makebox(0,0){$4^5$}}
            \put(20,-7 ){\makebox(0,0){$4^6$}}
            \put(38,-7 ){\makebox(0,0){$4^7$}}
            \end{picture}
            }
\savebox{\cfi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$5^0$}}
            \put(2,11){\makebox(0,0){$5^1$}}
            \put(20,11){\makebox(0,0){$5^2$}}
            \put(38,11){\makebox(0,0){$5^3$}}
            \put(-16,-7 ){\makebox(0,0){$5^4$}}
            \put(2,-7 ){\makebox(0,0){$5^5$}}
            \put(20,-7 ){\makebox(0,0){$5^6$}}
            \put(38,-7 ){\makebox(0,0){$5^7$}}
            \end{picture}
            }
\savebox{\csi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$6^0$}}
            \put(2,11){\makebox(0,0){$6^1$}}
            \put(20,11){\makebox(0,0){$6^2$}}
            \put(38,11){\makebox(0,0){$6^3$}}
            \put(-16,-7 ){\makebox(0,0){$6^4$}}
            \put(2,-7 ){\makebox(0,0){$6^5$}}
            \put(20,-7 ){\makebox(0,0){$6^6$}}
            \put(38,-7 ){\makebox(0,0){$6^7$}}
            \end{picture}
            }
\savebox{\cse}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$7^0$}}
            \put(2,11){\makebox(0,0){$7^1$}}
            \put(20,11){\makebox(0,0){$7^2$}}
            \put(38,11){\makebox(0,0){$7^3$}}
            \put(-16,-7 ){\makebox(0,0){$7^4$}}
            \put(2,-7 ){\makebox(0,0){$7^5$}}
            \put(20,-7 ){\makebox(0,0){$7^6$}}
            \put(38,-7 ){\makebox(0,0){$7^7$}}
            \end{picture}
            }

            
\newcommand{\cube}
        {\begin{picture}(100,100)(0,0)
            \put(0,0){\framebox(100,100){}}
            \put(50,-50){\framebox(100,100){}}
            \put(50,-50){\line(-1,1){50}}
            \put(150,-50){\line(-1,1){50}}
            \put(150,50){\line(-1,1){50}}
            \put(50,50){\line(-1,1){50}} 
            \put(-11,0){\usebox{\cfo}}
            \put(40,-48){\usebox{\csi}}
            \put(90,0){\usebox{\cfi}}
            \put(140,-48){\usebox{\cse}}
            \put(-12,95){\usebox{\cze}}
            \put(40,50){\usebox{\ctw}}
            \put(90,95){\usebox{\con}}
            \put(140,50){\usebox{\cth}}
            \end{picture}
            }
\put(103,346){\cube}
\put(253,351){\line(1,0){15}}
\put(268,346){\framebox{\Large Start}}

\put(350,400){\begin{picture}(10,10)
              \put(0,8){Dimension 0}
              \put(38,-35){Dim 1}
              \put(-21,-68){Dim 2}
              \put(0,0){\vector(1,0){75}}
              \put(0,0){\vector(0,-1){75}}
              \put(0,0){\vector(1,-1){75}}
              \end{picture}} 


\savebox{\cze}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^0$}}
            \put(2,11){\makebox(0,0){$\spadesuit^1$}}
            \put(20,11){\makebox(0,0){$\spadesuit^2$}}
            \put(38,11){\makebox(0,0){$1^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^0$}}
            \put(2,-7 ){\makebox(0,0){$\spadesuit^5$}}
            \put(20,-7 ){\makebox(0,0){$2^4$}}
            \put(38,-7 ){\makebox(0,0){$\spadesuit^7$}}
            \end{picture}
            }
\savebox{\con}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$1^0$}}
            \put(2,11){\makebox(0,0){$1^1$}}
            \put(20,11){\makebox(0,0){$\spadesuit^3$}}
            \put(38,11){\makebox(0,0){$1^3$}}
            \put(-16,-7 ){\makebox(0,0){$1^4$}}
            \put(2,-7 ){\makebox(0,0){$5^1$}}
            \put(20,-7 ){\makebox(0,0){$1^6$}}
            \put(38,-7 ){\makebox(0,0){$3^5$}}
            \end{picture}
            }
\savebox{\ctw}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^0$}}
            \put(2,11){\makebox(0,0){$3^0$}}
            \put(20,11){\makebox(0,0){$2^2$}}
            \put(38,11){\makebox(0,0){$2^3$}}
            \put(-16,-7 ){\makebox(0,0){$\spadesuit^6$}}
            \put(2,-7 ){\makebox(0,0){$2^5$}}
            \put(20,-7 ){\makebox(0,0){$6^2$}}
            \put(38,-7 ){\makebox(0,0){$2^7$}}
            \end{picture}
            }
\savebox{\cth}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^1$}}
            \put(2,11){\makebox(0,0){$3^1$}}
            \put(20,11){\makebox(0,0){$3^2$}}
            \put(38,11){\makebox(0,0){$3^3$}}
            \put(-16,-7 ){\makebox(0,0){$3^4$}}
            \put(2,-7 ){\makebox(0,0){$1^7$}}
            \put(20,-7 ){\makebox(0,0){$3^6$}}
            \put(38,-7 ){\makebox(0,0){$7^3$}}
            \end{picture}
            }
\savebox{\cfo}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^4$}}
            \put(2,11){\makebox(0,0){$4^1$}}
            \put(20,11){\makebox(0,0){$6^0$}}
            \put(38,11){\makebox(0,0){$4^3$}}
            \put(-16,-7 ){\makebox(0,0){$4^4$}}
            \put(2,-7 ){\makebox(0,0){$4^5$}}
            \put(20,-7 ){\makebox(0,0){$4^6$}}
            \put(38,-7 ){\makebox(0,0){$5^6$}}
            \end{picture}
            }
\savebox{\cfi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$5^0$}}
            \put(2,11){\makebox(0,0){$1^5$}}
            \put(20,11){\makebox(0,0){$5^2$}}
            \put(38,11){\makebox(0,0){$7^1$}}
            \put(-16,-7 ){\makebox(0,0){$5^4$}}
            \put(2,-7 ){\makebox(0,0){$5^5$}}
            \put(20,-7 ){\makebox(0,0){$4^7$}}
            \put(38,-7 ){\makebox(0,0){$5^7$}}
            \end{picture}
            }
\savebox{\csi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$4^2$}}
            \put(2,11){\makebox(0,0){$6^1$}}
            \put(20,11){\makebox(0,0){$2^6$}}
            \put(38,11){\makebox(0,0){$6^3$}}
            \put(-16,-7 ){\makebox(0,0){$6^4$}}
            \put(2,-7 ){\makebox(0,0){$7^4$}}
            \put(20,-7 ){\makebox(0,0){$6^6$}}
            \put(38,-7 ){\makebox(0,0){$6^7$}}
            \end{picture}
            }
\savebox{\cse}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$7^0$}}
            \put(2,11){\makebox(0,0){$5^3$}}
            \put(20,11){\makebox(0,0){$7^2$}}
            \put(38,11){\makebox(0,0){$3^7$}}
            \put(-16,-7 ){\makebox(0,0){$6^5$}}
            \put(2,-7 ){\makebox(0,0){$7^5$}}
            \put(20,-7 ){\makebox(0,0){$7^6$}}
            \put(38,-7 ){\makebox(0,0){$7^7$}}
            \end{picture}
            }

\put(0,152){\cube}
\put(150,157){\line(1,0){15}}
\put(165,152){\framebox{\Large Step 1}}

\savebox{\cze}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^0$}}
            \put(2,11){\makebox(0,0){$1^0$}}
            \put(20,11){\makebox(0,0){$\spadesuit^2$}}
            \put(38,11){\makebox(0,0){$1^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^0$}}
            \put(2,-7 ){\makebox(0,0){$\spadesuit^5$}}
            \put(20,-7 ){\makebox(0,0){$6^0$}}
            \put(38,-7 ){\makebox(0,0){$2^5$}}
            \end{picture}
            }
\savebox{\con}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^1$}}
            \put(2,11){\makebox(0,0){$1^1$}}
            \put(20,11){\makebox(0,0){$\spadesuit^3$}}
            \put(38,11){\makebox(0,0){$1^3$}}
            \put(-16,-7 ){\makebox(0,0){$1^4$}}
            \put(2,-7 ){\makebox(0,0){$5^1$}}
            \put(20,-7 ){\makebox(0,0){$3^4$}}
            \put(38,-7 ){\makebox(0,0){$7^1$}}
            \end{picture}
            }
\savebox{\ctw}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^0$}}
            \put(2,11){\makebox(0,0){$3^0$}}
            \put(20,11){\makebox(0,0){$2^2$}}
            \put(38,11){\makebox(0,0){$3^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^2$}}
            \put(2,-7 ){\makebox(0,0){$\spadesuit^7$}}
            \put(20,-7 ){\makebox(0,0){$6^2$}}
            \put(38,-7 ){\makebox(0,0){$2^7$}}
            \end{picture}
            }
\savebox{\cth}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^1$}}
            \put(2,11){\makebox(0,0){$3^1$}}
            \put(20,11){\makebox(0,0){$2^3$}}
            \put(38,11){\makebox(0,0){$3^3$}}
            \put(-16,-7 ){\makebox(0,0){$1^6$}}
            \put(2,-7 ){\makebox(0,0){$5^3$}}
            \put(20,-7 ){\makebox(0,0){$3^6$}}
            \put(38,-7 ){\makebox(0,0){$7^3$}}
            \end{picture}
            }
\savebox{\cfo}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^4$}}
            \put(2,11){\makebox(0,0){$4^1$}}
            \put(20,11){\makebox(0,0){$2^4$}}
            \put(38,11){\makebox(0,0){$6^1$}}
            \put(-16,-7 ){\makebox(0,0){$4^4$}}
            \put(2,-7 ){\makebox(0,0){$5^4$}}
            \put(20,-7 ){\makebox(0,0){$4^6$}}
            \put(38,-7 ){\makebox(0,0){$5^6$}}
            \end{picture}
            }
\savebox{\cfi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$5^0$}}
            \put(2,11){\makebox(0,0){$1^5$}}
            \put(20,11){\makebox(0,0){$7^0$}}
            \put(38,11){\makebox(0,0){$3^5$}}
            \put(-16,-7 ){\makebox(0,0){$4^5$}}
            \put(2,-7 ){\makebox(0,0){$5^5$}}
            \put(20,-7 ){\makebox(0,0){$4^7$}}
            \put(38,-7 ){\makebox(0,0){$5^7$}}
            \end{picture}
            }
\savebox{\csi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^6$}}
            \put(2,11){\makebox(0,0){$4^3$}}
            \put(20,11){\makebox(0,0){$2^6$}}
            \put(38,11){\makebox(0,0){$6^3$}}
            \put(-16,-7 ){\makebox(0,0){$6^4$}}
            \put(2,-7 ){\makebox(0,0){$7^4$}}
            \put(20,-7 ){\makebox(0,0){$6^6$}}
            \put(38,-7 ){\makebox(0,0){$7^6$}}
            \end{picture}
            }
\savebox{\cse}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$5^2$}}
            \put(2,11){\makebox(0,0){$1^7$}}
            \put(20,11){\makebox(0,0){$7^2$}}
            \put(38,11){\makebox(0,0){$3^7$}}
            \put(-16,-7 ){\makebox(0,0){$6^5$}}
            \put(2,-7 ){\makebox(0,0){$7^5$}}
            \put(20,-7 ){\makebox(0,0){$6^7$}}
            \put(38,-7 ){\makebox(0,0){$7^7$}}
            \end{picture}
            }
\put(273,152){\cube}
\put(423,157){\line(1,0){15}}
\put(438,152){\framebox{\Large Step 2}}

\savebox{\cze}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^0$}}
            \put(2,11){\makebox(0,0){$1^0$}}
            \put(20,11){\makebox(0,0){$2^0$}}
            \put(38,11){\makebox(0,0){$1^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^0$}}
            \put(2,-7 ){\makebox(0,0){$4^1$}}
            \put(20,-7 ){\makebox(0,0){$6^0$}}
            \put(38,-7 ){\makebox(0,0){$3^4$}}
            \end{picture}
            }
\savebox{\con}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^1$}}
            \put(2,11){\makebox(0,0){$1^1$}}
            \put(20,11){\makebox(0,0){$\spadesuit^3$}}
            \put(38,11){\makebox(0,0){$3^1$}}
            \put(-16,-7 ){\makebox(0,0){$5^0$}}
            \put(2,-7 ){\makebox(0,0){$5^1$}}
            \put(20,-7 ){\makebox(0,0){$2^5$}}
            \put(38,-7 ){\makebox(0,0){$7^1$}}
            \end{picture}
            }
\savebox{\ctw}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^2$}}
            \put(2,11){\makebox(0,0){$3^0$}}
            \put(20,11){\makebox(0,0){$2^2$}}
            \put(38,11){\makebox(0,0){$3^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^2$}}
            \put(2,-7 ){\makebox(0,0){$1^6$}}
            \put(20,-7 ){\makebox(0,0){$6^2$}}
            \put(38,-7 ){\makebox(0,0){$6^3$}}
            \end{picture}
            }
\savebox{\cth}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$2^1$}}
            \put(2,11){\makebox(0,0){$1^3$}}
            \put(20,11){\makebox(0,0){$2^3$}}
            \put(38,11){\makebox(0,0){$3^3$}}
            \put(-16,-7 ){\makebox(0,0){$\spadesuit^7$}}
            \put(2,-7 ){\makebox(0,0){$5^3$}}
            \put(20,-7 ){\makebox(0,0){$7^2$}}
            \put(38,-7 ){\makebox(0,0){$7^3$}}
            \end{picture}
            }
\savebox{\cfo}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^4$}}
            \put(2,11){\makebox(0,0){$\spadesuit^5$}}
            \put(20,11){\makebox(0,0){$2^4$}}
            \put(38,11){\makebox(0,0){$7^0$}}
            \put(-16,-7 ){\makebox(0,0){$4^4$}}
            \put(2,-7 ){\makebox(0,0){$5^4$}}
            \put(20,-7 ){\makebox(0,0){$6^4$}}
            \put(38,-7 ){\makebox(0,0){$5^6$}}
            \end{picture}
            }
\savebox{\cfi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$1^4$}}
            \put(2,11){\makebox(0,0){$1^5$}}
            \put(20,11){\makebox(0,0){$6^1$}}
            \put(38,11){\makebox(0,0){$3^5$}}
            \put(-16,-7 ){\makebox(0,0){$4^5$}}
            \put(2,-7 ){\makebox(0,0){$5^5$}}
            \put(20,-7 ){\makebox(0,0){$4^7$}}
            \put(38,-7 ){\makebox(0,0){$7^5$}}
            \end{picture}
            }
\savebox{\csi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^6$}}
            \put(2,11){\makebox(0,0){$5^2$}}
            \put(20,11){\makebox(0,0){$2^6$}}
            \put(38,11){\makebox(0,0){$2^7$}}
            \put(-16,-7 ){\makebox(0,0){$4^6$}}
            \put(2,-7 ){\makebox(0,0){$7^4$}}
            \put(20,-7 ){\makebox(0,0){$6^6$}}
            \put(38,-7 ){\makebox(0,0){$7^6$}}
            \end{picture}
            }
\savebox{\cse}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$4^3$}}
            \put(2,11){\makebox(0,0){$1^7$}}
            \put(20,11){\makebox(0,0){$3^6$}}
            \put(38,11){\makebox(0,0){$3^7$}}
            \put(-16,-7 ){\makebox(0,0){$6^5$}}
            \put(2,-7 ){\makebox(0,0){$5^7$}}
            \put(20,-7 ){\makebox(0,0){$6^7$}}
            \put(38,-7 ){\makebox(0,0){$7^7$}}
            \end{picture}
            }
\put(0,-60){\cube}
\put(150,-55){\line(1,0){15}}
\put(165,-60){\framebox{\Large Step 3}}

\savebox{\cze}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^0$}}
            \put(2,11){\makebox(0,0){$1^0$}}
            \put(20,11){\makebox(0,0){$2^0$}}
            \put(38,11){\makebox(0,0){$3^0$}}
            \put(-16,-7 ){\makebox(0,0){$4^0$}}
            \put(2,-7 ){\makebox(0,0){$5^0$}}
            \put(20,-7 ){\makebox(0,0){$6^0$}}
            \put(38,-7 ){\makebox(0,0){$7^0$}}
            \end{picture}
            }
\savebox{\con}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^1$}}
            \put(2,11){\makebox(0,0){$1^1$}}
            \put(20,11){\makebox(0,0){$2^1$}}
            \put(38,11){\makebox(0,0){$3^1$}}
            \put(-16,-7 ){\makebox(0,0){$4^1$}}
            \put(2,-7 ){\makebox(0,0){$5^1$}}
            \put(20,-7 ){\makebox(0,0){$6^1$}}
            \put(38,-7 ){\makebox(0,0){$7^1$}}
            \end{picture}
            }
\savebox{\ctw}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^2$}}
            \put(2,11){\makebox(0,0){$1^2$}}
            \put(20,11){\makebox(0,0){$2^2$}}
            \put(38,11){\makebox(0,0){$3^2$}}
            \put(-16,-7 ){\makebox(0,0){$4^2$}}
            \put(2,-7 ){\makebox(0,0){$5^2$}}
            \put(20,-7 ){\makebox(0,0){$6^2$}}
            \put(38,-7 ){\makebox(0,0){$7^2$}}
            \end{picture}
            }
\savebox{\cth}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^3$}}
            \put(2,11){\makebox(0,0){$1^3$}}
            \put(20,11){\makebox(0,0){$2^3$}}
            \put(38,11){\makebox(0,0){$3^3$}}
            \put(-16,-7 ){\makebox(0,0){$4^3$}}
            \put(2,-7 ){\makebox(0,0){$5^3$}}
            \put(20,-7 ){\makebox(0,0){$6^3$}}
            \put(38,-7 ){\makebox(0,0){$7^3$}}
            \end{picture}
            }
\savebox{\cfo}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^4$}}
            \put(2,11){\makebox(0,0){$1^4$}}
            \put(20,11){\makebox(0,0){$2^4$}}
            \put(38,11){\makebox(0,0){$3^4$}}
            \put(-16,-7 ){\makebox(0,0){$4^4$}}
            \put(2,-7 ){\makebox(0,0){$5^4$}}
            \put(20,-7 ){\makebox(0,0){$6^4$}}
            \put(38,-7 ){\makebox(0,0){$7^4$}}
            \end{picture}
            }
\savebox{\cfi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^5$}}
            \put(2,11){\makebox(0,0){$1^5$}}
            \put(20,11){\makebox(0,0){$2^5$}}
            \put(38,11){\makebox(0,0){$3^5$}}
            \put(-16,-7 ){\makebox(0,0){$4^5$}}
            \put(2,-7 ){\makebox(0,0){$5^5$}}
            \put(20,-7 ){\makebox(0,0){$6^5$}}
            \put(38,-7 ){\makebox(0,0){$7^5$}}
            \end{picture}
            }
\savebox{\csi}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit    ^6$}}
            \put(2,11){\makebox(0,0){$1^6$}}
            \put(20,11){\makebox(0,0){$2^6$}}
            \put(38,11){\makebox(0,0){$3^6$}}
            \put(-16,-7 ){\makebox(0,0){$4^6$}}
            \put(2,-7 ){\makebox(0,0){$5^6$}}
            \put(20,-7 ){\makebox(0,0){$6^6$}}
            \put(38,-7 ){\makebox(0,0){$7^6$}}
            \end{picture}
            }
\savebox{\cse}(10,10)
        {\begin{picture}(10,10)(0,0)
            \put(-16,11){\makebox(0,0){$\spadesuit^7$}}
            \put(2,11){\makebox(0,0){$1^7$}}
            \put(20,11){\makebox(0,0){$2^7$}}
            \put(38,11){\makebox(0,0){$3^7$}}
            \put(-16,-7 ){\makebox(0,0){$4^7$}}
            \put(2,-7 ){\makebox(0,0){$5^7$}}
            \put(20,-7 ){\makebox(0,0){$6^7$}}
            \put(38,-7 ){\makebox(0,0){$7^7$}}
            \end{picture}
            }
\put(273,-60){\cube}
\put(423,-55){\line(1,0){15}}
\put(438,-60){\framebox{\Large Step 4}}

\end{picture}


\caption{Data movement for all--to--all personalized communication
(see text and compare Table i)}

\end{figure}


\addtolength{\headsep}{1.1in}
\addtolength{\footskip}{-0.5in}
\clearpage


\begin{table}[h]
\caption{Schedule for $d=3$}.
% Entries indicate which relative address is sent
% in {\bf all} the nodes.}
 
\begin{center}

\begin{tabular}{cc|c|c|c|}
& \multicolumn{1}{c}{} &  \multicolumn{3}{c}{ Dimension} \\              
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{0} &
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} \\
              \cline{3-5}
              & 1 & 011 & 110 & 100 \\
Communication & 2 & 001 & 111 & 110 \\
Step          & 3 & 111 & 010 & 101 \\
              & 4 & 101 & 011 & 111 \\ \cline{3-5}
\end{tabular}
\end{center}
\end{table}

\clearpage

\begin{table}[h]
\caption{Schedule for $d=4$}

\begin{center}
\begin{tabular}{cc|c|c|c|c|}
& \multicolumn{1}{c}{} &  \multicolumn{4}{c}{ Dimension} \\              
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{0} &
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} \\
              \cline{3-6}
              & 1 & 0011 & 0110 & 1100 & 1000 \\
              & 2 & 0001 & 0111 & 1110 & 1010 \\
              & 3 & 0111 & 0010 & 1101 & 1100 \\
Communication & 4 & 0101 & 0011 & 1111 & 1110 \\
Step          & 5 & 1011 & 1110 & 0100 & 1001 \\
              & 6 & 1001 & 1111 & 0110 & 1011 \\
              & 7 & 1111 & 1010 & 0101 & 1101 \\
              & 8 & 1101 & 1011 & 0111 & 1111 \\ \cline{3-6}
\end{tabular}
\end{center}
\end{table}

\clearpage

\begin{table}[h]
\caption{Schedule for $d=5$}

\begin{center}
\begin{tabular}{cr|c|c|c|c|c|}
& \multicolumn{1}{c}{} &  \multicolumn{5}{c}{ Dimension} \\              
& \multicolumn{1}{c}{} & \multicolumn{1}{c}{0} &
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3}
& \multicolumn{1}{c}{4} \\
              \cline{3-7}
& 1 & 00011 & 00110 & 01100 & 11000 & 10000 \\
& 2 & 00001 & 00111 & 01110 & 11010 & 10010 \\
& 3 & 00111 & 00010 & 01101 & 11100 & 10100 \\
& 4 & 00101 & 00011 & 01111 & 11110 & 10110 \\
& 5 & 01011 & 01110 & 00100 & 11001 & 11000 \\
& 6 & 01001 & 01111 & 00110 & 11011 & 11010 \\
& 7 & 01111 & 01010 & 00101 & 11101 & 11100 \\
Communication & 8 & 01101 & 01011 & 00111 & 11111 & 11110 \\ 
Step & 9 & 10011 & 10110 & 11100 & 01000 & 10001 \\
& 10 & 10001 & 10111 & 11110 & 01010 & 10011 \\
& 11 & 10111 & 10010 & 11101 & 01100 & 10101 \\
& 12 & 10101 & 10011 & 11111 & 01110 & 10111 \\
& 13 & 11011 & 11110 & 10100 & 01001 & 11001 \\
& 14 & 11001 & 11111 & 10110 & 01011 & 11011 \\
& 15 & 11111 & 11010 & 10101 & 01101 & 11101 \\
& 16 & 11101 & 11011 & 10111 & 01111 & 11111 \\ \cline{3-7}
\end{tabular}
\end{center}
\end{table}

\addtolength{\headsep}{-1.8in}
\addtolength{\footskip}{1.2in}
\clearpage

\newpage

\noindent
{\Large \bf Acknowledgements}

I thank Lennart Johnsson for
several interesting discussions, 
and for introducing me to this problem and related work.
Without his motivating me to attack this problem, I never
would have worked on it.
I further thank 
Ching--Tien Ho for relating previous work in this area.
I also acknowledge
Mark Bromley,
Steve Heller,
Mike McKenna, and Walter Mascarenhas for all of their help
implementing this
and related algorithms on the Connection Machine.  

\vspace{0.2in}
\noindent
{\Large \bf Biography}

Alan Edelman received his Ph.D. degree in mathematics
from the Massachusetts
Institute of Technology in 1989, and the 
BS and MS degrees in mathematics from Yale University in 1984.

He is currently a Morrey Assistant Professor at the
mathematics department at the University of California
at Berkeley after finishing an NSF-Nato postdoctoral
fellowship at the CERFACS computing center in Toulouse,
France.

Alan's research interests include numerical linear
algebra, parallel computing, eigenvalues of random matrices,
and approximation theory.  He recently shared the
Gordon Bell prize for parallel computing and the Householder
prize for numerical linear algebra.


\newpage


\def\\{\medskip\noindent\hangindent .3in{}}
%\setlength{\baselineskip 11pt}
\frenchspacing
\begin{thebibliography}{99}

\bibitem{BOSTT}
D.P.~Bertsekas, C.~Ozveren, G.D.~Stamoulis, P.~Tseng, and J.N.~Tsitsiklis,
Optimal communication algorithms for hypercubes,
{\sl J. Parallel Distributed Comput.}, to appear.

\bibitem{F1}
P.M.~Flanders,
A unified approach to a class of data movements on
an array processor,
{\sl IEEE Transactions on Computers. C-31}
(1982), 809-819.


\bibitem{F2}
D.~Fraser,
Array permutation by index-digit permutation,
{\sl J. ACM 22}
(1976), 298-308.

\bibitem{J4}
C.T.~Ho, personal communication, August 1, 1990.

\bibitem{J1}
S.L.~Johnsson,
Communication efficient basic linear algebra computations
on hypercube architectures,
{\sl J. Parallel Distributed Comput. 4}
(1987), 133--172.

\bibitem{J3}
S.L.~Johnsson and C.T.~Ho,
Optimum broadcasting and personalized communication
in hypercubes,
{\sl IEEE Transactions on Computers. 38}
(1989), 1249-1268.

\bibitem{J2}
S.L.~Johnsson and C.T.~Ho,
Algorithms for matrix transposition on Boolean
$N$-Cube Configured Ensemble Architectures,
{\sl SIAM J. Matrix Anal. Appl. 9} 
(1988), 419--454.


\bibitem{NR}
W.H.~Press, B.P.~Flannery, S.A.~Teukolsky, and
W.T.~Vetterling,
{\sl Numerical Recipes: The Art of Scientific Computing,}
Cambridge University Press, Cambridge,
1986.

\bibitem{S}
P.N.~Swarztrauber,
Multiprocessor FFTs,
{\sl Parallel Computing 5}
(1987), 197-210.

\end{thebibliography}

\end{document}
