基于可重構(gòu)計算的矩陣分解并行結(jié)構(gòu)研究.pdf

1、隨著半導體制造工藝的進步,可編程門陣列(Field-Programmable Gate Array,FPGA)迅速發(fā)展,單芯片上可供快速實現(xiàn)的邏輯功能越來越多,基于FPGA的可重構(gòu)計算在高性能計算甚至是超級計算領(lǐng)域中的巨大潛力逐漸被挖掘出來。當前主流的FPGA芯片上往往具有高密度的可編程邏輯、大量存儲資源與計算資源,并通過集成DSP硬核以支持高性能浮點運算部件的實現(xiàn)。這些特點使得可重構(gòu)計算系統(tǒng)成為加速計算密集型應(yīng)用的一種非常重要的選擇。

2、在眾多受到關(guān)注的計算密集型問題中,矩陣分解尤其是矩陣三角化分解作為典型的基礎(chǔ)類應(yīng)用始終處于研究的核心地位,在求解線性方程組、求矩陣特征值等科學與工程問題中有重要的研究價值。
　　縱觀國內(nèi)外研究現(xiàn)狀,在矩陣三角化分解及應(yīng)用領(lǐng)域已經(jīng)取得了很多研究成果,但仍存在許多亟待解決的問題。根據(jù)可重構(gòu)計算并行結(jié)構(gòu)的特征構(gòu)建矩陣三角化分解并行計算模型,進一步改善三角化分解硬件結(jié)構(gòu)計算性能及關(guān)鍵技術(shù)成為當前該領(lǐng)域關(guān)注的課題。針對該課題,本文面向矩陣三

3、角化分解中共有的三角化計算過程,提出具有一般性的矩陣三角化計算FPGA并行結(jié)構(gòu)時空模型以及一種計算復雜度較低的矩陣三角化計算并行結(jié)構(gòu)模板。并圍繞三種具體的矩陣三角化分解:Cholesky分解、LU分解和QR分解在并行結(jié)構(gòu)模板上的高性能實現(xiàn)及優(yōu)化方法開展研究,取得的研究成果包括:
　　1、提出具有一般性的三角化計算FPGA并行結(jié)構(gòu)時空模型構(gòu)建方法和一種計算復雜度較低的矩陣三角化計算并行結(jié)構(gòu)模板。(1)對三角化計算線性變換的一般過程進

4、行分析,以子矩陣更新過程為粗粒度計算任務(wù)來開發(fā)任務(wù)間的流水并行;(2)在任務(wù)中以列計算為細粒度單位開發(fā)數(shù)據(jù)并行;(3)以求解有限域GF(p)上線性方程組的三角化計算問題為示例,面向三角化計算中子矩陣更新過程中提出適合硬件實現(xiàn)的子矩陣更新同一化算法并向FPGA上映射實現(xiàn)。
　　2、在三角化計算并行結(jié)構(gòu)模板上實現(xiàn)實數(shù)矩陣Cholesky分解,由此提出該算法的高性能FPGA并行結(jié)構(gòu)。分析Cholesky分解的求解特征,引入求解矩陣L的轉(zhuǎn)

5、置LT的LT-SC(LT-Submatrix-Cholesky),從而簡化問題的求解。從對比驗證的角度,給出兩種LT-SC的并行結(jié)構(gòu)實現(xiàn)方案。其中,方案二針對Cholesky分解特有的三角子矩陣更新過程對子矩陣更新同一化算法進行了改進,并在實現(xiàn)時通過增加PE陣列的使能信號向量以支持改進后的算法。提出的Cholesky分解FPGA并行結(jié)構(gòu)采用方案二的實現(xiàn),實驗結(jié)果表明該結(jié)構(gòu)與對比方案(方案一)相比具有更高的單位面積性能,且優(yōu)于相關(guān)工作和通

6、用處理器的軟件實現(xiàn)。
　　3、在三角化計算并行結(jié)構(gòu)模板上實現(xiàn)列選主元的實數(shù)矩陣LU分解,由此提出該算法的高性能FPGA并行結(jié)構(gòu)。分析LU分解的求解特征,對子矩陣更新同一化算法進行了擴展與改進以支持LU分解的列選主元,并在實現(xiàn)的并行結(jié)構(gòu)中增加與之匹配的硬件通路。提出的并行結(jié)構(gòu)在求解線性方程組完成同時支持前向三角回代及后向回代過程的LU分解,相當于實現(xiàn)了求解實系數(shù)增廣矩陣的高斯-約當消元算法。同時,針對大矩陣問題提出基于非遞歸和遞歸方