Power Flow Computation Using Field Programmable Gate Arrays A Thesis Submitted to the Faculty of Drexel University by Petya Vachranukunkiet in partial fulfillment of the requirements for the degree of Doctor of Philosophy June 2007 © Copyright 2007 Petya Vachranukunkiet. All Rights Reserved. ii Dedications To my loving wife for her continuous support iii Acknowledgments First and foremost I would like to express my heart felt gratitude to my advisors Prawat Nagvajara and Jeremy Johnson for providing the opportunity and the guidance necessary to complete this work. Their teaching, assistance, and encouragement have been instrumental in the research that I accomplished throughout my graduate life at Drexel University. I would like to thank my wife for enduring with me and supporting all of my efforts on a daily basis. Her love and constant encouragement gave me the drive to continue onward. Special thanks go out to Dr. Chika Nwankpa for providing additional knowledge, direction, and insight during my time working on the Drexel PowerGrid project. His aid was invaluable and I used many of his suggestions in shaping the form of my work. Finally I would like to thank my thesis advisory committee for participating in my dissertation defense. iv TABLE OF CONTENTS LIST OF TABLES............................................................................................................vii LIST OF FIGURES.........................................................................................................viii ABSTRACT......................................................................................................................xii CHAPTER 1. INTRODUCTION.......................................................................................1 1.1 Motivation...........................................................................................................1 1.1.1 Contingency Analysis.................................................................................2 1.2 Background.........................................................................................................5 1.2.1 Power Flow.................................................................................................5 1.2.2 Computation Technologies.........................................................................9 1.2.3 FPGA Architecture...................................................................................13 1.3 Objective...........................................................................................................18 1.4 Approach...........................................................................................................18 1.5 Contribution......................................................................................................19 1.6 Organization......................................................................................................20 CHAPTER 2. POWER FLOW COMPUTATION...........................................................21 2.1 Introduction.......................................................................................................21 2.2 Gauss Power Flow Method...............................................................................21 2.3 Newton Power Flow Method............................................................................24 CHAPTER 3. SPARSE LINEAR SOLVERS..................................................................32 3.1 Introduction.......................................................................................................32 3.2 Iterative Linear Solvers.....................................................................................33 3.3 Direct Linear Solvers........................................................................................37 v 3.4 Direct Sparse LU Decomposition.....................................................................42 3.4.1 Sparse Matrix Storage...............................................................................43 3.4.2 Ordering Sparse Matrices for Fill-In Reduction.......................................45 3.4.3 Ordering Sparse Matrices for Parallelism.................................................52 CHAPTER 4. HARDWARE DESIGN.............................................................................57 4.1 Introduction.......................................................................................................57 4.2 Design Specification.........................................................................................59 4.3 Analysis of LU Decomposition........................................................................62 4.4 Top Level Design..............................................................................................75 4.5 Floating Point Units..........................................................................................76 4.5.1 Floating point addition..............................................................................79 4.5.2 Floating point multiplication.....................................................................80 4.5.3 Floating point division..............................................................................82 4.6 Cache.................................................................................................................85 4.7 Pivot Logic........................................................................................................94 4.8 Sub-matrix Update Logic..................................................................................98 4.9 Hardware Debugging......................................................................................107 CHAPTER 5. BENCHMARK RESULTS.....................................................................108 5.1 Introduction.....................................................................................................108 5.2 Benchmark System.........................................................................................108 5.3 Hardware Prototype........................................................................................109 5.4 Performance Modeling....................................................................................118 5.5 Parallelism.......................................................................................................125 vi 5.6 Application......................................................................................................133 CHAPTER 6. CONCLUSIONS AND FUTURE WORK..............................................138 6.1 Summary of Contributions..............................................................................138 6.2 Future Work....................................................................................................138 LIST OF REFERENCES................................................................................................140 Vita..................................................................................................................................148 vii LIST OF TABLES Table 1. Power Flow Computation Applications................................................................2 Table 2. Sparse LU Decomposition Software Efficiency................................................58 Table 3. Benchmark Power System Jacobian Matrix Summary......................................63 Table 4. NNZ in L + U with Column Ordering...............................................................66 Table 5. NNZ in L + U with Symmetrical Ordering.......................................................66 Table 6. NNZ in L + U with Symmetrical Ordering and Diagonal Pivoting..................66 Table 7. Floating Point Operation Counts.......................................................................68 Table 8. Number of Entries Rejected for Pivot Column..................................................69 Table 9. Pivot Row Size Statistics...................................................................................73 Table 10. Pivot Column Size Statistics............................................................................73 Table 11. Compilation Results for Floating Point Units on Altera EP1S25F780C5 FPGA ...........................................................................................................................................78 Table 12. Solve Time in Seconds for Sparse Linear Solver Packages..........................109 Table 13. Number of Clock Cycles to Perform Sparse LU Decomposition with Two Merge Units....................................................................................................................116 Table 14. Number of Clock Cycles to Perform Sparse LU Decomposition with One Merge Unit......................................................................................................................116 viii LIST OF FIGURES Figure 1. Major Components of On-Line Security Analysis.............................................4 Figure 2. Comparison of VLSI Technologies...................................................................10 Figure 3. VLSI Computational Technology Design Flow Summary..............................10 Figure 4. General Field Programmable Gate Array Architecture.....................................14 Figure 5. Six-input LUT with Fast Carry Logic and Flip-Flop........................................16 Figure 6. Four Input Lookup Table with SRAM Configuration.......................................17 Figure 7. Graphical Illustration of Newton’s Method for an Arbitrary Function.............25 Figure 8. Newton Power Flow Computation Flow Chart and Breakdown......................31 Figure 9. Basic Gaussian Elimination Pseudocode...........................................................38 Figure 10. jki Gaussian Elimination Pseudocode and Inner Loop Data Dependency......39 Figure 11. kji Gaussian Elimination Pseudocode and Inner Loop Data Dependency......40 Figure 12. ijk Gaussian Elimination Pseudocode and Inner Loop Data Dependency Part 1 ...........................................................................................................................................41 Figure 13. ijk Gaussian Elimination Pseudocode and Inner Loop Data Dependency Part 2 ...........................................................................................................................................42 Figure 14. Sparse Matrix and Corresponding Compressed Storage.................................45 Figure 15. Sparse Matrix, Graph Representation, and Post LU Filled Matrix................49 Figure 16. Basic Minimum Degree Algorithm.................................................................50 Figure 17. Minimum Degree Ordered Sparse LU Decomposition...................................51 Figure 18. Matrix in BBD Form.......................................................................................54 Figure 19. Ordered 1648 Bus Jacobian Matrices Before LU Decomposition.................63 Figure 20. L+U Matrix for Ordered 1648 Bus Jacobian Matrices...................................64 ix Figure 21. Ratio of Matching Row Indices for Successive Updates to Total Pivot Column Size......................................................................................................................70 Figure 22. Pivot Row Size for Sub-Matrix Update..........................................................71 Figure 23. Pivot Column Size for Sub-Matrix Update....................................................72 Figure 24. Jacobian Matrix Data Transfer Time Relative to Pentium 4 Solve Time......74 Figure 25. LU Result Data Transfer Time Relative to Pentium 4 Solve Time................75 Figure 26. High Level Block Diagram of Sparse LU Hardware.....................................75 Figure 27. IEEE-754 Single Precision 32-bit Format......................................................77 Figure 28. Floating Point Addition Unit..........................................................................80 Figure 29. Floating Point Multiplication Unit.................................................................82 Figure 30. Floating Point Division Unit..........................................................................85 Figure 31. Top Level Cache Block Diagram...................................................................89 Figure 32. Cache Controller.............................................................................................90 Figure 33. Cache Tag Registers and Tag Array...............................................................91 Figure 34. Cache MSHR..................................................................................................93 Figure 35. Cache Serial/Parallel Conversion Units.........................................................94 Figure 36. Colmap Unit...................................................................................................96 Figure 37. Swap Unit.......................................................................................................97 Figure 38. Pivot Unit........................................................................................................98 Figure 39. Sub-Matrix Update Filter and Merge_Memory Units....................................99 Figure 40. LU Floating Point Multiply and Divide Units..............................................101 Figure 41. Sub-Matrix Update Merge Unit....................................................................103 Figure 42. Sub-Matrix Update Test Unit.......................................................................104