
\documentstyle[11pt]{article}

\input{psfig}
\input epsf

\textwidth=6.0in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in
 
\pagenumbering{roman}

\begin{document}

\begin{center}

{\LARGE \bf Phase 2 Final Report\\} 
\vspace*{1.0cm}
{\LARGE \bf
High Performance Computing and Parallel \\
Processing in the Utility Industry \\}
\vspace*{0.8cm}
{\Large \bf NMPC Project 07-9199} \\
\vspace*{1.5cm}
{\Large Northeast Parallel Architectures Center \\
\vspace*{0.2cm}
Syracuse University} \\
\vspace*{1.5cm}
{\Large December 13 1994} \\


\end{center}


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgements}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The people at Syracuse University who have worked on this project are: 
\begin{itemize}
\item {\bf Northeast Parallel Architectures Center} 
 \vspace*{0.1cm} \\ 
 Prof. Geoffrey Fox (Principal Investigator) \\
 Dr. Paul Coddington (Project Leader) \\
 Prof. Sanjay Ranka \\
 Prof. Salim Hariri \\
 Prof. Alok Choudhary \\
 Dr. James Allwright \\
 Kamala Anupindi \\
 David Koester \\
 Alvin Leung \\
 Siva Narendra 
\item {\bf School of Information Studies} 
 \vspace*{0.1cm} \\
 Prof. Mike Nilan \\
 Richard Southwick  \\
 Caren Obad 
\end{itemize}

\noindent
We have received invaluable help and guidance from the following people
at Niagara Mohawk Power Corporation: 
\begin{description}
 \item ~~\vspace*{-0.6cm}\\
 Sid Lipton (Project Co-ordinator) \\
 Larry Eng    \\
 Bill Merritt \\
 Wes Yeomans  \\
 Jack Brennan \\
 Danielle Dylan  
\end{description}

\noindent
The following people gave their time for interviews to develop the knowledge
base for the transient stability analysis expert system:
\begin{description}
 \item ~~\vspace*{-0.6cm}\\
 Larry Eng (NMPC), 
 Ricardo Gonzalez, Jonathon Mayo, Robert Waldele (NYPP),
 Michael Henderson, Larry Hochverg, Paul Roman, George Dunn (NYPA). 
\end{description}

\noindent
We have also benefited greatly from discussions with the following people: 
\begin{description}
 \item ~~\vspace*{-0.6cm}\\
 Tony Skjellum (Mississippi State University)  \\
 Joel Saltz (University of Maryland)  \\
 Chris Pottle (Cornell University)  \\
 David Wong (Ontario Hydro)  \\
 Nelson Simons (General Electric) \\ 
 Rana Mukerji (General Electric)  
\end{description}


\newpage

\tableofcontents

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{List of Acronyms}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{tabular}{ll}
{\bf AI}      & Artificial intelligence \\
{\bf BDF}     & Backward Differentiation Formula \\
{\bf CRPC}    & Center for Research on Parallel Computation \\
{\bf DAE}     & Differential Algebraic Equation \\
{\bf DEC}     & Digital Equipment Corporation \\
{\bf DSA}     & Dynamic Security Assessment \\
{\bf EMS}     & Energy Management System \\
{\bf EPRI}    & Electric Power Research Institute \\
{\bf ESEERCO} & Empire State Electrical Energy Research Corporation \\
{\bf ETMSP}   & Extended Transient Mid-term Stability Program \\
{\bf EUI}     & External User Interface \\
{\bf FDDI}    & Fiber Distributed Data Interface \\
{\bf GE}      & General Electric \\
{\bf HPF}     & High Performance Fortran \\
{\bf IBM}     & International Business Machines \\
{\bf IST}     & School of Information Studies \\
{\bf JCL}     & Job Control Language \\
{\bf MAPS}    & Multi-Area Production System \\
{\bf MIMD}    & Multiple Instruction Multiple Data \\
{\bf MPI}     & Message Passing Interface \\
{\bf MW}      & MegaWatts \\
{\bf NMPC}    & Niagara Mohawk Power Corporation \\
{\bf NPAC}    & Northeast Parallel Architectures Center \\
{\bf NUG}     & Non-Utility Generator \\
{\bf NYPP}    & New York Power Pool \\
{\bf NYPA}    & New York Power Authority \\
{\bf ODE}     & Ordinary Differential Equation \\
{\bf OLTSP}   & On-Line Transient Stability Program \\
{\bf PTI}     & Power Technology Inc. \\
{\bf SGI}     & Silicon Graphics Inc. \\
{\bf SIMD}    & Single Instruction Multiple Data \\
% {\bf STAG}    & ??? \\
{\bf SVC}     & Static VAR Controller \\ 
{\bf TASC}    & The Analytic Sciences Corporation \\
{\bf VAR}     & Volt-Amperes Reactive \\ 
\end{tabular}



\newpage


\pagenumbering{arabic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\addcontentsline{toc}{section}{Executive Summary}
\section*{Executive Summary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection*{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This project addresses the development of applications using high
performance computing, and in particular parallel processing, 
in the utility industry.
In Phase 1 of the project we described the feasibility and benefits
of using parallel computers within the industry, to improve the speed and 
accuracy of computer simulations in a number of areas.
We also explored the use of parallel computing and expert systems
to enable new capabilities that would be of benefit to NMPC.

The second phase of the project involved extending the research done in 
Phase 1, and developing and benchmarking prototype software for one 
particular application,
transient stability analysis. Algorithms were developed and implemented
on parallel computers to perform fast transient stability calculations,
and to automate the analysis of these calculations to enable the 
production of a fast on-line transient stability analysis package
that can be used as part of an Energy Management System (EMS).

One of the most difficult problems involved in developing a parallel 
transient stability analysis program is the implementation of a fast,
efficient sparse matrix solver, which is a notoriously difficult problem.
A large part of this work involved the development of a parallel 
sparse matrix solver.

Setting limits for the stable operation of the electrical network 
involves simulations that are very computationally intensive, 
and the analysis of the results is quite complex. For these reasons it is
currently done very infrequent by a group of planning engineers, and
therefore must use worst-case scenarios. 
The use of high performance computing and expert systems can enable the
development of a fast on-line transient stability analysis program which
would allow stability limits to be set dynamically based on actual 
operating conditions. 
This would provide less conservative estimates
of required generation and transmission reserves.

Due to the large scale of the power industry, even a small reduction
in operating overhead translates into large savings.
Estimates have indicated that the reduced operating margins that would
be allowed by dynamic security assessment 
could save NMPC millions of dollars per year.
This would also save energy resources and reduce environmental impact.

The Electric Power Research Institute (EPRI) has recognized this 
opportunity and is coordinating a major program to develop a program
for Dynamic Security Assessment (DSA), based on high performance 
workstation clusters and advanced expert systems.



\subsection*{Project Overview}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A major goal of this project is to reduce the time required for
transient stability analysis to 
the point where it can be used on-line in an Energy Management System, 
to assist in setting near-real-time stability limits. 
This requires:
%
\begin{itemize}
\item The development of an expert system and user interface for 
      classifying the output of the transient stability program as stable
      or unstable, and providing a method for using multiple transient 
      stability simulations to find stability limits.
\item The development of a fast on-line program for transient stability 
      analysis on high performance computers,
      that can be utilized by this expert system to allow the 
      on-line determination of stability limits.
\end{itemize}

\medskip
\noindent
{\bf Phase 1} of this project involved research to study the feasibility
of using parallel processing and expert systems for utility applications,
and the development of parallel algorithms and expert system rules 
for specific applications.\\
\\
{\bf Phase 2} of the project was the development and benchmarking of
prototype parallel programs and expert systems software. \\
\\
{\bf Phase 3} involves developing, documenting and testing production-grade
software which can be used at NMPC. \\


This report presents the work done in Phase 2 of the project. 


\subsection*{Parallel Computing for the Utility Industry}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Parallel computing has recently become a much more attractive option
for industrial applications, due to the introduction of powerful 
parallel computers based on standard workstations developed by 
mainstream computer companies such as IBM and DEC,
and the development of standardized portable parallel languages 
such as High Performance Fortran (HPF), a parallel extension to 
Fortran 90, and the Message Passing Interface (MPI), standardized
routines for passing data between processors.
Parallel computers based on workstation clusters offer an extremely
good ratio of price to performance, and software written in standard 
sequential languages can be run on each processor.

We believe distributed memory parallel computers based on 
workstation clusters, such as the IBM SP-2, 
are the most suitable high performance computers for the utility industry.
The architecture of these parallel machines is well-suited to the type
of applications used in an Energy Management System.
These machines also allow a much simpler integration and parallelization 
of programs developed for single workstation platforms, which are becoming 
a standard for computationally intensive utility applications.

For example, the program used for contingency evaluation at NMPC 
has been  %??
ported to the IBM RS/6000, so it would be quite straightforward to
implement this program in parallel on the IBM SP-2, where it could
do computations for different contingencies independently on different
processors.

The increased performance of these machines can also enable some
simulations that were previously done off-line, such as as unit commitment
and transient stability analysis, to be brought on-line and integrated
on a real-time basis with the Energy Management System.
This should allow a significant reduction of operating margins.


\subsection*{Transient Stability Analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Transient stability analysis examines the dynamic response of the power 
network for several seconds following a disturbance. 
The dynamics of each generator in the system is described by multiple 
differential equations, while the coupling between generators through the 
electrical network is described by non-linear algebraic equations. 
Together these lead to a system of differential-algebraic equations (DAEs).

The standard algorithms used for transient stability analysis decouple
this system into independent differential and algebraic equations.
The differential equations are solved using numerical integration,
while the algebraic equations are solved using iterative methods,
with each iteration requiring the solution of a set of linear
equations using sparse matrix techniques.
Transient stability analysis is very computationally intensive.
We are aiming to reduce the computation time by using parallel processing.

We are basing our work on the EPRI Extended Transient Mid-term Stability 
Program (ETMSP). Parallelizing this program involves two different
methods for the two different aspects of the program -- solving the 
generator equations and solving the nework equations.

The generator equations are almost completely independent, 
and thus should be easily 
parallelized. However the ETMSP program is not written in a manner
such that this independence can be easily utilized. We have identified
the problems involved and done some restructuring of the program to 
allow the setting up of the generator equations to be done in parallel. 
This accounts for about 20\% %?? 
of the work involved in solving the generator equations.
Solving the generator equations can also be done in parallel, but
this will require more restructuring of the code.

Solving the non-linear network equations involves an iterative method 
which requires the solution of large sparse matrix equations, 
where the sparse matrix represents the connectivity of the
electrical network. This part of the program can only be parallelized 
by using a parallel sparse matrix solver. Again, the integration of 
such a solver into ETMSP is not a simple task, since the program is 
structured and optimized for a specific sequential sparse matrix 
solution technique, and lacks the flexibility for easily interfacing
to a different solver. We have had to make substantial changes to the 
program to allow us to interface to a parallel sparse matrix solver.

So far we have parallelized certain sections of the program independently
of one another. To implement a
fully parallel version of ETMSP would require a substantial amount of
effort to integrate these different sections, which would also require 
further restructuring on the program. This would only be feasible if it
was done in collaboration with EPRI and the developers of the ETMSP 
program. This would be a major software engineering effort.

We believe it is feasible to parallelize the ETMSP transient
stability program and obtain speed-ups of around 10 on 16 processors.
This would require a speed-up of only 5-10 for the parallel sparse 
matrix program. 
This should be achievable with a better implementation of the MPI 
communications software on the IBM SP-2, which should be available 
very soon.
Speed-ups of greater than 10 on any number of processors will be difficult
to obtain, due to overheads from the communication of the data between
processors and imbalance in the distribution of the workload between 
processors. 
However a speed-up of 10 would allow near real-time transient stability 
analysis, which would be good enough to enable the development of an on-line 
program for setting stability limits.

Interfacing ETMSP to more advanced DAE solvers has proven to be an even
more difficult problem, since much of the program is ``hard-wired'' to 
the current solution technique. It would be a major undertaking to 
restructure the program to allow it to utilize these solvers.
However these methods are very attractive, since they should offer greater
accuracy for reduced computational cost, and parallel versions of these
algorithms already exist, which would make parallelization of the 
program very straightforward.


% We plan to benchmark a number of different parallel sparse solvers. ???


\subsection*{Sparse Matrix Algorithms} % ???
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Most simulations of power networks require the solution of large sets of 
sparse coupled linear equations, which is done using sparse matrix 
techniques.
Sparse matrix solvers require complicated and irregular data structures,
and are therefore much more difficult to parallelize than dense matrix
solvers, which are very regular.
Implementing an efficient parallel sparse
matrix solver has thus proven to be an extremely difficult task, and
can usually only be achieved by using problem-specific methods that 
identify and effectively utilize any structure present in the sparse
matrices.
General methods, although they exist, are usually less than optimal.

Power networks tend to be hierarchical in structure, and this can be
utilized to order the matrices into a structured 
block-diagonal-bordered form, where non-zero data elements occur
only in the borders and in blocks along the diagonal of the matrices.
We have performed a theoretical examination of the parallelism available
in block-diagonal-bordered matrices and developed software to
order matrices into this form.
We are developing parallel algorithms for two standard linear solvers --
Choleski factorization for symmetric matrices 
(which occur in many power 
systems problems, such as calculating network power flows),
and LU factorization for non-symmetric matrices 
(which occur in transient stability analysis).

We have developed two parallel sparse matrix solvers based on 
block-diagonal-bordered ordering of the matrices -- an LU direct
solver and a Gauss-Seidel iterative solver.
These algorithms have been implemented on a Thinking Machines 
CM-5 parallel computer using two different message-passing paradigms
(Active Messages and standard communications protocols), and ported 
to the IBM SP-2 using Message Passing Interface (MPI) communications
software.

The LU program gives speed-ups for LU factorization of 
10 or more on the CM-5 using Active Messages, 
and 5-10 using standard message passing protocols.
The development of the IBM SP-2 is recent enough that we have only been
able to use a preliminary implementation of the communications software, 
and the results have been less impressive. However an improved 
implementation of the software should be available very soon and we
expect the results to be similar to those on the CM-5 using standard
message passing.

Note that a speed-up of 5-10 in the sparse matrix solver is enough to 
provide an overall speed-up of 10 or more for a parallel 
implementation of the ETMSP transient stability program, since the
rest of the program can be very efficiently parallelized.

The speed-ups for the iterative Gauss-Seidel algorithm are not as good, 
although the overall time to obtain the solution is better than LU.
However this algorithm is not as numerically stable as the direct LU
solver, and we have seen problems with non-convergence using matrices
produced by the EPRI program. The Gauss-Seidel approach appears to have
substantial merit, however more work needs to be to carefully 
integrate it with the ETMSP solver, in order to overcome the numerical 
stability problems.


\subsection*{Expert System and User Interface}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In order to provide an on-line transient stability program, there must
be an automated procedure for analyzing the output of the program, and
classifying the results as being stable or unstable.
This is a complex task that is currently done off-line by a trained engineer.
Our approach to automating this process is to develop an expert system 
that solves the problem in the same way as a human engineer.
This expert system should be useful not only for on-line applications,
but also in helping the engineer in traditional off-line transient 
stability studies. Programs for transient stability analysis produce
tremendous amounts of graphical output which must be analyzed.
An expert system would be able to prioritize or filter this data,
and present the engineer with the results that are most useful for
making a decision.

In Phase 1 of this project, we conducted interviews with NMPC and 
New York Power Pool engineers to determine
criteria for classifying transient stability results, and used this
information to construct a decision model for this process.
This was used as input for the knowledge base of an expert system
for classification of transient stability results.
We have implemented a prototype version of this expert system.
This has been integrated with the ETMSP transient stability program.
This involves some post-processing of the transient stability output,
with the results passed to the expert system for stability classification.

Stability assessment of the simulation results is only one part of the 
process of setting transient stability limits. 
The engineer must also choose appropriate contingencies and 
parameter values in order to find the limiting value for a certain component
or interface, above which the network becomes unstable. 
This is a more difficult problem, but it can also be 

This involves configuring the expert system as a driver for the ETMSP 
program, so that the expert system sets the input parameters, 
starts an ETMSP run, analyzes the results, and then depending on the
results, can submit a new run with different parameters.
This process is iterated until the stability limit it found.



\subsection*{On-Line Transient Stability Analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\subsection*{Conclusions and Recommendations for Future Work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}


