\Section{Performance tuning on Monsoon}
\label{Section:id-performance}

\begin{fig}{figure:ip3d}{3D inner product written in Id, outer two
loops $k$-bounded, inner loop sequential.  {\tt imax}, {\tt jmax}, and {\tt
kmax} are compile-time constants.}
\begin{center}
\begin{minipage}{2.8in}
\footnotesize
\begin{verbatim}
def ip_3d a b = 
  { s = 0.0 ;
   in
     {for i <- 1 to imax BOUND ib do
        s_jk = 0.0;
        next s = s + 
         {for j <- 1 to jmax BOUND jb do
            s_k = 0.0;
            next s_jk = s_jk +
             {for k <- 1 to kmax do
                next s_k = 
                 s_k + a[i,j,k]*b[i,j,k];
                finally s_k};
            finally s_jk};
      finally s} };
\end{verbatim}
\end{minipage}
\end{center}
\end{fig}

The performance of Id on Monsoon is largely determined by two factors:
\begin{itemize}
\item The {\it total number of instructions} executed, which determines the
amount of computation and communication necessary.
\item The {\it CPU utilization}, which is affected by the loop bounds and
the frame allocation policy.  Idle cycles are caused by lack of
parallelism, load imbalance, and some hardware ``hazards''.
\end{itemize}
To the first order, the number of instructions executed depends only on the
program and its pragmas, and not the machine configuration -- i.e.~the same
program will execute about the same total number of instructions for a 1-
or 8-processor Monsoon.  CPU utilization does depend on the machine
configuration and attaining high CPU utilization requires setting the loop
bounds and in some cases, source code modification.

Id provides pragmas for inlining functions, unrolling loops, or declaring
loops to be sequential or $k$-bounded, all of which can have a dramatic
impact on the instruction count.  Id users almost always inline ({\tt
defsubst}) small, non-recursive functions.  In the following Sections, we
describe how these other pragmas and program modifications can be used to
tune PCG.

We will illustrate how to tune nested loops for performance using the
three-dimensional inner product function {\tt ip\_3d} shown in Figure
\ref{figure:ip3d}.  The outer and middle loops are annotated to be
$k$-bounded, and $k$-bounds are {\tt ib} and {\tt jb}, respectively.
Figure \ref{figure:loop-frames} shows the pattern of frame usage for the
$k$-bounded loops for this code when {\tt ib} is 3 and {\tt jb} is 4.

\SubSection{Choosing loop schemas}

\begin{fig}{figure:loop-frames}{Pattern of frame usage for nested
$k$-bounded loops for the 3D inner product.}
\illustrationx{3in}{figures/loop-frames.eps}
\end{fig}

Consider three different cases for implementing the innermost loop:
$k$-bounded, sequential, and completely unrolled.  Given the same loop
body, these three implementations of the same loop will require a
significantly different number of instructions to execute per iteration.

\paragraph*{Loop schema cycle counts.}

A completely unrolled loop is most efficient implementation of a dataflow
loop.  Complete unrolling is done by inserting the pragma {\tt @unfold
completely} inside the innermost loop.  This is possible only if the number
of iterations a loop executes is fixed and known at compile time.

\begin{fig}{figure:loop-cycle-counts}{Completely unrolled loops require the
minimal cycles per iteration.  Sequential and $k$-bounded implementations
of the same loop require more cycles.  In parentheses are the number of
bubbles incurred by each operation per iteration.}
\begin{center}
\small
\begin{tabular}{|l|rrr|}
\hline
\multicolumn{4}{|c|}{\bf Cycles/iteration of {\tt 3d\_ip} inner loop} \\
\hline
           & completely &            &           \\
{\bf Opcode} & unrolled & sequential & k-bounded \\
\hline
fork         &        2 &         3 &        6  \\
intplus      &        2 &         2 &        2  \\
i-fetch      &        2 &         2 &        3  \\
floattimes   &    2 (1) &     2 (1) &    2 (1)  \\
floatplus    &   1 (.5) &    1 (.5) &    2 (1)  \\
\hline
switch       &          &     4 (2) &        1  \\
intle        &          &         1 &        1  \\
\hline
message      &          &           &    4 (2)  \\
i-take       &          &           &        1  \\
i-put        &          &           &    2 (1)  \\
sync         &          &           &    3 (1)  \\
\hline
{\bf Total}  &  9 (1.5) &  15 (3.5) &   27 (6)  \\
\hline
\end{tabular}
\end{center}
\end{fig}

Figure \ref{figure:loop-cycle-counts} shows the differences in the cycle
counts for one iteration of three implementations of the inner loop of {\tt
ip\_3d}.  Figure \ref{figure:dataflow} is the loop body for the sequential
version of the inner loop of {\tt ip\_3d}.  There are two circulating or
induction variables in the loop: the running sum (called ``input 0'' in
Figure \ref{figure:dataflow}), which is a floating point value and the
index variable (called ``input 1'' in Figure \ref{figure:dataflow}), which
is either {\tt k} or a linear offset from {\tt k}.  The i-fetch instruction
is not associative with addition, so the base of the array and an integer
offset are necessary to perform a memory reference.

The completely unrolled version uses the minimum number of instructions to
implement one iteration of the inner loop -- the two fork instructions are
used to distribute the index {\tt k} to each intplus, which feeds the
i-fetch instructions.  The intplus instructions cannot be eliminated
because the i-fetch is not associative with addition.  The values returned
from the i-fetch are multiplied together, also incurring a bubble.  The
result of the multiplication is added to the running sum, and only half of
the cost of the addition is incurred by each additional iteration,
including half of the bubble.  There is no loop test in the completely
unrolled version.

The sequential implementation of the loop uses two switches to steer the
two induction variables around the loop, and each switch incurs a bubble.
An additional loop test ({\it intle}) is also performed, and an additional
fork is necessary to feed the loop test.

The $k$-bounded implementation of the loop uses two message instructions to
send the induction variables to the next iteration and associated frame.
The i-take and i-put instructions are used as semaphores to synchronize
between loop iterations to assure when a frame may be reused for a new
iteration.  The sync instructions gather signals from work being performed
in the current iteration to insure that all work is completed in the
current iteration.  Additional fork instructions are used to distribute
values to the new instructions.

Some traditional loop optimizations for conventional processors introduce
new induction variables.  For dataflow loops, such optimizations may
actually decrease performance even if fewer instructions are executed in
the loop body, because of additional switch and fork overheads, or from
additional overheads from message-passing for $k$-bounded loops.

\paragraph*{Loop startup and shutdown costs.}

In addition to the per iteration costs, loops have startup and shutdown
costs which may be significant, depending upon the loop schema.  Completely
unrolled loops have the minimum amount of startup cost -- the storing of
loop constants into the frame will be lifted to the next outer loop level
or else transformed into forks.  For sequential loops, constants must be
stored into the frame before the loop executes, and then extracted from the
frame after they are executed.  $k$-bounded loops incur the highest startup
and shutdown costs.  At startup for a $k$-bounded loop, $k$ frames are
allocated and then pointers are set in each frame to point to the previous
and next frame.  Loop constants are stored into each frame, and at
shutdown, the loop constants must be extracted and the frames deallocated.
Allocating and deallocating a frame takes about 60-70 cycles.  The
startup/shutdown cost of a $k$-bounded loop can be from about 100 to
several hundred cycles per $k$, depending on the number of loop constants.

Nesting of loops can exacerbate the number of loop constants which must be
stored and extracted.  A loop constant in an inner loop becomes a loop
constant for every loop nesting out to the loop which may change the value
of the loop constant.  Therefore, that constant must be stored and
extracted even though its value may not change between stores and
extractions if the middle loop does not change the value of the loop
constant.

Loop startup overhead can have a significant effect on performance when the
number of loop iterations is few.  In those cases, complete unrolling
should be considered when possible, even if slight algorithmic
restructuring is necessary.

\SubSection{Loop striding}

In vector and cache-based machines, the loop stride over array elements can
have a significant effect on performance because of memory interleaving,
cache associativity or line size.  For slightly different reasons, loop
stride makes a difference in Id also.  For example, in Id there is a
significant advantage in having an inner loop which has a constant stride
known at compile-time.  Because array extents are not known at compile
time, the innermost loop should iterate over the stride-1 dimension of the
array so that the compiler knows the stride of the loop at compile time.
If the compiler doesn't know the stride at compile-time, the stride becomes
a loop constant, which is more expensive than a literal.

For the completely unrolled case of {\tt ip\_3d}, if the array is not
aligned with the loop along the stride-1 dimension, an additional 6 cycles
per iteration are necessary because of two additional multiplications and
two additional loop constant-store instructions to save the loop constants
into the frame.  If we didn't know the array extents at compile-time, but
did know that the arrays were of the same extents, then only one additional
multiplication and constant-store would be necessary per iteration.

Loop interchange is the standard optimization to achieve loop/array stride
alignment \cite{Wolfe95}.  This optimization is not implemented in the Id
compiler: for this study, we performed this optimization by hand by making
certain that the innermost loop iterated over the 1-stride dimension of the
arrays.

\SubSection{Choosing $k$ for $k$-bounded loops}

In a triply nested loop such as {\tt ip\_3d}, suppose that the $k$-bound
for the outermost bounded loop is $ib$ and for the middle bounded loop is
$jb$.  The amount of interprocessor parallelism exposed is then on the
order of $ib \times jb$.  Given a certain machine configuration, we are
interested in setting the product $ib \times jb$ such that it will keep the
entire machine busy.  What are the optimal values of $ib$ and $jb$, such
that the number of instructions executed by the loops are minimized?

If there are $imax$ iterations of the outer loop executed, then the number
of frame allocations and initializations (requiring hundreds of cycles
apiece) is then: $ib + imax \times jb$.  For a set amount of parallelism
$ib \times jb$ we wish to exploit in a nested loop, in general it is better
to make $ib$ larger and $jb$ smaller to minimize loop initialization costs.
A possible optimization is to lift middle loop frame allocations so that it
occurs $ib$ times as opposed to $imax$ times.  The optimization has been
implemented, but has not worked reliably.

Large values of $k$ may not be useful if there are dependencies of any kind
(data, control, producer/consumer) between loop iterations, or if the
number of iterations is not significantly larger than $k$.  Choosing loop
bounds can make a tremendous difference in performance, as shown by Culler
\cite{Culler90}, but to date, no automatic compiler-directed policy has
been implemented which achieves high performance.

\SubSection{Other loop optimizations}

Partial loop unrolling (as opposed to complete unrolling) is effective for
loops which execute many iterations -- the loop body is increased while the
number of iterations is decreased, therefore amortizing loop overheads.
However, for loops which may execute a few iterations, unrolling may
decrease performance because of additional conditionals which are used to
determine if a loop has enough iterations left to execute a unrolled
version or a standard version.

%Conditionals in dataflow execution suffer
%from the same problems that loops do -- each free variable in the union of
%the conditional branches requires switches and forks, and nesting of
%conditionals and loops exacerbates this problem.

Strip mining is a useful optimization for high-overhead $k$-bounded loops.
To strip mine a loop, the iterations of a $k$-bounded loops are divided in
a block or interleaved fashion into pieces of work which are performed by
more efficient sequential loops.

Because dataflow execution allows for dynamic instruction-level
parallelism, dataflow loops may incur additional synchronization costs to
determine termination of an iteration.  In some cases, a certain loop
iteration must terminate before another iteration is initiated -- for
sequential loops, the two consecutive iterations may be sharing the same
synchronization space (i.e.\ the frame) or for $k$-bounded loops, an
iteration may not start before the frame $k$ iterations before is complete.
Because the parallelism is so fine-grained, additional sync instructions
may be inserted to determine when an iteration is complete.  Sometimes, the
inherent structure of the loop body performs much or all of the
synchronization, in which case redundant sync instructions may be removed
\cite{boon-loops}.

Finally, Ang ~\cite{boon-loops} has described a sequential loop schema for
Monsoon which is frame-based rather than switch-based, and which performs
better for a variety of applications.
