\documentclass[a4,portrait]{seminar}
\usepackage{pstcol} % To use the standard `color' package with Seminar
\usepackage{psfig} 
\usepackage{semcolor}
\input{seminar.bug}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{fancybox}
\usepackage{pst-ghsb}
\usepackage{pst-grad}

%\slideframe[\psset{fillstyle=gradient,gradientHSB=true,gradmidpoint=0,
%                   gradbegin=RedA,gradend=RedB}]{scplain}

\definecolor{Beige}{rgb}{0.96,0.96,0.86}
\definecolor{Yellow}{rgb}{1.,0.84,0.8}
\definecolor{Gold}{rgb}{1.,0.84,0.}
\definecolor{RedA}{hsb}{0.9,0.3,0.7}
\definecolor{RedB}{hsb}{0.9,0.3,1}
\definecolor{LightGray}{gray}{0.85}
\definecolor{Blue}{rgb}{0.,0.,1.}
\definecolor{Pink}{rgb}{0.9,0.75,0.8}
\definecolor{DarkGreen}{rgb}{1.,1.0,1.0}
\definecolor{DarkBlue}{rgb}{0.,0.5,1.0}
%\definecolor{Pink}{rgb}{1.,0.75,0.8}
\definecolor{LightCyan}{rgb}{0.88,1.,1.}
\definecolor{LightYellow}{rgb}{0.95,1.0,0.8}
\definecolor{red1}{rgb}{0.95,0.,0.}
\definecolor{mycol1}{rgb}{0.8,1,1}
\definecolor{mycol2}{rgb}{0.6,0.8,0.6}


%\slideframe[\psset{fillstyle=gradient,gradientHSB=true,gradmidpoint=0,
%                   gradbegin=RedA,gradend=RedB}]{scplain}

\newslideframe{IMAGE}{%
  \boxput{\rput(1,0){\includegraphics[scale=0.4]{iitlogo1.ps}}}{#1}}
\slideframe*{IMAGE}



\newpagestyle{au}{}{~~\textcolor{black}{Parallelization of Circuit Simulation}\hfill \rightmark  \hfill\thepage}
\pagestyle{au}
\newenvironment{Page}{\begin{slide*}}{\end{slide*}}


\newcommand{\heading}[1]{%
  \begin{center}
    {\large \bf \shadowbox{\color{black}{#1}} }
  \end{center}
  \vspace{1ex minus 1ex}}

\newcommand{\BigHeading}[1]{%
  \begin{center}
    {\huge \bf \shadowbox{\color{black}{#1}} }
    %{\huge \bf \shadowbox{\color{DarkBlue}{#1}} }
  \end{center}
  \vspace{1ex minus 1ex}}


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

\newcommand{\SlideColours}[3][black]{%
%\slideframe[\psset{fillstyle=gradient,gradientHSB=true,gradmidpoint=0,gradbegin=Pink,gradend=Pink}]{scplain}
\slideframe[\psset{linecolor=#1,fillcolor=#3,fillstyle=solid}]{scplain}
\color{#2}}
% #1 = frame line color (optional, default=black),
% #2 = foreground color, #3 = background color

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

\begin{document}

\SlideColours[black]{black}{mycol1}
%\SlideColours[mycol1]{black}{LightYellow}
\begin{Page}
\BigHeading{Parallelization} 
\BigHeading{of}
\BigHeading{Circuit Simulation}
\vspace{0.7in}
%\begin{center}
{\bf \it \textcolor{red}{Students}} \hspace{0.65in}    {\bf \it \textcolor{red}{Faculty}}  \\
Gaurav Trivedi 			    \hspace{0.28in}H. Narayanan (EE)      \\
Nilesh J. Bhattad		    \hspace{0.12in}Madhav P. Desai (EE)\\			
G. Anil Kumar                       \hspace{0.29in}Sachin Patkar (Maths) \\ 
V. Venkat Rao \par 
\vspace{0.6in} 
\hspace{1.7in}{\tiny EE Department,IITB}\\
%\end{center}
\end{Page}

%%% SLIDE 2
\begin{Page}
\BigHeading{\textcolor{black}{Motivation}}
{
\bi

\item To solve large circuits through {\bf \it \textcolor{red}{easily available, weakly connected}} cluster of computers.

\item Every general purpose circuit simulator has a {\bf \it \textcolor{red1}{DC-Analyzer}} in its innermost loop. So, we parallelize the DC analyzer.
\ei
}
\end{Page}


%%% SLIDE 
\begin{Page}
\BigHeading{\textcolor{black}{Application}}
{

{\bf \it \textcolor{red1}{DC-Analysis}} can be used to
\bi
\item Solve large {\bf \it \textcolor{red1}{ sparse linear equations}}. 
\item Solve {\bf \it \textcolor{red1}{pipe flow}} problems
\item Solve large{\bf \it \textcolor{red1}{Combinatorial Optimization}} problems (e.g. Min Cost flow problem)
\ei
}
\end{Page}


%%% SLIDE 3
\begin{Page}
\BigHeading{Introduction}
{
\bi
\im We decompose the circuit into {\bf \it \textcolor{red}{$k$-multiports}}. 
\im These decomposed $k$-multiports are solved independently in terms of {\bf \it \textcolor{red}{port conditions}}. This also gives {\bf \it \textcolor{red}{port behaviour}}. 
\im We use {\bf \it \textcolor{red}{port behaviour}} and {\bf \it \textcolor{red}{connection constraints}} between multiports for computing the port voltages and currents.
\im We use the decomposed multiports' solution in terms of {\bf \it \textcolor{red}{port conditions}} to get voltages and currents inside the multiports.
\ei
}
\end{Page}

%%% SLIDE 5 
\begin{Page}
\heading{Multiport Decomposition}
{
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[height=3.5in,width=3in]{Multidec.ps}
  \end{center}
\end{figure}
}
\end{Page}

%%% SLIDE 5 
\begin{Page}
\heading{Algorithm}
{
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[height=3.2in,width=3in]{original.ps}
	\caption{An example circuit}
  \end{center}
\end{figure}
}
\end{Page}

%%% SLIDE 5 
\begin{Page}
\heading{Algorithm}
{
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[height=3.2in,width=3in]{part.ps}
	\caption{Decomposed Circuit} 
 \end{center}
\end{figure}
}
\end{Page}

%%% SLIDE 5 
\begin{Page}
\heading{Algorithm}
{
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[height=3.2in,width=3in]{part1.ps}
	\caption{Port Behaviour Extraction} 
 \end{center}
\end{figure}
}
\end{Page}

%%% SLIDE 5 
\begin{Page}
\heading{Algorithm}
{
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[height=3.2in,width=3in]{part2.ps}
	\caption{Solving Individual Multiports } 
 \end{center}
\end{figure}
}
\end{Page}


%%% SLIDE 12 
\begin{Page}
\heading{Experimental Setup}
{
\bi

\im Experiments were performed on a cluster of {\bf \it \textcolor{red}{9-processors}} using a {\bf \it \textcolor{red}{10/100 Mbps unmanaged ethernet switch}}.
\im In this setup, one processor acted as {\bf \it \textcolor{red}{Master Processor}} and others were {\bf \it \textcolor{red}{Slave Processors}}. 
\im We used {\bf \it \textcolor{red}{ Multiport Decomposition}}. 
\im The speedup obtained approaches the number of processors provided the percentage of ports relative 
to total number of nodes is small {\bf \it \textcolor{red}{ (.5$\%$- 1$\%$)}}.
\vspace{0.2in}

\bi
\im As far as possible, access to the {\bf \it \textcolor{red}{hard disk}} is avoided.
\ei
\ei
}
\end{Page}




\begin{Page}
\heading{Circuit Description}
{
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\bf Circuit}  & {\bf Nodes } & { \bf Edges }   \\ \hline
g60k&  60,000  &  118940 \\ \hline
g105k& 105,000 &  208430 \\ \hline
g200k& 200,000 &  397420 \\ \hline
g300k& 300,000 &  596170 \\ \hline
g400k& 400,000 &  795900 \\ \hline
g500k& 500,000 &  994900 \\ \hline
g600k& 600,000 &  1194880\\ \hline
g700k& 700,000 &  1394860\\ \hline
\end {tabular}
\end {center}
\end {table}
}
\end{Page}

%%% SLIDE 13 
\begin{Page}
\heading{Results: 8-block partition}
\subheading{with {\bf \it \textcolor{red}{one slave processor}}}
{
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
{\bf Circuit}  & $t_{total}$ & $t_{comm}$ \\
                & (in sec)   & (in sec)   \\ \hline
g60k&  \hspace{0.1in}17& \hspace{0.1in}0     \\ \hline
g105k& \hspace{0.1in}36& \hspace{0.1in}1     \\ \hline
g200k& \hspace{0.1in}82& \hspace{0.1in}4     \\ \hline
g300k& \hspace{0.1in}125& \hspace{0.1in}4   \\ \hline
g400k& \hspace{0.1in}222& \hspace{0.1in}7   \\ \hline
g500k& \hspace{0.1in}282& \hspace{0.1in}7   \\ \hline
*g600k& \hspace{0.1in}417& \hspace{0.1in}10 \\ \hline
*g700k&  \hspace{0.1in}905& \hspace{0.1in}11 \\ \hline
\end {tabular}
\end {center}
\end {table}
}

* spilling out of RAM.

\end{Page}

%%% SLIDE 15 
\begin{Page}
\heading{Results: 8-block partition}
\subheading{Time for solving {\bf \it \textcolor{red}{Port Connection Diagram}}}
\subheading{by {\bf \it \textcolor{red}{2, 4}} and {\bf \it \textcolor{red}{8 Slave Processors}}}
{

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Circuit} & *$t_{2proc}$ &  *$t_{4proc}$ &  *$t_{8proc}$  \\
              & (in sec)  & (in sec)  &  (in sec)   \\ \hline
g60k&  \hspace{0.1in} 9   &\hspace{0.1in} 5&  \hspace{0.1in} 3     \\ \hline
g105k& \hspace{0.1in}19   &\hspace{0.1in}10&  \hspace{0.1in} 5     \\ \hline
g200k& \hspace{0.1in}40   &\hspace{0.1in}22&  \hspace{0.1in}12     \\ \hline
g300k& \hspace{0.1in}62   &\hspace{0.1in}34&  \hspace{0.1in}19   \\ \hline
g400k& \hspace{0.1in}121   &\hspace{0.1in}61&  \hspace{0.1in}33   \\ \hline
g500k& \hspace{0.1in}137   &\hspace{0.1in}77&  \hspace{0.1in}41   \\ \hline
g600k& \hspace{0.1in}223   &\hspace{0.1in}115& \hspace{0.1in}64   \\ \hline
g700k& \hspace{0.1in}437   &\hspace{0.1in}254& \hspace{0.1in}156  \\ \hline
\end {tabular}
\end {center}
\end {table}
\tiny
* $t_{2proc}$, $t_{4proc}$ and $t_{8proc}$ show the time spent in calculating {\bf \it \textcolor{red}{Port Behaviour}} using two, four and eight slave processors respectively.
\normalsize
}
\end{Page}

%%% SLIDE 16 
\begin{Page}
\heading{Results: 8-block partition}
\subheading{with {\bf \it \textcolor{red}{8 slave processors}}}
{

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
{\bf Circuit}  & $t_{total}$ & $t_{comm}$ \\
               & (in sec)   & (in sec)   \\ \hline
g60k& \hspace{0.1in} 4& \hspace{0.1in}0     \\ \hline
g105k&\hspace{0.1in} 7& \hspace{0.1in}1     \\ \hline
g200k&\hspace{0.1in}14& \hspace{0.1in}4     \\ \hline
g300k&\hspace{0.1in}21& \hspace{0.1in}4   \\ \hline
g400k&\hspace{0.1in}38& \hspace{0.1in}7   \\ \hline
g500k&\hspace{0.1in}49& \hspace{0.1in}7   \\ \hline
g600k&\hspace{0.1in}76& \hspace{0.1in}10 \\ \hline
g700k&\hspace{0.1in}220& \hspace{0.1in}11 \\ \hline
\end {tabular}
\end {center}
\end {table}

}
\end{Page}

%%% SLIDE 17 
\begin{Page}
\heading{Conclusion}
{
\bi
\im {\bf \it \textcolor{red}{Multiport Decomposition}} is a promising method of parallelization of circuit simulation.

\im {\bf \it \textcolor{red}{Port Connection Behaviour}} has been fully parallelized. 

\im Solution of the {\bf \it \textcolor{red}{Port Conductance Matrix}} needs to be parallelized.

\im Our results show speedups proportional to the number of processors
provided the blocks into which the network is broken up do
not have many ports in between {\bf \it \textcolor{red}{(number of ports $< 1\%$)}}.

\im The circuits of sizes up to {\bf \it \textcolor{red}{$700,000$ nodes}}
and {\bf \it \textcolor{red}{$1.4$ million edges}} have been solved by this technique in a few minutes using
facilities easy to obtain in any computational laboratory or
software house.

\ei

}
\end{Page}


\end{document}
