\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 bandwidth limitations. The
performance estimates in this section assume a $n \times n$ torus
connected machine and assume that all processors exchange messages of
$B$ bytes.  This system has $4 n^2$ links that can each transmit one
$f$ byte flit every $T_t$ microseconds.  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.  $n^4$ messages of length $B$ will be exchanged over the
system. The flits of all the messages will traverse $n^5 B/(2 f)$
physical links during the AAPC, and in the best case all $4 n^2$ links
of the torus can be used simultaneously.  Thus, the best case time to
completion is $\frac{(n^5B/(2f)) T_t}{4 n^2} = (n^3 B T_t)/(8 f)$
microseconds.  The peak aggregate bandwidth is then
\begin{equation}
 Agg_{system} = \frac{{\rm Total\ bytes\ sent}}{{\rm AAPC\ Time}} = 
\frac{B n^4}{\frac{n^3 B T_t}{8 f}} = \frac{8 f n}{T_t} 
\label{system-eqn}
\end{equation}
In this section, we present a message schedule and AAPC mechanism that
asymptotically matches the physical performance limit for
two-dimensional tori.



