\section{Alternative implementations of AAPC}
\label{other-sect}

There are many characteristics one can use to catagorize AAPC methods.
One division is between {\em informed} and {\em uninformed} methods.
Informed methods such as the direct AAPC algorithm described in
Section~\ref{opt-aapc-sect} use compile time information about the
structure of the communication to aid in developing good routing and
scheduling information. 

Message passing can be used to implement an uninformed communication
step. Uninformed algorithms are for more adaptable and may be the only
alternative if no compile time information is available. However, with
dense communication steps uninformed methods tend to have problems
with hot spots and congestion. In \cite{val82}, Valiant proves that
uninformed or oblivious routing can statistically avoid these hot
spots by first routing to a random location and then routing to the
final destination. On average this will double the message route
length, so this approach will at best get within half of the optimal
network usage for AAPC.

Run time adaptive routing methods have been proposed and studied as a
means to avoid hot spots. However, today's generation of distributed
memory machines do not incorporate adaptive routing, so the value of
adaptive routing algorithms can not be evaluated. However, it seems
unlikely that the local view available to an adaptive router is
sufficient to avoid all hot spots that can occur in an AAPC.

Another division of AAPC algorithms is between algorithms that utilize
wormhole routing and those that only rely on store and forward.
The direct AAPC algorithm requires a wormhole router to support
sending messages directly between processors that are not physically 
adjacent.

The algorithm proposed in~\cite{var92} only requires a very simple
network interface that supports communication between physically
adjacent processors. In this algorithm, all processors communicate to
the same set of relative processors. To send to relative processor
(x,y) takes $|x| + |y|$ steps. In the first $|x|$ steps all processors
send and receive data along the X axis, and in the last $|y|$ steps
all processors send and receive along the Y axis. By communicating to
relative destinations simultaneously, this algorithm will utillize all
of the machine's network bandwidth. However, this requires a machine
that has twice the memory bandwidth as network bandwidth. This is not
the case with iWarp and many other distributed machines are far more
balanced.  iWarp can only support two simultaneous relative
destinations, so this algorithm will at best reach half of iWarp's
peak aggregate network bandwidth.

Finally, AAPC algorithms differ by whether data is sent directly
to the final destination or not. The direct AAPC algorithm sends each
message directly to its final destination. This algorithm requires
$N^2$ message start ups and sends messages of size $B$.

In other algorithms, the processor sends several blocks of data
destined for different processors in one message. Generally, these
blocks of data are destined for the same dimension or area of the
machine. While a block of data may be sent to several intermediate
processors, the size of each message is larger and the actual number
of message start ups is smaller.

Several of these multistep algorithms for a mesh are described
in~\cite{bokhari92}. Here is one simple two step algorithm for a torus
First it performs an AAPC along the rows to arrange all the data in
its target column. Then it performs an AAPC along the columns to move
all the data to its target row. This algorithm needs only $2 \sqrt N$
steps message startup and moves blocks of size $\sqrt N B$. The larger
blocks better amortize the cost of the message start up, but this algorithm
requires more buffer management and only uses half of the network
bandwidth. 

If message start up is very expensive, the multistep algorithm is a
good approach. However, the trend for newer distributed memory
machines is to lower the message start up time through user level
access to the network and among other techniques.








