基于BWDSP1042的復數(shù)矩陣向量乘的優(yōu)化與實現(xiàn)

藺麗華 張美春 王佳儀 李 敏 門 浩

1(西安科技大學通信與信息工程學院 陜西 西安 710054) 2(西安電子科技大學電子工程學院 陜西 西安 710071)

0 引 言

矩陣向量乘在視頻圖像處理、無線通信、數(shù)學信號處理等領域應用廣泛。由于矩陣向量乘計算復雜度較高,運算過程效率低,導致其在一些領域中無法滿足系統(tǒng)實時處理的要求[1-2]。因此,提高矩陣向量乘的運算速度是十分必要的。目前,針對矩陣向量乘的研究已經十分成熟,但如何使之適應新的數(shù)字信號處理器以獲得更好的性能,是目前研究的重點。

針對如何高效實現(xiàn)矩陣向量乘,國內外做了大量研究,肖漢等[3]通過將矩陣向量乘分解成若干個子任務來提高運行速度。尹孟嘉等[4]通過構建性能度量模型為不同形態(tài)的矩陣選擇不同的存儲格式來提高算法的性能。蘇錦柱等[5]提出了一種基于FPGA的矩陣向量乘新的并行算法。以上的矩陣向量乘實現(xiàn)方法是針對稀疏矩陣向量乘,不具有普遍性。另外,與FPGA相比,DSP具有較高的運算能力,能夠實現(xiàn)實時處理,具有軟件的靈活性,且成本相對較低,在BWDSP1042上研究矩陣向量乘具有重要意義。

本文研究了復數(shù)矩陣向量乘在BWDSP1042處理器上的優(yōu)化和實現(xiàn)。根據(jù)該處理器的VLIW和SIMD硬件結構,使用軟件流水、循環(huán)展開、指令并行的手段,結合線性尋址和模八尋址的尋址方式,針對不同矩陣,提出兩種不同的優(yōu)化方法以提高復數(shù)矩陣向量乘的運行效率。方法一:按列分塊與減少二級循環(huán)內循環(huán)次數(shù)相結合的方法矩陣列非4的倍數(shù))。方法二:模八尋址和減少二級循環(huán)內循環(huán)次數(shù)相結合的方法(矩陣列為4的倍數(shù))。實驗結果表明:這兩種方法能夠有效減少矩陣向量乘的運行周期,充分挖掘了BWDSP1042處理器的潛能。

1 BWDSP1042處理器

BWDSP1042是中國電子科技集團公司第38研究所研制的首款多核處理器。其內部集成2個新一代處理器核eC104+[6]。eC104+采用16發(fā)射、單指令流,多數(shù)據(jù)流架構,其處理性能與BWDSP100相比得到大幅提升。

eC104+中有四個執(zhí)行宏(x、y、z、t),每個執(zhí)行宏中存在一個寄存器組和四個運算部件[7],其中運算部件包括一個超算器(SPU)、四個移位器(SHF)、八個乘法器(MUL)、八個算數(shù)邏輯單元(ALU)。eC104+的指令總線位寬是512位,包含兩條寫總線和兩條讀總線,且每條總線的位寬是256位。數(shù)據(jù)總線是全雙工,因此最多可同時使用三條數(shù)據(jù)總線實現(xiàn)數(shù)據(jù)傳輸。eC104+有6個大小為256k×32 bit的內存塊(block),每個內存塊中包含八個bank。內部有三個相互獨立且結構相同的地址發(fā)生器。eC104+內核的結構如圖1所示。

圖1 eC104+內核的結構

eC104+內核是13級流水線結構,可分為三部分,分別為由內存驅動的取指令3級(fe0～fe2)、指令緩沖3級(IAB0～IAB2)、由指令驅動的7級流水(指令譯碼4級(dc1～dc4),取操作數(shù)1級(ac),指令執(zhí)行1級(ex),指令結果寫回1級(wb))。如圖2所示,在水線的dc～wb級有很多因素會引起指令流水的停頓,主要因素包括數(shù)據(jù)bank沖突、數(shù)據(jù)相關、原子操作、分支、訪問核外存儲資源引發(fā)的等待、異常及程序控制指令等。

圖2 eC104+內核的13流水線結構

2 復數(shù)矩陣向量乘算法

傳統(tǒng)的復數(shù)矩陣向量乘由一個二級循環(huán)實現(xiàn),即復數(shù)矩陣A中的第t行與向量x中各個元素相乘、累加,完成yt的計算。具體過程如下所示:

復數(shù)矩陣:

式中:i表示虛部,r表示實部,m表示行,n表示列。

n維的復數(shù)向量:

x=(xi1+xr1,xi2+xr2,…,xin+xrn)T

(2)

A與x相乘得復數(shù)向量y:

y=(yi1+yr1,yi2+yr2,…,yim+yrm)T

(3)

任意yt滿足式:

該傳統(tǒng)運算方法,在BWDSP1042上實現(xiàn)具有運算效率低的問題。

3 復數(shù)矩陣-向量乘算法的優(yōu)化與實現(xiàn)

3.1 結合硬件資源優(yōu)化復數(shù)矩陣向量乘

本節(jié)結合BWDSP1042處理器的硬件結構以及尋址方式,使用按列分塊和模八尋址兩種優(yōu)化方法對復數(shù)矩陣向量乘進行優(yōu)化。

3.1.1傳統(tǒng)復數(shù)矩陣向量乘方法

傳統(tǒng)的復數(shù)矩陣向量乘在BWDSP1042中四個執(zhí)行宏中讀取的方法如圖3所示。

圖3 傳統(tǒng)復數(shù)矩陣向量乘在四個宏中的運算

此方法在BWDSP1042上實現(xiàn)的具體過程分為五步:

第一步:讀取數(shù)據(jù)。取復數(shù)矩陣A中第1行相鄰的四個復數(shù),以及向量中的四個復數(shù),其虛部和實部分別存放在四個執(zhí)行宏(x、y、z、t)中。

第二步:計算并讀取新的數(shù)據(jù)。矩陣A中第1行相鄰的四個復數(shù)與向量中的四個復數(shù)相乘累加,其結果存放在累加器中。

第三步:重復第二步,直至矩陣中的第一行與向量計算結束。

第四步:計算y1并保存。四個執(zhí)行宏的數(shù)相加得y1,將y1寫入內存。

第五步:重復第一步至第四步,計算矩陣所有的行與向量乘。直至得到復數(shù)矩陣向量乘的結果。

該方法在計算過程中,y1被分為8部分,分別存儲在四個執(zhí)行宏中,在乘累加計算完成后,需要額外消耗資源將不同執(zhí)行宏中的數(shù)相加。為解決該問題,本文提出了按列取數(shù)的方法。

3.1.2按列分塊計算復數(shù)矩陣向量乘的方法

在BWDSP1042上實現(xiàn)復數(shù)矩陣向量乘?？刹捎脠D4中對復數(shù)矩陣按列取四個復數(shù),分別在四個執(zhí)行宏中同時與向量中的復數(shù)相乘的方法。

圖4 按列計算復數(shù)矩陣向量乘的運算過程

此方法在BWDSP1042上具體的實現(xiàn)過程如下:

第一步:讀取數(shù)據(jù)。讀取復數(shù)矩陣中第1列的四個復數(shù),讀取向量中第一個復數(shù),分別存在四個執(zhí)行宏中。

第二步:計算并讀取新的數(shù)據(jù)。第一列的四個復數(shù)分別與向量中的第一個復數(shù)相乘,并將結果存放于累加器中。同時讀取矩陣下一列的四個復數(shù),以及向量的下一個復數(shù)。

第三步:重復執(zhí)行第二步,直至矩陣中前四行數(shù)據(jù)與向量乘運算結束。

第四步:保存數(shù)據(jù)。保存輸出向量y1～y4的值。

第五步:重復第一步至第四步的計算方法,依次計算其他行,直至得到輸出向量。

該方法循環(huán)一次,同時從四個執(zhí)行宏中輸出y1～y4的值,可避免不同執(zhí)行宏間數(shù)據(jù)相加的執(zhí)行過程,有效地節(jié)省了運行周期。

3.1.3模八尋址計算復數(shù)矩陣向量乘的方法

對于按列計算復數(shù)矩陣向量乘方法,當復數(shù)矩陣的列數(shù)是4的倍數(shù)時,讀取復數(shù)矩陣會產生bank沖突。bank沖突會造成流水線停頓,在停頓的若干個cycle內依次訪問沖突的地址,直到沖突解除才恢復流水。在程序中直接體現(xiàn)在讀取數(shù)據(jù)時,每讀一次數(shù)據(jù)流水線停頓兩次。

為了解決bank沖突,當復數(shù)矩陣的列數(shù)是4的倍數(shù)時,采用圖5的模八尋址方式,在讀取數(shù)據(jù)時,執(zhí)行宏x讀取第一行的第一個復數(shù),執(zhí)行宏y讀取第二行的第二個復數(shù),執(zhí)行宏z讀取第三行的第三個復數(shù),執(zhí)行宏t讀取第四行的第四個復數(shù),再與復數(shù)向量中的數(shù)據(jù)相乘。

圖5 模八尋址計算復數(shù)矩陣向量乘

3.2 結合軟件優(yōu)化技術優(yōu)化復數(shù)矩陣向量乘

BWDSP1042上的軟件優(yōu)化技術主要包括指令并行、循環(huán)展開、軟件流水三種方法[8-9]。

指令并行主要包括兩個方面:一是基于SIMD指令在數(shù)據(jù)級上的并行,即同時對四個執(zhí)行宏中的相同的運算單元以及通用寄存器進行相同的操作,或者同時訪問數(shù)據(jù)存儲器;二是在一個指令行中使用多個指令槽的技術。通過指令槽將多條語句分開,使多條指令同時執(zhí)行。

循環(huán)展開是多次重復循環(huán)體代碼,該方法通過使用大量代碼以提高代碼并行度和執(zhí)行效率,本質上為向量化的思想,運用循環(huán)展開的方法將迭代間并行更改為迭代內并行,節(jié)省了大量的分支判斷類指令與執(zhí)行條件指令等資源,進而提高了代碼效率。針對BWDSP1042的處理器,按照宏內指令編排原則,仿存及運算結果間隔兩周期有效,一般規(guī)定循環(huán)展開至少三次以填補空周期行。

軟件流水是通過代碼的交織以實現(xiàn)不同循環(huán)體間的并行,運用展開來大量減少循環(huán)次數(shù),其中單個循環(huán)體仍然順序執(zhí)行,充分運用了底層資源,進而將代碼效率最大化。

使用指令并行、循環(huán)展開、軟件流水優(yōu)化方法在循環(huán)體內存在執(zhí)行無效指令問題,針對復數(shù)矩陣向量乘運算,這些無效指令的執(zhí)行嚴重影響了運行效率。因此,本文提出減少二級循環(huán)內的循環(huán)次數(shù)的方法,在循環(huán)體外執(zhí)行循環(huán)體內未完成的部分,同時對下一次所需要的數(shù)據(jù)做處理。

圖6中指令行1讀入復數(shù)矩陣中四個復數(shù)以及復數(shù)向量中的一個復數(shù),其相應mul1、add1、acc1的運算過程在指令行4、指令行7、指令行10中執(zhí)行。指令行2和指令行3中的rea2和rea3用來填充rea1的兩個氣泡行,其相應的乘、加、累加操作分別在mul2、mul3、add2、add3、acc2、acc3中執(zhí)行,第一次執(zhí)行acc3后,跳轉至指令行10,繼續(xù)執(zhí)行。

圖6 二級循環(huán)次數(shù)大于9的實現(xiàn)方法

使用減少二級循環(huán)內的循環(huán)次數(shù)的方法時,在二級循環(huán)中執(zhí)行n-9次時,跳出二級循環(huán),此時剩余的9次循環(huán)已在二級循環(huán)體內完成了部分操作(圖中指令行4至指令行12中的實線中的指令)。順序執(zhí)行指令行13至指令行21,處理該過程未完成的部分(圖中指令行13至指令行21中的實線中的指令),同時在指令行13修訂下次的讀數(shù)地址,在指令行14至指令行24執(zhí)行修正地址后的rea、mul、add操作(圖中指令行14至指令行22中的虛線中的指令)。此方法通過減少二級循環(huán)的循環(huán)次數(shù),減少了無效指令的執(zhí)行次數(shù),提高了指令利用率,從而有效縮短了運行周期。

4 測試結果與分析

本文結合硬件資源和軟件優(yōu)化技術提出復數(shù)矩陣向量乘優(yōu)化的兩種方法。方法一:按列分塊與減少二級循環(huán)內循環(huán)次數(shù)相結合的方法(適用于:矩陣列非4的倍數(shù))。方法二:模八尋址和減少二級循環(huán)內循環(huán)次數(shù)相結合的方法(適用于:矩陣列為4的倍數(shù))。

為了驗證這兩種方法可有效提高BWDSP1042的數(shù)據(jù)處理速度。本實驗使用BWDSP1042配套的軟件開發(fā)環(huán)境ECS,分別測試了不同大小的復數(shù)矩陣向量乘。

圖7 按列取數(shù)方式以及減少二級循環(huán)內次數(shù)優(yōu)化前后對比

圖7中分別測試了復數(shù)矩陣大小為19×19、35×35、67×67時與復數(shù)向量相乘的運行周期,圖中灰色柱狀圖表示傳統(tǒng)按行取數(shù)在使用軟件優(yōu)化技術下的運行周期,白色柱狀圖表示在方法一下的運行周期。針對m×n的矩陣,該方法相對傳統(tǒng)方法可減少m×13拍的四個執(zhí)行宏相加的過程,另外減少了二級循環(huán)中指令行的執(zhí)行次數(shù)以及零開銷循環(huán)的執(zhí)行次數(shù)。由圖7可知:與傳統(tǒng)算法相比,本方法使運行周期縮短了64.4%～72.8%。

圖8測試了復數(shù)矩陣大小為16×16、32×32、64×64時與復數(shù)向量相乘的運行周期,三個矩陣的列數(shù)都是4的倍數(shù),采用傳統(tǒng)取數(shù)方式會產生bank沖突,導致每次讀數(shù)流水線停頓兩拍。對于m×n的矩陣,運行周期會多出拍。采用模八尋址的方式,可避免bank沖突。圖8中黑色柱狀圖表示傳統(tǒng)按行取數(shù)在使用軟件優(yōu)化技術下的運行周期,白色柱狀圖表示在方法二下的運行周期。由圖8可知,與傳統(tǒng)算法相比,本方法可將運行周期縮短68.4%～84.9%。

圖8 采用模八尋址以及減少二級循環(huán)內次數(shù)優(yōu)化前后對比

5 結 語

本文在使用指令并行,循環(huán)展開,軟件流水的基礎上,結合BWDSP1042的硬件結構,對復數(shù)矩陣向量乘進行優(yōu)化和實現(xiàn)。

1) 復數(shù)矩陣采用按列取數(shù),減少了執(zhí)行宏間數(shù)據(jù)相加的過程,可降低程序的復雜度。在一定程度上縮短了運行周期。

2) 采用減少復數(shù)矩陣向量乘中的二級循環(huán)內循環(huán)次數(shù),可以減少無效指令的執(zhí)行,充分利用了BWDSP1042的計算資源和存儲資源,提高了指令的運行效率。

3) 采用模八尋址的方式,消除了特殊矩陣下存在的bank沖突問題,加快了指令執(zhí)行速度。