基于CPU-GPU协同并行内点算法求解结构化非线性规划
|
摘要
大量工程应用问题可建模为结构化非线性规划,且这类问题的系数矩阵可分为稀疏型和稠密型两种类型.利用原始-对偶内点法(primal dual interior point method,PD-IPM),并结合分布式并行技术可高效求解此类问题.经典工程问题-机组组合(unit commitment,UC)为稀疏系数矩阵的结构化非线性规划,本文根据PD-IPM原理,对UC模型进行连续松弛预处理,结合快速解耦技术解耦牛顿修正方程并设计CPU-GPU协同并行算法求解子问题,最后将结果与带稠密型子问题的结构化非线性规划的求解结果进行比较和分析.实验结果显示,本文所设计的算法对于两种不同类型的结构化非线性规划求解均能获得较好的加速比.
A lot of practical application problems can be modeled as structured nonlinearprogramming,and these problems always have two type of coefficients matrices: sparse and dense. Combining the principle of primal dual interior point method( PD-IPM) and the distributed parallel technology can solve the problem efficiently. The unit commitment( UC) is a classical engineering problem which can be formulated as a structured nonlinear programming with sparse coefficients matrices.In this paper, according to the PD-IPM principle, the UC model is continuous relaxation preprocessed, and the Newton correction equations are decoupled by using the fast decoupling technique,which can be used to obtain the independent sub problems.Then,a CPU-GPU collaborative parallel method is proposed to solve the sub problems in parallel and the results are compared with the results of structured nonlinear programming with dense sub problem. The experimental results show that the proposed method for solving two different types of structured nonlinear programming has achieved a certain speedup.
A lot of practical application problems can be modeled as structured nonlinearprogramming,and these problems always have two type of coefficients matrices: sparse and dense. Combining the principle of primal dual interior point method( PD-IPM) and the distributed parallel technology can solve the problem efficiently. The unit commitment( UC) is a classical engineering problem which can be formulated as a structured nonlinear programming with sparse coefficients matrices.In this paper, according to the PD-IPM principle, the UC model is continuous relaxation preprocessed, and the Newton correction equations are decoupled by using the fast decoupling technique,which can be used to obtain the independent sub problems.Then,a CPU-GPU collaborative parallel method is proposed to solve the sub problems in parallel and the results are compared with the results of structured nonlinear programming with dense sub problem. The experimental results show that the proposed method for solving two different types of structured nonlinear programming has achieved a certain speedup.
引文
[1]Byrd R H,Hribar M E,Nocedal J. An interior point algo-rithm for large-scale nonlinear programming[J]. SIAMJournal on Optimization,1999,9(4):877-900.
[2]张立峰,刘昭麟,田沛.基于压缩感知的电容层析成像图像重建算法[J].电子学报,2017,45(2):353-358.Zhang L F,Liu Z L,Tian P. Imagereconstruction algorithmfor electrical capacitance tomography based on compressedsensing[J]. Acta Electronica Sinica,2017,45(2):353-358.(in Chinese)
[3]李旭超,宋博.原始-对偶模型的牛顿迭代原理与图像恢复[J].电子学报,2015,43(10):1984-1993.Li X C,Song B. New ton iterative principle of primal-dualmodel and image restoration[J]. Acta Electronica Sinica,2015,43(10):1984-1993.(in Chinese)
[4]卢风顺,宋君强,银福康,等. CPU/GPU协同并行计算研究综述[J].计算机科学,2011,38(3):5-9.Lu F S,Song J B,Yin F K,et al. Survey of CPU/GPUsynergetic parallel computing[J]. Computer Science,2011,38(3):5-9.(in Chinese)
[5]吴恩华.图形处理器用于通用计算的技术、现状及其挑战[J].软件学报,2004,15(10):1493-1504.Wu E H. State of the art and future challenge on generalpurpose computation by graphics processing unit[J]. Jour-nal of Softw are,2004,15(10):1493-1504.(in Chinese)
[6]张朝晖,刘俊起,徐勤建. GPU并行计算技术分析与应用[J].信息技术,2009,(11):86-89.Zhang C H,Liu J Q,Xu Q J. Analysis and application ofthe GPU parallel computing technology[J]. InformationTechnology,2009,(11):86-89.(in Chinese)
[7]巨涛,等.异构众核系统及其编程模型与性能优化技术研究综述[J].电子学报,2015,43(1):111-119.Ju T,et al. The feature programming model and perform-ance optimization strategy of heterogeneous many-coresystem:a review[J]. Acta Electronica Sinica,2015,43(1):111-119.(in Chinese)
[8]Chang Y S,Wei J Z,Zhao G Y,et al. A novel architectureof special arithmetic function unit for area-efficient pro-grammable vertex shader[J]. Chinese Journal of Electron-ics,2013,22(3):483-488.
[9] Ravie C,Ali M. Enhancing the simulation of membranesystem on the GPU for the N-Queens problem[J]. ChineseJournal of Electronics,2015,24(4):740-743.
[10]陈德扬,李亚楼,江涵,等.基于道路树分层的大电网潮流并行算法及其GPU优化实现[J].电力系统自动化,2014,38(22):63-69.Chen D Y,Li Y L,Jiang H,et al. A parallel pow er flowalgorithm for large scale grid based on stratified path treesand its implementation on GPU[J]. Automation of Elec-tric Pow er Systems. 2014,38(22):63-69.(in Chinese)
[11]张宁宇,高山,赵欣.基于GPU的机电暂态仿真细粒度并行算法[J].电力系统自动化,2012,36(9):54-60.Zhang N Y,Gao S,Zhao X. A fine granularity parallel al-gorithm for electromechanical transient stability simulationbased on graphic processing unit[J]. Automation of Elec-tric Pow er Systems. 2012,36(9):54-60.(in Chinese)
[12]Alili M V,Dinavahi V. SIMD-based large-scale transi-ent stability simulation on the graphics processing unit[J]. IEEE Trans on Power Systems,2010,25(3):1589-1599.
[13]Yang G W. A highly efficient GPU-CPU hybrid parallelimplementation of sparse LU factorization[J]. ChineseJournal of Electronics,2012,21(1):7-12.
[14]李文沅.电力系统安全经济运行———模型与方法[M].重庆:重庆大学出版社出版,1989. 147-169.
[15] Mehrtash M,et al. An interior point optimization methodfor stochastic security-constrained unit commitment inthe presence of plug-in electric vehicles[J]. Journal ofApplied Sciences,2016,16:189-200.
[16]简金宝,杨林峰,全然.基于改进多中心校正解耦内点法的动态最优潮流并行算法[J].电工技术学报,2012,27(6):232-241.Jian J B,Yang L F,Quan R. Parallel algorithm of dynamicoptimal pow er flow based on improved multiple centralitycorrections decoupling interior point method[J]. Transac-tions of China Electrotechnical Society,2012,27(6):232-241.(in Chinese)
[17]Yang L F,Jian J B,Wang Y Y,et al. Projected mixed in-teger programming formulations for unit commitmentproblem[J]. International Journal of Electrical Pow er&Energy Systems,2015,68(68):195-202.
[18] Sharma G,Agarwala A,Bhattacharya B. A fast parallelGauss Jordan algorithm for matrix inversion using CUDA[J]. Computers&Structures,2013,128:31-37.
[19]刘丽,沈杰,李洪林.基于GPU的矩阵求逆性能测试和分析[J].华东理工大学学报,2010,36(6):812-817.Liu L,Shen J,Li H L. Performance testing and analysisfor matrix inversion based on GPU[J]. Journal of EastChina University of Science and Technology,2010,36(6):812-817.(in Chinese)
[2]张立峰,刘昭麟,田沛.基于压缩感知的电容层析成像图像重建算法[J].电子学报,2017,45(2):353-358.Zhang L F,Liu Z L,Tian P. Imagereconstruction algorithmfor electrical capacitance tomography based on compressedsensing[J]. Acta Electronica Sinica,2017,45(2):353-358.(in Chinese)
[3]李旭超,宋博.原始-对偶模型的牛顿迭代原理与图像恢复[J].电子学报,2015,43(10):1984-1993.Li X C,Song B. New ton iterative principle of primal-dualmodel and image restoration[J]. Acta Electronica Sinica,2015,43(10):1984-1993.(in Chinese)
[4]卢风顺,宋君强,银福康,等. CPU/GPU协同并行计算研究综述[J].计算机科学,2011,38(3):5-9.Lu F S,Song J B,Yin F K,et al. Survey of CPU/GPUsynergetic parallel computing[J]. Computer Science,2011,38(3):5-9.(in Chinese)
[5]吴恩华.图形处理器用于通用计算的技术、现状及其挑战[J].软件学报,2004,15(10):1493-1504.Wu E H. State of the art and future challenge on generalpurpose computation by graphics processing unit[J]. Jour-nal of Softw are,2004,15(10):1493-1504.(in Chinese)
[6]张朝晖,刘俊起,徐勤建. GPU并行计算技术分析与应用[J].信息技术,2009,(11):86-89.Zhang C H,Liu J Q,Xu Q J. Analysis and application ofthe GPU parallel computing technology[J]. InformationTechnology,2009,(11):86-89.(in Chinese)
[7]巨涛,等.异构众核系统及其编程模型与性能优化技术研究综述[J].电子学报,2015,43(1):111-119.Ju T,et al. The feature programming model and perform-ance optimization strategy of heterogeneous many-coresystem:a review[J]. Acta Electronica Sinica,2015,43(1):111-119.(in Chinese)
[8]Chang Y S,Wei J Z,Zhao G Y,et al. A novel architectureof special arithmetic function unit for area-efficient pro-grammable vertex shader[J]. Chinese Journal of Electron-ics,2013,22(3):483-488.
[9] Ravie C,Ali M. Enhancing the simulation of membranesystem on the GPU for the N-Queens problem[J]. ChineseJournal of Electronics,2015,24(4):740-743.
[10]陈德扬,李亚楼,江涵,等.基于道路树分层的大电网潮流并行算法及其GPU优化实现[J].电力系统自动化,2014,38(22):63-69.Chen D Y,Li Y L,Jiang H,et al. A parallel pow er flowalgorithm for large scale grid based on stratified path treesand its implementation on GPU[J]. Automation of Elec-tric Pow er Systems. 2014,38(22):63-69.(in Chinese)
[11]张宁宇,高山,赵欣.基于GPU的机电暂态仿真细粒度并行算法[J].电力系统自动化,2012,36(9):54-60.Zhang N Y,Gao S,Zhao X. A fine granularity parallel al-gorithm for electromechanical transient stability simulationbased on graphic processing unit[J]. Automation of Elec-tric Pow er Systems. 2012,36(9):54-60.(in Chinese)
[12]Alili M V,Dinavahi V. SIMD-based large-scale transi-ent stability simulation on the graphics processing unit[J]. IEEE Trans on Power Systems,2010,25(3):1589-1599.
[13]Yang G W. A highly efficient GPU-CPU hybrid parallelimplementation of sparse LU factorization[J]. ChineseJournal of Electronics,2012,21(1):7-12.
[14]李文沅.电力系统安全经济运行———模型与方法[M].重庆:重庆大学出版社出版,1989. 147-169.
[15] Mehrtash M,et al. An interior point optimization methodfor stochastic security-constrained unit commitment inthe presence of plug-in electric vehicles[J]. Journal ofApplied Sciences,2016,16:189-200.
[16]简金宝,杨林峰,全然.基于改进多中心校正解耦内点法的动态最优潮流并行算法[J].电工技术学报,2012,27(6):232-241.Jian J B,Yang L F,Quan R. Parallel algorithm of dynamicoptimal pow er flow based on improved multiple centralitycorrections decoupling interior point method[J]. Transac-tions of China Electrotechnical Society,2012,27(6):232-241.(in Chinese)
[17]Yang L F,Jian J B,Wang Y Y,et al. Projected mixed in-teger programming formulations for unit commitmentproblem[J]. International Journal of Electrical Pow er&Energy Systems,2015,68(68):195-202.
[18] Sharma G,Agarwala A,Bhattacharya B. A fast parallelGauss Jordan algorithm for matrix inversion using CUDA[J]. Computers&Structures,2013,128:31-37.
[19]刘丽,沈杰,李洪林.基于GPU的矩阵求逆性能测试和分析[J].华东理工大学学报,2010,36(6):812-817.Liu L,Shen J,Li H L. Performance testing and analysisfor matrix inversion based on GPU[J]. Journal of EastChina University of Science and Technology,2010,36(6):812-817.(in Chinese)