【摘要】：稀疏矩陣結(jié)構(gòu)存在于眾多科學(xué)學(xué)科中,且在線性代數(shù)、數(shù)據(jù)挖掘和圖形分析等領(lǐng)域具有廣泛應(yīng)用。稀疏矩陣矢量乘在計(jì)算科學(xué)領(lǐng)域中具有重要意義。隨著通用圖形處理單元GPU編程模型和開發(fā)工具鏈的成熟,面向GPU加速稀疏矩陣矢量乘已得到研究者們的廣泛關(guān)注。稀疏對(duì)角矩陣是一類特殊的稀疏矩陣,其非零元素大多都集中在少量對(duì)角線上。DIA格式是最適合用來存儲(chǔ)稀疏對(duì)角矩陣的存儲(chǔ)格式,然而,當(dāng)稀疏對(duì)角矩陣中的對(duì)角線存在長斷行、長偏移或者散點(diǎn)等情況時(shí),如果繼續(xù)采用DIA去存儲(chǔ),將引起大量零元素填充,導(dǎo)致DIA核的性能大大下降。稀疏塊對(duì)角矩陣也是一類特殊的稀疏矩陣,其非零元素結(jié)構(gòu)呈現(xiàn)塊對(duì)角形態(tài)。顯然,DIA格式不適用存儲(chǔ)此類矩陣,CSR和ELL格式雖然能有效存儲(chǔ),但由于沒有利用其對(duì)角結(jié)構(gòu),其核的性能并不好。為此,本文從兩類矩陣出發(fā),基于GPU編程模型CUDA,深入研究面向GPU的稀疏對(duì)角矩陣矢量乘算法。本文的主要工作和貢獻(xiàn)如下:1.提出了基于GPU的自適應(yīng)并行稀疏對(duì)角矩陣矢量乘算法DIA-Adaptive。針對(duì)稀疏對(duì)角矩陣的對(duì)角線存在長偏移、長斷行以及少量散點(diǎn)情況,首先,依據(jù)一定規(guī)則將矩陣分為三類;進(jìn)而基于這些分類,除第一類采用原有的DIA算法外,其余兩類,分別提出新穎的BRCSD-I算法和BRCSD-Ⅱ算法與之相對(duì)應(yīng);最后,還設(shè)計(jì)了一個(gè)搜索引擎和代碼自動(dòng)生成器,任一稀疏對(duì)角矩陣經(jīng)過搜索引擎可自動(dòng)識(shí)別類型,選擇合適的存儲(chǔ)格式,并自動(dòng)生成對(duì)應(yīng)內(nèi)核。實(shí)驗(yàn)證明,本論文提出的DIA-Adaptive算法是有效的,具有較高的性能和良好的并行性。2.提出基于GPU的并行稀疏塊對(duì)角矩陣矢量乘算法IndexBDIA。針對(duì)一類稀疏塊對(duì)角矩陣,利用其塊呈對(duì)角結(jié)構(gòu),先將稀疏塊對(duì)角矩陣劃分成許多個(gè)某一尺寸大小的小矩陣塊,并記錄每一小矩陣塊對(duì)應(yīng)的行列索引值;進(jìn)而通過行列索引值找出塊對(duì)角線,塊對(duì)角線的建立大大減少了行列索引值的存儲(chǔ);最后,根據(jù)塊對(duì)角線偏移值對(duì)矩陣進(jìn)行行斷劃分存儲(chǔ),有效減少了塊對(duì)角線存在大偏移時(shí)所需要的零元素填充。實(shí)驗(yàn)證明,提出的IndexBDIA算法性能較好。3.應(yīng)用求解Klein-Gordon-Schrodinger(KGS)方程,驗(yàn)證本文提出的算法的有效性。針對(duì)離散2D和3DKGS方程后得到的稀疏對(duì)角線性系統(tǒng),基于GMRES算法,將本文提出的自適應(yīng)稀疏對(duì)角矩陣矢量乘算法引入,設(shè)計(jì)了一種新穎的GPU加速的時(shí)間域GMRES算法T-GMRES。實(shí)驗(yàn)證明,本文提出的算法應(yīng)用于求解2D和3D KGS方程是有效的。
【學(xué)位授予單位】：南京師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP301.6;TP332
【圖文】：

隨著通用圖形處理單兀（Ｇｒａｐｈｉｃｓ邋Ｐｒｏｃｅｓｓｉｎｇ邋Ｕｎｉｔ，邋ＧＰＵ）編程模型和開逡逑發(fā)工具鏈的成熟，ＧＲＪ給通用計(jì)算，特別是高性能計(jì)算帶來了前所未有的機(jī)遇。ＧＰＵ逡逑的設(shè)計(jì)理念與ＣＰＵ有很大不同如圖１．１所示。在ＧＰＵ中，絕大部分資源用于計(jì)逡逑算，當(dāng)前，ＧＰＵ的計(jì)算能力和帶寬都比ＣＰＵ高出一個(gè)數(shù)量級(jí)，主流ＧＰＵ的計(jì)算能逡逑力已達(dá)到６Ｔ０ＰＳ，存儲(chǔ)帶寬達(dá)到５００ＧＢ／Ｓ。因此本論文的運(yùn)算都是面向ＧＰＵ架構(gòu)的。逡逑ＩＩ邋｜ｉ邐Ｕ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋Ｉ邋ｉ邋１邋Ｉ邋Ｉ邋ＩＴＴ１逡逑邐ｕ邐Ｉ邋Ｉ邐Ｍ邐Ｉ邐Ｉ邐Ｉ邋Ｉ邐Ｍ邐［邐ｉ邐ｒｍ逡逑ＩＩ邐Ｕ邐ＩＩ邐Ｉ邋Ｉ邐Ｉ邐Ｉ邐１１邐１邋Ｉ邐Ｉ邐Ｉ邐Ｉ邋ｉｌ邋ｉ逡逑邐ＩＬ邐邐邋ｕ邐ｉ邋ｉ邐ｉ邋Ｉ邐ｉ邐Ｉ邐ｍ邐ｉ邋ｉ邐ｉ邐ｉ邐ｉ￣ｍ逡逑邐邋Ｍ邋Ｉ邋ｌｉ邋ＩＩ邋Ｉ邋Ｉ邋ＩＩ邋ＩＩ邋Ｉ邋ＩＩ邋ＩＩ逡逑0控制調(diào)節(jié)器邐ｂｒｆ丨！丨！邋！邋！邋！丨」Ｉ邋ｉ丨丨．ｌｌｊ逡逑，＿＿邐ｂｉ邋ＩＩ邋１邋ｉ邋１邋ＩＩ邋１邋Ｉ邋Ｉ邋Ｉ邋１邋ＩＴＴ１逡逑＾邋木邏輯單兀邋邐－邐－邐Ｕ邋Ｍ邋Ｉ邋ｉｌ邋ＩＩ邋Ｉ邋１１邋Ｉ邋１１邋１１邋１逡逑緩存邐邐邐邐逡逑？邋ＤＲＡＭ逡逑ＣＰＵ邐ＧＰＵ逡逑圖１．１邋ＣＰＵ和ＧＰＵ的體系結(jié)構(gòu)逡逑稀疏對(duì)角矩陣是一種特殊的稀疏矩陣，它的非零元素集中在少量的對(duì)角線上。且逡逑在許多領(lǐng)域有著廣泛的應(yīng)用。例如，在計(jì)算流體力學(xué)和電磁學(xué)等領(lǐng)域中的許多問題，逡逑采用有限差分法（Ｆｉｎｉｔｅ邋Ｄｉｆｆｅｒｅｎｃｅ邋Ｍｅｔｈｏｄ

ＤＩＡ邋（ＨＤＩ）格式來減少零元素的填充。在ＨＤＩ格式中，原始矩陣被劃分成若干個(gè)具逡逑有相同行數(shù)量的矩陣塊，且每個(gè)獨(dú)立矩陣塊采用ＤＩＡ格式存儲(chǔ)。由于ＤＩＡ格式的使逡逑用，ＨＤＩ格式無法解決矩陣中對(duì)角線存在偏移的情況。綜合上述研宄來看，對(duì)于圖１．２逡逑的稀疏對(duì)角矩陣存在的情況，現(xiàn)有算法都存在著一定的不足。因此，本論文對(duì)稀疏對(duì)逡逑角矩陣進(jìn)一步進(jìn)行研宄，基于ＣＵＤＡ邋（ＣｏｍｐｕｔｅＵｎｉｆｉｅｄＤｅｖｉｃｅＡｒｃｈｉｔｅｃｔｕｒｅ），通過提逡逑出一種自適應(yīng)的并行稀疏對(duì)角矩陣矢量乘算法，完美解決了稀疏對(duì)角矩陣中存在散點(diǎn)、逡逑長斷行或者對(duì)角線偏離主對(duì)角線較遠(yuǎn)等情況問題。逡逑另外，在均勻網(wǎng)格上離散偏微分方程組時(shí)，對(duì)于每個(gè)網(wǎng)格節(jié)點(diǎn)上具有高自由度的逡逑結(jié)構(gòu)化網(wǎng)格問題產(chǎn)生的矩陣，其非零元素結(jié)構(gòu)往往具有一定規(guī)律，呈現(xiàn)如圖１．３的樣逡逑式。圖１．３中的稀疏矩陣被稱為稀疏塊對(duì)角矩陣。逡逑顯然，ＤＩＡ格式不適合這種稀疏塊對(duì)角矩陣的存儲(chǔ)。ＣＳＲ和ＥＬＬ雖然能有效存逡逑２逡逑

？？邐？？？？？？＇？邋■長斷行逡逑圖１．２稀疏對(duì)角矩陣實(shí)例逡逑為此，Ｙｕａｎ邋等［５］２０１０邋年提出了邋ＤＤＤ－ＮＡｌＶＥ邋和邋ＤＤＤ－ＳＰＬＩＴ邋算法。ＤＤＤ－ＮＡｉＶＥ逡逑算法依次存儲(chǔ)對(duì)角線上元素，對(duì)于含有稠密對(duì)角線矩陣具有較好的效率，但無法解決逡逑對(duì)角線存在長斷行情況。ＤＤＤ－ＳＰＬＩＴ算法利用對(duì)角線將稀疏矩陣分塊，通過壓縮相逡逑同元素節(jié)省存儲(chǔ)空間。然而，這兩種算法均未給出并行解決方案。Ｓｕｎ等Ｗ在２０１１年逡逑提出了邋ＣＲＳＤ邋（Ｃｏｍｐｒｅｓｓｅｄ邋Ｒｏｗ邋Ｓｅｇｍｅｎｔ邋ｗｉｔｈ邋Ｄｉａｇｏｎａｌ邋Ｐａｔｔｅｒｎ）格式，相比邋ＤＩＡ，含巨逡逑大大減少零元素的填充。在ＣＲＳＤ中，通過定義對(duì)角線模式表示對(duì)角線分布，將對(duì)角逡逑線分到不同組，進(jìn)而將矩陣分成若干行段；如果行段中對(duì)角線上元素具有相同模式，逡逑則將此類行段看成一個(gè)存儲(chǔ)和操作單元

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張友惠;;分塊次對(duì)角矩陣的定義及性質(zhì)[J];湖南科技學(xué)院學(xué)報(bào);2008年04期

2 錢愛林,吳又勝;對(duì)稱雙邊對(duì)角矩陣的特征值問題[J];河西學(xué)院學(xué)報(bào);2005年05期

3 刁新軍;黃廷祝;曾翎;冉瑞生;;五對(duì)角矩陣的分解及其逆元素的快速算法[J];電子科技大學(xué)學(xué)報(bào);2005年06期

4 吳燕翔,王良恩,邱挺;二對(duì)角矩陣法及其在催化精餾塔模擬計(jì)算中的應(yīng)用[J];福州大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年01期

5 黃鏡新;模糊錯(cuò)誤二類5對(duì)角矩陣方程求解[J];廣東工業(yè)大學(xué)學(xué)報(bào);1998年S1期

6 周小莊，胡錫炎;實(shí)對(duì)稱五對(duì)角矩陣及其特征反問題[J];湖南大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年01期

7 吳長勤,張銀云;灰對(duì)角矩陣的一些性質(zhì)[J];安徽農(nóng)業(yè)技術(shù)師范學(xué)院學(xué)報(bào);1997年04期

8 周志華;吳漢金;李永元;侯懷德;;上機(jī)圖及配色效應(yīng)圖內(nèi)部轉(zhuǎn)換的數(shù)學(xué)模型[J];中國紡織大學(xué)學(xué)報(bào);1988年03期

9 錢岷江;;基于雙線性變換從S域到Z域的對(duì)角矩陣算法[J];現(xiàn)代機(jī)械;1988年04期

10 王秀玉,姜興武,李慧玲;對(duì)稱雙邊對(duì)角矩陣的性質(zhì)及廣義逆[J];東北師大學(xué)報(bào)(自然科學(xué)版);2005年03期

相關(guān)會(huì)議論文 前4條

1 黃鏡新;;二類4模糊錯(cuò)誤對(duì)角矩陣方程求解[A];1998年中國智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];1998年

2 王健;陳丙珍;何小榮;;化工過程模擬與優(yōu)化的新進(jìn)展——并行計(jì)算方法[A];過程系統(tǒng)工程2001年會(huì)論文集[C];2001年

3 毛希安;;二維NOE譜幅度矩陣的數(shù)學(xué)特性[A];第七屆全國波譜學(xué)學(xué)術(shù)會(huì)議論文摘要集[C];1992年

4 梁冬梅;馬玉臣;;多體格林函數(shù)方法研究二元砷化物的光電特性[A];中國化學(xué)會(huì)第十二屆全國量子化學(xué)會(huì)議論文摘要集[C];2014年

相關(guān)重要報(bào)紙文章 前1條

1 教育部考試中心命題一部、社會(huì)考試處;考研細(xì)看命題變化[N];中國教育報(bào);2002年

相關(guān)博士學(xué)位論文 前1條

1 聶璽;陣列信號(hào)二維測(cè)向算法研究[D];電子科技大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 夏羿飛;面向GPU的并行稀疏對(duì)角矩陣矢量乘算法研究及應(yīng)用[D];南京師范大學(xué);2019年

2 李志勇;基于對(duì)角矩陣的溫濕度模糊解耦控制系統(tǒng)的研究[D];石家莊鐵道大學(xué);2018年

3 藺彥玲;幾類特殊矩陣求其逆的快速算法研究[D];陜西科技大學(xué);2017年

4 鄭永梅;實(shí)對(duì)稱五對(duì)角矩陣的逆特征值問題[D];南京航空航天大學(xué);2009年

5 郭晶晶;圖的無符號(hào)拉普拉斯特征值[D];浙江師范大學(xué);2013年

6 劉婷;塊五對(duì)角線性方程求解[D];華東師范大學(xué);2009年

7 沈諾;關(guān)于某些三對(duì)角矩陣的研究[D];山東師范大學(xué);2014年

8 焦江磊;基于異構(gòu)系統(tǒng)的多對(duì)角矩陣并行計(jì)算研究[D];哈爾濱工程大學(xué);2016年

9 白翠霞;線性脈沖微分系統(tǒng)的漸近解[D];天津大學(xué);2009年

10 刁新軍;五對(duì)角矩陣和廣義等對(duì)角優(yōu)勢(shì)矩陣的數(shù)值分析[D];電子科技大學(xué);2004年

本文編號(hào)：2746746