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

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：2746746