\input{caption}
\makeatletter
\long\def\unmarkedfootnote#1{{\long\def\@makefntext##1{##1}\footnotetext{#1}
}}
\makeatother
\newcommand{\comment}[1]{}

\documentstyle[times,epsf,acmproc]{article}
\pagestyle{empty}

\setlength{\textheight}{8.8in}
\setlength{\columnsep}{1.8pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

\begin{document}
\bibliographystyle{acm}

\title{\Large\bf Computing the Pipelined Phase-Rotation FFT}
\author{
\begin{tabular}[c]{ c@{\extracolsep{2em}} c} 
 L.P. Withers, Jr., John E. Whelchel & David R. O'Hallaron, Peter J. Lieu \\
\\
{E-Systems, Inc., Melpar Div.} & {School of Computer Science}\\
{44983 Knoll Square}           & {Carnegie Mellon University}\\     
{Ashburn, Virginia 22011}      & {Pittsburgh, PA 15213} 
\end{tabular}
} 

\date{}
\maketitle 
\thispagestyle{empty}

\unmarkedfootnote{
Supported in part by the Air Force Office of Scientific Research under
Contract F49620--92--J--0131, in part by the Advanced Research
Projects Agency, and in part by an E-Systems IR\&D program.  
}

\thispagestyle{empty}

\begin{abstract}
The phase-rotation FFT is a new form of the FFT that replaces data
movement with multiplications by constant phasor multipliers.  The
result is an FFT that is simple to pipeline.  This paper completes the
pipelined design of the the original phase-rotation FFT, provides a
fundamental new description of the algorithm directly in terms of the
parallel pipeline, and describes a radix-2 implementation on the iWarp
computer system that balances computation and communication to run at
the full-bandwidth of the communications links, regardless of the
input data set size.
\end{abstract}

\section {Introduction}
The Fast Fourier Transform (FFT) is an important algorithm with
applications in signal processing and scientific computing. A typical
real-time signal processing application performs FFT's on a continuous
stream of sensor inputs arriving at fixed intervals. A pipeline of FFT
stages is a natural approach for processing such an input stream.
Unfortunately, conventional FFT algorithms are difficult to pipeline
because the input streams are permuted between each pipeline stage.
The Whelchel phase-rotation FFT~\cite{whelchel90} is a {\em new} form
of the FFT that replaces data movement at runtime with multiplications
by precomputed constants. The result is an FFT that is simple to
pipeline.

The Whelchel phase-rotation FFT~\cite{whelchel90} derives from the
Pease constant-geometry FFT~\cite{pease68}, which itself derives from
the original Cooley-Tukey FFT~\cite{cooley65} expressed in terms of
Kronecker products.  The phase-rotation FFT of radix $r$ is designed
for a pipeline of $r$ parallel data channels.  At each time step, in
each stage, the pipeline carries the next $r$ data points, one from
each channel, into a Discrete Fourier Transform (DFT) kernel.  Unlike
earlier pipelined FFT's~\cite{corinthios71,mcclellan78}, the
phase-rotation FFT has the key property that no data is switched
across channels, except within the DFT kernel and at the input and
output. Thus if the phase-rotation FFT is implemented in hardware, no
commutator switches are needed.

The phase-rotation approach extends easily to higher radices, reducing
memory and latency while preserving the high throughput and parallel
shuffling simplicity of lower radix versions.  The phase-rotation FFT
has also been extended to a vector-radix, multidimensional
parallel-pipeline FFT with the same qualities of the one-dimensional
algorithm, and without transposes~\cite{withers91}.

This paper reports the results of a project 
to implement the phase-rotation FFT on a parallel computer system. 
After a brief overview of the phase-rotation concept 
in Section~\ref{sec:basic}, 
the paper introduces a parallel-pipeline digit-reversing step that 
completes the pipelined design of the original phase-rotation FFT 
\cite{whelchel90} in Section~\ref{sec:phasedef}.  
Section~\ref{sec:recipes} provides, for the first time, 
a set of recipes that generate the twiddles and shuffle addresses 
necessary to implement the algorithm directly in a parallel pipeline. 
Finally, Section~\ref{sec:implementation} describes 
fine-grained mapping strategies to implement the $N$-point radix-2 
phase-rotation FFT on the iWarp system, 
that balance computation and 
communication to run at the full 40 Mbytes/sec rate of the iWarp
physical links for input data sets of any size $N$. 

\section{The basic idea} 
\label{sec:basic}
This section introduces the concept of the phase-rotation FFT.
Starting with the Pease constant-geometry FFT, we informally derive 
the pipelined phase-rotation FFT, identifying the key insights along
the way.

\subsection{Constant-geometry FFT}
Figure~\ref{fig:phase}(a) shows the flowgraph for a radix-$r$
$N$-point decimation-in-frequency (DIF) constant-geometry FFT, with
$r=2$ and $N=r^n=8$. There are $n$ stages. Each stage contains $N/r$
{\em kernels}. Each kernel is an operator that performs an $r$-point
DFT.  For radix 2, each kernel inputs two complex numbers and outputs
two complex numbers. (For simplicity, twiddles 
and the final digit-reversing shuffle 
are not explicitly shown in the flowgraph.) 
\begin{figure}
\epsfxsize=3.25in
\centerline{\epsfbox{phase.eps}}
\caption{Derivation of the phase-rotation FFT. {\rm (a) Initial
constant-geometry FFT. (b) Pipelined constant geometry FFT. (c) Pipelined
FFT based on cyclic rotations. (d) Pipelined phase-rotation FFT.}
} 
\label{fig:phase}
\end{figure}

Each stage in the constant-geometry FFT performs an identical perfect
stride-by-$s$ shuffle of its data vector, where $s = N/r$.  
An easy way to define the perfect shuffle is as follows: 
If the data vector is regarded as an $s \times r$ array, stored in
column-major order, then the perfect shuffle simply transposes it into
an $r \times s$ array.  For example, the following transpose is a
stride-by-4 perfect shuffle, for $N=8$ points and radix $r=2$:
\begin{center}
\begin{tabular} {l c c c}                      
$\left[ 
\begin{array} {c c} 
 0 & 4 \\
 1 & 5 \\
 2 & 6 \\
 3 & 7 
 \end{array} \right]$
&
 $\stackrel{T}{\longrightarrow}$
&
 $\left[ \begin{array} {c c c c} 
 0 & 1 & 2 & 3 \\
 4 & 5 & 6 & 7
\end{array} \right]$\\ 
\end{tabular} 
\end{center}
The data items in this example, labeled by their indices in the
original column vector, are regarded as equivalent to a $4 \times 2$
array composed by a stride-by-4 unstacking of the 8-point column
vector.  After the transpose, the $2 \times 4$ array is equivalent to
a new 8-point column vector composed by a stride-by-2 stacking.  As we
shall see, this transpose %% is difficult to do inside a pipeline. 
creates difficulties when we try to pipeline the constant-geometry FFT. 
And it is precisely these difficulties that
the phase-rotation FFT addresses.

\subsection{Pipelining the FFT}
Each stage of the constant-geometry FFT can be computed on a single
processor by pipelining the data.  For example,
Figure~\ref{fig:phase}(b) shows the pipeline for a single stage with
radix $r=2$.  The pipeline consists of a sequence of operators
connected by {\em pipeline segments}. Each pipeline segment consists
of $r$ parallel {\em channels}. Each channel carries a {\em stream} of
$N/r$ data points, which are labeled in this example by their indices
>from the original column vectors in Figure~\ref{fig:phase}(a). For
each pipeline segment, the $r$ data points in the same position in
each stream are known as an $r$-{\em frame}, or simply, a {\em frame}.
For example, in Figure~\ref{fig:phase}(b), the first frame in the
pipeline segment between ${\bf S}$ and ${\bf F}$ is (0,4), the second
frame is (1,5), and so on.

At each time step, the $r$ twiddle operators (${\bf T}$) collectively
read a frame (one complex number per operator), perform an
element-wise complex multiplication, and write the resulting frame.
Notice that each stream is operated on independently.  Similarly, the
kernel operator (${\bf F}$) reads a frame, computes the radix-$r$
kernel, and writes the resulting frame.  In this case, the streams are
not independent; each data item in the output frame is a function of
every data point in the input frame.

The twiddle and kernel operators pipeline nicely because during each
time step they independently read and write a single number from each
stream.  However, the pipelined shuffle operator (${\bf S}$) is less
well behaved.  To produce one output frame, the shuffle operator must
read and store the $r$ data points from each stream. Thus, ${\bf S}$
requires $r$ memory cycles to produce each frame. (Notice that ${\bf
S}$ transposes the data directly into an $r \times s$ pipeline
segment; but even starting with data already in an $r \times s$
pipeline, ${\bf S}$ still performs ``row-to-column'' motions.)  This
is an example of the {\em memory-bank conflict} discussed in
\cite[pp.31-32]{vanloan92}.  The conflict is clear in
Figure~\ref{fig:phase}(b).  To assemble its first output frame, ${\bf
S}$ must read both 0 and 4 from the upper stream to its left.  Then it
must read 1 and 5 from the lower stream, and so on.

We would like to replace the troublesome perfect shuffle operation
with a {\em parallel-pipeline shuffle}, where each stream is read and
written independently and in parallel. The next section describes the
insights that make this possible.

\subsection{The phase-rotation concept}
This section describes how to replace the perfect shuffle by a
parallel-pipeline shuffle, so that we can access the data streams in
parallel.  The basic idea is to rotate the data within frames, and
then compensate for these motions by phase rotations of the twiddle
factors.

We begin with a ``detour'' around the perfect shuffle. That is, we
find a sequence of three simpler shuffles that is equivalent to the
perfect shuffle.  This idea is shown graphically in
Figure~\ref{fig:decomp} for an $N$-point radix-2 example.  Each
radix-2 pipeline segment is represented as matrix. Each row in the
matrix corresponds to a stream, and each column corresponds to a
frame.  Frames (columns) are arranged left-to-right in reverse-time
order in the matrix.
\begin{figure}
\centering
\makebox{
\begin{tabular} {l c c c}                      
& 
 $\left[ \begin{array} {c c c c} 
 0 & 2 & 4 & 6 \\
 1 & 3 & 5 & 7
 \end{array} \right]$ 
&
 $\stackrel{{\bf S}}{\longrightarrow}$ 
&
 $\left[ \begin{array} {c c c c} 
 0 & 1 & 2 & 3 \\
 4 & 5 & 6 & 7
 \end{array} \right]$ 
\\ 
&
\\
& 
$\downarrow \; {\bf C}_{slow}$ & & $\uparrow \; {\bf C}_{fast}$ 
\\ 
& 
\\
&
 $\left[ \begin{array} {c c c c} 
 0 & 2 & 5 & 7 \\
 1 & 3 & 4 & 6             %% needs hand-drawn circles, squares 
 \end{array} \right]$ 
&
 $\stackrel{ \overline{\overline{\bf S}} }{\longrightarrow}$ 
&
 $\left[ \begin{array} {c c c c} 
 0 & 5 & 2 & 7 \\
 4 & 1 & 6 & 3             %% needs hand-drawn circles, squares 
\end{array} \right]$ 
\end{tabular} 
}
\caption{Replacing the perfect shuffle with three simpler shuffles.}
\label{fig:decomp}
\end{figure}

The first step in Figure~\ref{fig:decomp} is a set of cyclic
rotations, called ${\bf C}_{slow}$, which rotates each frame.  These
rotations are frame-wise in the sense that only data points contained
in the same frame are rotated across the streams.  Notice that in the
radix-2 case, half of the rotations leave the corresponding frame
unchanged.  The next step is a parallel-pipeline shuffle
$\overline{\overline{\bf S}}$, which permutes the data in each stream.
Notice that no data points need to be transferred between streams in
this step.  The last step is another set of frame-wise cyclic
rotations in the opposite direction, 
called ${\bf C}_{fast}$, which leave the data in the same
order that the perfect shuffle would.  Note that ${\bf C}_{slow}$ and
${\bf C}_{fast}$ change the number of rotations per frame at different
paces, one slow and one fast.  

If we apply the idea in Figure \ref{fig:decomp}) to each stage of the
pipelined FFT in Figure~\ref{fig:phase}(b), replacing each perfect
shuffle with three simpler shuffles, we get a pipelined FFT based on
cyclic rotations, which is shown in Figure~\ref{fig:phase}(c).

The kind of basic frame-wise rotations in Figure~\ref{fig:phase}(c)
that is applied at slow-varying, and then fast-varying rates, is
represented in general by the $r \times r$ cyclic (circular) shift
permutation matrix ${\bf C}_{r}$, made by permuting the rows of the
identity matrix ${\bf I}_r$ down by one row, 
and moving the bottom row up to the top. For example,
\begin{eqnarray*}
{\bf C}_{4} = \left(
\begin{array}{ c c c c }
0&0&0&1\\
1&0&0&0\\
0&1&0&0\\
0&0&1&0
\end{array} \right)\;\;.
\end{eqnarray*}
The key insight of the phase-rotation FFT is that the cyclic shift
theorem for the DFT can be applied to the cyclic shift operators in
Figure~\ref{fig:phase}(c).  In matrix form, the cyclic shift theorem for
a DFT is the relation
\begin{equation}
{\bf F}_{r}{\bf C}_{r} = {\bf D}_{r}{\bf F}_{r},
\label{eqn:shifttheorem}
\end{equation} 
where 
${\bf D}_{r}= diag( 1, \omega, \omega^{2}, ..., \omega^{r-1} )$
is a set of twiddles, and the DFT matrix of size $r$ is
\begin{displaymath}
{\bf F}_{r} = \frac {1}{\sqrt{r}} ( \omega^{jk})_{j,k=0}^{r-1} ,
\end{displaymath}
where $\omega = \exp{-\frac{2 \pi i}{r}}$.  For the pipelined FFT,
(\ref{eqn:shifttheorem}) says that phasor multipliers after a DFT
kernel give the same effect as a physical data rotation before the DFT
kernel.  Likewise, a physical rotation after the kernel is equivalent
to phasor multipliers before it. The meaning of
(\ref{eqn:shifttheorem}) is shown graphically in
Figure~\ref{fig:theorem} for a pipelined radix-2 kernel.  The shift
theorem implies that the data rotations in Figure~\ref{fig:phase}(c)
can be replaced by constant phasor multipliers.  These phasors can
then be absorbed by the twiddle factors on either side of the kernel,
leaving only a parallel-pipeline shuffle.  The result is the pipelined
phase-rotation FFT, which is shown in Figure~\ref{fig:phase}(d).  This
completes the informal derivation of the phase-rotation FFT.
\begin{figure}
\epsfxsize=3.25in
\centerline{\epsfbox{theorem.eps}}
\caption{Interpretation of ${\bf F}_{r}{\bf C}_{r} = {\bf D}_{r}{\bf
F}_{r}$}
\label{fig:theorem}
\end{figure}

The structure of the phase-rotation FFT in Figure~\ref{fig:phase}(d)
is similar to the original pipelined FFT in
Figure~\ref{fig:phase}(b), except that the phase-rotation 
FFT's shuffle is simpler. 
Though the twiddle values have been modified, 
the arithmetic steps for twiddle and kernel operators are unchanged. 
%\comment{The twiddle operators ($D^\prime$) are
%identical to the original twiddle operators ($T$), except now the
%twiddles incorporate the original twiddles, phasor multipliers for the
%${\bf C}_{fast}$ operator from the previous stage, and phasor
%multipliers for the ${\bf C}_{slow}$ operator from the next stage. The
%kernel operators are identical as well.}  
The important difference is that the perfect shuffle operator has now
been replaced by a parallel-pipeline shuffle that requires no
communication across the streams. There is, however, 
an additional set of twiddles during the final digit-reversing step.

%\comment First, there are no additional multiplications or additions,
%compared to the original pipelined FFT in Figure~\ref{fig:phase}(a).
%Second, the only internal communication across streams occurs at the
%kernel, and this communication is constrained, in that only data
%points within a single frame need to be switched across channels, and
%the switching is fixed for all frames.  } 

\section{Improved phase-rotation FFT}
\label{sec:phasedef}
In this section we define an improved version of
the original phase-rotation FFT described in \cite{whelchel90}. The
new version replaces the digit-reversing permutation at the end 
of the original phase-rotation FFT with a parallel-pipeline 
shuffle followed by frame-wise cyclic rotations.  
This last substitution completes the 
task of pipelining the constant-geometry FFT, so that  
in every stage, all communication
between streams is limited to data points within a single frame.

For radix $r$ and $N=r^n$ points ($n>1$), the 1-dimensional
phase-rotation FFT is a matrix factorization of the $N$-point DFT
matrix ${\bf F}_{N}$.  Starting with the Pease constant-geometry
factorization, we replace its perfect shuffles ${\bf S}$ by ${\bf S} =
{\bf C}_{fast} \overline{\overline{{\bf S}}} {\bf C}_{slow}$.
Similarly, at the left end we replace the radix-$r$
index-digit-reversing permutation ${\bf Q} = {\bf Q}_{N,r}$ of $N$
data points by ${\bf Q} = {\bf C}_{slow}^T \overline{\overline{\bf
Q}}{\bf C}_{slow}$, where $\overline{\overline{\bf Q}}$ is another
parallel-pipeline shuffle that will be defined formally in
Section~\ref{sec:recipes}. The phase-rotation FFT is then defined by:
\begin{eqnarray}
{\bf F}_{N} &=& {\bf Q} \cdot 
\prod_{j=1}^{n} \left( {\bf F}{\bf S}{\bf T}_{j} \right)
 = \cdots 
\left( \mbox{ \small
\begin{tabular}[c]{c} 
\small vigorous\\
\small algebraic\\
\small shuffling
\end{tabular}  } 
\right) \cdots 
\nonumber\\ 
%&=& 
%\left( \prod_{j=1}^{n-1} {\bf F}
%{\bf C}_{fast} \overline{\overline{{\bf S}}} 
% {\bf C}_{slow} {\bf T}_{j} \right) {\bf F}{\bf S}{\bf Q} 
% = \cdots \nonumber\\
&=& {\bf C}_{slow}^T \cdot \overline{\overline{\bf Q}}{\bf
D}_{fast}^{\prime} 
\left[  
\prod_{j=1}^{n} 
\left( {\bf F} \overline{\overline{{\bf S}}}{\bf D}_{j}^{\prime} \right) 
\right]
\cdot {\bf C}_{slow} . 
\label{eqn:phase} 
\end{eqnarray}
%
Let $s = N/r$ as before, and $r^{\prime} = N/r^2$.  ${\bf F}$ is a
direct (tensor, Kronecker) product ${\bf I}_{s} \otimes {\bf F}_{r} =
\mbox{diag}({\bf F}_{r}, {\bf F}_{r}, ...,{\bf F}_{r})$.  We interpret
this as a kernel DFT ${\bf F}_{r}$ operating on $s$ successive
frames of $r$ points placed in the pipeline.  For $j=1:n$, the other
parts of (\ref{eqn:phase}) are defined by
\begin{eqnarray}
{\bf C}_{slow} &=&  \bigoplus_{k=0}^{r-1} 
   \left( {\bf I}_{r^{\prime}} \otimes {\bf C}_{r}^{k} \right ) \nonumber\\ 
{\bf C}_{fast} &=&  {\bf I}_{r^{\prime}} \otimes 
   \left(   \bigoplus_{k=0}^{r-1} ({\bf C}_{r}^{T})^{k} \right ) \nonumber\\
\omega_j &=& exp \left({-\frac{2 \pi i}{r^{j}}} \right) \nonumber\\
{\bf D}_{r} &=& 
 diag( 1, \omega_{1}, \omega_{1}^{2}, ..., \omega_{1}^{r-1} ) 
 \nonumber\\ 
{\bf D}_{r^{j+1}} &=& 
 diag( 1, \omega_{j+1}, \omega_{j+1}^{2}, ..., \omega_{j+1}^{r^{j}-1} ) 
 \nonumber\\ 
{\bf D}_{slow}^{-1} &=&  \bigoplus_{k=0}^{r-1} 
   \left( {\bf I}_{r^{\prime}} \otimes {\bf D}_{r}^{-k} \right) 
   \nonumber\\ 
{\bf D}_{slow}^{\prime} &=&
              {\bf C}_{fast}^T {\bf D}_{slow}^{-1} {\bf C}_{fast}
\nonumber\\
{\bf D}_{slow}^{\prime \prime} &=& 
     \overline{\overline{{\bf S}}}^T 
     {\bf D}_{slow}^{\prime} 
     \overline{\overline{{\bf S}}} \nonumber\\
{\bf D}_{fast}^{-1}  &=&  {\bf I}_{r^{\prime}} \otimes 
   \left(   \bigoplus_{k=0}^{r-1} {\bf D}_{r}^{-k} \right) 
   \nonumber\\ 
{\bf D}_{fast}^{\prime} &=&
              {\bf C}_{slow}^T {\bf D}_{fast}^{-1}  {\bf C}_{slow}
\nonumber\\
{\tilde{\bf T}}_{j} &=& {\bf I}_{ \frac{N}{r^{(j+1)}} } \otimes 
   \left(  \bigoplus_{k=0}^{r-1}{\bf D}_{r^{j+1}}^{k} \right) \nonumber\\
%
{\bf T}_{j} &=& {\bf S}^{j\;T}{\tilde{\bf T}}_{j}{\bf S}^{j} \nonumber\\
{\bf T}_{j}^{\prime} &=& 
                 {\bf C}_{slow} {\bf T}_{j} {\bf C}_{slow}^T \nonumber\\
{\bf D}_{1}^{\prime} &=&      
     \left( \overline{\overline{{\bf S}}}^T 
            {\bf D}_{slow}^{-1} 
            \overline{\overline{{\bf S}}} \right) \cdot 
{\bf T}_{1}^{\prime}{\bf D}_{fast}^{-1}  \nonumber\\
{\bf D}_{j}^{\prime} &=& 
   {\bf D}_{slow}^{\prime \prime} {\bf T}_{j}^{\prime} {\bf D}_{fast}^{-1}
\;\;,
\;\;\;\; j=2:n-1 \nonumber\\ 
{\bf D}_{n}^{\prime} &=& 
{\bf D}_{slow}^{\prime \prime} {\bf T}_{n}^{\prime} = 
{\bf D}_{slow}^{\prime \prime} \;\;. 
\label{eqn:phasederivation}
\end{eqnarray}

The direct sums are of the form 
\begin{displaymath}
\bigoplus_{k=0}^{r-1} {\bf A}_{k} =
\mbox{diag}( {\bf A}_{0}, {\bf A}_{1},..., {\bf A}_{r-1} ), 
\end{displaymath}
and ${\bf A}^T$ denotes the transpose of ${\bf A}$. 
See \cite{withers91} for more on the basic definitions and relations
used to derive (\ref{eqn:phase}), as well as the generalization to
higher dimension FFT's.

Note that the stages in (\ref{eqn:phase}) are counted in reverse time
order by the index $j$. This is in keeping with the fact that
(\ref{eqn:phase}) is a decimation-in-frequency (DIF) version of the FFT.
The transpose of (\ref{eqn:phase}), with the product
$\prod_{j=n}^{1}$, is the decimation-in-time (DIT) version of the
phase-rotation FFT.

A ${\bf C}_{slow}$ shuffle and its inverse remain at the input and
output ends of the pipeline, respectively.  As we have seen, ${\bf
C}_{slow}$ is a completely frame-wise rotation.  It rotates
(commutates) the data within each successive frame (column $r$-vector)
of the $r \times s$ pipeline segment for a stage.  There is also an
implicit frame-wise broadcast within each FFT kernel engine, when an
$r$-point DFT is somehow computed.  So in the phase-rotation FFT, data
motion is all parallel, except for frame-wise motions at I/O and at
every FFT kernel.  The simplicity of the phase-rotation FFT is that no
data point ever moves both down and across the pipeline in one
time-step.

\section{Pipeline recipes}
\label{sec:recipes}
While the structure of the pipelined phase-rotation FFT is extremely
simple, experience has taught us that generating the appropriate
twiddles and shuffle indices from the matrix formulations of
(\ref{eqn:phase}) and (\ref{eqn:phasederivation}) is difficult and 
confusing.  To address this problem, we have developed a collection of
recipes for generating the phase-rotation twiddles and shuffle indices
off-line.  The recipes are defined for any 1D phase-rotation FFT of $N
= r^n$ points.  Following \cite{vanloan92}, they are written in a {\sc
Matlab}-like format.

As we saw in (\ref{eqn:phase}), the pipelined phase-rotation FFT
performs a typical ``twiddle, shuffle, kernel'' cycle at each stage.
Only the twiddles vary from stage to stage, and there is a
digit-reversing shuffle equivalent at the end.  To implement this FFT using
parallel $r \times s$ pipeline segments (one per stage), we insert the
$N$-vector of input data ${\bf x}$ into the pipeline as an $r \times
s$ array $X$: the first $r$ points of ${\bf x}$ go into the first
frame (column) $X$, the second $r$ points go into the second frame,
and so on.  We must also have a shuffle address and a twiddle factor
ready for each point in the pipeline.  In other words, we would like
to fill one $r \times s$ copy $A$ of the pipeline segment with
addresses, and another copy $D$ with twiddles.

Then the processors in each stage of the pipeline 
will know what to do at each time-step $t=0$:$s-1$. 
Using the current frame of addresses, 
they will fetch the current $r$-frame of data $X(0$:$r-1,A(0$:$r-1,t))$ and 
the current $r$-frame of twiddles $D(0$:$r-1,A(0$:$r-1,t))$ 
(pointwise in parallel), 
multiply these two frames pointwise, 
then do an $r$-point DFT ${\bf F}_r$ of the twiddled data frame.  
That is how each stage 
${\bf F} \overline{\overline{{\bf S}}}{\bf D}_{j}^{\prime}$ 
is implemented in the parallel pipeline. 

%% With this information in hand, the behavior of the processors that
%% execute each stage, 

The twiddle and shuffle recipes in this section are ``in place'' in
the sense that they work inside the $r \times s$ pipeline segments
that will contain the desired addresses and twiddles. (They are not
``in place'' in the usual sense, since we will freely use an input and an
output copy of a pipeline segment.)  This approach avoids constructing
and operating with large $N \times N$ matrices (each containing only
$N$ non-zero elements).  Each parallel-pipeline function recipe is
given a name similar to that of the $N \times N$ matrix factor in the
FFT (\ref{eqn:phase}) that it effectively implements.

\subsection{Shuffle recipes}
\label{sec:shufflerecipes}
As a convention, pipeline addresses (pipeline array row and column
indices) run 0:$r-1$ and 0:$s-1$, respectively.  To do
parallel-pipeline shuffles, we only need the horizontal (column)
addresses, since the data inside each pipe will only jump within that
stream (row).  The cross-stream shuffles, Cslow and Cfast, are
implemented using $\pi_{r}$ and its inverse, respectively. 
$\pi_{r}$ is a cyclic rotation of a frame (a vertical 
slice of the parallel pipeline) that has the effect of ${\bf y}_r =
{\bf C}_r{\bf x}_r$.  $\pi_{r}$ takes a column $r$-vector ${\bf x}_r =
(x_0, x_1, x_2, ..., x_{r-1})^T \mapsto {\bf y}_r = (x_{r-1}, x_0,
x_1, ..., x_{r-2})^T$.
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y$ = Cslow$( X )$ \\
\>    $col = 0$\\
\>    for $k = 1:r$\\
\>    \>  for $j = 1:r^{\prime}$\\
\>    \>    \>  $Y(:,col) = \pi_{r}^{k} (X(:,col))$\\
\>    \>    \>  $col = col + 1$\\
\>    \>  end \\
\>    end
\end{tabbing}       
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y$ = Cfast$( X )$ \\
\>    $col = 0$\\
\>    for $j = 1:r$\\
\>    \>  for $k = 1:r^{\prime}$\\
\>    \>    \>  $Y(:,col) = \pi_{r}^{-k} (X(:,col))$\\  %% -k for inv 3/8/94
\>    \>    \>  $col = col + 1$\\
\>    \>  end \\
\>    end
\end{tabbing}       
The inverses of Cslow and Cfast are formed simply by reversing
$\pi_{r}$ in the recipes above.  Next, we define some perfect shuffles.
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y$ = S$( X ) \;\;$ !stride by $s$\\
\>    $col = 0$\\
\>    for $row = 0:r-1$\\
\>    \>  for $k1 = 0:r:s-r$\\
\>    \>    \>  $k2 = k1+r-1$\\
\>    \>    \>  $Y(row,k1:k2) = X(:,col)$\\
\>    \>    \>  $col = col + 1$\\
\>    \>  end \\
\>    end
\end{tabbing}       
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y$ = S$^{-1}( X )\;\;$ !stride by $r$\\
\>    $col = 0$\\
\>    for $row = 0:r-1$\\
\>    \>  for $k1 = 0:r:s-r$\\
\>    \>    \>  $k2 = k1+r-1$\\
\>    \>    \>  $Y(:,col) = X(row,k1:k2)$\\
\>    \>    \>  $col = col + 1$\\
\>    \>  end \\
\>    end 
\end{tabbing}       
To implement the parallel-pipeline shuffles, 
$\overline{\overline{{\mbox{S}}}}$, 
$\overline{\overline{{\mbox{S}}}}^{-1}$, and 
$\overline{\overline{{\mbox{Q}}}}$, 
we will use the parallel-pipeline addresses $A$, which are 
computed by the following function:
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $A$ = 
           $\overline{\overline{\mbox{S}}}$\_addresses$(r,s)$ \\
\>    ${\bf a} = ( 0, r^{\prime}, ..., (r-1)r^{\prime})^T$  \> \> \>\\
\>    $col = 0$\\
\>    for $j = 1:r^{\prime}$\\
\>    \>  for $k = 1:r$\\
\>    \>    \>  $A(:,col) = {\bf a}$\\
\>    \>    \>  $col = col + 1$\\
\>    \>    \>  ${\bf a} = \pi_{r}({\bf a})$ \> \\
\>    \>  end \\
\>    \>  ${\bf a} = {\bf a} + {\bf 1}_{r}$ \\ %% \;\;\;(mod\;\;\; r)$ \> \>
\\
\>    end 
\end{tabbing}       
Looking closely, one can see Cfast$^{-1}$ at work producing the
addresses $A$ in the last function.  The addresses $A$ can also be
generated by loading a pipeline segment with simple $r \times r$
address blocks $B_{rr}$, and then applying Cfast$^{-1}$ to the
pipeline segment.  The first block to load is $B_{rr} =$
diag$(0$:$r^{\prime}$:$s-1)*{\bf 1}_{rr}$, where ${\bf 1}_{rr}$ is the
$r \times r$ matrix whose entries are all 1's.  The next block is

always $B_{rr} = B_{rr} + {\bf 1}_{rr}$, until the pipeline segment
contains $r^{\prime}$ blocks and is full.
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y = \overline{\overline{{\mbox{S}}}}( X )$ \\
\>    $A$ = $\overline{\overline{{\mbox{S}}}}$\_addresses$(r,s)$ \\
\>    for $row = 0:r-1$\\
\>    \>  $Y(row,:) = X(row,A(row,:))$ \\
\>    end 
\end{tabbing}       
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $Y = \overline{\overline{\mbox{S}}}^{-1}( X )$ \\
\>    $A$ = $\overline{\overline{{\mbox{S}}}}$\_addresses$(r,s)$ \\
\>    $[AA,I] =$ sort($A$)  \\
\>    for $row = 0:r-1$\\
\>    \>  $Y(row,:) = X(row,I(row,:))$ \\
\>    end 
\end{tabbing}       
In the above functions, sort($A$) sorts each row of an array $A$ in
ascending order. It returns the row-sorted array $AA$ and the
corresponding array of addresses $I$ where the successive row elements
were found in $A$.  After we have sorted the addresses $A$ for
$\overline{\overline{{\mbox{S}}}}$, $I$ has the addresses for
$\overline{\overline{\mbox{S}}}^{-1}$.

The pipeline addresses for $\overline{\overline{\mbox{Q}}}$ are
obtained by block-perfect shuffles (along the length of the pipeline)
of the addresses for $\overline{\overline{\mbox{S}}}$:
\begin{tabbing}
ttttabbb \=tab\=tab\=tab\=tab\=tab\=12345123451234512\= \kill
\>    {\bf function} $Y = \overline{\overline{\mbox{Q}}}( X, n )$ \\ 
\>    $A$ = $\overline{\overline{{\mbox{S}}}}$\_addresses$(r,s)$ \\
\\
\>    if $n > 2$ \\ 
\>    \>  for $ns = (n-2):-1:1 \;$ \\
%%                                 !perfect shuffle index exponent 
\>    \>    \>  $stride= r^ns$\\ 
\>    \>    \>  $block = r^{n-2-ns}\;\;\;$ ! block length \\ 
\>    \>    \>  $col2=0$\\ 
\>    \>    \>  for $k_1=1:stride$\\ 
\>    \>    \>  \> $col1 = (k_1-1)*block$\\ 
\>    \>    \>  \> for $k=1:r$\\  
\>    \>    \>  \> \> for $j=1:block$\\
\>    \>    \>  \> \> \> $B(:,col2)=A(:,col1)$\\
\>    \>    \>  \> \> \> $col1 = col1 + 1$\\
\>    \>    \>  \> \> \> $col2 = col2 + 1$\\
\>    \>    \>  \> \> end\\
\>    \>    \>  \> \> $col1 = col1 + (stride-1)*block$\\ 
\>    \>    \>  \> end\\
\>    \>    \>  end\\
\>    \>    \>  $A=B$\\
\>    \>  end\\
\>    end \\ 
\\
\>    for $row = 0:r-1$\\
\>    \>  $Y(row,:) = X(row,A(row,:))$ \\
\>    end  
\end{tabbing}       

\subsection{Twiddle recipes}
\label{sec:twiddlerecipes}
Every twiddle matrix ${\bf D}$ is diagonal, so it operates on a data
vector as a point-to-point vector multiply. Given some permutation
matrix ${\bf P}$, a new twiddle matrix ${\bf PDP}^T$ is equivalent to
a rediagonalizing of the vector shuffle of the diagonal of ${\bf D}$,
that is, ${\bf PDP}^T$ = diag$({\bf P}*$diag$({\bf D}))$.  (This is a
{\sc Matlab} notation: diag() puts the diagonal of a matrix in a
vector, and puts a vector in the diagonal of a matrix.)  Since we want
to perform shuffles within pipeline arrays, we reshape the twiddle
$N$-vector diag$({\bf D})$ as an $r \times s$ pipeline array $D$, just
as we originally reshaped the data vector.  Then we shuffle the
pipelined twiddles, to effect the equivalent of the vector shuffle
${\bf P}*$diag$({\bf D})$.  So we interpret the ${\bf PDP}^T$ operator
as an in-pipeline shuffle of the pipelined twiddles $D$, which are
then in position to operate on the pipelined data $X$ directly by
point-to-point multiplication, $Y = D.*X$. (As mentioned, the data will
actually be twiddled frame-by-frame in the pipelined implementation.)

We will interpret the twiddles expressed in (\ref{eqn:phasederivation}) this
way.  Each twiddle function below returns an $r \times s$ array $D$ of
twiddle factors (the actual twiddling of the data is not included):
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $D_{slow}$ = Dslow\_twiddles$( r, s )$ \\ 
\>    $\omega_{j} = exp(-2\pi i /r)$\\ 
\>    $t = 0$\\ 
\>    for $j = 0:(r-1)$\\
\>    \>  for $k = 0:(r^{\prime}-1)$\\
\>    \>    \>  $D_{slow}(:,t) = 
      (1, \omega_r^k, \omega_r^{2k}, ..., \omega_r^{(r-1)k})^T$ \\ 
\>    \>    \>  $t = t + 1$\\
\>    \>  end \\
\>    end 
\end{tabbing}       
\begin{tabbing}
ttttabbb \=tab\=tabbb \=tabbb1234512345123451234512\= \kill
\>    {\bf function} $D_{fast}$ = Dfast\_twiddles$( r, s )$ \\ 
\>    $\omega_{j} = exp(-2\pi i /r)$\\ 
\>    $t = 0$\\ 
\>    for $k = 0:(r^{\prime}-1)$\\
\>    \>  for $j = 0:(r-1)$\\
\>    \>    \>  $D_{fast}(:,t) = 
      (1, \omega_r^j, \omega_r^{2j}, ..., \omega_r^{(r-1)j})^T$ \\ 
\>    \>    \>  $t = t + 1$\\
\>    \>  end \\
\>    end 
\end{tabbing}       
The inverses of $D_{slow}$ and $D_{fast}$ are just their complex
conjugates, and are generated simply by replacing $\omega_{j}$ by
$\omega_{j}^{-1}$.
For stages $j = 1$:$n$ (counted down from $n$), we generate pipelined 
twiddles $\tilde{T}_j$ by 
\begin{tabbing}
ttttabbb \=tab\=tab\=tab\=1234512345123451234512\= \kill
\>    {\bf function} $\tilde{T}_j$ = 
                     $\tilde{\mbox{T}}$\_twiddles$( r, s, j )$ \\ 
\>    $\omega_{j} = exp(2\pi i /r^{j+1})$\\ 
\>    $\omega_{j}^{\prime} = \omega_{r^{j+1}}^r$\\ 
\>    for $k = 0:(r-1) \;\;$ ! direct sum loop\\ 
\>    \>  $t_1 = k \cdot r^{j-1}$\\ 
\>    \>  for $p = 0:(r-1)$\\ 
\>    \>    \>  $\tilde{T}_j(p,t_1) = \omega_{j}^{kp} $\\ 
\>    \>  end \\ 
\>    \>  $t_1 = t_1 + 1$\\ 
\>    \>  $t_2 = t_1 + r^{j-1}$\\ 
\>    \>  for $t = t_1:t_2\;\;$ ! fill next column from last \\ 
\>    \>    \>  $\tilde{T}_j(:,t) = \omega_{j}^{\prime k} \cdot 
                 \tilde{T}_j(:,t-1)$ \\ 
\>    \>  end \\ 
\>    end\\ 
\\
\>   if $j < n$ \\
\>    \>    $t_2 = r^j$\\
\>    \>    for $k = 0:(N/r^{j+1}) \;\;$ \\
\>    \>    \>  $t_1 = t_2$\\
\>    \>    \>  $t_2 = k \cdot r^j$\\
\>    \>    \>  $t = 0$\\
\>    \>    \>  for $t_0 = t_1:t_2$\\ 
\>    \>    \>    \>$\tilde{T}_j(:,t_0) = \tilde{T}_j(:,t)\;\;$ ! copy
columns\\ 
\>    \>    \>    \>$t = t + 1$\\ 
\>    \>    \>  end \\ 
\>    \>    end\\ 
\>    end 
\end{tabbing}       
The rest of the twiddle arrays can now be defined in terms of the
shuffles:
\begin{tabbing}
ttttabbb \=tab\=tabbbb\=tabbb \=tabbb1234512345123451234512\= \kill
\>    $D_{slow}^{\prime}$ \> \> = S$^{-1}( D_{slow}^{-1} )$ \\
\>    $D_{slow}^{\prime \prime}$ \> \> = Cslow$( D_{slow}^{\prime} )$ \\
\\
\>    $D_{fast}^{\prime}$ \> \> =  Cslow$( D_{fast}^{-1} )$ \\
\\
\>    $T_j$ \> \> = S$^{-1}( \tilde{T}_j )$ \\
\>    $T_j^{\prime}$ \> \> = Cslow$( T_j )$ \\
\\
\>    $D_1^{\prime}$ \> = 
           $\overline{\overline{\mbox{S}}}(D_{slow}^{-1}) 
                                  .* T_1^{\prime}.*D_{fast}^{-1}$\\
\>    if $1<j<n$\\
\>    \> $D_j^{\prime}$ \> = 
         $D_{slow}^{\prime \prime}.* T_j^{\prime}.*D_{fast}^{-1}$\\ 
\>    end \\ 
\>    $D_n^{\prime}$ \> = $D_{slow}^{\prime \prime}$ 
\end{tabbing}       

\section{Implementation issues} 
\label{sec:implementation}
In this section we describe issues that arise when the phase-rotation
FFT is implemented on a real parallel system.  In particular, we
describe implementation approaches for the radix-2 FFT on the iWarp
system. The main result is a scalable implementation of the pipelined
phase-rotation FFT that runs at the full 40 Mbytes/second rate of the
iWarp physical links.

\subsection{iWarp}
The iWarp is a private-memory multicomputer developed jointly by Intel
and Carnegie Mellon~\cite{iwarp}.  iWarp systems are 2-dimensional
tori of {\em nodes}, ranging in size from 4 to 1024 nodes. Each node
consists of an iWarp {\em component}, up to 16 Mbytes of off-chip
local memory, and a set of 8 unidirectional communication {\em links}
that physically connect the node to four neighboring nodes.  Each
component is a VLSI chip that contains a {\em processing agent} and a
{\em communication agent}. The processing agent is a general-purpose
load-store microprocessor that runs at a maximum rate of 20 MFLOPs.
Thus, a {\em clock}, or cycle time, is 50 ns.  The local memory is
accessed at a rate of 160 Mbytes/sec.  Each link runs at 40
Mbytes/sec, for a maximum aggregate bandwidth of 320 Mbytes/sec per
node.

The key feature of iWarp is its communication system, which is
summarized in Figure~\ref{fig:pathways}.  Each communication agent
contains a set of 20 hardware FIFO {\em queues}. Each queue can hold
up to 8 32-bit words, and can be accessed by user programs at the cost
of a register access. iWarp nodes communicate with other nodes using
unidirectional point-to-point structures called {\em pathways}. Each
pathway is a sequence of queues. Pathways can be created and destroyed
dynamically at runtime.  Data traveling along a pathway passes from
queue to queue {\em automatically}, without disturbing the
computations on intermediate nodes.  Multiple pathways can share the
same link by multiplexing in a round-robin fashion, one word at a
time. If each pathway has data to send, they are guaranteed a
proportional fraction of the link bandwidth. If only one pathway has
data to send, then it gets all of the link bandwidth.
\begin{figure}
%\epsfxsize=3.25in
\centerline{\epsfbox{pathways.eps}}
\caption{iWarp communication concepts.}
\label{fig:pathways}
\end{figure}

\subsection{Mapping strategies on iWarp}
The problem is to develop a mapping of the flowgraph in
Figure~\ref{fig:phase}(d) to an iWarp array.  The simplest mapping
strategy is to assign each flowgraph node to a unique processor node
of a linear array, route the flowgraph arcs through this array, and
then embed the resulting linear array in the iWarp torus. This
approach, called the PHASE5 mapping because it uses 5 iWarp nodes for
each FFT stage, is shown in Figure~\ref{fig:mappings}(a).

Each iWarp node in PHASE5 executes a small {\em node program} that
implements its flowgraph operator. Each twiddle node ($D^\prime$)
repeatedly reads a complex number from its input pathway 
multiplies it by the appropriate twiddle (precomputed off-line
using the recipes in Section~\ref{sec:twiddlerecipes}), and sends the
result to its output pathway.  Each shuffle
operator ($\overline{\overline{S}}$) repeatedly reads a complex data
item from its input pathway, stores it in memory, and uses the
appropriate shuffle index (again precomputed off-line using the
recipes in Section~\ref{sec:shufflerecipes}) to send an appropriate
double-buffered data point to the output pathway. The kernel node
($F$) repeatedly reads two complex numbers from its input pathways,
performs the radix-2 DFT kernel operation, and outputs two complex
numbers to its output pathways.

\begin{figure}
\epsfxsize=3.25in
\centerline{\epsfbox{mappings.eps}}
\caption{Strategies for mapping one stage of the FFT onto a linear array.
\rm{(a) PHASE5 mapping. (b) PHASE3 mapping.}}
\label{fig:mappings}
\end{figure}

Another approach, the PHASE3 mapping, combines the twiddle and shuffle
operators on a single node, as shown in Figure~\ref{fig:mappings}(b),
so that each stage requires 3 nodes instead of 5 nodes.  As we shall
see, the communication and computation throughputs of the two mappings
are identical.  The advantage of the PHASE3 mapping is that it is more
node-efficient, requiring fewer nodes per stage than the PHASE5
mapping.  The advantage of the PHASE5 mapping is its simplicity. Each
node is assigned exactly one operator from the flowgraph.

Figure~\ref{fig:phasenet} shows a working implementation of a
16K-point radix-2 phase-rotation FFT on a 64-node iWarp array at
Carnegie Mellon.  The implementation is based on the PHASE3 mapping
from Figure~\ref{fig:mappings}(b).  The large squares are iWarp nodes,
labeled with the corresponding operator and stage number, where $D$ is
a twiddle/shuffle pair and $F$ is a kernel.  The small squares are
queues.  The arrows are iWarp pathways. As an artifact of our display
program intermediate queues are not drawn. Each of the 14 FFT stages
uses 3 nodes, with an additional 3 nodes for the parallel-pipeline
digit-reversing step at the end.

\subsection{Performance}
Each iteration of each node program in the PHASE3 and PHASE5 mappings
runs in at most 8 clocks. At the peak rate of 40 Mbytes/sec, each link
can produce and consume a 32-bit floating-point number every 2 clocks.
Further, each data point in the pipeline is a complex number
consisting of a pair of 32-bit floating-point words. As a result, each
pathway consumes exactly half of the available link bandwidth.  Since
each link is shared by two pathways, and since the iWarp communication
agent gives each pathway an equal share of the link bandwidth, without
disturbing the computations on intermediate nodes, each link is fully
utilized.  The result is a radix-2 FFT that runs at the full 40
Mbytes/sec rate of an iWarp link, regardless of the number of points
in the FFT! Since each sample consists of 8 bytes, the FFT runs at a
constant rate of $5~ \mbox{Msamples/sec}.$ Given a sufficient number
of nodes, the iWarp phase-rotation FFT's will produce arbitrarily
large FFT's at this rate.  Perhaps even more important, the
performance is the same on smaller FFT's.

\begin{figure}
\epsfxsize=3.25in
\centerline{\epsfbox{phasenet.eps}}
\caption{16K-point pipelined phase-rotation FFT running at 40 Mbytes/sec
(350 MFLOPS) on iWarp}
\label{fig:phasenet}
\end{figure}

Another way to characterize performance is by computational
throughput, expressed as millions of floating-point operations per
second (MFLOPS). However, there is a subtlety involved in using MFLOPS
as a performance measure. The iWarp phase-rotation FFT performs 16
floating-point operations per iteration per stage (2 adds and 4
multiplies by each twiddle operator, and 4 adds by the kernel
operator).  But the standard formula for computing FFT MFLOPS is $5N
\log N$ floating-point operations per N-point FFT~\cite{carlson92},
which implies 10 floating-point operations per iteration per stage.
Therefore, the phase rotation FFT trades off ease of pipelining for
number of floating point operations.  To make a fair comparison with
other FFT algorithms, we must compute the phase rotation performance
using the standard of 10 floating-point operations per iteration per
stage, even though the phase-rotation FFT is actually performing 16
floating-point operations per iteration per stage.

Since each node program executes its computation in at most 8 clocks,
and since each clock is $50$ ns, each stage of the iWarp
phase-rotation FFT runs at a rate of $25~\mbox{MFLOPS}$ for an
aggregate performance over all $\log N$ stages of $25 \log N~
\mbox{MFLOPS}$.  For example, the 16K-point FFT in
Figure~\ref{fig:phasenet} achieves a measured performance of $25
\times 14 = 350$ MFLOPS (single precision) on the iWarp systems at CMU. 
By comparison, a highly optimized 16K-point FFT has been measured at
237 MFLOPS (double precision) on a single-processor Cray
Y-MP~\cite[p.114]{carlson92}.  The numbers are not directly comparable
because of the different floating-point precisions, but they do
suggest that the absolute performance of the phase-rotation FFT is
quite good.

\section{Concluding remarks}
We have described an improved version of the Whelchel pipelined
phase-rotation FFT, developed recipes for generating the appropriate
twiddles and shuffle indices off-line and directly in terms of the
parallel pipeline, outlined mapping approaches for the radix-2 case on
the iWarp parallel computer, and presented measured performance
results of an implementation on iWarp.

The improvement on the original phase-rotation FFT is significant in
that it eliminates a potential pipeline bottleneck during the digit
reversing step at the end.  The twiddle and shuffle recipes should be
helpful to the programmer who wants to implement the pipelined phase
rotation FFT. The iWarp implementation validates a simple and
realistic approach for building scalable pipelined FFT's on a
programmable parallel system. Further, the implementation demonstrates
that, given a balanced parallel computer architecture with word-level
access to the communication links, it is possible to build FFT's that
run at the full link bandwidth of the links, even when the FFT's are
relatively small.

Other parallel systems are being considered as targets for the
multidimensional phase-rotation FFT. For example, the Maspar MP2
provides indirect addressing and routing capabilities, which would
facilitate fetching data into and out of the kernel FFTs and
performing data communication with large kernels.  As another example,
the Cray T3D multicomputer, like iWarp, provides direct, low-latency,
word-level access to the communication system, which would support the
fine grained parallelism found in the phase-rotation FFT.

\section*{Acknowledgements}
We would like to thank Tom Warfel, LeeAnn Tzeng, Doug Noll, and Doug
Smith their help and suggestions.

\small
\bibliography{/afs/cs/project/iwarp/member/droh/bib/compiler,/afs/cs/project/iwarp/member/droh/bib/defs,/afs/cs/project/iwarp/member/droh/bib/me,/afs/cs/project/iwarp/member/droh/bib/refs}

\end{document}

    
    
    

