面向GPU的并行稀疏对角矩阵矢量乘算法研究及应用

发布时间：2020-07-08 15:54

【摘要】：稀疏矩阵结构存在于众多科学学科中,且在线性代数、数据挖掘和图形分析等领域具有广泛应用。稀疏矩阵矢量乘在计算科学领域中具有重要意义。随着通用图形处理单元GPU编程模型和开发工具链的成熟,面向GPU加速稀疏矩阵矢量乘已得到研究者们的广泛关注。稀疏对角矩阵是一类特殊的稀疏矩阵,其非零元素大多都集中在少量对角线上。DIA格式是最适合用来存储稀疏对角矩阵的存储格式,然而,当稀疏对角矩阵中的对角线存在长断行、长偏移或者散点等情况时,如果继续采用DIA去存储,将引起大量零元素填充,导致DIA核的性能大大下降。稀疏块对角矩阵也是一类特殊的稀疏矩阵,其非零元素结构呈现块对角形态。显然,DIA格式不适用存储此类矩阵,CSR和ELL格式虽然能有效存储,但由于没有利用其对角结构,其核的性能并不好。为此,本文从两类矩阵出发,基于GPU编程模型CUDA,深入研究面向GPU的稀疏对角矩阵矢量乘算法。本文的主要工作和贡献如下:1.提出了基于GPU的自适应并行稀疏对角矩阵矢量乘算法DIA-Adaptive。针对稀疏对角矩阵的对角线存在长偏移、长断行以及少量散点情况,首先,依据一定规则将矩阵分为三类;进而基于这些分类,除第一类采用原有的DIA算法外,其余两类,分别提出新颖的BRCSD-I算法和BRCSD-Ⅱ算法与之相对应;最后,还设计了一个搜索引擎和代码自动生成器,任一稀疏对角矩阵经过搜索引擎可自动识别类型,选择合适的存储格式,并自动生成对应内核。实验证明,本论文提出的DIA-Adaptive算法是有效的,具有较高的性能和良好的并行性。2.提出基于GPU的并行稀疏块对角矩阵矢量乘算法IndexBDIA。针对一类稀疏块对角矩阵,利用其块呈对角结构,先将稀疏块对角矩阵划分成许多个某一尺寸大小的小矩阵块,并记录每一小矩阵块对应的行列索引值;进而通过行列索引值找出块对角线,块对角线的建立大大减少了行列索引值的存储;最后,根据块对角线偏移值对矩阵进行行断划分存储,有效减少了块对角线存在大偏移时所需要的零元素填充。实验证明,提出的IndexBDIA算法性能较好。3.应用求解Klein-Gordon-Schrodinger(KGS)方程,验证本文提出的算法的有效性。针对离散2D和3DKGS方程后得到的稀疏对角线性系统,基于GMRES算法,将本文提出的自适应稀疏对角矩阵矢量乘算法引入,设计了一种新颖的GPU加速的时间域GMRES算法T-GMRES。实验证明,本文提出的算法应用于求解2D和3D KGS方程是有效的。
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP301.6;TP332
【图文】：

随着通用图形处理单兀（Ｇｒａｐｈｉｃｓ邋Ｐｒｏｃｅｓｓｉｎｇ邋Ｕｎｉｔ，邋ＧＰＵ）编程模型和开逡逑发工具链的成熟，ＧＲＪ给通用计算，特别是高性能计算带来了前所未有的机遇。ＧＰＵ逡逑的设计理念与ＣＰＵ有很大不同如图１．１所示。在ＧＰＵ中，绝大部分资源用于计逡逑算，当前，ＧＰＵ的计算能力和带宽都比ＣＰＵ高出一个数量级，主流ＧＰＵ的计算能逡逑力已达到６Ｔ０ＰＳ，存储带宽达到５００ＧＢ／Ｓ。因此本论文的运算都是面向ＧＰＵ架构的。逡逑ＩＩ邋｜ｉ逦Ｕ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋ｉ邋１邋Ｉ邋Ｉ邋ＩＴＴ１逡逑逦ｕ逦Ｉ邋Ｉ逦Ｍ逦Ｉ逦Ｉ逦Ｉ邋Ｉ逦Ｍ逦［逦ｉ逦ｒｍ逡逑ＩＩ逦Ｕ逦ＩＩ逦Ｉ邋Ｉ逦Ｉ逦Ｉ逦１１逦１邋Ｉ逦Ｉ逦Ｉ逦Ｉ邋ｉｌ邋ｉ逡逑逦ＩＬ逦逦邋ｕ逦ｉ邋ｉ逦ｉ邋Ｉ逦ｉ逦Ｉ逦ｍ逦ｉ邋ｉ逦ｉ逦ｉ逦ｉ￣ｍ逡逑逦邋Ｍ邋Ｉ邋ｌｉ邋ＩＩ邋Ｉ邋Ｉ邋ＩＩ邋ＩＩ邋Ｉ邋ＩＩ邋ＩＩ逡逑0控制调节器逦ｂｒｆ丨！丨！邋！邋！邋！丨」Ｉ邋ｉ丨丨．ｌｌｊ逡逑，＿＿逦ｂｉ邋ＩＩ邋１邋ｉ邋１邋ＩＩ邋１邋Ｉ邋Ｉ邋Ｉ邋１邋ＩＴＴ１逡逑＾邋木逻辑单兀邋逦－逦－逦Ｕ邋Ｍ邋Ｉ邋ｉｌ邋ＩＩ邋Ｉ邋１１邋Ｉ邋１１邋１１邋１逡逑缓存逦逦逦逦逡逑？邋ＤＲＡＭ逡逑ＣＰＵ逦ＧＰＵ逡逑图１．１邋ＣＰＵ和ＧＰＵ的体系结构逡逑稀疏对角矩阵是一种特殊的稀疏矩阵，它的非零元素集中在少量的对角线上。且逡逑在许多领域有着广泛的应用。例如，在计算流体力学和电磁学等领域中的许多问题，逡逑采用有限差分法（Ｆｉｎｉｔｅ邋Ｄｉｆｆｅｒｅｎｃｅ邋Ｍｅｔｈｏｄ

ＤＩＡ邋（ＨＤＩ）格式来减少零元素的填充。在ＨＤＩ格式中，原始矩阵被划分成若干个具逡逑有相同行数量的矩阵块，且每个独立矩阵块采用ＤＩＡ格式存储。由于ＤＩＡ格式的使逡逑用，ＨＤＩ格式无法解决矩阵中对角线存在偏移的情况。综合上述研宄来看，对于图１．２逡逑的稀疏对角矩阵存在的情况，现有算法都存在着一定的不足。因此，本论文对稀疏对逡逑角矩阵进一步进行研宄，基于ＣＵＤＡ邋（ＣｏｍｐｕｔｅＵｎｉｆｉｅｄＤｅｖｉｃｅＡｒｃｈｉｔｅｃｔｕｒｅ），通过提逡逑出一种自适应的并行稀疏对角矩阵矢量乘算法，完美解决了稀疏对角矩阵中存在散点、逡逑长断行或者对角线偏离主对角线较远等情况问题。逡逑另外，在均匀网格上离散偏微分方程组时，对于每个网格节点上具有高自由度的逡逑结构化网格问题产生的矩阵，其非零元素结构往往具有一定规律，呈现如图１．３的样逡逑式。图１．３中的稀疏矩阵被称为稀疏块对角矩阵。逡逑显然，ＤＩＡ格式不适合这种稀疏块对角矩阵的存储。ＣＳＲ和ＥＬＬ虽然能有效存逡逑２逡逑

？？逦？？？？？？＇？邋■长断行逡逑图１．２稀疏对角矩阵实例逡逑为此，Ｙｕａｎ邋等［５］２０１０邋年提出了邋ＤＤＤ－ＮＡｌＶＥ邋和邋ＤＤＤ－ＳＰＬＩＴ邋算法。ＤＤＤ－ＮＡｉＶＥ逡逑算法依次存储对角线上元素，对于含有稠密对角线矩阵具有较好的效率，但无法解决逡逑对角线存在长断行情况。ＤＤＤ－ＳＰＬＩＴ算法利用对角线将稀疏矩阵分块，通过压缩相逡逑同元素节省存储空间。然而，这两种算法均未给出并行解决方案。Ｓｕｎ等Ｗ在２０１１年逡逑提出了邋ＣＲＳＤ邋（Ｃｏｍｐｒｅｓｓｅｄ邋Ｒｏｗ邋Ｓｅｇｍｅｎｔ邋ｗｉｔｈ邋Ｄｉａｇｏｎａｌ邋Ｐａｔｔｅｒｎ）格式，相比邋ＤＩＡ，含巨逡逑大大减少零元素的填充。在ＣＲＳＤ中，通过定义对角线模式表示对角线分布，将对角逡逑线分到不同组，进而将矩阵分成若干行段；如果行段中对角线上元素具有相同模式，逡逑则将此类行段看成一个存储和操作单元

【相似文献】

相关期刊论文 前10条

1 张友惠;;分块次对角矩阵的定义及性质[J];湖南科技学院学报;2008年04期

2 钱爱林,吴又胜;对称双边对角矩阵的特征值问题[J];河西学院学报;2005年05期

3 刁新军;黄廷祝;曾翎;冉瑞生;;五对角矩阵的分解及其逆元素的快速算法[J];电子科技大学学报;2005年06期

4 吴燕翔,王良恩,邱挺;二对角矩阵法及其在催化精馏塔模拟计算中的应用[J];福州大学学报(自然科学版);2000年01期

5 黄镜新;模糊错误二类5对角矩阵方程求解[J];广东工业大学学报;1998年S1期

6 周小庄，胡锡炎;实对称五对角矩阵及其特征反问题[J];湖南大学学报(自然科学版);1996年01期

7 吴长勤,张银云;灰对角矩阵的一些性质[J];安徽农业技术师范学院学报;1997年04期

8 周志华;吴汉金;李永元;侯怀德;;上机图及配色效应图内部转换的数学模型[J];中国纺织大学学报;1988年03期

9 钱岷江;;基于双线性变换从S域到Z域的对角矩阵算法[J];现代机械;1988年04期

10 王秀玉,姜兴武,李慧玲;对称双边对角矩阵的性质及广义逆[J];东北师大学报(自然科学版);2005年03期

相关会议论文 前4条

1 黄镜新;;二类4模糊错误对角矩阵方程求解[A];1998年中国智能自动化学术会议论文集（上册）[C];1998年

2 王健;陈丙珍;何小荣;;化工过程模拟与优化的新进展——并行计算方法[A];过程系统工程2001年会论文集[C];2001年

3 毛希安;;二维NOE谱幅度矩阵的数学特性[A];第七届全国波谱学学术会议论文摘要集[C];1992年

4 梁冬梅;马玉臣;;多体格林函数方法研究二元砷化物的光电特性[A];中国化学会第十二届全国量子化学会议论文摘要集[C];2014年

相关重要报纸文章 前1条

1 教育部考试中心命题一部、社会考试处;考研细看命题变化[N];中国教育报;2002年

相关博士学位论文 前1条

1 聂玺;阵列信号二维测向算法研究[D];电子科技大学;2015年

相关硕士学位论文 前10条

1 夏羿飞;面向GPU的并行稀疏对角矩阵矢量乘算法研究及应用[D];南京师范大学;2019年

2 李志勇;基于对角矩阵的温湿度模糊解耦控制系统的研究[D];石家庄铁道大学;2018年

3 蔺彦玲;几类特殊矩阵求其逆的快速算法研究[D];陕西科技大学;2017年

4 郑永梅;实对称五对角矩阵的逆特征值问题[D];南京航空航天大学;2009年

5 郭晶晶;图的无符号拉普拉斯特征值[D];浙江师范大学;2013年

6 刘婷;块五对角线性方程求解[D];华东师范大学;2009年

7 沈诺;关于某些三对角矩阵的研究[D];山东师范大学;2014年

8 焦江磊;基于异构系统的多对角矩阵并行计算研究[D];哈尔滨工程大学;2016年

9 白翠霞;线性脉冲微分系统的渐近解[D];天津大学;2009年

10 刁新军;五对角矩阵和广义等对角优势矩阵的数值分析[D];电子科技大学;2004年

本文编号：2746746