结构化非线性规划的CPU-GPU协同并行内点算法研究

摘要

近年来，图形处理器(Graphics Processing Units，GPU)在非图形处理的通用计算领域取得了丰硕的研究成果，与此同时，在最优化计算领域，只依靠CPU对大规模问题进行求解遇到了计算资源不足的困难。因此，本文设计了基于CPU与GPU协同并行的方法来求解结构化非线性规划。结构化非线性规划的所有约束条件构成约束集合，约束集合中的约束项具有一定的耦合性和独立性，采用高效的内点算法求解该类问题时，其形成的修正方程系数矩阵具有分块带边的箭型结构。在工程应用上，许多实际问题具有这样的特征，比如:电力系统的机组组合问题、最优潮流问题、物流管理中的多商品网络流问题以及通信中的网络保护问题等，且其中机组组合问题是该类问题的典型代表。因此，对结构化非线性规划的研究可以帮助工程更好的做决策。
　　利用原始-对偶内点法求解诸如连续松弛的机组组合问题之类的结构化非线性规划时，通过合理的对变量和约束进行分组，可使得迭代过程中产生的牛顿修正方程的系数矩阵具有分块带边的特殊结构。本文基于快速解耦技术将该牛顿修正方程进行解耦，可以得到多个相互独立的子问题，从而采用CPU与GPU协同粗粒度并行的方式实现问题的快速求解。
　　针对粗粒度并行计算子线性系统难以充分利用GPU资源的问题，本文在粗粒度并行模式上进一步的优化研究。对求解过程中耗时最长的牛顿修正方程的子问题求解进行独立分析，设计并行高斯-约旦算法从细粒度的层面对其进行并行计算。
　　本文利用CPU-GPU从粗粒度的层面，分别协同并行求解带稀疏型和稠密型修正方程系数矩阵的两种应用问题。对不同规模的子问题分别进行了实验计算，结果表明本文的方法在考虑结构化非线性规划时，对预处理的模型，尤其是带稠密型子问题的结构化非线性规划可以得到比较好的并行效果。同时，从细粒度的层面设计并行高斯-约旦算法求解牛顿修正方程的子问题也取得了一定的加速比。因此，本文从粗粒度和细粒度两个角度分别进行了并行算法设计，具有求解带结构化非线性规划的潜力。

目录

声明

摘要

第一章 绪论

1．1 课题的背景与研究意义

1．2 国内外研究的现状

1．2．1 内点算法的研究现状

1．2．2 并行最优化研究现状

1．2．3 机组组合的研究现状

1．2．4 高斯约旦消元法的研究现状

1．3 本论文的主要研究内容

1．4 论文的组织结构

第二章 理论知识储备

2．1 MATLAB并行计算

2．1．1 MATLAB简介

2．1．2 MATLAB并行计算工具箱(Parallel Computing Toolbox，PCT)

2．2 GPU并行计算

2．2．1 GPU结构简介

2．2．2 GPU并行计算编程

2．2．3 GPU并行计算实现

2．3 内点算法

2．3．1 内点法的分类

2．3．2 原始-对偶内点法的基本原理

2．4 高斯约旦消元法

2．4．1 高斯约旦算法的概述

2．4．2 高斯约旦算法并行求矩阵的逆运算

第三章 并行内点算法设计与实现

3．1 结构化非线性规划的内点算法

3．1．1 结构化非线性规划的内点算法框架

3．1．2 对修正方程进行解耦

3．2 并行内点求解结构化机组组合问题

3．2．1 机组组合的目标函数

3．2．2 机组组合的约束条件

3．2．3 预处理机组组合的模型

3．2．4 求解机组组合的流程

3．3 CPU_GPU协同并行计算

3．4 实验结果分析

3．5 具有稠密子块的问题

第四章 求解稠密线性方程组子问题的改进高斯约旦算法

4．1 线性方程组子问题简介

4．2 基于高斯约旦求解矩阵的逆运算

4．2．1 高斯消元法与高斯-约旦消元法的区别

4．2．2 改进的高斯-约旦算法求解逆矩阵的流程

4．3 基于CUBLAS函数求矩阵的逆运算

4．3．1 基于CUBLAS求解矩阵的逆运算

4．4 数值实验分析

4．4．1 基于高斯约旦算法求矩阵的逆

4．4．2 并行高斯约旦法与CUBLAS函数库方法的实验结果比较

第五章 总结与展望

5．1 总结

5．2 展望未来

参考文献

致谢

攻读硕士学位期间参加的科研项目

攻读硕士学位期间发表论文情况

附录