基于CPU-GPU协同并行内点算法求解结构化非线性规划

doi:10.3969/j.issn.0372-2112.2019.02.018

电子学报 ›› 2019, Vol. 47 ›› Issue (2): 382-389.DOI: 10.3969/j.issn.0372-2112.2019.02.018

基于CPU-GPU协同并行内点算法求解结构化非线性规划

杨林峰^1,3, 胡桂莉^1,2, 张晨¹, 张振荣³

1. 广西大学计算机与电子信息学院, 广西南宁 530004;
2. 广西电网有限责任公司贵港供电局, 广西贵港 537100;
3. 广西多媒体通信与网络技术重点实验室, 广西南宁 530004

收稿日期:2017-08-28 修回日期:2018-09-04 出版日期:2019-02-25
- 通讯作者:
- 杨林峰
- 作者简介:
- 胡桂莉 女,1990年8月生于广西贵港市,广西大学计算机与电子信息学院硕士研究生,主要研究方向为计算机网络与并行分布式计算.E-mail:794453997@qq.com
- 基金资助:
- 国家自然科学基金 (No.51767003，No.51407037，No.61661004）; 广西自然科学基金 (No.2016GXNSFDA380019）; 广西电力系统最优化与节能技术重点实验室基金 (No.15-A-01-11）

CPU-GPU Cooperative Parallel Interior Point Method for Structured Nonlinear Programming

YANG Lin-feng^1,3, HU Gui-li^1,2, ZHANG Chen¹, ZHANG Zhen-rong³

1. School of Computer, Electronics and Information, Guangxi University, Nanning, Guangxi 530004, China;
2. Guigang Power Supply Bureau, Guangxi Power Grid, Guigang, Guangxi 537100, China;
3. Guangxi Key Laboratory of Multimedia Communications and Network Technology, Nanning, Guangxi 530004, China

Received:2017-08-28 Revised:2018-09-04 Online:2019-02-25 Published:2019-02-25
- Supported by:
- National Natural Science Foundation of China (No.51767003, No.51407037, No.61661004); Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (No.2016GXNSFDA380019); Fund of Guangxi Key Laboratory of Power System Optimization and Energy Technology (No.15-A-01-11)

摘要/Abstract

摘要： 大量工程应用问题可建模为结构化非线性规划，且这类问题的系数矩阵可分为稀疏型和稠密型两种类型.利用原始-对偶内点法（primal dual interior point method，PD-IPM），并结合分布式并行技术可高效求解此类问题.经典工程问题-机组组合（unit commitment，UC）为稀疏系数矩阵的结构化非线性规划，本文根据PD-IPM原理，对UC模型进行连续松弛预处理，结合快速解耦技术解耦牛顿修正方程并设计CPU-GPU协同并行算法求解子问题，最后将结果与带稠密型子问题的结构化非线性规划的求解结果进行比较和分析.实验结果显示，本文所设计的算法对于两种不同类型的结构化非线性规划求解均能获得较好的加速比.

关键词: 非线性规划, 内点法, 机组组合, CPU-GPU协同, 并行计算

Abstract: 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.

Key words: nonlinear programming, interior point method, unit commitment, CPU-GPU cooperative, parallel computing

中图分类号:

TP3-0

杨林峰, 胡桂莉, 张晨, 等. 基于CPU-GPU协同并行内点算法求解结构化非线性规划[J]. 电子学报, 2019, 47(2): 382-389.

YANG Lin-feng, HU Gui-li, ZHANG Chen, et al. CPU-GPU Cooperative Parallel Interior Point Method for Structured Nonlinear Programming[J]. Acta Electronica Sinica, 2019, 47(2): 382-389.

参考文献

[1] Byrd R H,Hribar M E,Nocedal J.An interior point algorithm for large-scale nonlinear programming[J].SIAM Journal on Optimization,1999,9(4):877-900.
[2] 张立峰,刘昭麟,田沛.基于压缩感知的电容层析成像图像重建算法[J].电子学报,2017,45(2):353-358. Zhang L F,Liu Z L,Tian P.Imagereconstruction algorithm for electrical capacitance tomography based on compressed sensing[J].Acta Electronica Sinica,2017,45(2):353-358.(in Chinese)
[3] 李旭超,宋博.原始-对偶模型的牛顿迭代原理与图像恢复[J].电子学报,2015,43(10):1984-1993. Li X C,Song B.Newton iterative principle of primal-dual model 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/GPU synergetic 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 general purpose computation by graphics processing unit[J].Journal of Software,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 of the GPU parallel computing technology[J].Information Technology,2009,(11):86-89.(in Chinese)
[7] 巨涛,等.异构众核系统及其编程模型与性能优化技术研究综述[J].电子学报,2015,43(1):111-119. Ju T,et al.The feature programming model and performance optimization strategy of heterogeneous many-core system: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 architecture of special arithmetic function unit for area-efficient programmable vertex shader[J].Chinese Journal of Electronics,2013,22(3):483-488.
[9] Ravie C,Ali M.Enhancing the simulation of membrane system on the GPU for the N-Queens problem[J].Chinese Journal 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 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.(in Chinese)
[11] 张宁宇,高山,赵欣.基于GPU的机电暂态仿真细粒度并行算法[J].电力系统自动化,2012,36(9):54-60. Zhang N Y,Gao S,Zhao X.A fine granularity parallel algorithm for electromechanical transient stability simulation based on graphic processing unit[J].Automation of Electric Power Systems.2012,36(9):54-60.(in Chinese)
[12] Alili M V,Dinavahi V.SIMD-based large-scale transient 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 parallel implementation of sparse LU factorization[J].Chinese Journal of Electronics,2012,21(1):7-12.
[14] 李文沅.电力系统安全经济运行——模型与方法[M].重庆:重庆大学出版社出版,1989.147-169.
[15] Mehrtash M,et al.An interior point optimization method for stochastic security-constrained unit commitment in the presence of plug-in electric vehicles[J].Journal of Applied Sciences,2016,16:189-200.
[16] 简金宝,杨林峰,全然.基于改进多中心校正解耦内点法的动态最优潮流并行算法[J].电工技术学报,2012,27(6):232-241. Jian J B,Yang L F,Quan R.Parallel algorithm of dynamic optimal power flow based on improved multiple centrality corrections decoupling interior point method[J].Transactions 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 integer programming formulations for unit commitment problem[J].International Journal of Electrical Power & Energy Systems,2015,68(68):195-202.
[18] Sharma G,Agarwala A,Bhattacharya B.A fast parallel Gauss 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 analysis for matrix inversion based on GPU[J].Journal of East China University of Science and Technology,2010,36(6):812-817.(in Chinese)

基于CPU-GPU协同并行内点算法求解结构化非线性规划

CPU-GPU Cooperative Parallel Interior Point Method for Structured Nonlinear Programming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[3]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[4]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[5]	王卫杰, 陈晓洁, 周海京. 基于区域分解的大规模并行有限元快速算法[J]. 电子学报, 2019, 47(3): 741-747.
[6]	曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报, 2019, 47(2): 266-273.
[7]	冯晓, 戴紫彬, 蔡路亭, 李伟. 基于Amdahl定律扩展的多核处理器性能模型研究[J]. 电子学报, 2017, 45(6): 1424-1430.
[8]	卞琛, 于炯, 英昌甜, 修位蓉. 并行计算框架Spark的自适应缓存管理策略[J]. 电子学报, 2017, 45(2): 278-284.
[9]	张立峰, 刘昭麟, 田沛. 基于压缩感知的电容层析成像图像重建算法[J]. 电子学报, 2017, 45(2): 353-358.
[10]	潘卫国, 何宁, 薛健, 吕科, 翟锐, 代双凤. 海量超声数据体可视化研究[J]. 电子学报, 2016, 44(2): 472-478.
[11]	周旭, 周炎涛, 李肯立, 欧阳艾嘉, 潘果. 基于Tile自组装模型的最大匹配问题算法研究[J]. 电子学报, 2015, 43(2): 262-268.
[12]	徐红, 黄朝耿, 宋洪波, 周志光, 李刚. 并行计算的全通数字滤波器结构[J]. 电子学报, 2015, 43(10): 2034-2039.
[13]	王勇献, 张理论, 车永刚, 徐传福, 刘巍, 程兴华. 结构网格CFD应用程序在天河超级计算机上的高效并行与优化[J]. 电子学报, 2015, 43(1): 36-44.
[14]	叶蕾;杨震;王天荆;孙林慧. 行阶梯观测矩阵、对偶仿射尺度内点重构算法下的语音压缩感知[J]. 电子学报, 2012, 40(3): 429-434.
[15]	过洁;徐晓旸;潘金贵. 虚拟场景的一种快速优化Kd-Tree构造方法[J]. 电子学报, 2011, 39(8): 1811-1817.