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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前10條

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

2 張健;孫輝先;陳曉敏;安軍社;;反熔絲FPGA的可靠性設計措施[A];第二十三屆全國空間探測學術交流會論文摘要集[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的智能火災報警系統(tǒng)的設計與研究[A];天津市電視技術研究會2012年年會論文集[C];2012年

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

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

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

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

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

10 許超;肖鐵;施柏鑫;;基于FPGA的電子內窺鏡視頻處理系統(tǒng)[A];全國第二屆信號處理與應用學術會議�？痆C];2008年

相關重要報紙文章 前10條

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

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

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

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

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

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

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

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

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

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

相關博士學位論文 前10條

1 鄔貴明;FPGA矩陣計算并行算法與結構[D];國防科學技術大學;2011年

2 周杰;合成孔徑雷達數(shù)據(jù)處理應用的細粒度并行算法與結構[D];國防科學技術大學;2010年

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

4 李鵬;基于元構件的FPGA硬件構件設計技術研究[D];解放軍信息工程大學;2011年

5 余慧;時分交換的新型FPGA互連結構研究[D];復旦大學;2011年

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

7 王忠明;SRAM型FPGA的單粒子效應評估技術研究[D];清華大學;2011年

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

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

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

相關碩士學位論文 前10條

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

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

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

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

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

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

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

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

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

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

本文編號：2626442