基于GPU的高性能并行优化算法研究

发布时间：2020-10-12 22:11

　　 随着高性能并行计算设备的日益普及,特别是高性能图形处理器(GPU)的迅猛发展,基于GPU高性能计算平台的并行优化应用服务解决方案引起国内外研究学者的极大关注。由于传统CPU、计算集群在计算资源以及能耗方面的限制,以及各类科学工程优化问题对于并行计算需求的不断提升,基于高性能并行计算的扩展模型、仿真计算、算法优化以及数值计算已经成为当前高性能计算的研究热点。高性能并行优化算法作为衔接底层并行计算平台及上层应用服务的关键部分,在算法性能的优化以及应用空间的扩展方面仍然存在严峻挑战和亟需解决的问题,需要对算法优化和数值计算问题的方法和技术不断提高和完善。基于此,本文将重点进行高性能并行计算随机数生成、智能算法优化和数值计算算法等方面的研究创新。针对随机数生成器、蚁群算法、最小平方估计等问题,采用GPU扩展加速比模型、GPU局部优化等技术,设计并提出三个关键的并行优化解决方案。 主要研究内容和创新点如下： (1)针对传统随机数生成速度较慢及加速优化模型扩展性较差的问题,通过对当前可扩展加速优化模型及随机数生成器机制的分析总结,给出一种考虑存储层次的GPU可扩展加速比优化模型,并基于该模型提出了一种简单的高性能并行计算随机数生成算法(简称为CUDA-RNG),该算法充分利用了GPU间的协同计算能力,最终可以生成高效率的随机数序列。实验结果表明,CUDA-RNG算法能够在连续计算运行时达到189.32倍的生成速度,且具有很小的内存负载开销。 (2)针对蚁群算法在大规模的最优化问题中难以得到最优解的问题,受蚁群算法在本质上具有并行性特点的启发,着重研究如何在GPU并行计算环境下提高蚁群算法的性能及效率。通过对TSP(旅行商)问题的蚁群算法建模,提出一种新的基于CUDA(统计算设备架构)的蚁群优化算法,简称为GACO。该算法结合了MMAS(MAX-MIN Ant System)和ACS(Ant Colony System)的共性特点进行混合信息矩阵更新、动态构建最短邻接路径和多路蚁群分布等优化策略。最后对GPU的性能优化方案做了分析,通过使用这些优化策略使得该算法跟同等类型的算法相比具有更高的速度和质量。实验结果表明,本文提出的GACO算法性能在搜索加速度上分别比ACS、MMAS要高出40.1倍与35.7倍。 (3)针对在数据规模较大情况下利用奇异值分解求最小平方时的时间消耗和内存空间代价过大的问题,提出了一种基于GPU的迭代式分割与合并的奇异值分解最小平方估计法,简称为IDMSVD。该算法可以有效的改善对于大型数据利用奇异值分解求最小平方问题时的运算时间和内存空间。最后在GPU的CUDA计算架构的中进行了实现,通过实验验证了算法的有效性。 本文所提出的算法具有普适意义,能够轻松地转移到其他的并行计算设备上,比如多核CPU或者大规模集群设备。更高性能的加速平台如CPU和GPU混合构架(或GPU集群)、GPU和FPGA(现场可编程门阵列)混合构架等都有望应用到高性能并行优化算法的研究中。
【学位单位】：大连理工大学
【学位级别】：博士
【学位年份】：2014
【中图分类】：TP332
【文章目录】：
摘要
ABSTRACT
1 绪论
    1.1 研究背景与意义
    1.2 并行技术
        1.2.1 并行计算机体系结构
        1.2.2 并行算法分类
        1.2.3 基于CUDA并行编程架构
    1.3 国内外研究现状
        1.3.1 经典优化技术研究现状
        1.3.2 现代智能优化技术研究现状
    1.4 本文的主要研究内容
    1.5 本文的组织结构
2 基于GPU的并行随机数生成优化算法
    2.1 引言
    2.2 相关工作
    2.3 算法描述
        2.3.1 加速比扩展模型
        2.3.2 随机序列递推公式
        2.3.3 数据类型转换
        2.3.4 并行随机数生成器
    2.4 实验及结果分析
        2.4.1 随机数生成实验
        2.4.2 加速比实验
    2.5 本章小结
3 基于GPU的并行蚁群优化算法
    3.1 引言
    3.2 相关工作
        3.2.1 智能优化算法
        3.2.2 蚁群算法原理
    3.3 算法描述
        3.3.1 TSP问题蚁群算法建模
        3.3.2 混合信息矩阵更新
        3.3.3 动态构建最短邻接路径
        3.3.4 多蚁群分布
        3.3.5 GPU局部性优化
    3.4 实验及结果分析
        3.4.1 算法实验
        3.4.2 性能优化实验
    3.5 本章小结
4 基于GPU的并行迭代式分割与合并优化算法
    4.1 引言
    4.2 相关工作
        4.2.1 最小平方估计问题
        4.2.2 解最小平方估计问题
    4.3 算法描述
        4.3.1 迭代式分割与合并
        4.3.2 复杂度分析
        4.3.3 矩阵转化
    4.4 实验及结果分析
        4.4.1 测试用例及平台
        4.4.2 实验结果
    4.5 本章小结
5 结论与展望
    5.1 结论
    5.2 创新点摘要
    5.3 展望
参考文献
攻读博士学位期间科研项目及科研成果
致谢
作者简介

【参考文献】

相关期刊论文 前1条

1 吴恩华;图形处理器用于通用计算的技术、现状及其挑战[J];软件学报;2004年10期

本文编号：2838348