藺麗華 張美春 王佳儀 李 敏 門(mén) 浩

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

0 引 言

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

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

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

1 BWDSP1042處理器

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

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

圖1 eC104+內(nèi)核的結(jié)構(gòu)

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

圖2 eC104+內(nèi)核的13流水線結(jié)構(gòu)

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

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

復(fù)數(shù)矩陣:

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

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

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

(2)

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

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

(3)

任意yt滿足式:

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

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

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

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

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

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

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

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

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

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

第三步:重復(fù)第二步,直至矩陣中的第一行與向量計(jì)算結(jié)束。

第四步:計(jì)算y1并保存。四個(gè)執(zhí)行宏的數(shù)相加得y1,將y1寫(xiě)入內(nèi)存。

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

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

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

在BWDSP1042上實(shí)現(xiàn)復(fù)數(shù)矩陣向量乘。可采用圖4中對(duì)復(fù)數(shù)矩陣按列取四個(gè)復(fù)數(shù),分別在四個(gè)執(zhí)行宏中同時(shí)與向量中的復(fù)數(shù)相乘的方法。

圖4 按列計(jì)算復(fù)數(shù)矩陣向量乘的運(yùn)算過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 測(cè)試結(jié)果與分析

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

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

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

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

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

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

5 結(jié) 語(yǔ)

本文在使用指令并行,循環(huán)展開(kāi),軟件流水的基礎(chǔ)上,結(jié)合BWDSP1042的硬件結(jié)構(gòu),對(duì)復(fù)數(shù)矩陣向量乘進(jìn)行優(yōu)化和實(shí)現(xiàn)。

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

2) 采用減少?gòu)?fù)數(shù)矩陣向量乘中的二級(jí)循環(huán)內(nèi)循環(huán)次數(shù),可以減少無(wú)效指令的執(zhí)行,充分利用了BWDSP1042的計(jì)算資源和存儲(chǔ)資源,提高了指令的運(yùn)行效率。

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