基于GPU平台的SVD并行计算研究与实现

发布时间：2017-05-12 04:03

  本文关键词：基于GPU平台的SVD并行计算研究与实现，由笔耕文化传播整理发布。

【摘要】：矩阵的奇异值分解作为一种重要的矩阵分解,在数学、物理学、医学、工学等学科和领域具有广泛的应用背景。矩阵奇异值分解数值计算的研究由来已久,其中,计算速度和精度是该项研究的基本内容,近几十年来,由于并行计算系统的出现,奇异值分解的并行算法研究逐渐成为热点,但是,以往的研究主要针对任务级并行,这种并行算法对矩阵的划分粒度较粗,适用于多处理器计算系统。近年来以GPU为代表的众核处理器采用SIMD或SIMT体系结构,传统的并行SVD算法在这些平台上计算并不能发挥出较高的效率。因此,本文将基于GPU平台的SVD并行计算作为本文的主要研究方向。本文首先研究了基于QR方法的SVD算法。作为应用最为广泛的算法,针对该算法的研究较为广泛,但由于该算法串行度较高,数据依赖性较强,其并行算法的效率通常不高。本文从运算速度和精度两方面分析了带Wilkinson位移的QR迭代算法、零位移QR迭代算法以及它们的混合选择算法的性能特点和差异,针对这些算法在上对角元素归零过程中的“向下越界”问题,在混合选择算法的基础上进行改进,设计了动态位移算法,对该算法进行的数值实验结果表明,该算法对矩阵收敛速度起到积极作用,相对传统算法的最高加速比在1.1以上;此外,本文设计了基于GPU平台的细粒度并行动态位移算法,并对其中的矩阵对角化更新提出了一种新的细粒度并行划分方法,该方法将算法中串行度较高的二对角矩阵更新部分在GPU高效并行执行,优化后的算法运行时间能减少10%左右。基于Jacobi方法的SVD算法是另外一种重要的算法,它具有相对精度高等特点,该方法分为双边Jacobi算法和单边Jacobi算法,其中,单边Jacobi算法运算量小,且其结构易于并行计算,本文对并行单边Jacobi算法进行了深入研究。数据调度序列用来生成每次并行迭代参与运算的列对组合,对算法性能起到关键作用,本文通过数值实验分析了列范数波动对算法收敛速度的影响,并基于此结果,研究了并行单边Jacobi算法的各类静态序列和动态序列的性能特点,针对单独使用静态序列无用计算过多、动态序列附加运算量大等问题,本文结合二者优势,给出了二者的混合序列算法,并结合列范数波动率给出了序列选择依据,数值实验结果表明,混合算法能够改善算法的收敛速度,运算速度相比传统算法能够提高10%以上。另外,本文设计了改进算法在GPU平台的细粒度并行算法,提出了静态序列更新在GPU实现的优化方法,避免了列交换带来的额外计算开销。最后,本文对提出的多种改进算法在NVIDIA Tesla C2050平台进行了实现,并对改进的算法实现进行了性能测试。本文的测试包含了算法执行的总时间以及其中的主要部分分步骤执行的时间,同时,对改进的算法和传统算法实现进行了性能比较,并对测试结果进行了分析和总结。测试结果表明:在精度一致的情况下,本文改进的动态位移QR迭代SVD算法相比混合选择算法的加速比最高能达到1.1,本文改进的混合序列并行单边Jacobi算法相比单纯使用静态序列和动态序列的算法加速比分别能达到1.15和1.05。另外,测试数据反映的部分信息能够为进一步优化提供方向。
【关键词】：奇异值分解 GPU QR Jacobi 并行计算
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O241.6;TP338.6
【目录】：

• 摘要5-7
• ABSTRACT7-16
• 第一章 绪论16-24
• 1.1 背景与意义16
• 1.2 研究现状16-22
• 1.2.1 基于QR方法的SVD算法16-17
• 1.2.2 基于Jacobi方法的SVD算法17-20
• 1.2.3 基于GPU平台的并行实现20-22
• 1.3 本文研究内容22-23
• 1.4 本文组织结构23-24
• 第二章 并行计算技术与开发环境24-38
• 2.1 并行执行环境24-26
• 2.1.1 传统并行计算系统24-25
• 2.1.2 GPU通用计算平台25-26
• 2.2 并行算法设计方法26-30
• 2.2.1 传统并行算法设计方法27-28
• 2.2.2 细粒度并行算法设计方法28-29
• 2.2.3 并行算法性能评估29-30
• 2.3 CUDA平台及GPU通用计算模型30-37
• 2.3.1 CUDA平台概述30-31
• 2.3.2 GPU通用计算模型31-37
• 2.4 小结37-38
• 第三章 QR迭代SVD并行算法研究38-53
• 3.1 QR迭代SVD算法38-42
• 3.1.1 基本算法原理38-39
• 3.1.2 基于Householder变换的二对角化39-40
• 3.1.3 二对角矩阵的对角化40-42
• 3.2 QR方法的局限及改进算法42-48
• 3.2.1 两种主要QR算法性能分析42-45
• 3.2.2 改进的动态位移QR算法45-46
• 3.2.3 动态位移QR算法性能分析46-48
• 3.3 改进算法在GPU平台的并行算法设计48-52
• 3.3.1 二对角化并行算法设计48-49
• 3.3.2 对角化并行算法设计49-52
• 3.4 小结52-53
• 第四章 基于JACOBI方法的SVD并行算法研究53-72
• 4.1 传统Jacobi算法53-57
• 4.1.1 双边Jacobi算法53-55
• 4.1.2 单边Jacobi算法55-57
• 4.2 混合序列单边Jacobi算法设计57-67
• 4.2.1 静态数据调度序列57-62
• 4.2.2 动态序列Jacobi算法分析62-64
• 4.2.3 改进的混合序列单边Jacobi算法64-65
• 4.2.4 混合序列算法精度控制65-67
• 4.3 混合序列算法性能分析67-68
• 4.4 混合序列算法在GPU平台的并行算法设计68-71
• 4.4.1 静态序列更新的实现优化68-69
• 4.4.2 并行单边Jacobi旋转69-71
• 4.5 小结71-72
• 第五章 基于GPU平台的算法实现与性能测试72-96
• 5.1 算法实现与测试平台72-75
• 5.1.1 软硬件平台72-74
• 5.1.2 测试方法74
• 5.1.3 测试技术74-75
• 5.2 动态位移QR迭代算法的GPU实现与性能测试75-88
• 5.2.1 总体实现方案75-76
• 5.2.2 原矩阵的二对角化76-80
• 5.2.3 二对角矩阵的对角化80-84
• 5.2.4 性能测试84-88
• 5.3 混合序列并行单边Jacobi算法的GPU实现与性能测试88-95
• 5.3.1 总体实现方案88-89
• 5.3.2 调度序列更新89-90
• 5.3.3 Jacobi旋转90-91
• 5.3.4 性能测试91-95
• 5.4 小结95-96
• 第六章 总结与展望96-99
• 6.1 本文工作总结96-97
• 6.2 展望97-99
• 致谢99-100
• 参考文献100-104
• 个人简历及攻读硕士学位期间的研究成果104-105

【相似文献】

中国期刊全文数据库 前10条

1 郑敏娟;贺炎;;未来的并行计算[J];中国科技信息;2007年12期

2 王宏琳;;数字滤波的并行计算[J];石油地球物理勘探;1984年02期

3 ;光计算[J];中国光学与应用光学文摘;2001年04期

4 孙安香,宋君强,李晓梅;数值气象预报中的并行计算研究[J];高技术通讯;2001年12期

5 赖国明,杨圣云;一种利用工作站群集的并行计算研究方案[J];河南大学学报(自然科学版);2004年02期

6 莫则尧;张爱清;曹小林;左风丽;;多介质辐射流体力学数值模拟中的并行计算研究[J];自然科学进展;2006年03期

7 张繁;王松;;并行计算在生物信息学中的应用[J];科技信息(科学教研);2007年36期

8 李晓梅,张宝琳,康立山;全国并行计算学术交流会的回顾——纪念全国并行计算专业委员会成立十周年[J];科学中国人;2000年12期

9 陈波,韩永国,刘志勤;高性能并行计算的研究与分析[J];四川师范学院学报(自然科学版);2003年02期

10 伍湘君,黄丽萍;超级计算机上矩阵乘的并行计算与实现[J];应用气象学报;2005年01期

中国重要会议论文全文数据库 前10条

1 黄宇光;;整体同步并行计算方法的现状与发展[A];信息科学与微电子技术:中国科协第三届青年学术年会论文集[C];1998年

2 罗文彩;陈小前;;并行计算的多方法优化协作[A];第二十四届中国控制会议论文集（上册）[C];2005年

3 左风丽;莫则尧;叶文华;;计算流体三维分裂格式的高效并行计算[A];中国工程物理研究院科技年报（2003）[C];2003年

4 王欣;李志山;张志远;;并行计算在弹塑性时程分析中的应用[A];信息化推动工程建设工业化——第四届工程建设计算机应用创新论坛论文集[C];2013年

5 张理涛;黄廷祝;谷同祥;左宪禹;;一种适合于分布式并行计算改进的平方共轭残差法[A];2008年全国开放式分布与并行计算机学术会议论文集(下册)[C];2008年

6 胡金初;;并行计算中的任务分配算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

7 宋庭新;李慧;;面向服务的有限元并行计算网格系统设计[A];湖北省机械工程学会设计与传动学会、武汉机械设计与传动学会2008年学术年会论文集（2）[C];2008年

8 裘懿勇;徐斌;刘晓明;;并行计算作业调度系统的架构及应用[A];第十四届中国科协年会第5分会场：绿色船舶与海洋装备创新发展及产业化论坛论文集[C];2012年

9 裘懿勇;徐斌;刘晓明;;并行计算作业调度系统的架构及应用[A];2012年MIS/S&A学术交流会议论文集[C];2012年

10 肖保国;杨顺华;邢建文;赵慧勇;;当地自适应建表方法在煤油超燃发动机并行计算中的应用[A];第十四届全国激波与激波管学术会议论文集（下册）[C];2010年

中国重要报纸全文数据库 前10条

1 轶嘉;英特尔全球首个并行计算中心落户无锡[N];人民邮电;2009年

2 曙光信息产业有限公司研发中心 温鑫;并行计算任重道远[N];中国计算机报;2007年

3 英特尔并行计算实验室研究员 TimothyMattson;并行计算:减少串行软件[N];中国计算机报;2007年

4 曙光信息产业有限公司研发中心 温鑫;并行计算软件开发概述[N];中国计算机报;2007年

5 刘霞;计算能力的提升需要一场革命[N];科技日报;2010年

6 安世亚太 雷先华;ANSYS高性能并行计算[N];中国航空报;2005年

7 张云泉;并行计算：迎接多核时代的挑战[N];计算机世界;2006年

8 本报记者 马文方;英特尔为何要牵头并行计算[N];中国计算机报;2009年

9 英特尔 赵军(Jun Zhao);PC机并行计算革命尚未成功[N];中国计算机报;2009年

10 ;Linux下的网络并行计算[N];计算机世界;2000年

中国硕士学位论文全文数据库 前10条

1 顾慧;基于异构平台的并行计算性能可视化研究[D];辽宁师范大学;2010年

2 徐晓华;光并行计算及其在图像处理和计算分子生物学中的应用[D];扬州大学;2005年

3 田甜;异构环境中并行计算模型与任务调度的研究[D];曲阜师范大学;2010年

4 刘杰;可扩展并行计算及其应用研究[D];湖南大学;2009年

5 孔令梅;三维变分同化并行计算研究及实现[D];国防科学技术大学;2005年

6 刘桂海;网格并行计算系统研究开发[D];西安理工大学;2008年

7 蔡佳佳;图像代数多核并行计算类库的构建与优化[D];厦门大学;2008年

8 陈维;有限单元并行计算方法在地震波动模拟中的应用[D];中国地震局工程力学研究所;2011年

9 陆良刚;土木工程有限元并行计算应用及其软件架构[D];中国地震局工程力学研究所;2011年

10 张立霞;电磁场有限元分析中并行计算的研究[D];河北工业大学;2006年

  本文关键词：基于GPU平台的SVD并行计算研究与实现，由笔耕文化传播整理发布。

，

本文编号：358697