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

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

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

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

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

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

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