
\documentstyle[11pt]{article}

\textwidth=6.0in
\textheight=8.5in
\topmargin=-0.5in
\oddsidemargin=0.25in
 
 \input{epsf}

\begin{document}

\begin{center}

{\LARGE \bf
The Application of High-Performance 
Parallel Computing to Production Cost Simulation \\}
% THE APPLICATION OF HIGH-PERFORMANCE 
% PARALLEL COMPUTING TO PRODUCTION COST SIMULATION \\}
\vspace*{1.5cm}
{\LARGE Proposal for the 1994 NYS/ERDA University-Industry \\
	Energy Research Program\\} 
\vspace*{1.5cm}
{\Large 
Northeast Parallel Architectures Center, \\ \smallskip
Syracuse University, Syracuse NY} \\ 
\vspace*{1.0cm}
{\Large  
Power Systems Engineering Department, \\ \smallskip
General Electric Industrial and Power Systems, Schenectady NY } \\
\vspace*{1.5cm}

\today

\end{center}


\newpage

\noindent
{\Large \bf PART 1. TECHNICAL PROPOSAL\\} 
\vspace*{0.3cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This project addresses the application of parallel computing 
to improve the performance of a leading program for production 
costing used in power system planning studies.

The Multi-Area Production Simulation (MAPS) program developed by the
General Electric Power Systems Engineering Department is used to study 
the management of power system generation and transmission resources to 
minimize generation production costs while considering transmission
security. It is used extensively by the New York Power Pool and New York
State utilities for production costing and planning studies.

Most of the computational time in running the MAPS program is in solving
a large optimization problem (the hourly secure dispatch problem) 
using a linear programming routine.
The aim of this project is to develop methods to greatly improve the 
performance of the linear programming section of MAPS.

The clear trend in cost-effective high-performance computing is the
use of scalable parallel computers. These machines can only be effectively
utilized if the existing methods or algorithms used in programs for standard
sequential computers are re-analyzed and parallel algorithms are developed.
The Northeast Parallel Architectures Center (NPAC) at Syracuse University is
a world leader in the development and application of parallel computing
technologies and parallel algorithms.

Our goal is to improve the performance of the core linear programming
routine used in the MAPS program by implementing a parallel version of this 
routine that can be used on commercial high-performance parallel computers.
We also aim to investigate the possibility of using alternative linear 
programming algorithms to increase the speed of the program even further.
This improvement in performance will greatly enhance the application of the
program to power system production costing and optimization studies, 
which is a key area of power system planning.

We propose a one year project to develop an improved, parallel algorithm for 
the linear programming kernel of the GE MAPS program, and to implement this 
using an industry standard parallel language in a program that can be
run on commercial high-performance parallel computers. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Background/Approach}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The trend toward increased buying and selling of power between utilities
and independent power producers requires larger scale production costing
simulations for power system planning.
In New York State, this involves simulations incorporating the entire
New York Power Pool, as well as neighboring utilities, in particular 
Ontario Hydro and the New England and PJM power pools.
This means transmission costs and constraints must be included
into any realistic production costing and planning studies. 

These complex simulations are handled by the Multi-Area Production
Simulation (MAPS) program developed by
General Electric Industrial and Power Systems.
The MAPS program provides an accurate through-time simulation
of production costs and network flows, taking into account generation,
transmission, loads and transactions. The generation component uses
hourly calculations for commitments and dispatches, always monitoring 
the anticipated post-contingency conditions (a secure dispatch), and
meeting company or pool demands.

MAPS is the only production simulation program that incorporates realistic 
modeling of transmission as well as generation.  Due to the detailed modeling
and the large scale of these simulations, which involve many utilities
and estimate costs per hour for an entire year or more, running the MAPS 
program on high-end single-processor workstations can be very time-consuming, 
taking up to 5 hours per simulation.
Reducing this time would greatly aid
in planning studies, by allowing many more alternative scenarios to be 
considered, to try to find the most cost-effective utilization of 
transmission and generation facilities over a large area.

Parallel processing is at the leading edge of high-performance computer
technology. It offers a much more cost-effective solution than traditional
mainframe and vector supercomputer technologies. 
Parallel computers are now being offered by leading computer vendors 
such as IBM, Digital Equipment Corporation (DEC), and Hewlett-Packard,
and industry standard parallel languages have recently been developed.
These developments are bringing parallel computing toward the mainstream 
of computing, and making it much more attractive for industrial applications.

There is enormous potential for the application of parallel computing
in many areas in the utility industry. A study done for ESEERCO by TASC
(ESEERCO Project EP-90-10)
showed that savings of millions of dollars per year are possible for
New York State utilities by the improved simulations that would be 
allowed by the use of high-performance computing.
However power utilities (and many other industries) are wary of investing
in this new technology, since it involves not only new hardware, but in
many cases new or modified software as well.
There is a need to create exemplar applications for parallel computers
to show that this new technology can truly benefit the utility industry.
This project aims to provide such an application in an important area of 
utility management.

MAPS is the only commercially available program that includes realistic 
transmission modeling and security constraints into production costing
simulation. However the price of such detailed and accurate modeling is
that simulation times can be quite long.
The results of this project would be used to improve the performance of the
MAPS program. This would provide utility planners with faster turn-around
time for their simulations, and allow them to explore a wider range of
possible scenarios for network planning studies. This would result in 
better optimization strategies for the development of power networks, 
and more cost-effective utilization of these networks.

The MAPS program is currently used by the following New York State 
organizations for production costing and planning studies:
\begin{itemize}
\item New York Power Pool
\item Long Island Lighting Corporation
\item Niagara Mohawk Power Corporation
\item Consolidated Edison Corporation
\item New York Power Authority
\item New York State Energy Office
\end{itemize}

\noindent
MAPS has been used for cost/benefit studies of pooling,
new power contracts and wheeling arrangements,
installing new transmission capability between neighboring utilities, 
development and siting of new generation facilities, 
retiring generators and using more energy imports,
introduction of VAR compensation, line reconductoring,
redispatching generation to meet environmental goals,
and many other applications, including optizing the use of 
phase angle regulators to reduce unwanted loop flows.

All of these studies allow the development of more cost-effective
solutions and provide substantial savings, as well as reduction of
energy use and environmental impact.
Greater savings could be achieved if the performance of the MAPS
program could be improved.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Statement of Work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

The goal of this project is to improve the speed of solution of the most 
time-consuming portion of the MAPS program for production cost simulation,
which is the determination of optimal power generation with transmission 
limits, or the ``secure dispatch'' problem for hourly intervals over time
periods on the order of a year.
This is to be done by developing and implementing improved parallel
algorithms for the linear programming routine used to solve the secure 
dispatch problem.

The programs will be developed using the IBM SP-1 parallel
computer at NPAC,
which is an integrated collection of standard IBM RS/6000 workstations
connected by a switched high-speed communications network.
The program development will be done using industry standard
parallel languages, so that the resulting program will be portable to
any parallel computer, including networks of workstations linked by
standard Ethernet connections.

GE will work with NPAC to provide a formulation of the problem 
and sample power system data.
NPAC will then work to develop methods for improving the performance
of the linear programming module, by studying alternate sequential
algorithms and developing parallel algorithms.
This will involve input from GE, since improving the performance of the
parallel algorithm may involve using different approximations and 
techniques for modeling the problem
than those used to obtain the best performance for a sequential program.
New algorithms for this problem will be developed, implemented, benchmarked, 
and compared in terms of simulation time and accuracy of results.



\subsection*{Project Management}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Team members from the Northeast Parallel Architectures Center (NPAC) 
will meet with members from General Electric (GE) when needed, 
to discuss the details of the program, the algorithms used, any 
necessary implementation details, and to discuss progress and plans.
Much of the interaction between NPAC, GE and external advisors can be 
done remotely by telephone and electronic mail.

Team members from NPAC and GE will make themselves available to the 
Energy Authority for an initial meeting and quarterly project review
meetings as required.


\subsection*{Technology Transfer}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

NPAC will apply parallel computing techniques and improved algorithms to
develop and implement a fast parallel linear programming algorithm
for solving the hourly secure dispatch problem that is the computational
core of the GE MAPS program. 
GE would then be able to integrate this improved parallel linear programming
algorithm into the MAPS program, to greatly reduce the run-time of the 
program, thereby increasing the utility and scope of application of the 
program.

The New York State institutions that would be interested in the results of
the final report are the New York Power Pool plus NYPP member utilities,
and the New York State Energy Office.

The results of this work will be presented at conferences and submitted
to journals related to both power systems computing and parallel computing.



\subsection*{Research, Development and/or Demonstration Tasks}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The following tasks will be required to research the problem and 
develop and document the parallel algorithms and programs:
\begin{enumerate}
\item A thorough study of the MINOS linear programming algorithm that 
      is the basis of the optimization routine used in MAPS program.
\item A study of how the secure dispatch optimization problem is formulated
      within the MAPS program, concentrating on features such as what
      approximations and assumptions are made in modeling the problem,
      and a study of how the linear programming algorithm is used within 
      the MAPS program.
\item A study of alternate linear programming techniques and software and
      an investigation of their applicability to this problem.
\item The implementation of alternate linear programming algorithms which
      seem likely to offer better performance than MINOS, and a comparison
      of the results with MINOS.
\item Research to develop parallel algorithms for the linear programming
      routine.
\item Development of programs to implement the parallel linear programming
      algorithms.
\item Benchmarking of the performance of the various parallel programs on 
      commercial parallel computers, and a comparison of the performance
      with the current sequential linear programming algorithm, using power
      system data provided by GE.
\item Documentation of the program and preparation of technical papers for
      presentation in appropriate journals and conferences.
\end{enumerate}


\subsection*{Reporting}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Quarterly progress reports will be presented to ERDA.
A final report will be presented at the end of the project.
These reports will describe the development of parallel linear programming
algorithms, 
investigations into the use of alternate linear programming algorithms, 
the implementation of these algorithms, 
and the benchmarking and comparison of these algorithms on various parallel
computers.


\subsection*{Schedule}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The schedule of work shown here is for the tasks enumerated above.
\vspace*{0.2cm}

\begin{figure}[h]
\epsfxsize=5.0in
\epsfbox{tasks.eps}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Organization and Effort}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The project team members will be:

\begin{itemize}

\item {\bf Northeast Parallel Architectures Center, Syracuse University} 
 \vspace*{0.1cm} \\ 
 Dr Paul Coddington (Project Manager) \\
 Professor Geoffrey Fox \\
 Alexander Mintskovsky 

\item {\bf General Electric Industrial and Power Systems}
 \vspace*{0.1cm} \\ 
 Dr Nelson Simons (GE team manager) \\ 
 Dr Len Garver \\ 
 Rana Mukerji 

\end{itemize}

\noindent
Resumes for all team members are enclosed at the end of part 1 of the proposal.

\medskip

The following table shows the number of hours each person will devote 
to the tasks enumerated above.
\vspace*{0.2cm}\\

\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|cccccccc|c|}
\hline 
            & \multicolumn{8}{c|}{TASK} & \\
            &  1  &  2  &  3  &  4  &  5  &  6  &  7  &  8  & TOTAL \\
\hline
Coddington  &  20 &  40 &  30 &  10 & 100 &  80 &  20 & 116 &  416 \\
Mintskovsky & 100 & 150 & 300 & 260 & 400 & 400 & 120 & 350 & 2080 \\  
Fox         &  0  &  0  & 20  &  0  &  60 &  10 &  0  & 14  & 104  \\
Garver      &  0  &  16 &  0  &  0  &  8  &  0  &  8  &  8  &  40 \\
Mukerji     &  0  &  32 &  0  &  0  &  8  &  0  & 16  & 16  &  72 \\
\hline
TOTAL       & 120 & 238 & 350 & 270 & 576 & 490 & 164 & 504 & 2712 \\
\hline
\end{tabular}
\vspace*{0.2cm}\\

\medskip

Professors Bill Bixby and John Dennis of Rice University 
are leading experts on optimization and linear programming algorithms,
and will be advising us in these areas.
NPAC and Rice University are members of the national
Center for Research on Parallel Computation.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Team Expertise}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

NPAC is a world-class organization for research in parallel computing.
It is a member of the national Center for Research on Parallel Computation
(CRPC). 
Geoffrey Fox, the director of NPAC, is a world-renowned expert in 
parallel computing who was heavily involved in the early development of
parallel computers and algorithms while at the California Institute 
of Technology.

NPAC has a large on-going program (ACTION/InfoMall) for 
industrial applications and technology transfer.
This technology transfer program is focussed on New York State companies,
and NPAC is involved in joint projects with many large corporations, 
including IBM, NYNEX, Martin Marietta, and Niagara Mohawk Power Corporation,
as well as a number of smaller software development companies.

NPAC has outstanding networking and computing facilities, including 
state-of-the-art parallel machines such as the IBM SP-1,
DEC Alpha Gigaswitch cluster, Thinking Machines CM-5, Intel iPSC,
nCUBE/2, and DECmpp. 
Through involvement with CRPC, we have access to other parallel supercomputers,
as well as state-of-the-art expertise in many areas of high-performance 
computing and communications.
CRPC includes some of the finest research groups in the world
in the field of optimization and linear programming, so we have access to
the best methods in this area.

NPAC is currently involved in a project with Niagara Mohawk Power Corporation,
to investigate the use of high-performance parallel computing for utility
applications.
This project, which is currently being led by Dr Paul Coddington,
is concentrating mainly on improving the performance of security model
programs for both planning studies and on-line simulations for the
control room Energy Management System, and in developing parallel 
sparse matrix algorithms, which are used in many power system simulations. 
Niagara Mohawk are major users of the MAPS program, and are very 
interested in the results of this project.

Alexander Mintskovsky, who will be performing most of the research and 
development work for this project, has previously worked with the 
Energy Research Institute at Syracuse University on software related
to utility applications, including forecasting gas distribution
requirements, and detecting wear in nuclear power station components. 

The Power Systems Engineering Department (PSED) is a component of
General Electric Industrial and Power Systems. Located in Schenectady, 
New York, the Department is under the leadership of Thomas F. Garrity.
The GE PSED group working on this project have been heavily involved
in the development of the MAPS program for many years.

PSED has a long history of involvement in utility and industrial power
and energy systems engineering and plays a key role in the design and
evaluation of these systems. 
In fulfilling this role, PSED provides guidance to GE product departments,
and electric utility and industrial customers concerning the development,
application and testing of power system equipment. In addition, PSED is
actively participating in research and development programs aimed at
developing and commercializing advanced energy and systems technologies.
Through these systems engineering efforts, PSED supports GE components,
electric utilities and agencies such as the Electric Power Research 
Institute and the U.S. Department of Energy.

The strength of PSED lies in the capabilities of personnel whose power 
systems engineering experience represents more than 1,500 man-years.
Programmers, engineering assistants, and secretaries support the 
engineering personnel in order to provide PSED with a balanced capability
for analyzing both present and future power systems.

The Power Systems Engineering Department is the seat of GE's scientific
and engineering competence in the field of electric bulk power systems.
Its precursor was the Central Station Engineering Division, formed in 
the early days of the electric utility industry, when the industry was
plagued with very practical and perplexing problems of synchronous 
stability and surge phenomena. Early and modern pioneers in this division
developed the basic theory of operation of synchronous systems, of lighting 
and switching surge phenomena, of economic operation of generation, and
of the reliability of generation systems. Their names -- 
Park, Doherty, Clarke, Crary, Kron, Concordia, Kirchmayer -- are familiar
to those who are acquainted with electric utility system technology. 
Today's PSED, schooled in the traditions of these people, has become an
organization of unusual breadth as well as depth in the field of electric
utility energy systems. Its intimate knowledge of electric utility practices 
and requirements makes it the ideal vehicle for studies of electric utility
power system performance. It has increasingly applied its talents to the
needs of the electric utility industry and agencies of state and federal 
governments. 

\bigskip

\noindent
The following is a list of recent publications by team members that are
relevant to this project:
\begin{enumerate}
\item 
L.L.~Garver, G.A.~Jordan, D.A.~Keegan and N.W.~Simons,
The Integrated Effects of Generation and Transmission on Annual Production 
Costs, EPRI Conference on Applications of Power Production Simulation,
Washington, DC, June 1990.
\item 
N.W.~Simons, L.L.~Garver, R.~Mukerji, 
Transmission Constrained Production Costing: A Key to Pricing Transmission 
Access, Public Utilities Fortnightly, vol. 131, no. 3, 1993.
\item
G.C. Fox, Parallel Computing in Industry -- An Initial Survey,
Proceedings of the Fifth Australian Supercomputing Conference, 
Melbourne, 1992.
\item
K. Mills and G.C. Fox, High Performance Computing and Communications
Applications Development and Technology Transfer to Industry,
Proceedings of The New Frontiers:  A Workshop on Future Directions of
Massively Parallel Processing, IEEE Computer Society Press,
Los Alamitos, CA, June 1993.
\item
InfoMall: A Scalable Organization for the Development of HPCC Software 
and Systems, NPAC technical report SCCS-531.
\item
D.P. Koester, S. Ranka, and G.C. Fox,
Power Systems Transient Stability -- A Grand Computing Challenge,
NPAC technical report SCCS-549.
\item
D.P. Koester, S. Ranka, and G.C. Fox,
Parallel Block-Diagonal-Bordered Sparse Linear Solvers for
Electrical Power System Applications,
Proceedings of the Scalable Parallel Libraries Conference, October 1993,
IEEE Press.
\item 
K.~Anupindi, P.~Coddington, G.C.~Fox and A.~Skjellum,
Parallel Differential Algebraic Equation Solvers for Power System Transient
Stability Analysis, 
Proceedings of the Scalable Parallel Libraries Conference, October 1993,
IEEE Press.
\item 
G.C. Fox, P. Coddington, A. Choudhary, S. Hariri, M. Nilan and S. Ranka,
High Performance Computing and Parallel Processing in the Utility Industry:
Final report for Phase 1,
NPAC report SCCSI-542 for Niagara Mohawk Power Corporation.
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Cost-Sharing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ???

\renewcommand{\arraystretch}{1.0}
\begin{tabular}{lr}
Energy Authority          & \qquad  54.3\%    \\       
University team member    & \qquad              \\
\quad -- actual dollars   & \qquad   9.9\%    \\
\quad -- in-kind          & \qquad  27.2\%    \\
Industrial team member    & \qquad              \\
\quad -- actual dollars   & \qquad   8.6\%    \\
\quad -- in-kind          & \qquad   --\phantom{\%}         \\
Other sources:            & \qquad   --\phantom{\%}         \\
~		          & \qquad  $\overline{~~~~~~~}$  \\
~		          & \qquad  100\%
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Royalties}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

GE is willing to negotiate a royalty for ERDA if a commercial parallel 
MAPS program is developed that uses the results of this project.
GE has already invested approximately \$10M in developing the MAPS program,
so the amount of royalty for the \$100K ERDA investment in this project 
would necessarily be quite small.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Letters of Commitment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Letters of commitment from Syracuse University and General Electric
are enclosed.

\end{document}


