Sparse Linear Solver for Power System Analysis Using FPGA

摘要

Load flow computation and contingency analysis is the foundation of power system analysis. Numerical solution to load flow equations are typically computed using Newton-Raphson iteration, and the most time consuming component of the computation is the solution of a sparse linear system needed for the update each iteration. When an appropriate elimination ordering is used, direct solvers are more effective than iterative solvers. In practice these systems involve a larger number of variables (50,000 or more); however, when the sparsity is utilized effectively these systems can be solved in a modest amount of time (seconds). Despite the modest computation time for the linear solver, the number of systems that must be solved is large and current computation platforms and approaches do not yield the desired performance. Because of the relatively small granularity of the linear solver, the use of a coarse-grained parallel solver does not provide an effective means to improve performance. In this talk, it is argued that a hardware solution, implemented in FPGA, using fine-grained parallelism, provides a cost-effective means to achieve the desired performance. Previous work 1, 2, 3 has shown that FPGA can be effectively used for floating-point intensive scientific computation. It was shown that high MFLOP rates could be achieved by utilizing multiple floating- point units, and FPGA could outperform PCs and workstations, running at much higherlock rates, on dense matrix computations. The current work argues that similar benefit can be obtained for the sparse matrix computations arising in power system analysis. These conclusions are based on operation counts and system analysis for a collection of benchmark systems arising in practice. Benchmark data indicates that between 1 and 3 percent of peak floating point performance was obtained using a state-of-the-art sparse solver (UMFPACK) running on 2.60 GHz Pentium 4.