\documentstyle[palatino,oneinchmargins,12pt]{article}

\renewcommand{\thetable}{\Roman{table}}

\input support/acaro-figure-macro.tex
\input support/6851macro
\input support/macros

\def\baselinestretch{1.5}

\pagestyle{empty}

\begin{document}

\bf

\begin{center}
\codebox{
\< \procname{GCM-Gross}\\
$\velinit,\Pinit,\Tinit,\Sinit,\rinit$ $\gets$ \procname{compute\_initial\_ocean\_states}() \\
\keyword{for} each time step $n$ \\
\> Perform the following computation \\
margin \= step no \= states \= get \= procedures \kill
\> Step 1 \>   $\Gveli$     \> $\gets$ \> \procname{estimate\_Gv}($\veln$,$\Pn$,$\rn$) \\ 
\> Step 2 \>   $\Pm$        \> $\gets$ \> \procname{diagnose\_pressure}($\Pn$,$\veln$,$\Gveli$)\\
\> Step 3 \>   $\velm$      \> $\gets$ \> \procname{advance\_velocity}($\Pm$,$\vn$,$\Gveli$) \\
\> Step 4 \>   $\Tm$        \> $\gets$ \> \procname{advance\_temperature}($\Tn$,$\velm$) \\
\> Step 5 \>   $\Sm$        \> $\gets$ \> \procname{advance\_salinity}($\Sn$,$\velm$) \\
\> Step 6 \>   $\rho^{n+1}$ \> $\gets$ \> \procname{calculate\_density}($\Tm$,$\Sm$) \\
\keyword{return}($\velfinal,\Pfinal,\Tfinal,\Sfinal,\rfinal$)
}\\
\end{center}

\newpage

\begin{center}
\codebox{
\< $\tau$ is the tolerance, $\pz$ is an initial estimate of $\pfinal$ \mbox{\hspace{2in}}\\
\< \procname{Elliptic\_Solver}($\pz$,\Gdiv,\Vdiv) \\
$f$ $\gets$ \procname{compute\_source}(\Gdiv,\Vdiv) \\
$\rz \gets f - \A \pz;$ \\
$\bz \gets \K \rz$ \\
$\xi^{0} \gets \bz$ \\
\keyword{while} $\sqrt{\ip{\ri}{\ri}} > \tau$ \keyword{do} \\
\> $\gamma \gets (\ip{\ri}{\xi^{i}})$ \\
\> $\Ai \gets \gamma \; / \; (\ip{\bi}{\A \bi})$ \\
\> $\pj \gets \pi + \Ai \bi$ \\
\> $\rj \gets \ri - \Ai \A \bi$ \\
\> $\xi^{i+1} \gets \K \rj$ \\
\> $\Bi \gets (\ip{\rj}{\xi^{i+1}}) \; / \; \gamma$ \\
\> $\bj \gets \xi^{i+1} + \Bi \bi $ \\
\> $i   \gets i+1 $\\
\keyword{return}($\pfinal$)}
\end{center}

\newpage

\begin{center}
\codebox{
\< \procname{GCM} () \\
$\velinit,\Pinit,\Tinit,\Sinit,\rinit$ $\gets$ \procname{compute\_initial\_ocean\_states()} \\
\keyword{for} each time step $n$ \\

\begin{tabular}{llclrl}
Step 1.1 & $\Gvel$  & $\gets$ & \procname{predict\_Gv}($\veln$,$\rn$) \hspace{1.5cm} & 170 FPops &\\
Step 1.2 & $\veli$  & $\gets$ & \procname{predict\_velocity}($\veln$,$\Pn$,$\Gvel$) &  20 FPops &\\
Step 1.3 & $\Gveli$ & $\gets$ & \procname{correct\_Gv}($\veln$,$\veli$,$\rn$)       & 277 FPops &\\

Step 2.1 & \Gdiv    & $\gets$ & \procname{compute\_div}($\Gveli$)                   &   8 FPops &\\
Step 2.2 & \Vdiv    & $\gets$ & \procname{compute\_div}($\vel$)                     &   8 FPops &\\
{\bf Step 2.3} & $\Pm$    & $\gets$ &
\procname{elliptic\_solver}($\Pn$,\Gdiv,\Vdiv)      & {\bf 16 FPops} & $+$
\hspace{.23cm} {\bf 32FPops/iteration}\\
Step 3   & $\velm$  & $\gets$ & \procname{correct\_velocity}($\veln$,$\Pm$,$\Gveli$) & 20 FPops &\\

Step 4.1 & $\Gt$    & $\gets$ & \procname{predict\_Gt}($\Tn$,$\velm$)               & 39 FPops  &\\
Step 4.2 & $\Ti$    & $\gets$ & \procname{predict\_temperature}($\Tn$,$\Gt$)        &  2 FPops  &\\
Step 4.3 & $\Gti$   & $\gets$ & \procname{correct\_Gt}($\Tn$,$\Ti$,$\velm$)         & 79 FPops  &\\
Step 4.4 & $\Tm$    & $\gets$ & \procname{correct\_temperature}($\Tn$,$\Gti$)       &  2 FPops  &\\

Step 5.1 & $\Gs$    & $\gets$ & \procname{predict\_Gs}($\Sn$,$\velm$)               &  35 FPops &\\
Step 5.2 & $\Si$    & $\gets$ & \procname{predict\_salinity}($\Sn$,$\Gs$)           &   2 FPops &\\
Step 5.3 & $\Gsi$   & $\gets$ & \procname{correct\_Gs}($\Sn$,$\Si$,$\velm$)         &  79 FPops &\\
Step 5.4 & $\Sm$    & $\gets$ & \procname{correct\_salinity}($\Sn$,$\Gsi$)          &   2 FPops &\\

Step 6   & $\rho^{n+1}$ & $\gets$ & \procname{calculate\_density}($\Tm$,$\Sm$)      &   6 FPops &\\
\hline
\multicolumn{3}{|l}{\bf Total per time step}&                                        & {\bf 765 FPops} & \multicolumn{1}{l|}{$+$ \hspace{.23cm} {\bf 32FPops/iteration}}\\
\hline
\end{tabular}
\\
\keyword{return}($\velfinal,\Pfinal,\Tfinal,\Sfinal,\rfinal$)
}
\end{center}

\newpage

\begin{center}
\illustrationx{5in}{figures/dfg-new.eps} 
\end{center}

\begin{quote}
Macro dataflow graph of the main loop
\end{quote}

\newpage

\illustrationx{5in}{figures/fully-parallel-model-GCM.ps}

\newpage

\illustrationy{3.5in}{figures/data-parallel-model.eps}

\newpage

\illustrationx{6in}{figures/layout-new.eps}

\newpage

\begin{tabular}{lcccccc}
\hline
\hline
                      &  Req.~FPOps/ & Occurrences & \multicolumn{4}{c}{Cycles per Required Floating Point Op}\\
{\bf Operation}       &  element & in elliptic & \multicolumn{2}{c}{\it Multithreaded} & \multicolumn{2}{c}{\it Data-parallel} \\
                      &          &             & {\it Work} & {\it Work$+$Idle} & {\it Raw} & {\it Adjusted}\\
\hline                                                    
inner product         &        2 &  4 $\times$ & 10.1  &             &  2.6  & 4.4 \\
\hline                                               
$aX+Y$                &        2 &  3 $\times$ & 24.4  &             &  3.2  & 5.4 \\
\hline                                               
7-point stencil       &       13 &  1 $\times$ & 11.5  &             & 10.4  & 17.3 \\
\hline                                               
preconditioner        & $\sim$ 5 &  1 $\times$ & 16.2  &             &  4.0  & 6.7 \\
\hline
\\
{\bf elliptic solver} & $\sim$ 32/iter. &      & {\bf 14.0} & {\bf 18.9} & {\bf 12.0} & {\bf 20.1} \\
\hline
\\
{\bf GCM Overall}     &          &             & {\bf 13.8} & {\bf 14.6} &  {\bf 9.1} & {\bf 15.2} \\
\hline
\hline
\end{tabular}

\begin{quote}
Comparison of performance for the best Id and CM Fortran versions with
cycles per required floating point operation, for the $168 \times 90 \times
4$ Pacific ocean with 60\% water.  (2 processor Monsoon, 32 processor
CM-5).  The {\it Work} number for Monsoon includes floating point
operations and support instructions.  The {\it Adjusted} number on CM-5 is
{\it Raw} number $\div$ .60.
\end{quote}

\newpage

\begin{large}
\begin{verbatim}
def ip_3d a b = 
  { s = 0.0 ;
   in
     {for i <- 1 to imax BOUND ibound do
        s_jk = 0.0;
        next s = s + 
         {for j <- 1 to jmax BOUND jbound 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{large}

\newpage

\rawillustrationx{4.0in}{figures/loop-bound.ps}

\newpage

\begin{tabular}{lrrr}
\hline
\hline
                       & \multicolumn{3}{c}{\bf Loop Schema of Inner Loop (in 1000's cycles)}  \\
{\bf Type}             & Bounded ($k=2$)  & Sequential & Unrolled    \\
\hline          
Int Ops                &      958         &      444   &      202    \\
\hline          
Float Ops              &      167         &      137   &      122    \\
\hline          
Fetch Ops              &      618         &      256   &      135    \\
\hline          
Store Ops              &      126         &       35   &        4    \\
\hline          
Bubbles                &    1,501         &      457   &      185    \\
\hline          
Move Ops               &    2,628         &    1,055   &      193    \\
\hline          
Other                  &    3,121         &      868   &      102    \\
\hline          
\\
{\bf Work}             &    9,169         &    3,252   &      943    \\
\hline          
\\
Idles                  &      153         &      151   &      182    \\
{\bf Work} $+$ Idles   &    9,322         &    3,404   &    1,125    \\
\hline
\hline
\end{tabular}

\begin{quote}
$ibound = 5$, $jbound = 2$, 2 processor Monsoon
\end{quote}

\newpage

\rawillustrationx{6in}{figures/inner-product.ps} 

\newpage

\begin{center}
\begin{tabular}{lrrr}
\hline
\hline
                  & \multicolumn{3}{c}{\bf One Iteration of Elliptic Solver (in 1000's cycles)}  \\
{\bf Type}        & Water-Only & Everywhere & Hybrid    \\
\hline          
Int Ops               &  6,646 &  3,976 &  3,403 \\
\hline                                      
Float Ops             &  1,283 &  1,878 &  1,324 \\
\hline                                      
Fetch Ops             &  3,826 &  2,495 &  1,965 \\
\hline                                      
Store Ops             &  1,426 &    837 &    764 \\
\hline                                      
Bubbles               &  7,692 &  3,357 &  2,893 \\
\hline                                      
Move Ops              & 14,677 &  5,293 &  4,397 \\
\hline                                      
Other                 &  9,718 &  1,445 &  1,514 \\
\hline                                      
{\it Total Work}      & 45,270 & 19,261 & 16,261 \\
\hline                                      
\\                                          
Idles                 & 10,975 &  6,321 &  6,321 \\
{\it Work $+$ Idles}  & 56,245 & 25,582 & 21,999 \\
\hline
\\
Work / required FLOP  &  39.0  &   16.6 &   14.0 \\
Cycles / required FLOP & 48.4  &   22.0 &   18.9 \\
\hline          
\hline          
\end{tabular}
\begin{quote}
Comparison of the three versions of the elliptic solver for the $168
\times 90 \times 4$ Pacific ocean.  ($ibound=5$, $jbound=3$, 2 processor Monsoon
\end{quote}
\end{center}

\newpage

\begin{center}
\begin{tabular}{lrrrrrrrr}
\hline
\hline
                  & \multicolumn{8}{c}{\bf Monsoon Cycles per Required Floating Point Op}\\
{\bf Operation}   & {\bf Computation} & {\bf Memory} &
\multicolumn{2}{c}{\bf Sync.~Overhead} & {\bf Other} & {\it Total} & {\bf Idle} & {\it Total $=$}\\
                  &             &        & Bubble  & Move &       & {\it Work} & & {\it Work$+$Idle} \\
\hline                                                    
inner product     &         3.1 &    1.4 & 1.9     &  2.3 & 1.4   &     10.1    &   3.1 & 13.2\\
\hline                                                           
$aX+Y$            &         5.5 &    3.1 & 5.6     &  9.0 & 1.1   &     24.4    & 109.3 & 133.7\\
\hline                                                           
7-point stencil   &         2.6 &    2.1 & 2.5     &  4.2 & 0.2   &     11.5    &  24.7 & 36.2 \\
\hline                                                           
preconditioner    &         3.6 &    2.2 & 3.9     &  5.0 & 1.4   &     16.2    &  45.8 & 62.0 \\
\hline
\\
{\bf elliptic solver} &     4.1 &    2.4 & 2.5     &  3.8 & 1.3   &  {\bf 14.0} &   4.9 & {\bf 18.9} \\
\hline
\\
{\bf GCM Overall} &         3.8 &    2.3 & 2.6     &  3.6 & 1.4   &  {\bf 13.8} &   0.8 & {\bf 14.6} \\
\hline
\hline
\end{tabular}


\end{center}

\begin{quote}
Cycles per required floating point operation, for the $168 \times 90 \times
4$ Pacific ocean, using the {\it hybrid} version of GCM.  ($ibound=5$,
$jbound=3$, 2 processor Monsoon.)
\end{quote}

\newpage

\illustrationx{6in}{figures/cm5.ps}

\newpage

\begin{center}
\begin{tabular}{lrccrcr}
\hline
\hline
                & \multicolumn{6}{c}{\bf CM-5 Vector Unit Cycles per Floating Point Operation} \\
{\bf Operation} & \multicolumn{1}{c}{\bf Computation} &
\multicolumn{2}{c}{\bf Communications} & {\bf Raw Total} & {\bf \% Water} & {\bf Adjusted Total}\\
                   & & Reduce & CSHIFT & \\
\hline
inner product    & 0.3  &  2.4  & {\it none} &     2.6  & $\div$ \%60 & 4.4 \\
\hline
$aX+Y$           & 3.2  &  {\it none} & {\it none} &     3.2  & $\div$ \%60 & 5.4 \\
\hline 
7-point stencil &  5.4  &  {\it none} &  5.0  &   10.4  & $\div$ \%60 & 17.3 \\
\hline
preconditioner   & 4.0  &  {\it none} & {\it none} &     4.0  & $\div$ \%60 & 6.7 \\
\hline
\\
{\bf elliptic solver} & 4.1  & 5.2  & 2.7  & 12.0  & $\div$ \%60 & {\bf 20.1 } \\
\hline
\\
{\bf GCM Overall}& 7.0  &  0.5  & 1.6  &      9.1  & $\div$ \%60 & {\bf 15.2 } \\
\hline
\hline
\end{tabular}
\end{center}


\newpage

\illustrationx{7in}{figures/scaling-raw.ps}

\end{document}
