【摘要】：可重構(gòu)計算是一種基于定制硬件實現(xiàn)的計算形式,現(xiàn)場可編程門陣列(FPGA)便是典型的可重構(gòu)計算平臺。近年來,FPGA芯片集成了越來越多的硬件資源,提供了強大的計算能力,可重構(gòu)計算領(lǐng)域已漸漸步入可重構(gòu)超級計算的時代。矩陣計算是科學(xué)和工程應(yīng)用的核心問題,FPGA可重構(gòu)計算系統(tǒng)在加速矩陣計算方面具有巨大的潛力。然而,FPGA實現(xiàn)矩陣計算還面臨著硬件編程、并行算法設(shè)計、硬件結(jié)構(gòu)優(yōu)化等挑戰(zhàn),已有的矩陣計算硬件結(jié)構(gòu)占用了大量FPGA資源、存儲需求太高、帶寬需求過大,可擴展性也很差。 為應(yīng)對這些問題和挑戰(zhàn),本文對矩陣計算的FPGA實現(xiàn)技術(shù)進(jìn)行了深入的研究。本文的主要工作和創(chuàng)新點如下: (1)提出了面向基本矩陣運算的FPGA設(shè)計方法和高性能、高存儲效率分塊矩陣乘并行結(jié)構(gòu)。以矩陣向量乘和矩陣乘為例,研究了矩陣計算FPGA實現(xiàn)技術(shù)中的時空映射和模型構(gòu)建方法,實驗評測驗證了這兩種基本矩陣運算并行結(jié)構(gòu)的自動生成框架。利用包括循環(huán)分塊在內(nèi)的一系列變換和優(yōu)化,推導(dǎo)出數(shù)據(jù)傳輸優(yōu)化、存儲優(yōu)化的分塊矩陣乘并行算法,得到了一種能夠處理任意數(shù)據(jù)規(guī)模矩陣的高性能、高存儲效率的矩陣乘并行結(jié)構(gòu)。實驗結(jié)果表明該并行結(jié)構(gòu)優(yōu)于相關(guān)工作,且存儲需求從O(b2)降到了O(b),b為數(shù)據(jù)塊大小。 (2)提出了FPGA列選主元LU分解細(xì)粒度流水線并行算法和實現(xiàn)該算法的線性陣列。提出的并行算法能夠充分開發(fā)LU分解中的流水線并行和數(shù)據(jù)重用,可以擴展到下三角方程組求解和多右端項的線性方程組求解問題。本文提出了FPGA全硬件實現(xiàn)稠密線性方程組求解的并行結(jié)構(gòu),結(jié)構(gòu)的核心是實現(xiàn)該并行算法的線性陣列,線性陣列可以同時實現(xiàn)列選主元LU分解和下三角方程組求解。本文還給出了該并行結(jié)構(gòu)的性能模型,從而可以更好地分析和預(yù)測其性能。實驗結(jié)果表明該并行結(jié)構(gòu)優(yōu)于相關(guān)工作和通用處理器的軟件實現(xiàn)。 (3)提出了FPGA分塊稠密矩陣分解的并行算法和并行結(jié)構(gòu)。以不選主元LU分解為例,提出了一種分而治之的稠密矩陣分解分塊策略和FPGA實現(xiàn)方法。該策略對串行LU分解應(yīng)用包括循環(huán)分塊、時空映射在內(nèi)的一系列變換,推導(dǎo)出能夠處理任意規(guī)模矩陣的分塊LU分解并行算法。主要思想是把LU分解算法分解成細(xì)粒度計算任務(wù),細(xì)粒度任務(wù)能夠直接映射到FPGA實現(xiàn)的線性陣列,這些任務(wù)按照正確的順序在線性陣列上執(zhí)行。提出了實現(xiàn)該算法的高性能、高存儲效率分塊LU分解并行結(jié)構(gòu)。與需要兩組線性陣列的結(jié)構(gòu)相比,該結(jié)構(gòu)僅需要一組線性陣列,且存儲需求從O(b2)降到了O(b),b為數(shù)據(jù)塊大小。本文還把該分塊策略和實現(xiàn)方法擴展到了多FPGA系統(tǒng),并應(yīng)用到Cholesky分解。實驗結(jié)果表明,提出的并行結(jié)構(gòu)計算效率高于通用處理器。 (4)提出了兩種稀疏矩陣LU分解并行算法和實現(xiàn)這些算法的并行結(jié)構(gòu)。稀疏矩陣LU分解的數(shù)值計算是直接法求解稀疏線性方程組過程中最耗時的一部分,本文提出了兩種稀疏矩陣LU分解并行算法:Right-Looking (RL) LU分解并行算法和Left-Looking (LL) LU分解并行算法。前者能夠通過開發(fā)分解因子的數(shù)據(jù)重用來減少數(shù)據(jù)傳輸,后者能夠通過動態(tài)相關(guān)性檢測來開發(fā)更多的并行性;兩種算法對應(yīng)的并行結(jié)構(gòu)都能夠動態(tài)生成分解因子的數(shù)據(jù)結(jié)構(gòu)。實驗結(jié)果表明,LL LU分解的并行結(jié)構(gòu)的性能優(yōu)于RL LU分解的并行結(jié)構(gòu)和通用處理器的軟件實現(xiàn)。 (5)提出了新穎的稀疏矩陣向量乘(SpMV)并行結(jié)構(gòu)和共軛梯度法(CG)并行結(jié)構(gòu)。迭代法的計算量往往都集中在處理SpMV,本文對SpMV并行結(jié)構(gòu)進(jìn)行了深入的研究,并應(yīng)用到了CG的FPGA實現(xiàn)。提出了一種適合于FPGA設(shè)計的稀疏矩陣分塊方法和存儲格式,基于該存儲格式的SpMV并行結(jié)構(gòu)可以有效處理任意大型稀疏矩陣。與相關(guān)工作相比,本文提出的兩種高效的SpMV并行結(jié)構(gòu)無需改變?nèi)魏卧O(shè)計參數(shù)便可以處理任意矩陣,其中一種結(jié)構(gòu)可以有效減少零的填充。實驗結(jié)果表明,提出的SpMV并行結(jié)構(gòu)的性能優(yōu)于相關(guān)工作和通用處理器的軟件實現(xiàn);提出的CG并行結(jié)構(gòu)的性能也優(yōu)于通用處理器的軟件實現(xiàn)。
【圖文】：

值表的直接硬件實現(xiàn)，下面以一個 3 輸入的 LUT 為例來說其原入 LUT 實現(xiàn)了布爾函數(shù) f(a, b, c) = a AND (b OR c)，a、b 和 入的值，LUT 選擇圖中左邊一列數(shù)的值（這些值實際上存儲在基儲器中），如果輸入為 000、001、010、011 和 100，輸出均為101、110 和 111，則輸出均為 1，從而實現(xiàn)了布爾函數(shù) f(a, b, c)。

值表的直接硬件實現(xiàn)，，下面以一個 3 輸入的 LUT 為例來說其原入 LUT 實現(xiàn)了布爾函數(shù) f(a, b, c) = a AND (b OR c)，a、b 和 入的值，LUT 選擇圖中左邊一列數(shù)的值（這些值實際上存儲在基儲器中），如果輸入為 000、001、010、011 和 100，輸出均為101、110 和 111，則輸出均為 1，從而實現(xiàn)了布爾函數(shù) f(a, b, c)。
【學(xué)位授予單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2011
【分類號】：TP338.6;TN791

【相似文獻(xiàn)】

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

1 郭軍;{9尾勤;;入侵檢測中模式匹配算法的FPGA實現(xiàn)[J];系統(tǒng)仿真學(xué)報;2007年14期

2 鄔貴明;竇勇;王淼;;Cholesky分解細(xì)粒度并行算法[J];計算機工程與科學(xué);2010年09期

3 袁海洋;江先陽;劉鋒;王高峰;;應(yīng)用于ROHC的CRC算法硬件實現(xiàn)[J];微電子學(xué);2011年05期

4 陳玉泉;一種并行CRC算法的實現(xiàn)方法[J];現(xiàn)代電子技術(shù);2005年22期

5 張雪芹,林家駿,吳超;基于FPGA的遺傳算法的實現(xiàn)[J];計算機工程;1999年09期

6 徐琳;李曉民;譚光明;劉新春;卜東波;馮圣中;孫凝暉;;面向FPGA的RNA二級結(jié)構(gòu)預(yù)測并行算法研究[J];計算機學(xué)報;2006年02期

7 周杰;陳嘯洋;趙建勛;竇勇;;大矩陣QR分解的FPGA設(shè)計與實現(xiàn)[J];計算機工程與科學(xué);2010年10期

8 肖傳偉;周懷得;李志慧;郝志航;;多DSP智能相機的設(shè)計[J];微計算機信息;2006年17期

9 賀衛(wèi)東;段哲民;龔誠;;基于FPGA的大點數(shù)FFT算法研究[J];電子測量技術(shù);2007年11期

10 江潔;鄧玨瓊;張廣軍;周富強;;光條紋中心的實時快速提取[J];光學(xué)技術(shù);2008年02期

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

1 侯金華;;基于FPGA的SOC系統(tǒng)可靠性設(shè)計[A];2011中國電工技術(shù)學(xué)會學(xué)術(shù)年會論文集[C];2011年

2 張健;孫輝先;陳曉敏;安軍社;;反熔絲FPGA的可靠性設(shè)計措施[A];第二十三屆全國空間探測學(xué)術(shù)交流會論文摘要集[C];2010年

3 ;Design and Research of Video Fire Detection System Based on FPGA[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

4 董雪;費建軍;白嬌楊;;基于FPGA的智能火災(zāi)報警系統(tǒng)的設(shè)計與研究[A];天津市電視技術(shù)研究會2012年年會論文集[C];2012年

5 肖松;李躍華;張金林;;基于FPGA局部動態(tài)可重構(gòu)的抗SEU容錯系統(tǒng)研究[A];教育部中南地區(qū)高等學(xué)校電子電氣基礎(chǔ)課教學(xué)研究會第二十屆學(xué)術(shù)年會會議論文集（下冊）[C];2010年

6 王瑋;錢偉康;應(yīng)懷樵;;基于FPGA的PXI高速數(shù)據(jù)采集系統(tǒng)硬件設(shè)計[A];現(xiàn)代振動與噪聲技術(shù)（第九卷）[C];2011年

7 錢偉康;梁利娟;王麗麗;;一種基于FPGA的CAN總線船舶監(jiān)控系統(tǒng)[A];全國第三屆信號和智能信息處理與應(yīng)用學(xué)術(shù)交流會�？痆C];2009年

8 楊學(xué)友;葉振忠;劉常杰;李博文;;一種高速智能化視覺傳感器設(shè)計[A];第三次全國會員代表大會暨學(xué)術(shù)會議論文集[C];2002年

9 魯艷;雷維嘉;謝顯中;;基于Avalon接口的交織編碼技術(shù)的FPGA實現(xiàn)[A];2010年通信理論與信號處理學(xué)術(shù)年會論文集[C];2010年

10 許超;肖鐵;施柏鑫;;基于FPGA的電子內(nèi)窺鏡視頻處理系統(tǒng)[A];全國第二屆信號處理與應(yīng)用學(xué)術(shù)會議專刊[C];2008年

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

1 海英;賽靈思發(fā)布新型FPGA芯片方案[N];人民郵電;2009年

2 ;實現(xiàn)FPGA產(chǎn)品差異化[N];中國電子報;2011年

3 ;FPGA為消費電子提供安全保證[N];中國電子報;2011年

4 本報記者 趙艷秋　馮曉偉 馮健;FPGA：市場應(yīng)用廣 門檻需降低[N];中國電子報;2009年

5 本報記者 馮曉偉;FPGA格局難改 新興企業(yè)勝算幾何？[N];中國電子報;2009年

6 ;異步架構(gòu)FPGA實現(xiàn)業(yè)界最高速度[N];中國電子報;2009年

7 ;突破功耗和成本限制設(shè)計中國需要的FPGA[N];中國電子報;2009年

8 ;通信仍是FPGA最大市場[N];中國電子報;2009年

9 本報記者 梁紅兵;賽靈思：降低FPGA應(yīng)用門檻[N];中國電子報;2010年

10 華北光電技術(shù)研究所 劉剛;FPGA+DSP升級熱像設(shè)計[N];中國電子報;2010年

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

1 鄔貴明;FPGA矩陣計算并行算法與結(jié)構(gòu)[D];國防科學(xué)技術(shù)大學(xué);2011年

2 周杰;合成孔徑雷達(dá)數(shù)據(jù)處理應(yīng)用的細(xì)粒度并行算法與結(jié)構(gòu)[D];國防科學(xué)技術(shù)大學(xué);2010年

3 張承暢;多FPGA系統(tǒng)的關(guān)鍵問題及應(yīng)用研究[D];重慶大學(xué);2011年

4 李鵬;基于元構(gòu)件的FPGA硬件構(gòu)件設(shè)計技術(shù)研究[D];解放軍信息工程大學(xué);2011年

5 余慧;時分交換的新型FPGA互連結(jié)構(gòu)研究[D];復(fù)旦大學(xué);2011年

6 謝丁;FPGA互連結(jié)構(gòu)評估系統(tǒng)研究與實現(xiàn)[D];復(fù)旦大學(xué);2011年

7 王忠明;SRAM型FPGA的單粒子效應(yīng)評估技術(shù)研究[D];清華大學(xué);2011年

8 廖永波;SOC軟硬件協(xié)同方法及其在FPGA芯片測試中的應(yīng)用研究[D];電子科技大學(xué);2010年

9 唐玉蘭;偽布爾可滿足性算法及其在FPGA布線中的研究應(yīng)用[D];江南大學(xué);2010年

10 王建莊;基于FPGA的高速圖像處理算法研究及系統(tǒng)實現(xiàn)[D];華中科技大學(xué);2011年

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

1 鄧文壇;基于FPGA實現(xiàn)的粒子濾波算法研究[D];北京交通大學(xué);2008年

2 周志娟;相移波束形成的FPGA實現(xiàn)[D];哈爾濱工程大學(xué);2011年

3 許沖;激光脈沖定距算法研究與FPGA實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2011年

4 葉忠彬;基于FPGA的數(shù)字頻率合成系統(tǒng)的設(shè)計與實現(xiàn)[D];電子科技大學(xué);2011年

5 彭涵陽;無串?dāng)_超聲測距系統(tǒng)的激勵方法及基于FPGA的設(shè)計與實現(xiàn)[D];天津大學(xué);2010年

6 杜國女;基于FPGA的音樂景觀燈的設(shè)計與實現(xiàn)[D];蘭州交通大學(xué);2011年

7 隆志遠(yuǎn);基于FPGA和光電耦合的旋轉(zhuǎn)機械非接觸雙向信號傳輸系統(tǒng)[D];南京航空航天大學(xué);2010年

8 袁臻;電動多葉光柵通訊部分的FPGA實現(xiàn)[D];上海交通大學(xué);2009年

9 劉開健;基于FPGA的實時圖像處理系統(tǒng)的設(shè)計與實現(xiàn)[D];昆明理工大學(xué);2008年

10 劉鈺力;基于FPGA的SHA256高效數(shù)字加密系統(tǒng)[D];蘭州大學(xué);2011年

本文編號：2626442