\documentstyle[portrait,fancybox,psfig]{seminar}
\newpagestyle{au} {}{~~High Performance Numerical Linear Algorithms\hfill \rightmark
\hfill\thepage}
\pagestyle{au}
\newenvironment{Page}{\begin{slide*}}{\end{slide*}}
\newcommand{\heading}[1]{%
  \begin{center}
    {\large \bf \shadowbox{#1} }
  \end{center}
  \vspace{1ex minus 1ex}}

\newcommand{\subheading}[1]{%
    \mbox{\bf #1}%
  \vspace{1ex minus 1ex}}
\newcounter{counter}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\im}{\item}
\newcommand{\un}{\underline}
\begin{document}
\bibliographystyle{alpha}

\begin{Page}
\centerline{Ph.D. Research Seminar on}
\vspace{0.05in}
\heading{\small{High Performance Numerical Linear Algorithms}}
\begin{center}
{\small by }\\
{\bf Gaurav Trivedi}\\
\vspace {0.3in}
{\small under the guidance of }\\
%\vspace {0.3in}
{\small \bf Prof. H. Narayanan} \\
and\\
{\small \bf Prof. Madhav P. Desai} \\
%\vspace {0.3in}
%\newfont{\iitblogofont}{iitblogo}
%\newcommand{\iitbseal}{\iitblogofont a}
%\parbox{\logowidth}{\iitbseal}\\[1mm]
\small{Department of Electrical Engineering } \\
\small{Indian Institute of Technology} \\
\small{Mumbai} \\
\small{May, 2000}\\

\end {center}
\end{Page}

%%% SLIDE 1
\begin{Page}
\heading{Presentation Outline}
{
I will talk about
\bi
\im Motivation
\im Fundamentals of Parallel Processing
\im Implementation Details
\im Performance Analysis
\im Linear Algorithms
\im Proposed future work
\ei
}
\end{Page}



%%% SLIDE 2
\begin{Page}
\heading{Motivation}
{
\bi
\item Limitation of the traditional computers.
\item Advancement in hardware and architecture enables to exploit parallelism.
\item Lagging in software development relatively to hardware development.
\ei
}
\end{Page}

%%% SLIDE 3
\begin{Page}
\heading{Fundamentals of Parallel Processing}
{
\begin{itemize}
\item Models of multiunit processor:
\bi
\im Tightly Coupled Model
\im Loosely Coupled Model
\ei
\end{itemize}

\begin{enumerate}
\item Advantages of Tightly coupled model
\bi
\im Increased throughput
\im Less cost effective
\im Less communication overhead
\im Increased  reliability
\ei
\item Advantages of Loosely coupled model
\bi
\im Resource sharing
\im Computation speedup
\im Less cost effective
\im Reliability
\ei
\end{enumerate}
}
\end{Page}

%%% SLIDE 4
\begin{Page}
\heading{Classification of parallel processors}
{
\begin{itemize}
\item Types of parallel processors
\bi
\im Single Instruction Stream Single Data Stream (SISD)
\im Single Instruction Stream Multiple Data Stream (SIMD)
\im Multiple Instruction Stream Single Data Stream (MISD)
\im Multiple Instruction Stream Multiple Data Stream (MIMD)
\ei
\end{itemize}
}
\end{Page}

%%% SLIDE 5
\begin{Page}
\heading{Different Architectures}
{
\begin{center}
\begin{figure}[p]  
\centerline{{\psfig{figure=fig1.ps,height=2in,width=2.9in}}}
\caption{SISD Organization}
\end{figure}
\end{center}
\newpage
\begin{center}   
\begin{figure}[p]
\centerline{{\psfig{figure=fig4.ps,height=6cm,width=5cm}}}
\caption{SIMD Organization}
\end{figure}
\end{center}
\newpage

\begin{center}
\begin{figure}[p]
\centerline{{\psfig{figure=fig7.ps,height=7cm,width=7cm}}}
\caption{MISD Organization}
\end{figure}
\end{center}
\newpage

\begin{center}
\begin{figure}[p]
\centerline{{\psfig{figure=fig3.ps,height=7cm,width=7cm}}}
\caption{MIMD Organization}  
\end{figure}
\end{center}
}
\end{Page}

%%% SLIDE 6
\begin{Page}
\heading{Pipelining}
{
These are the basic types of pipelining,which appear in the pipeline processors:\par
\begin{enumerate}
\item Instruction pipeline
\item Arithmetic pipeline.
\end{enumerate}

}
\end{Page}

%%% SLIDE 7
\begin{Page}
\heading{General Issues of parallel processing}
{
Some other issues, that affect performance are:
\begin{enumerate}
\item Virtual Shared Memory
\item Memory Issues: Example given
\item Interconnection Issues
\item Message Passing
\end{enumerate}
}
\end{Page}

%%% SLIDE EXAMPLE
\begin{Page}
\heading{Example of Memory Management}
{
The example itself concerns the dense matrix-matrix multiplication $C = AB + C$. The matrices are square and of order 1024. Assume a page
contains 65,536 elements; then it follows that 64 columns of a matrix can be stored on 1 page and that all three matrices can be stored on 48 pages in total.
Let us assume that the available main memory space can contain 16 pages. This implies that if we have access to successive columns of a matrix, we have a page
fault after every 64 columns. Here it is also assumed that a page fault takes about 0.5 seconds of I/O time. Different ways to compute $C = AB + C$ are given
below:

\begin{enumerate}
\item Inner-product approach - ijk\\
\tiny
\begin{verbatim}
        DO 30 I = 1, N
           DO 20 J = 1, N
              DO 10 K = 1, N
                 C(I,J) = A(I,K) * B(K,J) + C(I,J) 
  10          CONTINUE
  20       CONTINUE
  30    CONTINUE
\end{verbatim}
It will 93 days for the I/O!!!!
\normalsize
\item Column-wise update of C - jki\\
\tiny
\begin{verbatim}

        DO 30 J = 1, N
           DO 20 K = 1, N
              DO 10 I = 1, N
                C(I,J) = A(I,K) * B(K,J) + C(I,J)
  10          CONTINUE
  20       CONTINUE
  30    CONTINUE
It will 2.25 Hrs for the I/O!!
\end{verbatim}
\normalsize
\item Partitioning the matrices into block-columns - blocked jki
\tiny
\begin{verbatim}

        DO 40 J = 1, N, NB
           DO 30 K = 1, N, NB
              DO 20 JJ = J, J+NB-1
                 DO 10 KK = K, K+NB-1
                C(:, JJ) = A(:, KK) * B(KK, JJ) + C(:, JJ)
  10             CONTINUE
  20          CONTINUE
  30       CONTINUE
  40    CONTINUE
It will 70 seconds for the I/O.
\end{verbatim}
\normalsize
\end{enumerate}
}
\end{Page}



%%%SLIDE 8
\begin{Page}
\heading{Implementation Details}
{
\begin{enumerate}
\item Parallel Decomposition and Data Dependency Graphs
\item Synchronization
\item Load Balancing
\end{enumerate}
}
\end{Page}

%%%SLIDE 9
\begin{Page}
\heading{Performance Consideration}
{
\begin{enumerate}
\item Speedup
\begin{equation}
Sp(n) = \frac{T(l)}{T(n)}
\end{equation}
\item Efficiency
\begin{equation}
E(n) = \frac{S(n)}{n}
\end{equation}
\item Amdahl's Law
\begin{equation}
t = \frac{(1-f)N}{S} + \frac{fN}{V}
\end{equation}
Here, $f$ is the fractional work, which can be done in parallel
\item General form of Amdahl's Law
\begin{equation}
r = \frac{N}{ \frac{N_{1}}{r_{1}} + \frac{N_{2}}{r_{2}} +....+ \frac{N_{n}}{r_{n}}} Mflops
\end{equation}
\item Amdahl's Law for pineline processors
\begin{equation}
r_{N} = \frac{r_{\infty}}{n_{1/2}/N + 1}
\end{equation}
\item Amdahl's Law for parallel processing
\begin{equation}
S_{p} = \frac{p}{(f+(1-f)p)}
\end{equation}
\item Gustafson's Model
\begin{equation}
S_{p,f} = p+(1-p)(1-f)
\end{equation}  
\end{enumerate}
}
\end{Page}

%%%SLIDE 10
\begin{Page}
\heading{Linear Algorithm}
{
\begin{enumerate}
\item Point Algorithm\par
\hspace{0.5in}for $j = 1$ step $1$ until $n$ \par
\hspace{1in}$b \leftarrow L_{j}^{-1}P_{j}b$;\par
\hspace{0.5in}end;\par 
\hspace{0.5in}Solve $Ux = b$;
\end{enumerate}
}
\end{Page}

%%%SLIDE 11
\begin{Page}
\heading{Linear Algorithms continued....}
{
\begin{enumerate}
\item Right-Looking Algorithm\\
\tiny
STEP 1:
\begin{equation}
PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
L_{21} & I & 0\\
L_{31} & 0 & I\\
\end{array}\right]
\left[\begin{array}{lll}
U_{11} & U_{12} & U_{13}\\
0 & \hat{A_{22}} & \hat{A_{23}}\\
0 & \hat{A_{32}} & \hat{A_{33}}\\
\end{array}\right]
\end{equation}
where $L_{11}$ and $U_{11}$ are $k$x$k$ matrices and $P$ is a permutation matrix representing the effects of pivoting. The blocks labeled $\hat{A_{ij}}$ are
the updated portion of $A$ and has not yet been factored, and will be referred to as the active sub-matrix.\\
STEP 2:
\begin{equation}
\left[\begin{array}{ll}
 I  & 0 \\
 0  & P_{2}\\
\end{array}\right] PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
L_{21} & L_{22} & 0\\
L_{31} & L_{32} & I\\   
\end{array}\right]
\left[\begin{array}{lll}
U_{11} & U_{12} & U_{13}\\
0 & U_{22} & U_{23}\\
0 & 0 & \hat{A_{33}}\\
\end{array}\right]
\end{equation}
where $P_{2}$ is the permutation matrix of the order $n-k$.\\
STEP 3:
\begin{equation}
P_{2}
\left[\begin{array}{l}
 \hat{A_{22}}\\
 \hat{A_{32}}\\
\end{array}\right]=
\left[\begin{array}{l}
L_{22}\\
L_{32}\\
\end{array}\right]U_{22}
\end{equation}
\\
STEP 4:
\begin{equation}
\left[\begin{array}{l}
 \hat{A_{22}}\\
 \hat{A_{32}}\\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
 \hat{A_{22}}\\
 \hat{A_{32}}\\
\end{array}\right]
\end{equation}
and
\begin{equation}
\left[\begin{array}{l}
L_{21}\\
L_{31}\\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
L_{21}\\
L_{31}\\
\end{array}\right]
\end{equation}\\
\newpage
STEP 5:
Solve the triangular system  
\begin{equation}
U_{23} = L_{22}^{-1}\hat{A_{23}}
\end{equation} 
to compute the next block row of $U$.
\\
STEP 6: Update $\hat{A_{33}}$
\begin{equation}
\hat{A_{33}} \leftarrow \hat{A_{33}} - L_{32}U_{23}
\end{equation}\\
STEP 7: $repeat$ the STEP 2 - STEP 6, $until$ $A=LU$\\
\normalsize
\end{enumerate}
}
\end{Page}

%%%SLIDE 12
\begin{Page}
\heading{Linear Algorithms continued....}
{
\begin{enumerate}
\item Left-Looking Algorithm\\
\tiny
STEP 1: Assume that
\begin{equation}
PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
L_{21} & I & 0\\
L_{31} & 0 & I\\
\end{array}\right]
\left[\begin{array}{lll}
U_{11} & A_{12} & A_{13}\\
0 & A_{22} & A_{23}\\
0 & A_{32} & A_{33}\\
\end{array}\right]
\end{equation}\\
STEP 2:
\begin{equation}
\left[\begin{array}{ll}
 I  & 0 \\
 0  & P_{2}\\  
\end{array}\right] PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
L_{21} & L_{22} & 0\\
L_{31} & L_{32} & I\\
\end{array}\right]
\left[\begin{array}{lll}
U_{11} & U_{12} & A_{13}\\
0 & U_{22} & A_{23}\\   
0 & 0 & A_{33}\\  
\end{array}\right]
\end{equation}\\
STEP 3: Solve the triangular system
\begin{equation}  
U_{12} = L_{11}^{-1}A_{12}
\end{equation}\\
STEP 4: Update the rest of the middle block column of U,
\begin{equation}
\left[\begin{array}{l}
\hat{A_{22}} \\
\hat{A_{32}} \\
\end{array}\right] \leftarrow
\left[\begin{array}{l}
A_{22} \\
A_{32}\\
\end{array}\right] -
\left[\begin{array}{l}  
L_{21}\\
L_{31}\\
\end{array}\right]U_{12}
\end{equation}\\  
STEP 5: Perform the factorization
\begin{equation}
P_{2}
\left[\begin{array}{l}
\hat{A_{22}} \\ 
\hat{A_{32}} \\
\end{array}\right] =
\left[\begin{array}{l}
L_{22} \\
L_{32}\\
\end{array}\right] U_{22}
\end{equation}\\
\newpage
STEP 6: Lastly the pivoting
\begin{equation}
\left[\begin{array}{l}
A_{23} \\
A_{33} \\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
A_{23} \\
A_{33}\\
\end{array}\right]
\end{equation}
and
\begin{equation}
\left[\begin{array}{l}
L_{21} \\
L_{31} \\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
L_{21}\\
L_{31}\\
\end{array}\right]
\end{equation}\\
\normalsize
\end{enumerate}
\normalsize
}
\end{Page}

%%%SLIDE 13
\begin{Page}
\heading{Linear Algorithms continued....}
{
\begin{enumerate}
\item Crout Algorithm\\
\tiny
STEP 1: Assume that
\begin{equation}
PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
0 & I & 0\\
0 & 0 & I\\
\end{array}\right]
\left[\begin{array}{lll}
I & U_{12} & U_{13}\\
L_{21} & A_{22} & A_{23}\\
L_{31} & A_{32} & A_{33}\\
\end{array}\right]
$$\par$$
\hspace{1.5in}
\left[\begin{array}{lll}
U_{11} & 0 & 0\\
0 & I & 0\\
0 & 0 & I\\
\end{array}\right]
\end{equation}\\
STEP 2: For factorization,solve
\begin{equation}   
\left[\begin{array}{ll}
A_{22} & A_{23}\\
\end{array}\right] \leftarrow
\left[\begin{array}{ll}
A_{22} & A_{23}\\
\end{array}\right] - L_{12}
\left[\begin{array}{ll}
U_{12} & U_{13}\\
\end{array}\right]   
\end{equation}\\
and
\begin{equation}  
A_{32} \leftarrow A_{32} - L_{31}U_{12}
\end{equation}\\
STEP 3: Do factorization
\begin{equation}
P_{2}
\left[\begin{array}{l}
A_{22} \\
A_{32} \\
\end{array}\right] =   
\left[\begin{array}{l}
L_{22} \\
L_{32}\\
\end{array}\right] U_{22}
\end{equation}\\
STEP 4: Replace
\begin{equation} 
\left[\begin{array}{l}
A_{23} \\
A_{33} \\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
A_{23} \\
A_{33}\\
\end{array}\right]
\end{equation}
and
\begin{equation}
\left[\begin{array}{l} 
L_{21} \\
L_{31} \\
\end{array}\right] \leftarrow
P_{2}
\left[\begin{array}{l}
L_{21}\\
L_{31}\\
\end{array}\right]
\end{equation}
and put  
\begin{equation}
U_{23} = L_{21}^{-1}A_{23}
\end{equation}\\
STEP 5:  
\begin{equation}
P_{2}PA=
\left[\begin{array}{lll}
L_{11} & 0 & 0\\
L_{21} & L_{22} & 0\\
0 & 0 & I\\
\end{array}\right]
\left[\begin{array}{lll}
I & 0 & U_{13}\\
0 & I & U_{23}\\
L_{31} & L_{32} & A_{33}\\
\end{array}\right]
$$\par$$
\hspace{1.5in}
\left[\begin{array}{lll}
U_{11} & U_{12} & 0\\
0 & U_{22} & 0\\
0 & 0 & I\\
\end{array}\right]
\end{equation}\\
STEP 6: $repeat$ STEP 2 - STEP 5 $until$ $LU$ decomposition complete.\\
\normalsize
\end{enumerate}
\normalsize
}
\end{Page}

%%%SLIDE 11
\begin{Page}
\heading{Future Work}
{
\begin{itemize}
\item After discussing various aspects for the parallel processing and high performance computing, the future work will involve the following:
\bi
\im A detailed survey of computer architecture, specifically for pipelined processors,is to be done.
\im Since optimization of the code is of utmost importance, so the in-depth knowledge is to be gained in the field of compiler theory.
\im Message passing strategies need to be explored in a greater detail.
\im Linear Algebra algorithms for the uniprocessor computation and its extensions for the multiprocessor paradigm are to be devised.
\im There is a need for the general algorithms to be made compatible to the multiprocessor systems. 
\im Algorithms have to be discovered or devised, which are best suitable for shared memory systems.
\ei
\end{itemize}
}
\end{Page}


\end{document}
