
%  TO DO
% =======
%
% Edit Sparse matrix section, plus intro and conclusion, DAEs
% Parallel Computing section needs checking.
%


\documentstyle[11pt]{article}

\input epsf

\textwidth=6.0in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in
 

\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:Intro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Project Objectives}
\label{sec:Objectives} 

The goal of this project is to evaluate the possible use of high performance
computing, and in particular parallel processing, in the utility industry.
This is being done in two ways: 
\begin{enumerate}
\item A general survey of utility applications (in particular those used
      at NMPC) to identify those for which parallel processing could be
      effectively and beneficially utilized.
\item A detailed study of two particular applications, unit commitment and 
      transient stability analysis, and the development of parallel algorithms
      for these two applications.
\end{enumerate}

The main focus of this project 
is the development of a parallel transient stability program and associated
expert system which can be used on-line in a control room 
Energy Management System (EMS) to set 
dynamic transient stability limits.
This is perceived as potentially being of substantial benefit to NMPC,
in terms of cost savings and improved network reliability.
The techniques and algorithms used to develop such a system should also
be applicable to other areas of power systems simulation.

\begin{description}
\item [] Phase 1 of this project was a study of the feasibility of using
      parallel processing and expert systems for these applications. 
%
\item [] Phase 2 of the project is to develop and benchmark prototype parallel 
      programs and expert systems software.
%
\item [] Phase 3 involves developing, documenting and testing production-grade
      software which can be used at NMPC.
\end{description}


\subsection{Overview of the Report}
\label{sec:Overview} 

In this report we present the results of Phase 1 of this project, 
the feasibility study, and also discuss some of the work planned for
the future.

In section~\ref{sec:UnitComm} we study two different optimization methods for 
solving the unit commitment problem, and the use of parallel processing
to find better solutions in a shorter time.

In the following sections we examine the use of parallel processing to 
improve the performance of the security model for the on-line EMS used
at NMPC.

Section~\ref{sec:ContEval} investigates the use of parallel processing to 
improve contingency evaluation simulations.

Section~\ref{sec:TSA} examines methods for speeding-up transient
stability analysis, including improved sequential algorithms and the
requirements for developing a parallel transient stability program.

Section~\ref{sec:Sparse} presents our research on the development of
parallel algorithms for solving sparse matrix equations, 
which are a key element of transient stability analysis 
and many other power systems applications.

Section~\ref{sec:ExpertSystem} discusses the development of an expert system
for analyzing transient stability data and setting stability limits,
for both on-line simulations and off-line studies.

Section~\ref{sec:OLTS} integrates the results from the previous four sections
and discusses the feasibility of an on-line system for calculating
transient stability limits for use within the EMS security model.
A similar EPRI project to develop an on-line program for dynamic security 
assessment is also discussed.

Section~\ref{sec:Parallel} gives an overview of the relevant issues involved
in using parallel computers, and in particular the identification of
the best parallel hardware, languages, software, and algorithms for
power utility applications.

Section~\ref{sec:Survey} gives preliminary results on a survey of 
utility applications which would benefit from parallel processing.
This survey concentrates on the main algorithms used in these 
applications, and identifies whether efficient parallel algorithms 
already exist for these applications, or would need to be developed.



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Unit Commitment}
\label{sec:UnitComm} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Conclusions and Recommendations}
\label{sec:UnitCommConc} 

In this section of the project we have:
\begin{itemize}
\item Investigated the use of unit commitment at NMPC, in particular
      the DYNAMICS program being developed by EPRI.
\item Studied the use of parallel dynamic programming techniques for 
      unit commitment.
\item Devised a method for migrating a parallel dynamic programming
      code from a shared memory to a distributed memory architecture. 
\item Investigated the use of simulated annealing for unit commitment.
\item Devised a strategy for implementing a unit commitment program using
      simulated annealing, and begun implementing this program using a
      public-domain simulated annealing package.
\item Developed a preliminary implementation of a general-purpose simulated
      annealing program which used improved techniques for automatically
      finding a good cooling schedule, which has so far been the main
      difficulty in effectively applying simulated annealing to general
      optimization problems.
\item Devised and implemented a parallel version of this general simulated
      annealing program.
\end{itemize}

Since the new EPRI unit commitment program DYNAMICS is so fast and 
effective, it seems that implementing a parallel unit commitment program
would not be of benefit to NMPC.
If NYPP believed it beneficial to have a program such as DYNAMICS 
running pool-wide unit commitment studies every few seconds rather than 
minutes, the parallel algorithms developed in this project could be used 
to parallelize DYNAMICS 
(or any other unit commitment program that NYPP may use).
However it seems unlikely that this capability would be required.
We therefore do not recommend continuing work on a parallel unit 
commitment program in Phase 2.

The focus of the work in this section has been on parallel algorithms for 
simulated annealing and dynamic programming. 
Simulated annealing is a general technique which can be used for any 
hard optimization problem. 
It is therefore likely that a parallel simulated annealing algorithm
could be of use in other utility applications, 
for example the MAPS and ENGINEOUS programs from General Electric, 
which use optimization techniques to try to find the most
cost-effective network configurations for planning studies.
These are discussed in section \ref{sec:ENGINEOUS}.
MAPS currently uses linear programming techniques for optimization.
We therefore recommend that research be directed toward developing and
improving parallel algorithms for simulated annealing and linear 
programming.



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Contingency Evaluation}
\label{sec:ContEval} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Conclusions and Recommendations}
\label{sec:ContEvalConc} 

In this section of the project we have:
\begin{itemize}
\item Investigated the use of the security model in the NMPC Energy 
      Management System, in particular contingency evaluation and
      state estimation.
\item Proposed a simple method for parallelizing contingency screening
      and evaluation over independent contingencies.
\item Analyzed the possible use and benefits of an on-line program for
      setting stability limits.
\item Proposed a method for utilizing parallel processing to enable 
      the development of an on-line program for providing cost-effective
      strategies for preventive and corrective action to control room 
      operators.
\end{itemize}

It should be straightforward to implement an efficient parallel program 
for contingency evaluation that would run on a network of IBM RS/6000
workstations or an IBM SP-1 parallel computer, by parallelizing over
contingencies.
This would be extremely difficult with the current STAG EMS software
used on the IBM mainframe, 
but would require only minimal changes to the new EMS software  
being developed by STAG for RS/6000 workstations.
If parallelization of the state estimator was necessary, this could most
easily be done by overlapping the state estimation from the current 
telemetry data with contingency evaluation of the previously computed state.

Implementing a parallel contingency evaluation program
would require a collaboration between NPAC, NMPC and STAG.


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Transient Stability Analysis}
\label{sec:TSA}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Conclusions and Recommendations}
\label{sec:TSAConc} 

In this section of the project we have:
\begin{itemize}
\item Studied the sequential and parallel algorithms currently used for 
      transient stability analysis.
\item Studied the EPRI ETMSP transient stability program in detail, and
      devised an approach for parallelizing this program.
\item Begun the integration of a parallel sparse matrix solver into ETMSP
      for solving the network equations.
\item Proposed a strategy for restructuring the solution of the generator
      equations in ETMSP to allow for the use of independent parallelism.
\item Investigated the use of improved ODE and DAE solvers for 
      transient stability analysis.
\item Surveyed available DAE solvers and recommended DASSL and LIMEX as
      most suitable for solving the transient stability problem. 
\item Improved the structure of the parallel DAE solver Cdassl to make
      it easier to interface this program with ETMSP and different
      parallel sparse matrix solvers.
\item Investigated the requirements for integrating DAE solvers into 
      the framework of ETMSP.
\end{itemize}
 
We have decided to base our studies on the EPRI transient stability program
ETMSP, rather than the PTI PSS/E program currently used at NMPC.
This has been done for a number of reasons, including availability 
of the source code and documentation, access to the program developers,
and availability of previous work on parallelism done by EPRI.

We believe that it is feasible to parallelize the ETMSP transient
stability program and obtain speed-ups of around 10 on 16 processors.
Increasing the number of processors used beyond 16 is unlikely to have 
much effect, due to the lack of scalability of parallel sparse
matrix algorithms to larger numbers of processors.

Further improvements should be obtainable by using improved algorithms,
such as DAE solvers with variable integration time-steps and variable
order of convergence. The parallel DAE solver Cdassl seems particularly
promising, although integrating it into ETMSP will involve substantial
effort, since parts of ETMSP are ``hard-wired'' to the current solution
technique.

During Phase 2 we plan to make substantial progress on developing 
prototype parallel programs based on ETMSP, using both the current 
decoupled methods and new methods incorporating DAE solvers.
We will initially implement this program using a message passing language
for the IBM SP-1. This will be migrated to standardized parallel languages
(High Performance Fortran and Message Passing Interface) 
when good compilers become available.
Since we are using the EPRI transient stability program ETMSP, 
we recommend that this part of the project be co-ordinated with EPRI.



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parallel Sparse Matrix Algorithms}
\label{sec:Sparse} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Expert System and User Interface}
\label{sec:ExpertSystem} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Conclusions and Recommendations}
\label{sec:ESConc} 

In this section of the project we have:
\begin{itemize}
\item Conducted interviews with NMPC and NYPP engineers to determine
      criteria for classifying transient stability results.
\item Constructed a decision model for this process and used this as
      input for the knowledge base of an expert system.
\item Implemented a preliminary version of an expert system for 
      classification of transient stability results.
\item Investigated other work in applying expert systems and 
      artificial intelligence for utility applications.
\end{itemize}
 

Currently the input to the expert system has been given as a simple
user determination of the rules as applied to graphical output 
(basically the user mimicking the experts). 
Clearly for an on-line system we want to remove the user from this loop, 
and process the numerical output from the transient stability program
to obtain this information. So far we have been unable to do this, since
we do not have access to the source code for the PTI PSS/E program.
However we will be utilizing the EPRI ETMSP program in the future,
which will allow us to do some post-processing
on the output from this program in order to create a genuine automated
system for interpreting the transient stability data.

Analysis of the output data for 
stability assessment is only one part of the process of setting 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.  While there is 
likely to be considerable individual variability from engineer to 
engineer in these aspects, we would suggest that the process is not 
likely to be chaotic and consistent decision patterns may be elicited.  
This problem is a logical next step for further investigation in Phase 2.

Although our efforts so far were primarily directed toward the problem of 
analyzing transient stability off-line, we recognize an industry demand 
for expert system technologies on the operations side as well as the 
planning side.  In fact, it seems safe to say that the volume and 
complexity of data and decisions (decisions with economic 
consequences) faced by operators on-line in today's EMS systems makes 
this area the most needful of AI technology.  We would further 
recommend that in the face of information overload, issues such as the
human-computer interface will be critically important for the successful 
implementation of expert system technologies (e.g. in dynamic security 
assessment).  We suggest that this is an important area for further 
study, and we plan to investigate this problem starting in Phase 2
of this project. 



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{On-Line Transient Stability Analysis}
\label{sec:OLTS} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Conclusions and Recommendations}
\label{sec:OLTSConc} 

In this section of the project we have:
\begin{itemize}
\item Analyzed the requirements for an on-line program for
      transient stability analysis.
\item Analyzed the requirements, benefits, and feasibility of an on-line 
      program for providing transient stability limits for use within
      the NMPC Operations Center Energy Management System.
\item Studied the related EPRI project for dynamic security assessment,
      and identified areas that complement or overlap our project.
\item Investigated the use of parallelism for dynamic security assessment
      and the determination of transient stability limits. 
\end{itemize}
 

We believe it is feasible to develop an on-line system which will 
provide transient stability limits to control room operators. 
Parallel algorithms to speed up transient stability analysis, 
and an expert system knowledge base to classify the results, 
have already been identified, and development of prototype programs
to implement these functions has begun. 
There are four main obstacles to be overcome to develop a program which
will provide on-line stability limits:
%
\begin{enumerate}
\item {\bf Development of a parallel version of ETMSP.}\\
      The main difficulty here is that ETMSP is a large and complex
      program, so fully implementing the parallel algorithm will take
      quite some time. 
\item {\bf Development of an expert system for classifying stability.}\\
      An on-line expert system is needed to classify the ETMSP output
      as being stable or unstable.
\item {\bf Development of an expert system for finding stability limits.}\\
      We also need some expert system rules that describe how an engineer
      would use the transient stability program to find the stability limit
      for a particular component or interface in the system. 
\item {\bf Integration of the on-line stability program into the control
      room EMS.}\\
      This is quite a large software engineering problem, which would 
      require input from STAG, the developers of the EMS software. 
      The on-line stability program would need to access the network data 
      from the EMS state estimator and the results of load flow simulations, 
      and return stability limits in a form which is usable by the EMS 
      security model programs and the operators.
      It should also interface to study mode operation of the EMS programs.
\end{enumerate}
%
Assuming no major unforseen problems (which are always possible in any
research project of this kind), we would expect that items 1,2 and 3
could be completed by the end of this year. Another few months would
be required for intensive testing and validation of these programs.
Estimating the time required to integrate our program into the control
room EMS is a more difficult problem. Currently we do not have enough 
information on the STAG EMS software. It may also be difficult to negotiate
an agreement on interfacing software developed by STAG, EPRI and NPAC.
However as a very rough estimate, we would expect the integration would take 
at least an additional 6 months, with another few months for validation and 
testing.  It should be feasible to integrate 
this system with the current EMS mainframe environment, however a system
using the workstation-based EMS software being developed by STAG 
would be easier to work with.

An on-line program to provide transient stability limits could 
therefore be available by the summer of 1995.
Further testing and improvements would probably be required after that date.
This is in accord with our original proposal for the time required for
Phase 3 (the development phase) of this project, which we had estimated 
to be roughly 18 months after the completion of Phase 2 (which ends in 
March 1994), implying a Phase 3 completion date of September 1995.



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parallelism and Computational Issues}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subsection{Conclusions and Recommendations}
\label{sec:ParCompConc} 

In this section of the project we have studied issues relevant to 
the use of parallel computing in the utility industry. 
Parallel computing has become a much more attractive option for industrial 
applications, due to the following recent developments:
\begin{itemize}
\item Powerful parallel computers developed by mainstream computer 
      companies such as IBM, DEC and Hewlett-Packard, that are
      based on scalable clusters of high performance workstations.
\item Standardized portable parallel languages such as High Performance 
      Fortran (HPF) and Message Passing Interface (MPI).
\item The development of libraries of portable parallel programs, 
      such as the SCALAPACK linear algebra package.
\end{itemize}
 
We believe distributed memory MIMD parallel computers based on 
workstation clusters, such as the IBM SP-1, 
are the most suitable high performance computers for the utility industry.
The architecture of these parallel machines is well-suited to any of
the applications discussed here, from the simple independent parallelism
of contingency evaluation, to problems where fast inter-processor
communication is critical, such as parallel sparse matrix solvers.
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.
Workstation clusters offer an extremely good ratio of price to performance.

Parallelizing compilers are still in their infancy and do not give good
performance for most applications. The efficient use of parallel computers
requires the development of parallel algorithms. Depending on the application,
this may require anything from very small modifications to the sequential 
program, to an algorithm which is very different than the one used in a 
sequential program.

Standardized parallel languages such as HPF and MPI should be used
for developing commercial parallel software. However good compilers for
these languages are not expected to be available for at least another
year. In the meantime, parallel programs should be written in a manner
that will allow easy migration of the software to these standard languages,
and will preferably be portable among different parallel computers. 
Where possible, standard libraries of portable parallel programs should be
utilized.
If specialized routines such as parallel block-diagonal-bordered sparse matrix
algorithms need to be developed, they should be written in such a way that
they have similar interfaces to programs in standard parallel libraries.



\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Survey of High Performance Computing and Parallel Processing 
         in the Utility Industry}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subsection{Conclusions and Recommendations}
\label{sec:SurveyConc} 

In this section of the project we have surveyed a variety of applications
used in the utility industry, identified the basic algorithms used in
these applications, and indicated whether parallel versions of these
algorithms already exist or could be developed. 
We will extend this survey in Phase 2 of the project.

We have so far identified the following areas as being the most promising
applications of parallel processing to the utility industry:
\begin{itemize}
\item Independent parallelism for contingency evaluation and 
      dynamic security assessment.
\item Use of parallel transient stability methods for mid-term and long-term
      stability programs such as EPRI's ETMSP and LTSP.
\item Parallel eigenvalue solvers for voltage and small signals stability
      programs.
\item Parallel optimization techniques such as simulated annealing and
      linear programming for production costing programs such as MAPS.
\item Use of parallel processing to integrate multiple simulation programs
      into an advanced on-line Energy Management System.
\item Use of job-level parallelism to increase turn-around time for the many
      programs that are run concurrently in a central corporate computing 
      facility.
\end{itemize}
 


\end{document}


