\section{The phased AAPC architecture}
\label{opt-aapc-sect}

Since the AAPC step is communication-limited, one can calculate an
upper limit on performance by looking at network limitations. The
performance estimates in this section assume a $n \times n$ torus
connected machine with a system clock of $S$ MHz that can transmit a 4
byte word in $T_t$ cycles. We also assume that all processors exchange
messages of $B$ words.  This system has $4 n^2$ links that can each
transmit one word every $T_t$ cycles.  In the case of best
performance, all messages follow a shortest path and all physical
links are busy, so on average each message will cross $n / 2$ physical
links.  The words that make up the $n^4$ messages of length $B$ will
traverse $n^5 B / 2$ physical links during the AAPC, and all $4 n^2$
links of the torus can be used simultaneously.  Thus, the best case
time to completion is $\frac{(n^5B/2) T_t}{4 n^2} = (n^3 B T_t)/8$
cycles.  The peak aggregate bandwidth is then
\begin{equation}
 Agg_{system} = \frac{S \times {\rm Total\ bytes\ sent}}{\frac{n^3 B T_t}{8}} =
\frac{4 B n^4 S}{\frac{n^3 B T_t}{8}} = \frac{32 n S}{T_t} 
\label{system-eqn}
\end{equation}
In this section, we
present an AAPC schedule and mechanism that approaches this physical
limit.



