基于fpga的大規(guī)模矩陣q分解算法的研究與實(shí)現(xiàn)

基于fpga的大規(guī)模矩陣q分解算法的研究與實(shí)現(xiàn)

1面向中小型企業(yè)的熔噴算法設(shè)計(jì)與實(shí)現(xiàn)大規(guī)模區(qū)塊鏈分解廣泛應(yīng)用于數(shù)據(jù)處理、計(jì)算機(jī)科學(xué)、計(jì)算流量、結(jié)構(gòu)力學(xué)等領(lǐng)域。由于QR分解運(yùn)算量巨大,傳統(tǒng)方法是在大規(guī)模并行機(jī)上進(jìn)行加速。目前還沒有基于FPGA(FieldProgrammableGateArray,簡稱FPGA)平臺加速大規(guī)模矩陣QR方面的研究。隨著集成電路技術(shù)的發(fā)展,FPGA芯片的計(jì)算能力和片內(nèi)存儲資源迅速增長。同時(shí),FPGA器件以其可編程性、細(xì)粒度并行能力、豐富的硬件資源、靈活的算法適應(yīng)性和較低的功耗成為理想的可編程系統(tǒng)平臺。近年來,有很多面向中小規(guī)模QR分解的FPGA設(shè)計(jì)與實(shí)現(xiàn),如4*4、64*64等。小規(guī)模QR分解,如4*4,一般采用二維Systolic陣列來實(shí)現(xiàn)。雖然二維陣列結(jié)構(gòu)處理器可以提供很高的并行性,但其硬件代價(jià)很大,陣列中處理單元數(shù)量一般達(dá)到O(n2)。當(dāng)矩陣規(guī)模較大時(shí),由于芯片面積和功耗等因素的限制,很難實(shí)現(xiàn)二維結(jié)構(gòu)的處理陣列。為了實(shí)現(xiàn)規(guī)模較大的QR分解,人們提出了各種折疊和影射方法,將二維結(jié)構(gòu)陣列折疊成一維結(jié)構(gòu)。QR處理器陣列應(yīng)用折疊技術(shù)面臨兩個(gè)難題:三角陣列結(jié)構(gòu)的設(shè)計(jì)和處理單元的設(shè)計(jì)。文獻(xiàn)將邊界和內(nèi)部處理單元分別實(shí)現(xiàn),文獻(xiàn)將QR陣列中的邊界和內(nèi)部處理單元合并為一個(gè)處理單元。由折疊和映射方法得到線性陣列的處理單元數(shù)都為O(n),這對于中等規(guī)模系統(tǒng)的實(shí)現(xiàn)還是可以接受的。但是,當(dāng)規(guī)模為1K*1K、4K*4K甚至更大時(shí),要實(shí)現(xiàn)O(n)量級的處理單元數(shù)的線性陣列是很困難的。本文在分析了基于快速GivensRotation的QR(GR-QR)分解算法數(shù)據(jù)依賴關(guān)系,提出了操作級的細(xì)粒度QR分解并行算法,并在FPGA平臺上實(shí)現(xiàn)了一種可擴(kuò)展結(jié)構(gòu)的QR分解陣列處理器。綜合結(jié)果表明,StratixIIEP2S130F1020C5FPGA芯片最多可以集成15個(gè)GR-PE,并且頻率可達(dá)101MHz。相對于2.0GHzPentium雙核CPU,該陣列處理器可取得19倍的加速比。2快速gr-cr算法的數(shù)據(jù)依賴關(guān)系基于GivensRotation的QR分解(GR-QR)是數(shù)值穩(wěn)定性最好的算法之一。但是,對于規(guī)模為n*n的矩陣來說,GR-QR算法中乘加的運(yùn)算量為O(5n3)。為了減少GR-QR算法的計(jì)算量,人們提出許多快速Q(mào)R分解算法。例如,文獻(xiàn)提出GR-QR的一種快速算法,使乘法的運(yùn)算量減少了一半,該算法乘法和加法的運(yùn)算量總共為O(10n3/3)。經(jīng)過GivensRotation變換后,原始矩陣A變換為上三角矩陣R,單位矩陣I變換為正交矩陣Q。為了便于描述基于GR-QR算法,我們將原始矩陣A和單位矩陣I合并為矩陣B,如圖1所示。數(shù)據(jù)相關(guān)是并行程序和并行體系結(jié)構(gòu)設(shè)計(jì)的重要方面。本文主要關(guān)注GR-QR算法中外層循環(huán)片間的數(shù)據(jù)相關(guān)。這里,我們將更新因子計(jì)算稱為程序塊B1,而將更新操作稱為程序塊B2。圖2詳細(xì)描述了基于快速GR-QR算法數(shù)據(jù)依賴關(guān)系。其中,圖2a是GR-QR算法的總體框架;圖2b是第i層外層循環(huán)和第(i+1)層外層循環(huán)程序塊之間的數(shù)據(jù)依賴關(guān)系;圖2c以第i層循環(huán)中程序塊B2(i,i+3)和第(i+1)層循環(huán)中程序塊B1(i+1,i+3)為例進(jìn)一步細(xì)化了外層循環(huán)間的數(shù)據(jù)依賴關(guān)系。由圖2c可以看出,當(dāng)?shù)趇層循環(huán)更新出程序塊B1(i+1,i+3)所需的第一個(gè)數(shù)據(jù)就可以啟動(dòng)該程序塊的執(zhí)行。這也是細(xì)粒度并行程序設(shè)計(jì)的基礎(chǔ)。3高速gr-111粒度的計(jì)算方法及其可擴(kuò)展性分析3.1計(jì)算處理單元b根據(jù)上一節(jié)中的數(shù)據(jù)依賴關(guān)系,本節(jié)采用并行化外層循環(huán)片策略對快速GR-QR算法進(jìn)行并行實(shí)現(xiàn)。算法1采用單程序多數(shù)據(jù)流模型(SingleProgramMultipleData,簡稱SPMD)描述基于快速GR-QR分解細(xì)粒度并行算法的執(zhí)行過程。該算法包括初始化、計(jì)算、同步與數(shù)據(jù)存儲和下次計(jì)算準(zhǔn)備四個(gè)階段。初始化階段確定該處理單元的PID號,并根據(jù)PID號得到該處理單元計(jì)算上三角矩陣和正交矩陣的初始位置。計(jì)算階段主要完成上三角矩陣R和正交矩陣Q一行的計(jì)算,并且在上一個(gè)處理單元更新的基礎(chǔ)上完成矩陣B的更新操作。如語句S31和S34所示,第一個(gè)處理單元從DRAM存儲器中讀取數(shù)據(jù),其它處理單元從上一個(gè)處理單元中接收數(shù)據(jù)。語句S36則表示最后一個(gè)處理單元將更新結(jié)果寫回執(zhí)DRAM存儲器,而其余處理單元將其更新結(jié)果傳給下一個(gè)處理單元。正如上一節(jié)中的數(shù)據(jù)依賴關(guān)系圖所示,當(dāng)每個(gè)處理單元接收到第一個(gè)有效數(shù)據(jù)就可以啟動(dòng)該處理單元,并且當(dāng)完成一個(gè)更新操作就可將該更新結(jié)果傳給下一個(gè)處理單元。因此,S34、S35和S36可以并行執(zhí)行。在同步與數(shù)據(jù)存儲階段,當(dāng)最后一個(gè)處理單元完成更新操作,即所有處理完成本次計(jì)算和更新操作。將上三角矩陣R和正交矩陣Q一行的計(jì)算結(jié)果寫回至DRAM中。而下次計(jì)算準(zhǔn)備階段,確定下次的計(jì)算位置并判斷算法是否結(jié)束。如果算法結(jié)束發(fā)送計(jì)算結(jié)束信號,否則跳至語句S2進(jìn)行下一個(gè)計(jì)算。算法1PE[PID](1≤PID≤p)的快速GivensRotation細(xì)粒度并行算法3.2計(jì)算單元更新算法由并行算法不難得到快速GR-QR分解計(jì)算過程的時(shí)空圖。圖3是以4個(gè)處理單元的并行GR-QR時(shí)空圖。正如圖3所示,GR-QR細(xì)粒度并行算法的主要開銷包括DRAM數(shù)據(jù)讀取、更新操作流水線排空和Q和R矩陣結(jié)果存儲等三部分。為方便描述該結(jié)構(gòu)的可擴(kuò)展性,我們做如下假設(shè):(1)矩陣規(guī)模為n*n;(2)處理單元數(shù)為p,且n?p;(3)計(jì)算單元更新操作流水線級數(shù)為α,且n?α;(4)外部DRAM存儲帶寬為B;(5)計(jì)算流水線的計(jì)算頻率為F。下面以時(shí)鐘周期為單位分別計(jì)算QR分解算法的系統(tǒng)開銷,則第i次計(jì)算上述三部分的時(shí)鐘周期開銷分別為(2n-i*p)(n-i*p)/B、α*p/F和(2n-i*p)/B,即第i次上三角矩陣R和正交矩陣Q一行計(jì)算的時(shí)鐘周期開銷為:Ti=(2n2+2np)?(np?p2)i+p2i2B+αpF(1)Τi=(2n2+2np)-(np-p2)i+p2i2B+αpF(1)其中,0≤i≤s且s=n/p。那么,整個(gè)QR分解計(jì)算所需時(shí)鐘周期數(shù)為:TFGR=T0+T1+?+Ts=5n36pB+5n2B?5np6B+αnF(2)ΤFGR=Τ0+Τ1+?+Τs=5n36pB+5n2B-5np6B+αnF(2)因?yàn)橛衝?p和n?α,總的時(shí)鐘周期數(shù)可以近似為:TFGR=5n36pB(3)ΤFGR=5n36pB(3)因此,總的系統(tǒng)時(shí)鐘周期開銷與處理單元數(shù)和外部DRAM存儲帶寬成反比,說明該細(xì)粒度并行算法具有良好的可擴(kuò)展性。4可擴(kuò)展fr-11100矩陣處理器4.1基于sdram的具有統(tǒng)一模式設(shè)計(jì)根據(jù)快速GR-QR細(xì)粒度并行算法,我們設(shè)計(jì)了可擴(kuò)展結(jié)構(gòu)的QR分解陣列處理器(如圖4所示)。為了提高存儲帶寬,該系統(tǒng)采用雙SDRAM存儲結(jié)構(gòu)。SDRAM_0和SDRAM_1分別用來存儲原始數(shù)據(jù)、中間結(jié)果和最終的計(jì)算結(jié)果。SDRAMController則是主機(jī)和系統(tǒng)中處理單元與SDRAM的接口模塊,主要完成主機(jī)和處理單元對SDRAM數(shù)據(jù)訪問。處理單元(GR-PE)是系統(tǒng)中的計(jì)算模塊,完成系統(tǒng)中所有的計(jì)算工作。各個(gè)處理單元之間以及第一個(gè)和最后一個(gè)處理單元與SDRAM存儲控制器之間由FIFO連接。MainController是系統(tǒng)的總控模塊,協(xié)調(diào)系統(tǒng)中所有模塊有序工作。假設(shè)系統(tǒng)的原始數(shù)據(jù)存放在SDRAM_0中。由統(tǒng)一模式QR分解細(xì)粒度并行算法可知,第一個(gè)處理單元(GR-PE_0)從SDRAM_0中接收數(shù)據(jù),其它處理單元從前一個(gè)處理單元接收數(shù)據(jù)。當(dāng)處理單元接收到第一個(gè)數(shù)據(jù)時(shí)就啟動(dòng)計(jì)算,并且當(dāng)完成更新操作立即將其結(jié)果傳給下一個(gè)處理單元。若是最后一個(gè)處理單元(GR-PE_p-1),則將更新結(jié)果寫回至SDRAM_1。每個(gè)處理單元每次完成矩陣Q和R一行或一列的計(jì)算,并且當(dāng)所有處理單元完成其對應(yīng)Q和R一行或一列的計(jì)算時(shí),便將其計(jì)算結(jié)果寫回到SDRAM_0。綜上所述,該QR分解陣列處理器結(jié)構(gòu)具有以下特點(diǎn):(1)雙存儲器結(jié)構(gòu),可以SDRAM的存儲帶寬增加一倍;(2)數(shù)據(jù)驅(qū)動(dòng)策略,即第一個(gè)數(shù)據(jù)到達(dá)便可啟動(dòng)該處理單元的計(jì)算;(3)數(shù)據(jù)的計(jì)算與通信相重疊,系統(tǒng)具有很高的計(jì)算通信比;(4)數(shù)據(jù)在處理單元之間流動(dòng),減少了對SDRAM存儲帶寬的需求;(5)細(xì)粒度的任務(wù)分配策略,每個(gè)處理單元完成矩陣Q和R一行或一列的計(jì)算,有利于系統(tǒng)的負(fù)載平衡;(6)每個(gè)處理單元只需與其前后兩個(gè)處理單元進(jìn)行數(shù)據(jù)交互,結(jié)構(gòu)簡單并且具有良好的可擴(kuò)展性。4.2factorcarli模塊如圖5所示,快速GR-QR分解處理單元(GR-PE)主要由更新因子計(jì)算模塊(FactorCal_Pipeline)、數(shù)據(jù)更新模塊(UpdateCal_Pipeline)以及一些存儲部件組成。其中,FactorCal_Pipeline模塊主要用來計(jì)算更新因子α、β、γ、di和dj。UpdateCal_Pipeline模塊用于完成數(shù)據(jù)的更新操作。FIFO_Dj用于緩存該GR-PE更新完成的參數(shù)dj,并傳給下一個(gè)GR-PE。片內(nèi)存儲器RAM用于存放從上一個(gè)GR-PE傳送過來的第一行數(shù)據(jù),并與其后從上一個(gè)GR-PE傳送過來的其它行數(shù)據(jù)及更新因子進(jìn)行更新操作。每完成一次更新操作就將第一行的更新結(jié)果寫回RAM中,而其它行更新完成的數(shù)據(jù)傳給下一個(gè)GR-PE。當(dāng)該GR-PE完成所有的更新操作時(shí),RAM中存放的便是矩陣Q和R的一行結(jié)果。5altratixiiiep2s130、犯配電系統(tǒng)的ssc3圖1我們采用StratixIIFPGA測試平臺進(jìn)行實(shí)驗(yàn)。測試平臺主要包括:Altera的StratixIIEP2S130F1020C5FPGA芯片、兩條MicronMT16LSDT12864A的1GBSDRAM存儲器和USB2.0接口。5.1大規(guī)模矩陣的crc-pe本實(shí)驗(yàn)在StratixIIFPGA測試平臺對快速GR-QR陣列處理器進(jìn)行綜合,結(jié)果如表1所示。該陣列處理器最大可以完成規(guī)模為4K*4K矩陣的QR分解。為了實(shí)現(xiàn)大規(guī)模矩陣QR分解,GR-PE中的局部存儲器采用M4Ks和M-RAMs存儲塊實(shí)現(xiàn)。15個(gè)GR-PE的M4Ks和M-RAMs存儲塊使用率可達(dá)99.8%,其它資源的使用率也與GR-PE數(shù)量成正比。由于FPGA芯片內(nèi)布局布線的原因,陣列處理器的頻率隨GR-PE數(shù)量的增加有所下降。5.2加速比分析圖6所示是系統(tǒng)加速比與陣列處理器中處理單元數(shù)量之間的關(guān)系。從圖6中不難看出,系統(tǒng)加速比與處理單元數(shù)成正比關(guān)系,證明該陣列處理器結(jié)構(gòu)具有良好的可擴(kuò)展性。且由3.2節(jié)的性能分析結(jié)果可知,處理單元數(shù)的增加并不額外增加外部存儲帶寬。同時(shí),加速比隨著矩陣規(guī)模的增大而增大,說明該結(jié)構(gòu)的陣列處理器更適于大規(guī)模QR分解算法。5.3fpgaacelrator軟件環(huán)境分析基于Pentium雙核CPU和QR分解陣列處理器兩個(gè)平臺,我們對512*512、1K*1K、2K*2K和4K*4K四種規(guī)模矩陣QR的性能進(jìn)行測試,結(jié)果如表2所示。其中,C++的編程環(huán)境為VC++6.0,并且是release版本。SSE(1)和SSE(2)分別為單線程和雙線程SSE,而FPGAAccelerator為包含15個(gè)FGR-PE的陣列處理器。與Pentium通用處理器的C++性能相比,FPGAAccelerator可取得17.628到19.002倍的加速比。而與雙線程SSE相比可取得近4倍的性能加速。6可擴(kuò)展性測試實(shí)驗(yàn)本文對大規(guī)模矩陣QR分解的FPGA實(shí)現(xiàn)進(jìn)