\documentclass[landscape,dvips]{foils}

%\documentclass[a4paper,landscape,headrule]{foil


%\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

%\MyLogo{Slide}

\def\centerr{}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
%\usepackage{amsfonts}
\def\w{{\cal W}}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage{color}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage[ps2pdf]{hyperref}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\def\basswidt{4.0in}
\def\gutter{0.2in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsi
ze}{\par}

%\setlength{\textheight}{8.5in}
%\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in


\def\helv{\sffamily bfseries}
\def\noi{\noindent}
\def\la{\langle}
\def\rf{\rangle}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\aa{\alpha}
\def\bb{\beta}
\def\dd{\delta}
\def\pr{{\rm Pr}}
\def\l{\ell}
\def\t{\theta}
\def\d{\delta}
\def\eps{\varepsilon}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\wt{\widetilde}
\def\ol{\widehat}
\def\TG{\wt{G}}

\def\TX{\wt{X}}
\def\TF{\wt{F}}
\def\TV{\wt{V}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Var{{\bf Var}}
\def\E {{\bf E }}
\def\kk{\kappa}
\def\TH{\widetilde{H}}
\def\th{\widetilde{h}}
\def\la{\langle}
\def\ra{\rangle}
\def\om{\omega}
\def\L{{\cal L}}
\def\I{{\cal I}}
\def\sign{\hbox{\rm sign}}
\def\w{{\cal W}}
\def\W{{\cal W}}
\def\A{{\cal A}}
\def\M{{\cal M}}

\def\N{{\cal N}}
\def\D{{\cal D}}
\def\B{{\cal B}}
\def\hb{\hat{b}}
\def\MT{{\bf T}}
\def\bb{{\bf b}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\pstat{{\bf \Pi}}

%\def\bb{\beta}
\def\ee{\epsilon}
\def\GG{\Gamma}
\def\mm{\mu}
\def\oo{\omega}
\def\ss{\sigma}
\def\w{{\cal W}}
\def\E{{\mathbf E}}
\def\G{{\mathbf G}}
\def\V{{\mathbf V}}
\def\vv{{\mathbf v}}
\def\uu{{\mathbf u}}


\def\roh{\rho _{H}}
\def\alph{{\cal S}}
\def\te{{\bf t}}
\def\pat{{\bf p}}
\def\ahz{A_\w(z)}
\def\phb{P(H)}
\def\pht{P_H(H)}
\def\langa{{\cal S}}
\def\lgh{{\cal R}}
\def\lrh{{\cal R}}
\def\llh{{\cal L}}
\def\luh{{\cal U}}
\def\lah{{\cal S}}
\def\lmh{{\cal M}}

\def\lbar{\bar{L} (z)}
\def\ltilde{L_{\w} (z)}
\def\dht{D_{\w}(z)}
\def\mht{{\bf M}(z)}

\def\uht{U_{\w}(z)}
\def\uhit{U_{\w}^i(z)}

\def\aht{A_{\w}(z)}
\def\bht{B_{\w}(z)}
\def\mfz{{F} (z)}
\def\mgz{{\cal G} (z)}
\def\rhi{R_{i}(z)}
\def\fah{A_\w(z)}
\def\fuh{L_\w(z)}
\def\dh{D_\w}
\def\nh{N_\w}
\def\ah{A_{\w}}
\def\dhz{{P(H)z^m+(1-z)A_\w(z)}}
\def\nhz{{P(H)z^m+(1-z)(A_\w(z)-1)}}
\def\ltr{{{\cal T} _r}}
\def\ltt{{{\cal T} }}
\def\lt0{{{\cal T}_0}}
\def\T{{\cal T}}
\def\trn{t_{r,n}}
\def\Var{{\bf Var}}

\def\L{{\cal L}}
\def\R{{\cal R}}
\def\U{{\cal U}}

\def\M{{\cal M}}
\def\TM{M_{\w}}
\def\TU{U_{\w}}
\def\VP{{\bf P}}
\def\VZ{{\bf Z}}

\def\I{{\bf I}}
\def\CD{{\cal D}}
\def\CP{{\cal P}}
\def\cha#1{{[\![\,#1\,]\!]}}

\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\la{\langle}
\def\ra{\rangle}
\def\eod{\vrule height 6pt width 5pt depth 0pt}

\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\ol{\overline}
\def\P{{\bf P}}
\def\l{\ell}
\def\eps{\varepsilon}
\def\r{\bar R}
\def\R{\bar R}
\def\A{{\cal A}}
\def\E{{\bf E}}
\def\CR{{\cal R}}
\def\P{{\cal P}}
\def\S{{\cal S}}
\def\a{\alpha}
\def\M{{\cal M}}
\def\H{{\cal H}}
\def\SF{{\cal SF}}
\def\Z{{\Bbb Z}}
\def\Real{{\Bbb R}}
\def\RR{\Real}

\def\CC{{\Bbb C}}
\def\th{\theta}
\def\Var{{\rm Var ~}}
\def\phb{P(H)}
\def\VP{{\bf P}}
\def\pstat{{\bf \Pi}}
\def\VT{{\bf T}}
\def\F{{\Bbb F}}
\def\l{\ell}
\def\W{{\cal W}}
\def\VZ{{\bf Z}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\I{{\bf I}}
\def\wt{\widetilde}
\def\pr{{\rm Pr}}
\def\eps{\varepsilon}
\def\lef{\preceq}

\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\green}[1]{{\color{green} #1}}
\newcommand{\red}[1]{{\color{red} #1}}

\newcommand{\stitle}[1]{\foilhead{\red{#1}}\vspace{-0.5in}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{i
temize}\end
{small}}}

\begin{document}

\title{{\color{red} Scaling Linear Solvers to Petascale Systems}}
\author{}
\date{}

\maketitle

\thispagestyle{empty}

%Slide
\stitle{Analytical Modeling -- Basics}

\begin{itemize}
\item
A number of performance measures are intuitive.
\item
Wall clock time -- the time from the start of the first processor to
the stopping time of the last processor in a parallel ensemble. But how
does this scale when the number of processors or problem instance
is changed, or the program is ported to another machine?
\item
How much faster is the parallel version? This begs the obvious followup
question -- what is the baseline serial version with which we compare?
Can we use a suboptimal serial program to make our parallel program look
\item
Raw FLOP count -- What good are FLOP counts when they dont solve a problem?
\end{itemize}


\stitle{Scaling Characteristics of Parallel Programs}

\begin{itemize}
\item
The efficiency $E$ of a parallel program can be written
in terms of speedup $S$, serial time $T_S$ and parallel time $T_P$ as:
\[ E = \frac{S}{p} = \frac{T_S}{pT_P}\] or
\begin{equation}
E = \frac{1}{1 + \frac{T_o}{T_S}}.
\label{eq_eff}
\end{equation}
\item
The total overhead function $T_o$ here is defined as $T_o = pT_P - T_S$.
\item
The total overhead function $T_o$ is an increasing function of
$p$. 
\end{itemize}

\stitle{Scaling Characteristics of Parallel Programs}

\begin{itemize}
\item
For a given problem size (i.e., the value of
$T_S$ remains constant), as we increase the number of processing elements,
$T_o$ increases.
\item
The overall efficiency of the parallel program goes down. This is the case
for all parallel programs.
\end{itemize}


\stitle{Scaling Characteristics of Parallel Programs}

\begin{itemize}
\item
Total overhead
function $T_o$ is a function of both problem size $T_S$ and the number of
processing elements $p$.
\item
In many cases, $T_o$ grows sublinearly with respect to
$T_S$.
\item
In such cases, the efficiency increases if the problem size is
increased keeping the number of processing elements constant.
\item
For such systems, we can simultaneously increase the problem size and number
of processors to keep efficiency constant.
\item
Such systems are called {\em scalable} parallel systems.
\end{itemize}

\stitle{Scaling Characteristics of Parallel Programs}

\begin{itemize}
\item
Recall that cost-optimal parallel systems have an efficiency of $\Theta(1)$.
\item
Scalability and cost-optimality are therefore related.
\item
A scalable parallel system can always be
made cost-optimal if the number of processing elements and the size of the
computation are chosen appropriately.
\end{itemize}

\stitle{Isoefficiency Metric of Scalability}

\begin{itemize}
\item
For a given problem size, as we increase the number of processing elements,
the overall efficiency of the parallel system goes down for all systems.
\item
For some systems, the efficiency of a parallel system increases if the problem
size is increased while keeping the number of processing elements constant.
\end{itemize}

\stitle{Isoefficiency Metric of Scalability}


\vspace*{0.75in}
\centerline{\psfig{figure=perf.figures/isoeff.eps,width=5.5in}}
\centerr{Variation of efficiency: (a) as the number of processing elements is in
creased
for a given problem size; and (b) as the problem size is increased for a
given number of processing elements. The phenomenon illustrated in graph (b)
is not common to all parallel systems.
}

\stitle{Isoefficiency Metric of Scalability}

\begin{itemize}
\item
What is the rate at which the problem size must increase with
respect to the number of processing elements to keep the efficiency
fixed?
\item
This rate determines the scalability of the system. The slower this
rate, the better.
\end{itemize}

\stitle{Isoefficiency Metric of Scalability}

\begin{itemize}
\item
We can write
parallel runtime as:
\begin{eqnarray}
T_P & = & \frac{W + T_o(W,p)}{p} \label{eq-tp-new-3}\end{eqnarray}
Here, $W$ is the problem size, i.e., the number of basic steps in the 
algorithm.
\item
The resulting expression for speedup is
\begin{eqnarray}
S  =  \frac{W}{T_P} \nonumber 
  =  \frac{Wp}{W + T_o(W,p)}. \label{eq-s-new-3} \end{eqnarray}
\item
Finally, we write the expression for efficiency as
\begin{eqnarray}
E  =  \frac{S}{p} 
  =  \frac{W}{W + T_o(W,p)} 
  =  \frac{1}{1 + {T_o(W,p)}/W}.
\label{eq-e-new-3}
\end{eqnarray}
\end{itemize}

\stitle{Isoefficiency Metric of Scalability}

\begin{itemize}
\item
For scalable parallel systems, efficiency can be maintained at a
fixed value (between 0 and 1) if the ratio $T_o/W$ is maintained at
a constant value.
\item
For a desired value $E$ of efficiency,
\begin{eqnarray}
E & = & \frac{1}{1 + {T_o(W,p)}/W}, \nonumber \\
\frac{T_o(W,p)}{W} & = & \frac{1-E}{E}, \nonumber \\
W & = &\frac{E}{1-E}T_o(W,p). \label{neweq-aug23-1}
\end{eqnarray}
\item
If $K = E/(1-E)$ is a constant depending
on the efficiency to be maintained, since $T_o$ is a function of
$W$ and $p$, we have
\begin{eqnarray}
W & = & KT_o(W,p).
\label{eq-iso-3}
\end{eqnarray}
\end{itemize}

\stitle{Isoefficiency Metric of Scalability}

\begin{itemize}
\item
The problem size $W$ can usually be obtained as a function of $p$ by
algebraic manipulations to keep efficiency constant.
\item
This function is called the {\em isoefficiency function}.
\item
This function determines the ease with which a parallel system can maintain
a constant efficiency and hence achieve
speedups increasing in proportion to the number of processing elements.
\end{itemize}


\stitle{Pseudo-Analytical Approach to Performance Prediction}

\begin{itemize}
\item
Analytical approaches provide precise asymptotic estimates of
scalability. They can be applied to algorithms and provide
gross guidance to architecture design.
\item
Empirical approaches work on performance extrapolation. They are
often inaccurate and work on realizations of programs. They
provide little guidance to algorithm and architecture designers.
\item
Simulation-based approaches combine static analysis, dynamic
profiling, and a discrete-event based simulation. They are often
slow, and are only as accurate as the simulation.
\item
We adopt an analytical approach to performance modeling, but
parametrize models using experimental data.
\end{itemize}


\stitle{Pseudo-Analytical Approach to Performance Prediction}

\begin{itemize}
\item
Approach based on factoring out program behavior and machine
characteristics.
\item
Characterize program behavior (computation requirements, communication
overheads) using experimental data fitted on asymptotic estimates.
\item
Characterize platform using experimental data for communication
overheads for underlying permutations.
\item
Match program and platform characterizations for accurate 
performance modeling.
\end{itemize}


\stitle{Scalability Case Study: Spike Solver Performance}

\begin{table}[h!b!p!]
\caption{Spike\_TA0 Algorithm Steps}
\vspace*{0.5in}
\begin{tabular}{lll}
\hline
Number & Description & Cost            \\\hline 
1    &   Factorize the Diagonal Blocks & $O(n\times k^{2})$  \\
2    &   Compute Tips of Spikes        & $O(k^{3})$         \\
3    &   Communicate Tips of Spikes    & $O(k^{2})$        \\
4    &   Factorize The Reduced System  & $O(k^{3})$             \\
5    &   Modify the Right Hand Side    & $O(n\times k)$    \\
6    &   Communicate Tips of MRHS      & $O(k)$         \\
7    &   Solve the Reduced System      & $O(k^{2})$  \\
8    &   Communicate Soln. of Reduced System & $O(k)$ \\
9    &   Matrix Vector Multiplication  & $O(k^{2})$ \\
10   &   Retrieve the Solution         & $O(n \times k)$ \\
\hline
\end{tabular}
\label{table1}
\end{table}


\stitle{Scalability Case Study: Spike Solver Performance}


\centerline{\psfig{figure=detailed_IBM_new.ps,width=6.25in,angle=-90}}

\centerline{Parametrizations of various steps for an IBM JS21.}



\stitle{Scalability Case Study: Spike Solver Performance}

\vspace*{1.0in}

\centerline{\epsfig{figure=js21.eps,width=6.25in}}

\centerline{Observed and predicted speedups on the IBM JS21.}



\stitle{Scalability Case Study: Spike Solver Performance}

\vspace*{1.0in}
\begin{itemize}
\item
Isoefficiency of the Spike solver is close to linear ($O(p)$).
\item
This implies that strong scaling should yield close to linear
speedups.
\end{itemize}

\stitle{Scalability Case Study: Spike Solver Performance}


\vspace*{1.0in}
\centerline{\epsfig{figure=js21_scaled.eps,width=6.25in}}

\centerline{Observed and predicted scaled speedups on the IBM JS21.}


\stitle{Scalability Case Study: Spike Solver Performance}


\vspace*{1.0in}
\centerline{\epsfig{figure=js21_peta.eps,width=6.25in}}

\centerline{Predicted Spike Scaling to petaFLOPS onn the IBM JS21.}


\stitle{Scalability Case Study: Spike Solver Performance}

Shared address space nodes, though complicate life!

\centerline{\psfig{figure=detailed_SGI_new.ps,width=6.25in,angle=-90}}

\centerline{Parametrizations of various steps for an SGI Altix.}



\stitle{Scalability Analysis: Conclusions}

\begin{itemize}
\item
Proposed and demonstrated a novel pseudoanalytical approach for 
scalability analysis.
\item
Technique factors application and architecture abstractions to
enable portability studies.
\item
Application to Spike solver shows high degree of predictive accuracy.
\item
Demonstrated projected scaling of Spike to petascale.
\end{itemize}



\stitle{Scalability Analysis: Ongoing Work}

\begin{itemize}
\item
Complete study by analysing a broader class of platforms.
\item
Characterize other test-cases to fully validate scalability analysis
methodology.
\end{itemize}


\stitle{Avenues for Future Efforts}





\stitle{Reference Slides}



\stitle{Other Scalability Metrics}

\begin{itemize}
\item
A number of other metrics have been proposed, dictated by specific
needs of applications.
\item
For real-time applications, the objective is
to scale up a system to accomplish a task in a specified time bound.
\item
In memory constrained environments, metrics operate at the limit of
memory and estimate performance under this problem growth rate.
\end{itemize}

\stitle{Other Scalability Metrics: Scaled Speedup}

\begin{itemize}
\item
Speedup obtained when the problem size
is increased linearly with the number of processing elements.
\item
If scaled speedup is close to linear, the system is considered scalable.
\item
If the isoefficiency is near linear, scaled speedup curve is close to
linear as well.
\item
If the aggregate memory grows linearly in $p$, scaled speedup increases
problem size to fill memory.
\item
Alternately, the size of the problem is increased subject to an
upper-bound on parallel execution time.
\end{itemize}

\stitle{Scaled Speedup: Example}

\begin{itemize}
\item
The serial runtime of multiplying a matrix of dimension $n \times n$ with
a vector is $t_cn^2$.
\item
For a given parallel algorithm, 
\begin{equation}
S = \frac{t_c n^2}{t_c \frac{n^2}{p} + t_s \log p + t_w n}
\label{matvecspd}
\end{equation}
\item
Total memory requirement of this algorithm is $\Theta(n^2)$.
\end{itemize}

\stitle{Scaled Speedup: Example (continued)}

Consider the case of memory-constrained scaling.

\begin{itemize}
\item
We have $m = \Theta(n^2) = \Theta(p)$.
\item
Memory constrained scaled speedup is given by
\[
S' = \frac{t_c c \times p}{t_c \frac{ c \times p}{p} + t_s \log p +
t_w \sqrt{ c \times p}}
\]
or $S' = O(\sqrt p)$.
\item
This is not a particularly scalable system.
\end{itemize}

\stitle{Scaled Speedup: Example (continued)}

Consider the case of time-constrained scaling.

\begin{itemize}
\item
We have $T_P = O(n^2/p)$.
\item
Since this is constrained to be constant, $n^2 = O(p)$.
\item
Note that in this case, time-constrained speedup is identical to
memory constrained speedup.
\item
This is not surprising, since the memory and time complexity of the
operation are identical.
\end{itemize}

\stitle{Scaled Speedup: Example}

\begin{itemize}
\item
The serial runtime of multiplying two matrices of dimension $n \times n$
is $t_cn^3$.
\item
The parallel runtime of a given algorithm is:
\[
T_P = t_c \frac{n^3}{p} + t_s \log p + 2t_w\frac{n^2}{\sqrt{p}}
\]
\item
The speedup $S$ is given by:
\begin{equation}
S = \frac{t_c n^3}{t_c \frac{n^3}{p} + t_s \log p + 2t_w\frac{n^2}{\sqrt{p}}}
\label{matmatspd}
\end{equation}
\end{itemize}

\stitle{Scaled Speedup: Example (continued)}

Consider memory-constrained scaled speedup.

\begin{itemize}
\item
We have memory complexity $m = \Theta(n^2) = \Theta(p)$, or
$n^2 = c\times p$.
\item
At this growth rate, scaled speedup $S'$ is given by:
\[
S' = \frac{t_c (c \times p)^{1.5}}{t_c \frac{(c \times p)^{1.5}}{p} + t_s \log p
 + 2t_w\frac{c \times p}{\sqrt{p}}} = O(p) \]
\item
Note that this is scalable.
\end{itemize}

\stitle{Scaled Speedup: Example (continued)}

Consider time--constrained scaled speedup.

\begin{itemize}
\item
We have $T_P = O(1) = O(n^3/p)$, or $n^3 = c\times p$.
\item
Time-constrained speedup $S''$ is given by:
\[
S'' = \frac{t_c c\times p}{t_c \frac{c\times p}{p} + t_s \log p + 2t_w\frac{(c\times p)^{2/3}}{\sqrt{p}}} = O(p^{5/6})
\]
\item
Memory constrained scaling yields better performance.
\end{itemize}


\stitle{Serial Fraction $f$}

\begin{itemize}
\item
If the serial runtime
of a computation can be divided into a totally parallel and a totally
serial component, we have:
\[ W = T_{ser} + T_{par}. \]
\item
From this, we have,
\[ T_P = T_{ser} + \frac{T_{par}}{p}. \]
\begin{equation}
T_P = T_{ser} + \frac{W - T_{ser}}{p}
\label{ser_frac}
\end{equation}
\end{itemize}

\stitle{Serial Fraction $f$}

\begin{itemize}
\item
The serial fraction $f$ of a parallel program is defined as:
\[ f = \frac{T_{ser}}{W}. \]
Therefore, we have:
\begin{eqnarray*}
T_P & = & f \times W + \frac{W - f\times W}{p}  \\
\frac{T_P}{W} & = & f + \frac{1-f}{p}
\end{eqnarray*}
\end{itemize}

\stitle{Serial Fraction}

\begin{itemize}
\item
Since $S = W/T_P$, we have
\[ \frac{1}{S} = f + \frac{1-f}{p}. \]
\item
From this, we have:
\begin{equation}
f = \frac{1/S - 1/p}{1 - 1/p}.
\label{ser_comp}
\end{equation}
\item
If $f$ increases with the number of processors, this is an indicator of
rising overhead, and thus an indicator of poor scalability.
\end{itemize}

\stitle{Serial Fraction: Example}

Consider the problem of extimating the serial component of the
matrix-vector product.

We have:
\begin{equation}
f = \frac{\frac{t_c \frac{n^2}{p} + t_s \log p + t_w n}{t_c n^2}}{1 - 1/p}
\end{equation}
or
\begin{eqnarray*}
f & = & \frac{t_s p \log p + t_w np}{t_cn^2} \times \frac{1}{p-1} \\
f & \approx & \frac{t_s \log p + t_w n}{t_cn^2}
\end{eqnarray*}

Here, the denominator is the serial runtime and the numerator is the
overhead.




\end{document}

