\documentclass[10pt,psfig,letterpaper,twocolumn]{article}
\usepackage{geometry}
\usepackage{graphics}
\usepackage{setspace}
\usepackage[scaled=0.9]{helvet}
%\usepackage{Mynatbib}
\singlespacing
\paperwidth 8.5in
\paperheight 11in
\oddsidemargin 0in
%\oddsidemargin -0.25in
%\topskip 0in
%\topsep 0in
\headsep 1.3cm 
%\headsep 6mm 
%\headheight 0in 
%\topmargin 0in
%\topmargin -0.25in
\geometry{left=0.75in,top=0.75in,right=0.75in,bottom=1in}
%\evensidemargin 
\textwidth 7in 
\textheight 9.25in
\columnsep 0.4in
%\headheight 0cm
%\footheight 1cm
%\footskip 0in 
%\partopsep -0.5cm
%\textfloatsep 0.3cm
%\intextsep 0.3cm

%\makeatletter
%\newenvironment{tablehere}{\def\@captype{table*}}{}

\pagestyle{empty} 
%\newenvironment{figurehere}
%  {\def\@captype{figure}}
%  {}
%\makeatother
\renewcommand{\abstractname}{\fontfamily{phv}\selectfont{\normalsize{\bfseries{ABSTRACT}}}}
\renewcommand{\refname}{\fontfamily{phv}\selectfont{\normalsize{\bfseries{REFERENCES}}}}
\addcontentsline{toc}{chapter}{References}
\begin{document}
\bibliographystyle{acm} 
%\bibliographystyle{plain} 

%\bibliographystyle{named} 
%\include{ref}


%\pagestyle{plain} 
%\def\Try#1#2{{\fontfamily{#1}\selectfont}}
\title{\fontfamily{phv}\selectfont{\huge{\bfseries{Parallelization of DC-Analyzer}}}}
\author{
{\fontfamily{ptm}\selectfont{\large{\bfseries{G. Anil Kumar}}}}\thanks{Texas Instruments, Wind Tunnel Road, Murugeshpalya, Bangalore-560017. email: anilk@india.ti.com }, \and
{\fontfamily{ptm}\selectfont{\large{\bfseries{Gaurav Trivedi}}}}\thanks{Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai-400076. email: trivedi@ee.iitb.ac.in}, \and 
{\fontfamily{ptm}\selectfont{\large{\bfseries{Madhav P. Desai}}}}\thanks{Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai-400076. email: madhav@ee.iitb.ac.in}, \and
{\fontfamily{ptm}\selectfont{\large{\bfseries{H. Narayanan}}}}\thanks{ Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai-400076. email: hn@ee.iitb.ac.in}\\
}
\date{}
\maketitle
\thispagestyle{empty}
\begin{abstract}
Physical problems offer scope for macro level parallelization of solution by their essential structure. For parallelization of
electrical network simulation, the most natural structure based method is that of {\it Multiport Decomposition}. In this paper
this method is used for the simulation of electrical networks consisting of resistors, independent and controlled sources using 
a distributed cluster of weakly coupled processors. 
Results are presented for the cases where the number of processors
are $1$,$2$,$4$,$8$ and for circuit sizes upto $700,000$ nodes and
$1.4$ million edges. We use a cluster of Pentium IV processors linked 
through a 10/100 Mbps ethernet switch.\\
\end{abstract}
{\fontfamily{phv}\selectfont{\normalsize{\bfseries{Keywords:}}}}
Multiport Decomposition, Parallel processor, simulation.
\section*{\fontfamily{phv}\selectfont{\normalsize{\bfseries{INTRODUCTION}}}}

It is becoming increasingly necessary to solve very large circuits
accurately because of higher chip densities and also
because of the incorporation of high frequency effects.
Usually such circuits are too large to be solved on a single
processor and some form of distributed computing \cite{DON} has to be resorted to.
We have chosen the model of cluster computing in which all the processors are connected 
through  weak media. This level of resources is easy to obtain in almost any computational
laboratory or software house. \par

The general approach used by us to parallel process a circuit simulator 
is to decompose the circuit into $k$ `multiports'. These
decomposed $k$ multiports are solved independently. After obtaining the port behaviour 
we use the connection constraints between multiports
for computing the port voltages and currents.
It is necessary therefore that decomposed
blocks should have minimum interconnection between themselves.
Every general purpose circuit simulator has a {\it DC-Analyzer} at its core. 
In any iteration of non-linear circuit analysis a circuit simulator solves a 
circuit consisting only of elements: resistors (R),controlled sources (CS), 
voltage sources (V) and Current sources (J). Thus, We can exploit parallelism, first, by parallelizing each 
iteration of the non-linear analysis \cite{SIE} and second, by parallelizing the {\it DC-Analyzer} 
\cite{GAK,NJB,GT} itself. 

\section*{\fontfamily{phv}\selectfont{\normalsize{\bfseries{MULTIPORT DECOMPOSITION AND METHOD USED}}}}

A electrical circuit is divided into $k$ parts by using {\it Multiport Decomposition} \cite{HN} in such a way that there is no 
interaction between the $k$ parts. The decomposed parts may be large but the number of ports should be minimum. \par
A network $N$, which is to be decomposed into two multiports, is given in figure \ref{multi}. $N_{A}$ and $N_{B}$ are the 
subnetworks of $N$. Assume that the devices in both of the network are decoupled.
It can be seen that the currents in $N_{B}$ can affect the currents in $N_{A}$ or vice-versa
according to the KCE constraint at $n_{1},n_{2}$. Simultaneously voltages in $N_{A}(N_{B})$ can affect the
voltages in $N_{B}(N_{A})$ because voltage $v_{1} = v_{n_{1}} - v_{n_{2}}$. Thus the constraint on
all currents and voltages of $N$ remain the same if we replace the network by the decomposed network. Both 
the original and decomposed networks are shown in figure \ref{multi}. The conditions 
$v_{P} = v_{P^{'}}, i_{P} = -i_{P^{'}}$, are imposed by the {\it port connection diagram} which is shown by two dotted lines in
parallel in figure \ref{multi}. 

\begin{figure}[!ht]
{\centering \resizebox*{3in}{3in}{\includegraphics{fig6.ps}} \par}
\caption{\fontfamily{ptm}\selectfont{\normalsize{Multiport Decomposition Technique}}}
\label{multi}
\end{figure}

The method used for circuit decomposition is {\it Multiport Decomposition}. The analysis is
performed by {\it DC-Analyzer} \cite{SHBP} which uses the {\it Two-Graph Method} \cite{SHBP}. An elementary 
partitioner was used to obtain the graph of the network into subgraphs of approximately equal size with very
few common nodes. {\it PVM} \cite{PVM,PVMS} is used for communicating among processors. Implementation details are given in
\cite{GAK,NJB,GT}.

\section*{\fontfamily{phv}\selectfont{\normalsize{\bfseries{RESULTS}}}}

Parallelization of DC-Analyzer was implemented using the network of PIV 1.6 GHz processors each having 
256MB RAM. Processors used were connected through a 10/100 Mbps Switch. Results are given for different circuit sizes.
In each circuit voltage and current sources are kept constant at $14\%$ and $7\%$ of the circuit size respectively. 
Results are presented for the $8$ block partitions. For comparison, we have given the results for a $10$ block partition with $2$
slave processors. Here, $t_{1},t_{2},t_{4}$ and $t_{8}$ is the total time (in seconds) taken by $1,2,4$ and $8$ slave processors.  
\begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} 
\hline
{Circuit} & 
\multicolumn{4}{c|}{8-block Partition} & 
10-block Partition\\ \cline{2-6}
     & $t_{1}$ & $t_{2}$ & $t_{4}$ & $t_{8}$& $t_{2}$\\ \hline 
g60k &17  & 10 &  6 &  4 & 11 \\ \hline 
g105k&36  & 21 & 11 &  7 & 23 \\ \hline 
g200k&82  & 43 & 25 & 14 & 52 \\ \hline 
g300k&125 & 64 & 36 & 21 & 84 \\ \hline 
g400k&222 & 126& 66 & 38 & 131\\ \hline 
g500k&282 & 145& 85 & 49 & 178\\ \hline 
g600k&417 & 237& 129& 76 & 281\\ \hline 
g700k&905 & 504& 319& 220& 490\\ \hline
\end {tabular}
\end {center}
\end {table}
\section*{\fontfamily{phv}\selectfont{\normalsize{\bfseries{CONCLUSION}}}}
In this paper a method of parallelization of circuit simulation
is outlined which is based on the structure (topology) of the network
viz. {\it Multiport Decomposition}.
We use this method to parallelize the DC-Analyzer noting that 
since a DC-Analyzer lies at the core of every general purpose simulator, this would amount
to parallelizing the circuit simulator.
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 (number of ports $< 1\%$).
We find it interesting that a method which uses no 
sparsity exploiting technique except the simple structural one 
of multiport decomposition does as well as can be hoped for with the best 
kind of parallelization. We note that circuits of sizes up to $700,000$ nodes
and $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.
\bibliography{ref}
\end{document}
