本文關(guān)鍵詞：基于GPU平臺(tái)的SVD并行計(jì)算研究與實(shí)現(xiàn)，由筆耕文化傳播整理發(fā)布。

【摘要】：矩陣的奇異值分解作為一種重要的矩陣分解,在數(shù)學(xué)、物理學(xué)、醫(yī)學(xué)、工學(xué)等學(xué)科和領(lǐng)域具有廣泛的應(yīng)用背景。矩陣奇異值分解數(shù)值計(jì)算的研究由來已久,其中,計(jì)算速度和精度是該項(xiàng)研究的基本內(nèi)容,近幾十年來,由于并行計(jì)算系統(tǒng)的出現(xiàn),奇異值分解的并行算法研究逐漸成為熱點(diǎn),但是,以往的研究主要針對任務(wù)級并行,這種并行算法對矩陣的劃分粒度較粗,適用于多處理器計(jì)算系統(tǒng)。近年來以GPU為代表的眾核處理器采用SIMD或SIMT體系結(jié)構(gòu),傳統(tǒng)的并行SVD算法在這些平臺(tái)上計(jì)算并不能發(fā)揮出較高的效率。因此,本文將基于GPU平臺(tái)的SVD并行計(jì)算作為本文的主要研究方向。本文首先研究了基于QR方法的SVD算法。作為應(yīng)用最為廣泛的算法,針對該算法的研究較為廣泛,但由于該算法串行度較高,數(shù)據(jù)依賴性較強(qiáng),其并行算法的效率通常不高。本文從運(yùn)算速度和精度兩方面分析了帶Wilkinson位移的QR迭代算法、零位移QR迭代算法以及它們的混合選擇算法的性能特點(diǎn)和差異,針對這些算法在上對角元素歸零過程中的“向下越界”問題,在混合選擇算法的基礎(chǔ)上進(jìn)行改進(jìn),設(shè)計(jì)了動(dòng)態(tài)位移算法,對該算法進(jìn)行的數(shù)值實(shí)驗(yàn)結(jié)果表明,該算法對矩陣收斂速度起到積極作用,相對傳統(tǒng)算法的最高加速比在1.1以上;此外,本文設(shè)計(jì)了基于GPU平臺(tái)的細(xì)粒度并行動(dòng)態(tài)位移算法,并對其中的矩陣對角化更新提出了一種新的細(xì)粒度并行劃分方法,該方法將算法中串行度較高的二對角矩陣更新部分在GPU高效并行執(zhí)行,優(yōu)化后的算法運(yùn)行時(shí)間能減少10%左右�；贘acobi方法的SVD算法是另外一種重要的算法,它具有相對精度高等特點(diǎn),該方法分為雙邊Jacobi算法和單邊Jacobi算法,其中,單邊Jacobi算法運(yùn)算量小,且其結(jié)構(gòu)易于并行計(jì)算,本文對并行單邊Jacobi算法進(jìn)行了深入研究。數(shù)據(jù)調(diào)度序列用來生成每次并行迭代參與運(yùn)算的列對組合,對算法性能起到關(guān)鍵作用,本文通過數(shù)值實(shí)驗(yàn)分析了列范數(shù)波動(dòng)對算法收斂速度的影響,并基于此結(jié)果,研究了并行單邊Jacobi算法的各類靜態(tài)序列和動(dòng)態(tài)序列的性能特點(diǎn),針對單獨(dú)使用靜態(tài)序列無用計(jì)算過多、動(dòng)態(tài)序列附加運(yùn)算量大等問題,本文結(jié)合二者優(yōu)勢,給出了二者的混合序列算法,并結(jié)合列范數(shù)波動(dòng)率給出了序列選擇依據(jù),數(shù)值實(shí)驗(yàn)結(jié)果表明,混合算法能夠改善算法的收斂速度,運(yùn)算速度相比傳統(tǒng)算法能夠提高10%以上。另外,本文設(shè)計(jì)了改進(jìn)算法在GPU平臺(tái)的細(xì)粒度并行算法,提出了靜態(tài)序列更新在GPU實(shí)現(xiàn)的優(yōu)化方法,避免了列交換帶來的額外計(jì)算開銷。最后,本文對提出的多種改進(jìn)算法在NVIDIA Tesla C2050平臺(tái)進(jìn)行了實(shí)現(xiàn),并對改進(jìn)的算法實(shí)現(xiàn)進(jìn)行了性能測試。本文的測試包含了算法執(zhí)行的總時(shí)間以及其中的主要部分分步驟執(zhí)行的時(shí)間,同時(shí),對改進(jìn)的算法和傳統(tǒng)算法實(shí)現(xiàn)進(jìn)行了性能比較,并對測試結(jié)果進(jìn)行了分析和總結(jié)。測試結(jié)果表明:在精度一致的情況下,本文改進(jìn)的動(dòng)態(tài)位移QR迭代SVD算法相比混合選擇算法的加速比最高能達(dá)到1.1,本文改進(jìn)的混合序列并行單邊Jacobi算法相比單純使用靜態(tài)序列和動(dòng)態(tài)序列的算法加速比分別能達(dá)到1.15和1.05。另外,測試數(shù)據(jù)反映的部分信息能夠?yàn)檫M(jìn)一步優(yōu)化提供方向。
【關(guān)鍵詞】：奇異值分解 GPU QR Jacobi 并行計(jì)算
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：O241.6;TP338.6
【目錄】：

• 摘要5-7
• ABSTRACT7-16
• 第一章 緒論16-24
• 1.1 背景與意義16
• 1.2 研究現(xiàn)狀16-22
• 1.2.1 基于QR方法的SVD算法16-17
• 1.2.2 基于Jacobi方法的SVD算法17-20
• 1.2.3 基于GPU平臺(tái)的并行實(shí)現(xiàn)20-22
• 1.3 本文研究內(nèi)容22-23
• 1.4 本文組織結(jié)構(gòu)23-24
• 第二章 并行計(jì)算技術(shù)與開發(fā)環(huán)境24-38
• 2.1 并行執(zhí)行環(huán)境24-26
• 2.1.1 傳統(tǒng)并行計(jì)算系統(tǒng)24-25
• 2.1.2 GPU通用計(jì)算平臺(tái)25-26
• 2.2 并行算法設(shè)計(jì)方法26-30
• 2.2.1 傳統(tǒng)并行算法設(shè)計(jì)方法27-28
• 2.2.2 細(xì)粒度并行算法設(shè)計(jì)方法28-29
• 2.2.3 并行算法性能評估29-30
• 2.3 CUDA平臺(tái)及GPU通用計(jì)算模型30-37
• 2.3.1 CUDA平臺(tái)概述30-31
• 2.3.2 GPU通用計(jì)算模型31-37
• 2.4 小結(jié)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方法的局限及改進(jìn)算法42-48
• 3.2.1 兩種主要QR算法性能分析42-45
• 3.2.2 改進(jìn)的動(dòng)態(tài)位移QR算法45-46
• 3.2.3 動(dòng)態(tài)位移QR算法性能分析46-48
• 3.3 改進(jìn)算法在GPU平臺(tái)的并行算法設(shè)計(jì)48-52
• 3.3.1 二對角化并行算法設(shè)計(jì)48-49
• 3.3.2 對角化并行算法設(shè)計(jì)49-52
• 3.4 小結(jié)52-53
• 第四章 基于JACOBI方法的SVD并行算法研究53-72
• 4.1 傳統(tǒng)Jacobi算法53-57
• 4.1.1 雙邊Jacobi算法53-55
• 4.1.2 單邊Jacobi算法55-57
• 4.2 混合序列單邊Jacobi算法設(shè)計(jì)57-67
• 4.2.1 靜態(tài)數(shù)據(jù)調(diào)度序列57-62
• 4.2.2 動(dòng)態(tài)序列Jacobi算法分析62-64
• 4.2.3 改進(jìn)的混合序列單邊Jacobi算法64-65
• 4.2.4 混合序列算法精度控制65-67
• 4.3 混合序列算法性能分析67-68
• 4.4 混合序列算法在GPU平臺(tái)的并行算法設(shè)計(jì)68-71
• 4.4.1 靜態(tài)序列更新的實(shí)現(xiàn)優(yōu)化68-69
• 4.4.2 并行單邊Jacobi旋轉(zhuǎn)69-71
• 4.5 小結(jié)71-72
• 第五章 基于GPU平臺(tái)的算法實(shí)現(xiàn)與性能測試72-96
• 5.1 算法實(shí)現(xiàn)與測試平臺(tái)72-75
• 5.1.1 軟硬件平臺(tái)72-74
• 5.1.2 測試方法74
• 5.1.3 測試技術(shù)74-75
• 5.2 動(dòng)態(tài)位移QR迭代算法的GPU實(shí)現(xiàn)與性能測試75-88
• 5.2.1 總體實(shí)現(xiàn)方案75-76
• 5.2.2 原矩陣的二對角化76-80
• 5.2.3 二對角矩陣的對角化80-84
• 5.2.4 性能測試84-88
• 5.3 混合序列并行單邊Jacobi算法的GPU實(shí)現(xiàn)與性能測試88-95
• 5.3.1 總體實(shí)現(xiàn)方案88-89
• 5.3.2 調(diào)度序列更新89-90
• 5.3.3 Jacobi旋轉(zhuǎn)90-91
• 5.3.4 性能測試91-95
• 5.4 小結(jié)95-96
• 第六章 總結(jié)與展望96-99
• 6.1 本文工作總結(jié)96-97
• 6.2 展望97-99
• 致謝99-100
• 參考文獻(xiàn)100-104
• 個(gè)人簡歷及攻讀碩士學(xué)位期間的研究成果104-105

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 鄭敏娟;賀炎;;未來的并行計(jì)算[J];中國科技信息;2007年12期

2 王宏琳;;數(shù)字濾波的并行計(jì)算[J];石油地球物理勘探;1984年02期

3 ;光計(jì)算[J];中國光學(xué)與應(yīng)用光學(xué)文摘;2001年04期

4 孫安香,宋君強(qiáng),李曉梅;數(shù)值氣象預(yù)報(bào)中的并行計(jì)算研究[J];高技術(shù)通訊;2001年12期

5 賴國明,楊圣云;一種利用工作站群集的并行計(jì)算研究方案[J];河南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期

6 莫?jiǎng)t堯;張愛清;曹小林;左風(fēng)麗;;多介質(zhì)輻射流體力學(xué)數(shù)值模擬中的并行計(jì)算研究[J];自然科學(xué)進(jìn)展;2006年03期

7 張繁;王松;;并行計(jì)算在生物信息學(xué)中的應(yīng)用[J];科技信息(科學(xué)教研);2007年36期

8 李曉梅,張寶琳,康立山;全國并行計(jì)算學(xué)術(shù)交流會(huì)的回顧——紀(jì)念全國并行計(jì)算專業(yè)委員會(huì)成立十周年[J];科學(xué)中國人;2000年12期

9 陳波,韓永國,劉志勤;高性能并行計(jì)算的研究與分析[J];四川師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2003年02期

10 伍湘君,黃麗萍;超級計(jì)算機(jī)上矩陣乘的并行計(jì)算與實(shí)現(xiàn)[J];應(yīng)用氣象學(xué)報(bào);2005年01期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 黃宇光;;整體同步并行計(jì)算方法的現(xiàn)狀與發(fā)展[A];信息科學(xué)與微電子技術(shù):中國科協(xié)第三屆青年學(xué)術(shù)年會(huì)論文集[C];1998年

2 羅文彩;陳小前;;并行計(jì)算的多方法優(yōu)化協(xié)作[A];第二十四屆中國控制會(huì)議論文集（上冊）[C];2005年

3 左風(fēng)麗;莫?jiǎng)t堯;葉文華;;計(jì)算流體三維分裂格式的高效并行計(jì)算[A];中國工程物理研究院科技年報(bào)（2003）[C];2003年

4 王欣;李志山;張志遠(yuǎn);;并行計(jì)算在彈塑性時(shí)程分析中的應(yīng)用[A];信息化推動(dòng)工程建設(shè)工業(yè)化——第四屆工程建設(shè)計(jì)算機(jī)應(yīng)用創(chuàng)新論壇論文集[C];2013年

5 張理濤;黃廷祝;谷同祥;左憲禹;;一種適合于分布式并行計(jì)算改進(jìn)的平方共軛殘差法[A];2008年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊)[C];2008年

6 胡金初;;并行計(jì)算中的任務(wù)分配算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

7 宋庭新;李慧;;面向服務(wù)的有限元并行計(jì)算網(wǎng)格系統(tǒng)設(shè)計(jì)[A];湖北省機(jī)械工程學(xué)會(huì)設(shè)計(jì)與傳動(dòng)學(xué)會(huì)、武漢機(jī)械設(shè)計(jì)與傳動(dòng)學(xué)會(huì)2008年學(xué)術(shù)年會(huì)論文集（2）[C];2008年

8 裘懿勇;徐斌;劉曉明;;并行計(jì)算作業(yè)調(diào)度系統(tǒng)的架構(gòu)及應(yīng)用[A];第十四屆中國科協(xié)年會(huì)第5分會(huì)場：綠色船舶與海洋裝備創(chuàng)新發(fā)展及產(chǎn)業(yè)化論壇論文集[C];2012年

9 裘懿勇;徐斌;劉曉明;;并行計(jì)算作業(yè)調(diào)度系統(tǒng)的架構(gòu)及應(yīng)用[A];2012年MIS/S&A學(xué)術(shù)交流會(huì)議論文集[C];2012年

10 肖保國;楊順華;邢建文;趙慧勇;;當(dāng)?shù)刈赃m應(yīng)建表方法在煤油超燃發(fā)動(dòng)機(jī)并行計(jì)算中的應(yīng)用[A];第十四屆全國激波與激波管學(xué)術(shù)會(huì)議論文集（下冊）[C];2010年

中國重要報(bào)紙全文數(shù)據(jù)庫 前10條

1 軼嘉;英特爾全球首個(gè)并行計(jì)算中心落戶無錫[N];人民郵電;2009年

2 曙光信息產(chǎn)業(yè)有限公司研發(fā)中心 溫鑫;并行計(jì)算任重道遠(yuǎn)[N];中國計(jì)算機(jī)報(bào);2007年

3 英特爾并行計(jì)算實(shí)驗(yàn)室研究員 TimothyMattson;并行計(jì)算:減少串行軟件[N];中國計(jì)算機(jī)報(bào);2007年

4 曙光信息產(chǎn)業(yè)有限公司研發(fā)中心 溫鑫;并行計(jì)算軟件開發(fā)概述[N];中國計(jì)算機(jī)報(bào);2007年

5 劉霞;計(jì)算能力的提升需要一場革命[N];科技日報(bào);2010年

6 安世亞太 雷先華;ANSYS高性能并行計(jì)算[N];中國航空報(bào);2005年

7 張?jiān)迫?并行計(jì)算：迎接多核時(shí)代的挑戰(zhàn)[N];計(jì)算機(jī)世界;2006年

8 本報(bào)記者 馬文方;英特爾為何要牽頭并行計(jì)算[N];中國計(jì)算機(jī)報(bào);2009年

9 英特爾 趙軍(Jun Zhao);PC機(jī)并行計(jì)算革命尚未成功[N];中國計(jì)算機(jī)報(bào);2009年

10 ;Linux下的網(wǎng)絡(luò)并行計(jì)算[N];計(jì)算機(jī)世界;2000年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 顧慧;基于異構(gòu)平臺(tái)的并行計(jì)算性能可視化研究[D];遼寧師范大學(xué);2010年

2 徐曉華;光并行計(jì)算及其在圖像處理和計(jì)算分子生物學(xué)中的應(yīng)用[D];揚(yáng)州大學(xué);2005年

3 田甜;異構(gòu)環(huán)境中并行計(jì)算模型與任務(wù)調(diào)度的研究[D];曲阜師范大學(xué);2010年

4 劉杰;可擴(kuò)展并行計(jì)算及其應(yīng)用研究[D];湖南大學(xué);2009年

5 孔令梅;三維變分同化并行計(jì)算研究及實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2005年

6 劉桂海;網(wǎng)格并行計(jì)算系統(tǒng)研究開發(fā)[D];西安理工大學(xué);2008年

7 蔡佳佳;圖像代數(shù)多核并行計(jì)算類庫的構(gòu)建與優(yōu)化[D];廈門大學(xué);2008年

8 陳維;有限單元并行計(jì)算方法在地震波動(dòng)模擬中的應(yīng)用[D];中國地震局工程力學(xué)研究所;2011年

9 陸良剛;土木工程有限元并行計(jì)算應(yīng)用及其軟件架構(gòu)[D];中國地震局工程力學(xué)研究所;2011年

10 張立霞;電磁場有限元分析中并行計(jì)算的研究[D];河北工業(yè)大學(xué);2006年

  本文關(guān)鍵詞：基于GPU平臺(tái)的SVD并行計(jì)算研究與實(shí)現(xiàn)，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：358697