
\documentstyle[12pt]{article}
\nonstopmode
\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}
\renewcommand{\baselinestretch}{1.30}
\textwidth=6.0in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in

\input{psfig}

\begin{document}

\section{Background}

    The rapid increase in computer performance has led to increased
opportunities in the application of computing to the power systems industry.
The report, "Comprehensive Study of Supercomputing and its Applicability
to the Utility Industry" by TASC, concludes that by 1995, even small
improvements in operations, peak reduction, transmission, and avoided
customer interruption "can translate into total annual dollar savings that are
nearly an order of magnitude greater than the annual cost of operating a
supercomputer."  In a Niagria-Mohawk internal memorandum by Bill Merritt to Larry Kuhl
dated
15 July 1992, it is
proposed that improved contingency analysis and transient stability analysis
could save Niagria Mohawk 
{\bf \$1.7 million} per year without sacrificing system
reliability by intelligently reducing the present operating margins.  Additional analysis capability
could determine safe generator dispatches that reduce the present conservative
operating margins used today.  The magnitude of this additional analysis will require
supercomputing capabilities in order to develop timely analysis for operations staff
to make informed decisions.  

    It is widely recognized within the computer industry that increased
supercomputer speeds will necessarily involve parallel computing.  This is
evidenced by the plans for parallel computing by such traditional
supercomputing companies as Cray, Digital and IBM and by the success of
parallel supercomputers like the Connection Machine.  The Federal High
Performance Computing and Communication Initiative (FHPCCI) both
endorses this concept and will accelerate progress.  The Syracuse University
team is at the leading edge of this initiative and currently funded by DARPA
to produce portable software systems for parallel machines.  Furthermore,
considerable experience has been gained in recent years on a variety of
parallel computing architectures.  For example, the Caltech Concurrent
Computation Program, while it was under the direction of Geoffrey Fox, was
able to successfully implement 50 large parallel application codes from all
areas on the hypercube architecture.

    Parallel computing has now been developed to the point where it is
possible to examine computationally intense computer applications; for example,
those computer programs required to support daily power utility operations; to determine what parallel algorithms can
implement those applications and to determine the most effective parallel computer
architecture to run those algorithms.  Without a doubt, concurrent processing
architectures will be the basis for forthcoming teraflop ({\em trillion} floating
point operations per second) supercomputers.  Extensive contingency analysis or detailed,
accurate transient stability analysis will require these impressive computing
capabilities.
However, parallel processing requires the algorithms and software to be
rethought and often reimplemented.  This critical issue
is a key point of this proposal.

    The Syracuse Team has excellent qualifications, indicated by the
DARPA project mentioned above and by our membership in the prestigious
NSF Science and Technology Center devoted to making parallel computation
practical.  In this project, we are involved in parallel software and direct all
the parallel application work at the participating institutions (Caltech, Rice,
Syracuse Universities and Los Alamos National Laboratory).  Our proposed
project for Niagara Mohawk also benefits from the State funded ACTION-NYS,
which provides infrastructure support and cost sharing for the parts of
the project which have generic value to the power industry.

    We expect that the use of high-performance parallel computers
will permit additional system modeling during daily operations, and this additional
knowledge of the system status will have direct benefits for Niagara Mohawk.
Daily planning activities that examined stability analysis were previously impossible due
to
their extensive run-times.  Significantly faster computational capabilities will allow
operating
the system with more conservative margins, thus saving money while maintaining the
present standards for reliable operations or possibly even improving system reliability.
Reduction of operating margins may even affect the need to expand generation capability.
In addition, reduced fuel consumption, saved by eliminating excessive operating margins,
will have positive affects on environmental impact.  Reduced fuel consumption can equate
to
reduced emissions.
Reducing costs without sacrificing system reliability and reducing the environmental
impact of
generator emissions will benefit consumers and both corporate image and corporate profits.




\section{Parallel Sparse Matrix Algorithms}

    Sparse matrices are some of the most challenging problems for parallel
machines, but they are key to power system transient stability analysis, in addition to
many other power system 
applications.  Significant progress has already been made with concurrent sparse matrix
solvers.  Various organizations have efforts in progress to develop general sparse matrix
solvers.  There has already been substantial work
in
this area especially by Michael Heath at Oak Ridge National Laboratory and
Ian Duff in Europe and groups at Sandia.
We have a student
working with a group at Livermore Laboratory National Laboratory on a related gas pipeline
simulation.  Several of these efforts are currently being monitored.  In addition, a  Computer
Information Science (CIS) Ph.D candidate at Syracuse University is presently
working under our supervision on parallel sparse matrix techniques especially suited 
for power systems applications. 
During this study phase, parallel sparse matrix solvers will be developed that interface
with the differential-algebraic equation solvers also being investigated.  

	The in-house research at Syracuse University will develop specialized sparse matrix
solvers that exploit hierarchical structure in the underlying problem.  Sparse matrices
result when solving the differential-algebraic equations that represent the generator
differential equations and the power distribution network when examining system
dynamics that result from a fault in a transient stability analysis.  
During the first study phase, in addition to monitoring work by Heath on general
sparse matrix solvers, three competing 
techniques
will be examined to solve sparse power system matrices:
\begin{enumerate}
\item direct methods
\item iterative methods, and
\item composite direct/iterative methods.
\end{enumerate}
Critical to any of these approaches are techniques to reorder the linear sparse matrices
to exploit the underlying hierarchy.  For direct techniques, reordering enhances
parallelism, by identifying independent portions of matrices that can be computed with
minimal interprocessor communications.  Also for direct techniques, optimal reordering
will minimize the number of calculations by limiting the added calculations due to
fillin.  For iterative techniques, such as waveform relaxation, reordering according to
the hierarchical nature of the underlying problem is required for rapid convergence.
Reordering can be used to improve load balancing for either direct or iterative
techniques.  

	Diakoptics theory and the actual matrix sparsity structure (the power distribution
network structure) will be used to 
develop algorithms to reorder the sparse matrices resulting from power system
applications into block-bordered diagonal form. Figure~\ref{Two-layer}
illustrates how Diakoptics could be used to reorder a sparse matrix representation of a
network into this highly desirable form.  Several layers of hierarchy may exist in
state or regional power networks.  Figure~\ref{Three-layer} illustrates a recursive reordering
of a three-layer hierarchical network.  The differential-algebraic equations for a power
system transient stability problem can be represented in block bordered diagonal form as
depicted in figure~\ref{SM-TSA}.  There are distinct portions of the matrix that
represent the generator differential equations and the power distribution network.  By
reordering the power distribution network, additional independent matrix partitions
are available.  
After the matrix is reordered according to the underlying
structure, additional reordering may be required to more effectively balance the number
of calculations.  Reordering to balance the load for individual processors often requires the
trade-off where the number of equations in the border is expanded in the process of
equalizing the number of floating point operations in the independent blocks.  Load
balancing could result in slightly more calculations, however, the effect of
additional calculations should be mitigated by a better distribution of all 
calculations over the multiple processors.  This is illustrated in figure~\ref{Trade}.

\begin{figure}

  \vspace*{2in}
  \special{psfile=prop1.ps
           vscale=60 hscale=60
           voffset=0 hoffset=108}
  \caption{Two-Layer Hierarchical Network \label{Two-layer}}
\end{figure}

\begin{figure}
  \vspace*{2in}
  \special{psfile=prop2.ps
           vscale=60 hscale=60
           voffset=0 hoffset=150}
  \caption{Three-Layer Hierarchical Network \label{Three-layer}}

  \vspace*{2in}
  \special{psfile=prop3.ps
           vscale=60 hscale=60
           voffset=0 hoffset=150}
  \caption{Transient Stability Analysis Sparse Matrix Form \label{SM-TSA}}

  \vspace*{2in}
  \special{psfile=prop4.ps
           vscale=60 hscale=60
           voffset=0 hoffset=86}
  \caption{Tradeoff of Load Balance and Fillin in the Matrix Borders \label{Trade}}
\end{figure}

	For pure direct methods, there are four sequential steps:
\begin{enumerate}
\item parallel factorization of independent blocks
\item parallel factorization of coupling equations 
\item parallel forward reduction, and 
\item parallel backward substitution.
\end{enumerate}
These individual steps are clearly illustrated in figure~\ref{PD-tech}.  By reordering the
matrix into block-bordered diagonal form, many of the operations that would be sequential
in a general solver (for example, parallel forward reduction and parallel backward
substitution) are now highly parallel.  This will simplify the
development of scalable, transportable algorithms.  Iterative waveform relaxation 
techniques would solve the tightly coupled equations in the blocks first, then
include the coupling equations.  Iterative techniques with rapid convergence could be
used concurrently in the independent blocks, while concurrent solutions of the entire set
of equations would require slower convergent algorithms.  Composite direct/iterative
techniques could solve the equations in the blocks by direct methods, then iteratively
update the answers to consider the interconnections.  The direct solution of independent
blocks can be viewed as a preconditioning step for the overall iterative solution.  The
benefit of this technique is that fillin in the borders of the block-bordered diagonal
matrix is eliminated, possibly reducing the number of calculations.  

\begin{figure}
  \vspace*{2in}
  \special{psfile=prop5.ps
           vscale=60 hscale=60
           voffset=0 hoffset=130}
  \caption{Parallel Direct Techniques \label{PD-tech}}
\end{figure}


    Parallel sparse matrix solvers are critically dependent on a proper
match between particular problem and machine architecture and "general approaches" are
often less than optimal.
It is essential to have matrices of representative sizes to successfully research  this real-life problem. 
We will work with Niagara Mohawk to obtain
the actual structure of the 
transmission network for three interconnected power grids:
\begin{enumerate}
\item Niagria Mohawk's network
\item the New York State Power Pool network, and
\item the Eastern US regional power network.
\end{enumerate}
It would not be surprising if our research indicates that different techniques are applicable for the different size
networks.   The problem size will also influence the applicable hardware.  

	We expect that transient stability analysis for 300 generators and a
2000 bus network system would perform
well on the 32 node MIMD computers that NPAC presently has.  However, a "small,"
say 10 generator and 50 bus network, system would not have enough parallelism to easily
make use of existing parallel computers.  Meanwhile, the large 10 teraflop ($10^{13}$ floating point operations
per second) parallel supercomputers available in the year 2000 will probably
contain 10,000 nodes.  This will be too much parallelism for a simulation of
Niagara Mohawk's system but could be well suited for the transmission
system covering a large geographic area.  The coordination of grids over a
large region may be an exciting possibility opened up by the parallel
supercomputers of the future.  

	An additional source of parallelism in the power system
transient stability problem, is the examination of multiple, independent  fault events simultaneously.
Such a technique could significantly improve parallel computer speed-up and efficiency by matching Niagria Mohawk's
requirements to available computer architectures.  The solution of the class of
concurrent problems where there is precedence in the order of the calculations, such
as the solution of linear equations, generally
has monotonically decreasing efficiency as the number of processors is increased.
However, transient stability analyses for independent faults can be processed 
totally independently.  To better describe this phenomenon, an example will be
presented.  

	Presently, scalable general sparse matrix solvers developed by Heath yield
compounded speedups of 1.5 for every time the number of processors is doubled.  For a
transient stability analysis on a 64 ($2^{6}$) processor MIMD parallel computer, 
eight independent faults can be analyzed using eight processors per
fault in the same time that only three independent faults can be analyzed if all 64
processors are dedicated to analyzing a single fault at a time.  The use of all 64
processors, however, could yield the solution to a single transient stability fault
in only 30\% of the time required for eight
processors, If time permits, it is cost effective to spread the multiple independent
cases to separate groups of processors, and
exploit the requirement to examine multiple faults to
enhance efficiency.  This exploitable parallelism is depicted in
figure~\ref{Con-imp}.  It is our belief that the specialized sparse matrix algorithms 
being developed for this effort can significantly improve upon the speedups reported
in this example for a general sparse
matrix solver.  

\begin{figure}
  \vspace*{4in}
  \special{psfile=prop6.ps
           vscale=120 hscale=120
           voffset=0 hoffset=0}
  \caption{Exploitable Parallelism \label{Con-imp}}
\end{figure}




\end{document}
\endinput



