基于GPU加速的一种线性规划算法及其应用

论文摘要

线性规划问题是运筹学的一个基本分支,在资金分配和任务调度等各类经济生活中有着极其重要的作用,主要用来解决如何利用现有的资源,使得预期目标达到最优。但在处理大规模问题时,所需计算时间和内存都较大,并行算法很好的解决了上述问题。近年来,计算机图形处理器GPU (Graphic Processing Unit)的高速发展,其可编程能力、并行计算能力以及高速的浮点计算能力为通用计算提供了一个很好的平台。NVIDIA公司推出支持GPU编程的CUDA (Compute Unified Device Architecture)统一计算设备架构,为研究人员利用GPU进行并行计算研究提供了更加快捷的方法。本文针对传统单纯形法在求解大规模线性规划问题时存在效率上的不足,利用GPU的并行计算特性,提出了一种基于GPU加速的单纯形法。该算法充分利用了GPU的并行性,将典式的计算和检验数向量σ的计算迁移到GPU中,由n个线程同时进行；基础可行解的确定以及θ的计算也可以分别用n个与m个线程并行进行,大大降低了每次循环的所需时间。之后将传统的单纯形法与本文的方法做实验进行了比较,取得了较好的加速比。最后将本文算法与危险化学品泄露下的应急疏散相结合,对于应急疏散的突发性与制定疏散策略的实时性的特点,本文算法能过给予很好的满足。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 问题提出与研究意义
• 1.1.1 问题的提出
• 1.1.2 研究意义
• 1.2 国内外相关研究进展
• 1.2.1 线性规划的解法及存在的问题
• 1.2.2 GPU并行计算技术
• 1.3 本文的研究内容与结构
• 2 基于GPU加速的线性规划解法
• 2.1 模型设计分析
• 2.1.1 并行线性规划模型的设计
• 2.1.2 CUDA中的通信
• 2.1.3 CUDA中的数据存储
• 2.2 基于GPU加速的单纯形法
• 2.2.1 GPU中典式、基础可行解与θ的计算
• 2.2.2 单纯形法的GPU转化
• 2.2.3 针对GPU的优化处理
• 2.3 本章小结
• 3 基于GPU加速的单纯形法在危化品泄露中的应用
• 3.1 危化品泄露后的应急疏散模型
• 3.2 本文算法在应急疏散中的应用
• 3.3 实验结果与分析
• 3.3.1 实验结果比较
• 3.3.2 实验结果分析
• 3.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢