% Section on example program (DAXPY)

\section{An example: DAXPY}

\label{sec-daxpy}

DAXPY is the inner loop of the Linpack benchmark:
\beginid
    for i = 1 to N do
        Y[i] = a * X[i] + Y[i]
\endid
We assume that the current frame (context) contains the following
data, with symbolic names for the frame slots shown at left (in the
codes below, the {\cf dFP} and {\cf sFP} registers point at this
frame):

\begin{quote}\cf
\begin{tabular}{r|l|}
\cline{2-2}
            & ... \\
\cline{2-2}
N     & Loop trip \\
\cline{2-2}
XP    & {\em pointer to\/} X[1] \\
\cline{2-2}
YP    & {\em pointer to\/} Y[1] \\
\cline{2-2}
A     & {\em loop constant\/} A \\
\cline{2-2}
YLim  & {\em pointer to\/} Y[N] \\
\cline{2-2}
            & ... \\
\cline{2-2}
\end{tabular}
\end{quote}

\subsection{Uniprocessor Code}

Uniprocessor {\archname} code for the DAXPY loop is shown below (in a
uniprocessor, there is only local memory, which contains arrays
{\cf X} and {\cf Y}).  We use names beginning with ``{\cf r}'' as
symbolic names for general purpose registers. For clarity, the loop
has not been unrolled (a compiler would typically do this).

\beginid
  load  rXP, dFP[XP]     -- {\em load ptr to \/} X
  load  rYP, dFP[YP]     -- {\em load ptr to \/} Y
  load  rA,  dFP[A]      -- {\em load loop const:\/} a
  load  rYlim, dFP[YLim] -- {\em load loop const:\/} Y {\em ptr limit}
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jgt   rB, OUT          -- {\em zero-trip loop if greater\/}
\null
LOOP:
  load  rXI, rXP         -- X[i] {\em into\/} rXI  {\bf (L1)}
  load  rYI, rYP         -- Y[i] {\em into\/} rYI  {\bf (L2)}
  add   rXP,rXP,8        -- {\em incr ptr to\/} X
  fmul  rTmp,rA,rXI      -- a*X[i]
  fadd  rTmp,rTmp,rYI    -- a*X[i] + Y[i]
  store rYP, rTmp        -- {\em store into\/} Y[i]  {\bf (S1)}
  add   rYP,rYP,8        -- {\em incr ptr to\/} Y
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jle   rB, LOOP         -- {\em fall out of loop if greater\/}
\null
OUT:
  {\em ... loop sequel ...\/}
\endid
The code runs entirely within the Data Processor (in a uniprocessor,
{\sc sP} plays no role).

\subsection{Multiprocessor Code: Using {\tt rload}s to Mask Latency}

Suppose {\cf X[I]} and {\cf Y[I]} are on remote nodes of a
multiprocessor.  The two loads {\bf (L1)} and {\bf (L2)} need to be
changed to remote loads.  We will issue {\cf rload}s to initiate the
movement of {\cf X[i]} and {\cf Y[i]} into the local frame, and we
will free up the processor to do other work.  Each response arrives at
{\sc sP}, deposits the value into the frame, and tries to join with
the other response at frame location {\cf c1}.  When the join
succeeds, {\sc sP} enables the thread in the Data Processor that
computes with these data, executes an {\cf rstore} and continues to
the next iteration.

When the loop completes, it gives up the Data Processor by executing a
{\cf next} instruction.  Meanwhile, the {\cf rstore} acknowledgments
all arrive at {\sc sP} and join at frame
location {\cf c2}.  The continuation of this join is the loop
sequel; the sequel executes only after all {\cf rstore}s have
completed.  Here is the augmented frame layout and the new code (it is
easier to start reading the code at the Data Processor section):
\begin{quote}\cf
\begin{tabular}{r|l|}
\cline{2-2}
            & ... \\
\cline{2-2}
N     & Loop trip \\
\cline{2-2}
XP    & {\em pointer to\/} X[1] \\
\cline{2-2}
YP    & {\em pointer to\/} Y[1] \\
\cline{2-2}
A     & {\em loop constant\/} A \\
\cline{2-2}
YLim  & {\em pointer to\/} Y[N] \\
\cline{2-2}
XI    & {\em copy of\/} X[I] \\
\cline{2-2}
YI    & {\em copy of\/} Y[I] \\
\cline{2-2}
c1    & {\em join counter for\/} rloads \\
\cline{2-2}
c2    & {\em join counter for\/} rstores \\
\cline{2-2}
            & ... \\
\cline{2-2}
\end{tabular}
\end{quote}


\beginid
;;
;; {\em Synchronization Processor Message Handlers}
;;
L1$_S$:
  store sFP[XI],   rV1   -- {\em store away incoming } X[I]
  join  c1, 2, CONTINUE$_D$ -- {\em attempt continuation of loop}
  next                   -- {\em next message}
\null
L2$_S$:
  store sFP[YI],   rV1   -- {\em store away incoming } Y[I]
  join  c1, 2, CONTINUE$_D$ -- {\em attempt continuation of loop}
  next                   -- {\em next message}
\null
S1$_S$:
  load  rN, sFP[N]       -- {\em total number of stores}
  join  c2, rN, OUT$_D$     -- {\em sequel when all stores complete}
;;
;; {\em Data Processor Threads}
;;
  load  rXP, dFP[XP]     -- {\em load ptr to \/} X
  load  rYP, dFP[YP]     -- {\em load ptr to \/} Y
  load  rYlim, dFP[YLim] -- {\em load loop const:\/} Y {\em ptr limit}
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jgt   rB, OUT$_D$         -- {\em zero-trip loop if greater\/}
\null
LOOP$_D$:
  rload rXP, L1$_S$         -- {\em initiate load\/} X[i] {\bf (L1)}
  rload rYP, L2$_S$         -- {\em initiate load\/} Y[i] {\bf (L2)}
  next
\null
CONTINUE$_D$:
  load  rXI, dFP[XI]     -- {\em load copy of \/} X[I]
  load  rYI, dFP[YI]     -- {\em load copy of \/} Y[I]
  load  rA,  dFP[A]      -- {\em load loop const:\/} a
  load  rXP, dFP[XP]     -- {\em load ptr to \/} X
  load  rYP, dFP[YP]     -- {\em load ptr to \/} Y
  load  rYLim, dFP[YLim] -- {\em load loop const:\/} Y {\em ptr limit}
\null
  fmul  rTmp,rA,rXI      -- a*X[i]
  fadd  rTmp,rTmp,rYI    -- a*X[i] + Y[i]
  rstore rYP, rTmp,S1$_S$   -- {\em store into\/} Y[i] {\bf (S1)}
  add   rXP,rXP,8        -- {\em increment ptr to\/} X
  add   rYP,rYP,8        -- {\em increment ptr to\/} Y
  store dFP[XP],   rXP   -- {\em store ptr to \/} X
  store dFP[YP],   rYP   -- {\em store ptr to \/} Y
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jle   rB, LOOP$_D$        -- {\em fall out of loop if greater\/}
  next
\null
OUT$_D$:
  {\em ... loop sequel ...\/}
\endid

\subsection{Analysis of Multiprocessor Code}

Here we see the clear and unpleasant consequence of our choice that
{\cf rload}s deposit into the frame and not into registers.  Now, the
Data Processor performs more loads and stores on the current frame
than in the uniprocessor case.  The reason is that since we relinquish
the Data Processor at the {\cf next} instruction after the {\cf
rload}s, the registers may have changed by the time we get the Data
Processor back at label {\cf CONTINUE$_D$}.  Thus, we have to
repeatedly reload the the {\cf X} and {\cf Y} pointers and the loop
constants {\cf A} and {\cf YLim}, and repeatedly store the incremented
{\cf X} and {\cf Y} pointers back.

Now, in a multiprocessor, all these extra instructions may actually
pay off when compared with nodes built with conventional processors,
because {\em none of them are long latency operations,} they are all
local.  Suppose we have an MPA built with conventional processors and
the same load/store instructions are used for remote locations (\ie\
the code looks like the uniprocessor code presented earlier).  Here is
a comparison of the dynamic instruction counts of the Data Processor
for the body of the inner loop for the two codes, generalized for
$k$-way unrolling:

\begin{center}\small
\begin{tabular}{|l|c|c|cc|cc|}
\hline
             & Arith  & Br  & \multicolumn{2}{|c|}{Local} & \multicolumn{2}{|c|}{Remote} \\
             &        &     & Ld     & St    & Ld    & St  \\
\hline
Conventional & $1+4k$ & $1$ &  $0$   &  $0$  &  $2k$ & $k$ \\
processor    &        &     &        &       &       &     \\
\hline
{\archname}  & $1+4k$ & $2$ & $4+2k$ & $2$   &  $2k$ & $k$ \\
\hline
\end{tabular} \\
Ld = {\cf load}, St = {\cf store}, $k$ = degree of unrolling
\end{center}

\noindent
Of the five arithmetic operations in the loop body, only the {\cf cmp}
is not replicated on loop unrolling.  For {\archname}, even in an
unrolled loop, the two loop constants and the two pointers to {\cf X}
and {\cf Y} need to be loaded only once and the two incremented
pointers need to be stored only once; also, we count the {\cf next}
instruction as a branch.

Assume that arithmetic, branch and local loads and stores cost one
time unit.  For the conventional processor, assume that the remote
loads cost an average of $l$ units (the processor stalls waiting for
the reference to complete), and assume that each remote store costs
only 1 unit because it is likely to find the just-loaded {\cf Y[i]} in
the cache.  For {\archname}, we charge one unit for {\cf rload}s and
{\cf rstore}s, since they are non-blocking message sends.  We charge
no additional cost for the thread switch at {\cf next}, assuming
sufficient parallelism in the continuation queue to keep the processor
busy with other work.  Therefore, {\archname} will take less overall
execution time when,
\[ 9k + 9 \leq 2kl + 5k + 2\]
If the loop is unrolled 8 times ($k = 8$) then the {\archname} code is
preferred whenever the average global penalty is $l \geq 2.4$. That
is, if the expected value of the remote load/store penalty is about 3
units or more, then the extra local instructions executed by the
multiprocessor code are worth it.

As a calibration point, consider a cache coherent multiprocessor with
miss penalty of 100 units (see for example the Stanford
DASH\cite{Lenoski90a}). If the cache miss rate exceeds about 2--3\%
then the multithreaded code would be prefered to relying on the cache.

\bigskip

\subsection{Other Optimizations}

{\em Speculative Avoidance of the extra {\tt load}'s and {\tt
store}'s\/}: The multithreaded code and coherent caching are not
mutually exclusive.  If fact, as Culler has observed~\cite{Culler90a},
the multithreaded code overhead can be mitigated by speculating that
the {\cf rload}s and {\cf rstore}s will hit the cache.  We only pay
the cost of a thread switch in case the cache misses. In many ways,
this is the same tradeoff offered by the April processor used in
Alewife~\cite{Agarwal90a}.  Here is the modified code.

\beginid
;;
;; {\em Synchronization Processor Message Handlers}
;;
L1$_S$:
  store sFP[XI],   rV1   -- {\em store away incoming } X[I]
  join  c1, 3, CONTINUE$_D$ -- {\em attempt continuation of loop}
  next                   -- {\em next message}
\null
L2$_S$:
  store sFP[YI],   rV1   -- {\em store away incoming } Y[I]
  join  c1, 3, CONTINUE$_D$ -- {\em attempt continuation of loop}
  next                   -- {\em next message}
\null
L3$_S$:
  join  c1, 3, CONTINUE$_D$ -- {\em attempt continuation of loop}
  next                   -- {\em next message}
\null
S1$_S$:
  load  rN, sFP[N]       -- {\em total number of stores}
  join  c2, rN, OUT$_D$     -- {\em sequel when all stores complete}
  next                   -- {\em next message}
;;
;; {\em Data Processor Threads}
;;
  load  rXP, dFP[XP]     -- {\em load ptr to \/} X
  load  rYP, dFP[YP]     -- {\em load ptr to \/} Y
  load  rA,  dFP[A]      -- {\em load loop const:\/} a
  load  rYlim, dFP[YLim] -- {\em load loop const:\/} Y {\em ptr limit}
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jgt   rB, OUT$_D$         -- {\em zero-trip loop if greater\/}
\null
LOOP$_D$:
  rload rXP, L1$_S$         -- {\em initiate load\/} X[i] {\bf (L1)}
  rload rYP, L2$_S$         -- {\em initiate load\/} Y[i] {\bf (L2)}
\null
  load  rC1, dFP[c1]     -- {\em load join counter\/}      {\bf (L3)}
  cmp   rB, 2, rC1       -- {\em Two responses arrived?\/} {\bf (C1)}
  jeq   rB, FAST\_CONTINUE$_D$ -- {\em yes, skip save/restore\/} {\bf (J1)}
                         -- {\em gamble failed; save modified regs\/}
  store dFP[XP],   rXP   -- {\em store ptr to \/} X        {\bf (S2)}
  store dFP[YP],   rYP   -- {\em store ptr to \/} Y        {\bf (S3)}
  start L3$_S$, dFP, 0      -- {\em start 3rd synch thread\/} {\bf (S4)}
  next                   -- {\em do something else\/}
\null
CONTINUE$_D$:               -- {\em  gamble failed; restore regs}
  load  rA,  dFP[A]      -- {\em load loop const:\/} a
  load  rXP, dFP[XP]     -- {\em load ptr to \/} X
  load  rYP, dFP[YP]     -- {\em load ptr to \/} Y
  load  rYlim, dFP[YLim] -- {\em load loop const:\/} Y {\em ptr limit}
\null
FAST\_CONTINUE$_D$:           -- {\em directly here if gamble succeeds}
  store dFP[c1], 0       -- {\em re-initialize join counter}
  load  rXI, dFP[XI]     -- {\em load copy of \/} X[I]
  load  rYI, dFP[YI]     -- {\em load copy of \/} Y[I]
\null
  fmul  rTmp,rA,rXI      -- a*X[i]
  fadd  rTmp,rTmp,rYI    -- a*X[i] + Y[i]
  rstore rYP, rTmp,S1$_S$   -- {\em store into\/} Y[i]         {\bf (S1)}
  add   rXP,rXP,8        -- {\em increment ptr to\/} X
  add   rYP,rYP,8        -- {\em increment ptr to\/} Y
  cmp   rB,rYP,rYLim     -- {\em compare ptr to \/} Y {\em with limit\/}
  jle   rB, LOOP$_D$        -- {\em fall out of loop if greater\/}
  next
\null
OUT$_D$:
  {\em ... loop sequel ...\/}
\endid

\noindent
Unlike the previous version, the data processor now loads all relevant
values into registers before the loop, including the loop constants
{\cf a} and {\cf ylim}, gambling that it can keep them there.  After
issuing the two {\cf rload}s in statements {\bf L1} and {\bf L2}, it
peeks at the join counter {\cf c1} ({\bf L3}, {\bf C1}).  If the two
{\cf rload} responses have already arrived (say, because of a cache
hit), {\cf c1} will have been incremented from 0 to 2; the gamble
succeeds and we jump directly to {\cf FAST\_CONTINUE$_D$}.  In this
case, we only load the values that arrived on the message; the loop
constants and {\cf X} and {\cf Y} pointers are already in registers.
Note also that after the two pointer increments ({\cf add}
instructions), we no longer store the pointers back into the frame.

If the gamble fails ({\cf c1} $<2$ in statement {\bf C1}), we save
modified registers ({\bf S2}, {\bf S3}), start a third (trivial)
message handler in {\sc sP} which will synchronize with the returning
{\cf rload} responses ({\bf S4}), and switch to another thread.  In
{\sc sP}, when the three message handlers at {\cf L1$_S$} {\cf
L2$_S$}, and {\cf L3$_S$} have executed (two {\cf rload} responses,
one started locally at {\bf S4}), the data processor thread at {\cf
CONTINUE$_D$} is initiated, which reloads the two loop constants and
the two pointers into registers before proceeding.

A number of tricks could be used to improve the probability that the
gamble succeeds.  Other useful instructions could be executed after
the {\cf rload}s and before peeking at the join counter.  For example,
if the loop is unrolled $n$ times, all $2n$ {\cf rload}s could be
issued before looking for the responses for the first pair.  We could
even busy-wait a little, polling the join counter a few times before
giving up.

{\em Loop splitting\/}: The loop can be split into several loops
working on independent chunks of the arrays, so that the remote loads
of one loop are overlapped with computation in other loops, and vice
versa.

Clearly, there are a number of challenging compilation issues.  We
will discuss some software issues in Section \ref{sec-compiling}.


% ----------------------------------------------------------------
