SCCS-???

High Performance Computing and Parallel Processing

in the Utility Industry

Paul Coddington

Northeast Parallel Architectures Center, Syracuse University,

111 College Place, Syracuse NY 13244-4100

February 23, 1994

Abstract

This is the abstract

1 Introduction

The development of powerful, inexpensive microprocessors has created a revolution in the computing industry. High performance workstations, and parallel computers that combine the power of many fast processors, are offering performance exceeding that of mainframes and traditional vector supercomputers at a fraction of the cost. However, as is always the case with new computer technology, the development of applications software has lagged behind the development of new hardware, especially in the area of parallel processing.

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 have demonstrated 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 have also explored the use of parallel computing and expert systems to enable new capabilities that would be of great benefit to NMPC.

Power utilities have two main constraints – security and economy. The power network must be operated in such a way that it is stable under any reasonable conditions, including possible equipment failures. This requires the provision of reserve generation and transmission capacity. The other major constraint is economy. Utilities would like to provide the most cost-effective generation and transmission of the power needed to cover demand and meet security constraints. Choosing which generators to commit to power production (unit commitment), and how the power required to match the forecast demand should be distributed among these generators (economic dispatch), is a difficult optimization problem. Environmental constraints must also be considered.

Substantial changes are occurring in the utility industry. There is increasing competition from Non-Utility Generators (NUGs); more contracts for buying and selling power being made between neighboring utilities and NUGs; and increasing demand by NUGs for access to utility transmission networks. These changes will make the secure and efficient management of the power network even more complex and time-critical. This will require more advanced computers, computer software, and man-machine interfaces.

Computer simulation currently plays a major role in the utility industry, in both longterm network planning, and the on-line Energy Management System (EMS) used by control room operators for handling the day-to-day running of the power grid. Many of the simulations are compute-bound, and the use of high performance computing would allow more accurate and more frequent simulations to be performed, providing increased security and 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 reducing operating margins by improving simulations could save NMPC millions of dollars per year. This would also save energy resources and reduce environmental impact.

The recent TASC report on the application of supercomputing to the utility industry did a creditable job of summarizing the trends in supercomputing, and outlining the types of compute-intensive utility problems which could benefit from high performance computing. However the report does not emphasize the fact that the hardware used in high performance computers, such as vector and parallel processing, requires special software to be utilized effectively. Although vectorizing and parallelizing compilers do exist for many of these computers, it is very rare for a standard sequential program to obtain anywhere near the peak performance of these machines, and in many cases the speed-ups obtained over sequential workstations are negligible. Obtaining the best performance from parallel computers almost always requires different methods (or algorithms) to those used on sequential machines. For some problems, implementing efficient parallel programs can be very difficult. Simulations of power systems generally require the solution of sparse linear equations, which are one of the most difficult applications to implement on parallel computers.

2 Project Overview

One of the main goals of this project is to identify the basic algorithms used in various utility applications, and to determine whether they can be parallelized efficiently, or if appropriate parallel algorithms already exist that could be applied to these problems. We have therefore undertaken the following activities concerned with this broad objective:

• A study of the relevant issues involved in using parallel computing in the utility industry, and recommendations for the most suitable parallel hardware, software, and languages.

• A survey of utility applications to determine those that are amenable to parallel processing.

We have also concentrated on developing parallel algorithms for the following specific applications that could benefit from high performance computing:

• contingency evaluation

• transient stability analysis

• sparse matrix algorithms

• optimization for unit commitment and network planning

Improving the performance of application programs can open up new areas of use. 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. We are therefore also working on the following problems:

• The development of an expert system and user interface for classifying the output of the transient stability program as stable or unstable, and provide a method for using multiple transient stability simulations to find stability limits.

• The development of a fast on-line program for transient stability analysis that can be utilized by this expert system to allow the on-line determination of stability limits.

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.

Phase 2 of the project is to develop and benchmark prototype parallel programs and expert systems software.

Phase 3 involves developing, documenting and testing production-grade software which can be used at NMPC.

This report presents the work done in Phase 1 of the project. We have studied various applications used at NMPC, obtained a detailed knowledge of the programs and the sequential algorithms currently used, devised strategies for parallelizing these programs, demonstrated the feasibility and benefits of using parallel processing for a number of existing utility applications, and explored the possibility of enabling new capabilities by the use of parallel computing and expert systems. In some cases we have made substantial progress in writing programs to implement these parallel algorithms and expert systems, which we plan to continue in Phase 2 of this project.

3 Parallelism and Computational Issues

Parallel computing has become a much more attractive option for industrial applications, due to the following recent developments:

• Powerful parallel computers developed by mainstream computer companies such as IBM, DEC and Hewlett-Packard, that are based on clusters of high performance workstations.

• Standardized portable parallel languages such as High Performance Fortran (HPF) and the Message Passing Interface (MPI).

• The development of libraries of portable parallel programs, such as the SCALAPACK linear algebra package.

We believe distributed memory 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. 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.

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.

4 Contingency Evaluation

An important aspect of the operation of an electrical power network is the security model, which simulates the response of the network to possible disturbances (or contingencies). These simulations allow control room operators to identify and control possible sources of cascading failures, that could cause a disruption of power generation or transmission.

In the NMPC Energy Management System, contingency evaluation is done on a list of over 200 independent contingencies. A very approximate simulation is first done to screen out the less problematic contingencies, and a full simulation is done on the 10-20 worst cases. Parallel processing can be used very simply and very efficiently by independently simulating different contingencies on different processors. This would allow more frequent contingency evaluation; a more accurate screening procedure; and the testing of more contingencies, with the possibility of evaluating the effects of multiple contingencies at one time, which is currently not addressed.

The current software used in the NMPC EMS is run on an IBM mainframe, and would be extremely difficult to parallelize, since it uses some non-standard languages and software management techniques that are far removed from the standardized languages and operating systems used in modern workstations and parallel computers. However the EMS software is currently being ported to IBM RS/6000 workstations, and is expected to be available this year. Only minimal changes to this new software would be required to implement an efficient parallel program for contingency evaluation that could run on a network of IBM RS/6000 workstations or an IBM SP-1 parallel computer. Implementing such a program would require a collaboration between NPAC, NMPC and STAG (the developers of the EMS software).

Parallel processing could also enable the development of an on-line program to help an operator in devising proactive strategies for preventive or corrective action in a situation where the occurrence of a contingency would violate stability limits. A program could be used to simulate many possible scenarios in parallel, in order to identify a workable strategy to deal with a stability problem. If the security model could be integrated with a pricing model, then an even better approach would be to search for not just a stable strategy, but one that would minimizing incurred costs.

5 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 and improved algorithms.

It has been decided to base our work on the EPRI transient stability program ETMSP. We have studied this program in detail, and devised an approach for parallelizing this program, drawing on recommendations of previous EPRI research. The generator equations are 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. This would require substantial restructuring of the program, which should be straightforward, but may take some time to complete, due to the complexity of the program. The network equations can only be parallelized by using a parallel sparse matrix solver. We are developing such a solver, and have begun writing routines to integrate a parallel solver into ETMSP. We plan to benchmark a number of different parallel sparse solvers. We believe it is feasible to parallelize the ETMSP transient stability program and obtain speed-ups of around 10 on 16 processors. 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.

Further improvements could be obtained by using better algorithms. We are investigating the use of advanced public-domain differential-algebraic equation solvers. These methods offer variable timestep and variable convergence numerical integration techniques that should allow faster simulations and improved accuracy. We have surveyed available DAE solvers and found that DASSL and LIMEX appear to be the most suitable for solving the transient stability problem. Another advantage in using DAE solvers is that a parallel implementation of DASSL, known as Cdassl, already exists. We are investigating the requirements for integrating DAE solvers into the framework of ETMSP. This is not as straightforward as had been expected, since parts of ETMSP are “hard-wired” to the current solution technique.

During Phase 2 we aim to make substantial progress on developing prototype parallel programs based on ETMSP, using both the current decoupled methods and DAE solvers. These programs will initially be implemented using a message passing language for the IBM SP-1, and migrated to standardized parallel languages when good compilers for these new languages 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.

6 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 a parallel block-diagonal-bordered Choleski solver and implemented it on the Thinking Machines CM-5 parallel computer using a message-passing paradigm. Preliminary results show that the speed-up that can be obtained from this program is limited due to the limited amount of calculation required. LU factorization should give a larger speed-up, since it requires more calculation. We are currently working on developing a parallel LU solver for transient stability analysis, that should achieve speed-ups of 5-10, which is enough to provide a speed-up of 10 or more for a parallel implementation of the ETMSP transient stability program. Using DAE solvers for the transient stability problem produces larger matrices with additional available calculations, due to the inclusion of the generator equations. These matrices are naturally in block-diagonal-bordered form. The increased size and computational complexity of these matrices should allow even greater speed-up for parallel LU factorization.

Tasks remaining in our work include the development and implementation of two additional parallel block-diagonal-bordered sparse matrix solvers, a direct solver based on LU factorization and an iterative Gauss-Seidel solver. These programs will be ported to the IBM SP-1 parallel computer.

7 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 offline 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, through an improved user interface.

We have 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 has been used as input for the knowledge base of an expert system for classification of transient stability results. We have implemented a preliminary version of this expert system. In Phase 2 this will be integrated with the ETMSP transient stability program. This will involve 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 we believe an expert system can also be developed for this process. This will be investigated in Phase 2.

The volume and complexity of data and decisions faced by EMS operators is likely to increase in the future. There is a growing movement in the utility industry toward the use of expert systems and artificial intelligence to cope with this problem. In the face of information overload, issues such as the human-computer interface will be critically important for the successful implementation of these expert system technologies. 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.

8 On-Line Transient Stability Analysis

Off-line transient stability analysis is currently used to set the component and interface stability limits used by NMPC Operations. These are set by infrequent studies (every few months), using a worst-case scenario. An on-line program to provide stability limits on a near-real-time basis using the actual operating state of the power network would reduce the amount of excess generation required to satisfy security constraints, and increase secure transmission capability to allow greater transfer of power from areas with lower generation costs. It is estimated that NMPC could save as much as $3M per year in this way. EPRI have given similar arguments for large savings as motivation for a large project to develop an on-line program for dynamic security assessment, that aims to incorporate transient stability analysis into an EMS contingency evaluation.

We have analyzed the requirements for an on-line program for transient stability analysis, and the determination of stability limits, and studied the related EPRI project for dynamic security assessment. The basic requirements for an on-line transient stability analysis program are shown in Figure 1. We believe it is feasible to develop an on-line system that will provide transient stability limits to control room operators. There are four main obstacles to be overcome to develop such a program:

1. A faster program for transient stability analysis.

We are investigating three approaches to tackle this problem:

• Parallelizing over contingencies.

• Development of a parallel version of ETMSP.

• The use of improved algorithms such as DAE solvers.

2. Development of an expert system for classifying stability.

3. Development of an expert system for finding stability limits.

4. Integration of the on-line stability program into the control room EMS.

We have already made substantial progress in the first two areas. Developing an on-line stability program that can be integrated into the control room EMS would require an agreement on interfacing software developed by STAG, EPRI and NPAC. Assuming that this could be arranged, we estimate that such a program could be developed in Phase 3 of this project, and be ready for testing at NMPC by the summer of 1995.

Figure 1: Requirements for a program for on-line transient stability analysis 9

9 Optimization for Unit Commitment and Network Planning

The focus of the work in this section of the project has been on parallel algorithms for optimization techniques, such as simulated annealing and dynamic programming. Optimization methods are used in many utility applications, for example to find the most cost-effective solutions for unit commitment and network planning.

The standard method for solving the unit commitment problem is the use of dynamic programming optimization techniques. Previous research at Syracuse University developed parallel dynamic programming algorithms that were used to implement a parallel unit commitment program on a shared memory parallel computer. We have determined a straightforward procedure for migrating this parallel dynamic programming code from a shared memory to a distributed memory architecture.

We have also investigated the use of simulated annealing, a general-purpose optimization technique, for unit commitment. We devised a strategy for using simulated annealing for unit commitment, and have begun implementing this program using a public-domain simulated annealing package. We have also developed a preliminary implementation of our own improved simulated annealing program, which uses methods to automatically find good parameters that otherwise must be tuned by hand for each different problem in order for simulated annealing to work effectively. We have also developed a parallel version of this program.

Unit commitment at NMPC is currently done manually using a spreadsheet that sets up a simple prioritized list of generators, with the least expensive generators having highest priority. EPRI have developed an advanced program called DYNAMICS that incorporates unit commitment, economic dispatch, and environmental and emissions constraints. NMPC is a test utility for this project. This program runs unit commitment for NMPC in only 1 minute on an IBM RS/6000 workstation. Unit commitment for the whole New York Power Pool could be run on-line in only a few minutes using this program. This is fast enough that continued development of a parallel unit commitment program appears unneccessary.

Optimization techniques are also used to search for the most cost-effective network configurations for planning studies, as is done by the MAPS and ENGINEOUS programs from General Electric. MAPS currently uses linear programming techniques for optimization, however simulated annealing could work well for this complex problem. We therefore recommend that research be directed toward developing and improving parallel algorithms for simulated annealing and linear programming.

10 Survey of High Performance Computing and Parallel Processing in the Utility Industry

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. The survey has so far concentrated on programs related to the security and economics of power network management and planning. We plan to extend the scope of 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:

• Parallelism over independent contingencies for contingency evaluation and dynamic security assessment.

• Use of parallel transient stability methods, including parallel sparse matrix and DAE solvers, for mid-term and long-term stability analysis programs such as EPRI’s ETMSP and LTSP.

• Use of existing parallel eigenvalue solvers for voltage and small signals stability programs.

• Development of parallel optimization techniques such as simulated annealing and linear programming for production costing programs such as MAPS.

• Use of parallel processing to integrate multiple simulation programs into an advanced on-line Energy Management System.

• Use of job-level parallelism, i.e. running different programs on different processors rather than time-sharing on a single processor, to increase turn-around time for the many programs that are run concurrently in a central corporate computing facility.

11 Conclusions and Recommendations for Future Work

In Phase 1 of this project, we have demonstrated the feasibility and benefits of using parallel processing for a number of existing utility applications, such as contingency evaluation and transient stability analysis. We have also explored the use of parallel computing and expert systems to enable new capabilities, such as an on-line program for setting network stability limits and an expert system for optimizing network planning, that would be of great benefit to NMPC.

We believe these results warrant the implementation of Phase 2 of this project, to develop prototype parallel programs for those applications that we have shown can benefit from the use of parallel processing, and to further study the use of parallel processing for other applications. We recommend pursuing the follow action items in Phase 2 of this project:

1. Restructuring the ETMSP code for solving the generator equations, to allow independent parallelism over generators.

2. Developing parallel block-diagonal-bordered LU and iterative sparse matrix solvers for use within ETMSP.

3. Porting our parallel sparse matrix programs to the IBM SP-1.

4. Integrating a number of parallel sparse matrix solvers into ETMSP.

5. Benchmarking the performance of various parallel sparse matrix solvers within ETMSP.

6. Integrating a parallel DAE solver into ETMSP for solving the transient stability equations.

7. Implementing a prototype expert system for the classification of transient stability output data.

8. Developing a decision model for the process of determining stability limits.

9. Formulating specifications for an on-line program for determining stability limits.

10. Investigating the structure of the STAG EMS software for the IBM mainframe and RS/6000 platforms, with regard to parallelizing the contingency analysis program and integrating an on-line program for setting stability limits.

11. Studying the feasibility of parallelizing the MAPS program.

12. Investigating the possible use of improved linear programming and simulated annealing optimization techniques within MAPS.

13. Studying the feasibility of using parallel versions of MAPS and ETMSP within EN-GINEOUS.

14. Extending our survey of programs used at NMPC and the possible applications of parallel processing to these programs.

Acknowledgements

This work has been supported in part by Niagara Mohawk Power Corporation, the New York State Science and Technology Foundation, the NSF under co-operative agreement No. CCR-9120008, and ARPA under contract No. DABT63-91-K-0005.

The following people from NPAC and IST at Syracuse University have contributed to this work: Geoffrey Fox, Alok Choudhary, Salim Hariri, Mike Nilan, Sanjay Ranka, James Allwright, Kamala Anupindi, David Koester, Alvin Leung, Siva Narendra, Richard Southwick, Caren Obad.

We have received invaluable help and guidance from the following people at Niagara Mohawk Power Corporation: Sid Lipton, Larry Eng, Bill Merritt, Wes Yeomans, Jack Brennan, Danielle Dylan.

The following people gave their time for interviews to develop the knowledge base for the transient stability analysis expert system: Larry Eng (NMPC), Ricardo Gonzalez, Jonathon Mayo, and Robert Waldele (NYPP), Michael Henderson, Larry Hochverg, Paul Roman, and George Dunn (NYPA).

We have also benefited greatly from discussions with the following people: Tony Skjellum (Mississippi State University), Joel Saltz (University of Maryland), Chris Pottle (Cornell University), David Wong (Ontario Hydro and Powertech), Nelson Simons, Rana Mukerji and Len Garver (General Electric).