基于BWDSP1042的復數矩陣向量乘的優化與實現

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

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

0 引 言

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

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

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

1 BWDSP1042處理器

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

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

圖1 eC104+內核的結構

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

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

2 復數矩陣向量乘算法

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

復數矩陣:

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

n維的復數向量:

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

(2)

A與x相乘得復數向量y:

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

(3)

任意yt滿足式:

該傳統運算方法,在BWDSP1042上實現具有運算效率低的問題。

3 復數矩陣-向量乘算法的優化與實現

3.1 結合硬件資源優化復數矩陣向量乘

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

3.1.1傳統復數矩陣向量乘方法

傳統的復數矩陣向量乘在BWDSP1042中四個執行宏中讀取的方法如圖3所示。

圖3 傳統復數矩陣向量乘在四個宏中的運算

此方法在BWDSP1042上實現的具體過程分為五步:

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

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

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

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

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

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

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

在BWDSP1042上實現復數矩陣向量乘。可采用圖4中對復數矩陣按列取四個復數,分別在四個執行宏中同時與向量中的復數相乘的方法。

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

此方法在BWDSP1042上具體的實現過程如下:

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

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

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

第四步:保存數據。保存輸出向量y1～y4的值。

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

該方法循環一次,同時從四個執行宏中輸出y1～y4的值,可避免不同執行宏間數據相加的執行過程,有效地節省了運行周期。

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

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

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

圖5 模八尋址計算復數矩陣向量乘

3.2 結合軟件優化技術優化復數矩陣向量乘

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

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

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

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

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

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

圖6 二級循環次數大于9的實現方法

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

4 測試結果與分析

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

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

圖7 按列取數方式以及減少二級循環內次數優化前后對比

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

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

圖8 采用模八尋址以及減少二級循環內次數優化前后對比

5 結 語

本文在使用指令并行,循環展開,軟件流水的基礎上,結合BWDSP1042的硬件結構,對復數矩陣向量乘進行優化和實現。

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

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

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