一种基于图形处理器加速的批量LU分解算法
|
摘要
潮流计算是电力系统计算的基础,其核心是LU分解计算,因此电力系统潮流计算加速的关键在于LU分解加速。当前,基于中央处理器(CPU)的并行算法已经成熟,性能提升空间有限。图形处理器(GPU)作为协处理器,在科学计算方面具有强大的优越性,被广泛应用到电力系统潮流计算中。文中首先分析了GPU结构和并行运行架构,然后介绍了LU分解原理,并选择了合适的矩阵排序算法和稀疏矩阵存储模型,借助统一计算设备架构(CUDA)编程模型实现了基于GPU的单个LU分解和批量LU分解并行加速,最后在仿真设备上测试了5个不同的案例,对比分析其并行算法的加速效果。仿真测试结果表明,基于GPU的批量稀疏LU分解并行算法,平均可以获得25～50倍的加速效果。
Power flow calculation is the basis of power system calculation, and its core is LU decomposition calculation. Therefore, the key to power system power flow calculation acceleration is LU decomposition acceleration. Currently, parallel algorithms based on central processing units(CPU) have matured and limited space for performance improvement. As a coprocessor, the graphics processor(GPU) has powerful advantages in scientific computing and is widely used in power system power flow calculation. This paper first analyzes the GPU structure and parallel operation architecture, then introduces the LU decomposition principle, and selects the appropriate matrix sorting algorithm and sparse matrix storage model. The GPU-based single LU decomposition is realized by the unified computing device architecture(CUDA) programming model. Parallel acceleration with batch LU decomposition. Finally, five different cases were tested on the simulation device, and the acceleration effect of the parallel algorithm was compared and analyzed. The simulation test results show that the GPU-based batch sparse LU decomposition parallel algorithm can obtain an acceleration effect of 25～50 times on average.
Power flow calculation is the basis of power system calculation, and its core is LU decomposition calculation. Therefore, the key to power system power flow calculation acceleration is LU decomposition acceleration. Currently, parallel algorithms based on central processing units(CPU) have matured and limited space for performance improvement. As a coprocessor, the graphics processor(GPU) has powerful advantages in scientific computing and is widely used in power system power flow calculation. This paper first analyzes the GPU structure and parallel operation architecture, then introduces the LU decomposition principle, and selects the appropriate matrix sorting algorithm and sparse matrix storage model. The GPU-based single LU decomposition is realized by the unified computing device architecture(CUDA) programming model. Parallel acceleration with batch LU decomposition. Finally, five different cases were tested on the simulation device, and the acceleration effect of the parallel algorithm was compared and analyzed. The simulation test results show that the GPU-based batch sparse LU decomposition parallel algorithm can obtain an acceleration effect of 25～50 times on average.
引文
[1]夏沛,汪芳宗.大规模电力系统快速潮流计算方法研究[J].电力系统保护与控制,2012,40(9):38-42.XIA Pei,WANG Fangzong.Study on fast power flow calculation methods of large-scale power systems[J].Power Systems Protection and Control,2012,40(9):38-42.
[2]涂志军,曹晔,李伟,等.一种新型高斯赛德尔算法在电力系统潮流计算中的应用研究[J].江西科技,2010,28(6):807-813.TU Zhijun,CAO Ye,LI Wei,et al.Application research of a new gaussian seidel algorithm in power system power flow calculation[J].Jiangxi Science,2010,28(6):807-813.
[3]李俊,肖宏,唐荣平,等.一种潮流计算的PQ改进算法研究[J].大众科技,2014,16(10):103-105.LI Jun,XIAO Hong,TANG Rongping,et al.Research of power flow calculation based on an improved PQ algorithm[J].Popular Science&Technology,2014,15(4):103-105.
[4]刘乐.基于牛顿拉夫逊法的含分布式电源配电网潮流计算[D].石家庄:河北科技大学,2018.LIU Le.Power flow calculation with distributed generation distribution network based on newton raphson method[J].Shi jiazhuang:Hebei University of Science and Technology,2018.
[5]陈珩.电力系统稳态分析[M].北京:中国电力出版社,2016:97-107.CHEN Heng.Power system steady state analysis[m].Beijing:China Electric Power Press,2016:97-107.
[6]徐晓飞,曹祥玉,姚旭,等.一种基于Doolittle LU分解的线性方程组并行求解方法[J].电子与信息学报,2010,32(8):2019-2022.XU Xiaofei,CAO Yuxiang,YAO Xu,et al.Parallel solving method of linear equations based on doolittle LU decomposition[J].Journal of Electronics&Information Technology,2010,32(8):2019-2022.
[7]VAN A R A M.A general purpose version of the fast decoupled load flow[J].IEEE Tans PWRS,2012,4(2):760-770.
[8]邓兴升,孙虹虹.自适应谱修正LU分解法解算高病态法方程[J].大地测量与地球动力学,2014,34(6):135-139.DENG Xingsheng,SUN Honghong.Self-adaptive spectrum correction LU decomposition algorithm for solving a normal equation with severely ill-conditioned matrix[J].Journal of Geodesy and Geodynamics,2014,34(6):135-139.
[9]张国芳,罗雅迪,李静,等.大电网潮流修正方程并行求解实现方法[J].电力系统保护与控制,2017,45(19):117-122.ZHANG Guofang,LUO Yadi,LI Ting,et al.Parallel solution method of power flow correction equation for large-scale power grid[J].Power System Protection and Control,2017,45(19):117-122.
[10]马洲俊,樊飞龙,王勇,等.基于多源异构数据的配电网故障信息挖掘与诊断[J].供用电,2018,35(8):31-39.MA Zhoujun,FAN Feilong,WANG Yong,et al.Distribution network fault information mining and diagnosis based on multisource heterogeneous data[J].Distribution&Utilization,2018,35(8):31-39.
[11]孟晓丽,唐巍,刘永梅,等.大规模复杂配电网三相不平衡潮流并行计算方法[J].电力系统保护与控制,2015,43(13):45-51.MENG Xiaoli,TANG Wei,LIU Yongmei,et al.Parallel computing of three-phase unbalanced power flow in large-scale complex distribution network[J].Power System Protection and Control,2015,43(13):45-51.
[12]傅志生,白晓清,李佩杰,等.一种快速求解大规模安全约束最优潮流的多核并行方法[J].电力系统保护与控制,2015,43(3):29-37.FU Zhisheng,BAI Xiaoqing,LI Peijie,et al.A high-speed multi-core parallel method for solving large-scale security constrained OPF[J].Power System Protection and Control,2015,43(3):29-37.
[13]夏俊峰,杨帆,李静,等.基于GPU的电力系统并行潮流计算的实现[J].电力系统保护与控制,2010,38(18):100-103.XIA Junfeng,YANG Fan,LI Jing,et al.Implementation of parallel power flow calculation based on GPU[J].Power System Protection and Control,2010,38(18):100-110.
[14]陈德扬,李亚楼,江涵,等.基于道路树分层的大电网潮流并行算法及其GPU优化实现[J].电力系统自动化,2014,38(22):63-69.CHEN Deyang,LI Yalou,JIANG Han,et al.A parallel power flow algorithm for large-scale grid based on stratified path trees and its implementation on GPU[J].Automation of Electric Power Systems,2014,38(22):63-69.
[15]陈颖,林锦贤,吕暾.LU分解和Laplace算法在GPU上实现[J].计算机应用,2011,31(3):851-855.CHEN Ying,LIN Xianjin,LYU Yun,et al.Implementation of LU decomposition and Laplace algorithms on GPU[J].Journal of Computer Applications,2011,31(3):851-855.
[16]唐坤杰,董树锋,宋永华.基于不完全LU分解预处理迭代法的电力系统潮流算法[J].中国电机工程学报,2017,37(S1):55-62.TANG Kunjie,DONG Shufeng,SONG Yonghua.Power flow algorithm based on iterative method with incomplete LU decomposition preconditioning[J].Proceedings of the CSEE,2017,37(S1):55-62.
[17]LI X,LI F.GPU-based power flow analysis with Chebyshev Preconditioner and conjugate gradient method[J].Electric Power Systems Research,2014,116(11):87-93.
[18]FANBER R.CUDA application design and development[M].Waltham:Elsevier,2011:133-145.
[19]卢风顺,宋君强,银福康,等.CPU/GPU协同并行计算研究综述计算机科学[J].计算机科学,2011,38(3):5-9.LU Fengshun,SONG Junqiang,YIN Fukang,et al.Survery of CPU/GPU synergetic parallel computing[J].Computer Science,2011,38(3):5-9.
[20]鲍威,凌卫家,张静,等.含VSC-MTDC的交直流混合电网潮流计算模型及稀疏性处理技术[J].电力自动化设备,2016,36(5):43-48.BAO Wei,LING Weijia,ZHANG Jing,et al.Power flow calculation model and parse matrix disposal techniques for AC/DChybrid power system with VSC-MTDC[J].Electric Power Automation Equipment,2016,36(5):43-48.
[21]秦成明.基于多核CPU加速的电力系统并行潮流算法研究[D].南京:东南大学,2017.QIN Chengming.Parallel power flow algorithm for power system based on mutli-core CPU acceleration[J].Nanjing:Southeast University,2017.
[2]涂志军,曹晔,李伟,等.一种新型高斯赛德尔算法在电力系统潮流计算中的应用研究[J].江西科技,2010,28(6):807-813.TU Zhijun,CAO Ye,LI Wei,et al.Application research of a new gaussian seidel algorithm in power system power flow calculation[J].Jiangxi Science,2010,28(6):807-813.
[3]李俊,肖宏,唐荣平,等.一种潮流计算的PQ改进算法研究[J].大众科技,2014,16(10):103-105.LI Jun,XIAO Hong,TANG Rongping,et al.Research of power flow calculation based on an improved PQ algorithm[J].Popular Science&Technology,2014,15(4):103-105.
[4]刘乐.基于牛顿拉夫逊法的含分布式电源配电网潮流计算[D].石家庄:河北科技大学,2018.LIU Le.Power flow calculation with distributed generation distribution network based on newton raphson method[J].Shi jiazhuang:Hebei University of Science and Technology,2018.
[5]陈珩.电力系统稳态分析[M].北京:中国电力出版社,2016:97-107.CHEN Heng.Power system steady state analysis[m].Beijing:China Electric Power Press,2016:97-107.
[6]徐晓飞,曹祥玉,姚旭,等.一种基于Doolittle LU分解的线性方程组并行求解方法[J].电子与信息学报,2010,32(8):2019-2022.XU Xiaofei,CAO Yuxiang,YAO Xu,et al.Parallel solving method of linear equations based on doolittle LU decomposition[J].Journal of Electronics&Information Technology,2010,32(8):2019-2022.
[7]VAN A R A M.A general purpose version of the fast decoupled load flow[J].IEEE Tans PWRS,2012,4(2):760-770.
[8]邓兴升,孙虹虹.自适应谱修正LU分解法解算高病态法方程[J].大地测量与地球动力学,2014,34(6):135-139.DENG Xingsheng,SUN Honghong.Self-adaptive spectrum correction LU decomposition algorithm for solving a normal equation with severely ill-conditioned matrix[J].Journal of Geodesy and Geodynamics,2014,34(6):135-139.
[9]张国芳,罗雅迪,李静,等.大电网潮流修正方程并行求解实现方法[J].电力系统保护与控制,2017,45(19):117-122.ZHANG Guofang,LUO Yadi,LI Ting,et al.Parallel solution method of power flow correction equation for large-scale power grid[J].Power System Protection and Control,2017,45(19):117-122.
[10]马洲俊,樊飞龙,王勇,等.基于多源异构数据的配电网故障信息挖掘与诊断[J].供用电,2018,35(8):31-39.MA Zhoujun,FAN Feilong,WANG Yong,et al.Distribution network fault information mining and diagnosis based on multisource heterogeneous data[J].Distribution&Utilization,2018,35(8):31-39.
[11]孟晓丽,唐巍,刘永梅,等.大规模复杂配电网三相不平衡潮流并行计算方法[J].电力系统保护与控制,2015,43(13):45-51.MENG Xiaoli,TANG Wei,LIU Yongmei,et al.Parallel computing of three-phase unbalanced power flow in large-scale complex distribution network[J].Power System Protection and Control,2015,43(13):45-51.
[12]傅志生,白晓清,李佩杰,等.一种快速求解大规模安全约束最优潮流的多核并行方法[J].电力系统保护与控制,2015,43(3):29-37.FU Zhisheng,BAI Xiaoqing,LI Peijie,et al.A high-speed multi-core parallel method for solving large-scale security constrained OPF[J].Power System Protection and Control,2015,43(3):29-37.
[13]夏俊峰,杨帆,李静,等.基于GPU的电力系统并行潮流计算的实现[J].电力系统保护与控制,2010,38(18):100-103.XIA Junfeng,YANG Fan,LI Jing,et al.Implementation of parallel power flow calculation based on GPU[J].Power System Protection and Control,2010,38(18):100-110.
[14]陈德扬,李亚楼,江涵,等.基于道路树分层的大电网潮流并行算法及其GPU优化实现[J].电力系统自动化,2014,38(22):63-69.CHEN Deyang,LI Yalou,JIANG Han,et al.A parallel power flow algorithm for large-scale grid based on stratified path trees and its implementation on GPU[J].Automation of Electric Power Systems,2014,38(22):63-69.
[15]陈颖,林锦贤,吕暾.LU分解和Laplace算法在GPU上实现[J].计算机应用,2011,31(3):851-855.CHEN Ying,LIN Xianjin,LYU Yun,et al.Implementation of LU decomposition and Laplace algorithms on GPU[J].Journal of Computer Applications,2011,31(3):851-855.
[16]唐坤杰,董树锋,宋永华.基于不完全LU分解预处理迭代法的电力系统潮流算法[J].中国电机工程学报,2017,37(S1):55-62.TANG Kunjie,DONG Shufeng,SONG Yonghua.Power flow algorithm based on iterative method with incomplete LU decomposition preconditioning[J].Proceedings of the CSEE,2017,37(S1):55-62.
[17]LI X,LI F.GPU-based power flow analysis with Chebyshev Preconditioner and conjugate gradient method[J].Electric Power Systems Research,2014,116(11):87-93.
[18]FANBER R.CUDA application design and development[M].Waltham:Elsevier,2011:133-145.
[19]卢风顺,宋君强,银福康,等.CPU/GPU协同并行计算研究综述计算机科学[J].计算机科学,2011,38(3):5-9.LU Fengshun,SONG Junqiang,YIN Fukang,et al.Survery of CPU/GPU synergetic parallel computing[J].Computer Science,2011,38(3):5-9.
[20]鲍威,凌卫家,张静,等.含VSC-MTDC的交直流混合电网潮流计算模型及稀疏性处理技术[J].电力自动化设备,2016,36(5):43-48.BAO Wei,LING Weijia,ZHANG Jing,et al.Power flow calculation model and parse matrix disposal techniques for AC/DChybrid power system with VSC-MTDC[J].Electric Power Automation Equipment,2016,36(5):43-48.
[21]秦成明.基于多核CPU加速的电力系统并行潮流算法研究[D].南京:东南大学,2017.QIN Chengming.Parallel power flow algorithm for power system based on mutli-core CPU acceleration[J].Nanjing:Southeast University,2017.