基于BWDSP平臺的信號處理庫函數(shù)優(yōu)化

于海洋 陳冠林 蔣天翔 蔣慧麗 彭昌

（國家計算機網(wǎng)絡(luò)與信息安全管理中心安徽分中心 安徽省合肥市 230041）

1 引言

信號處理庫函數(shù)包括數(shù)字濾波器、窗函數(shù)、變換、倒譜分析、統(tǒng)計信號處理等函數(shù)。本文從變換、窗函數(shù)這兩部分中選取若干函數(shù)進行優(yōu)化。

本文的主要工作如下：

（1）針對變換部分中FFT（快速傅里葉變換）、IFFT（逆快速傅里葉變換）、CZT（線性調(diào)頻Z變換）這三個函數(shù)的串行算法在BWDSP上運行效果不理想的狀況，作者參考x86環(huán)境下c語言函數(shù)使用嵌入?yún)R編的優(yōu)化方式，在保留測試文件、頭文件使用c語言的形式下，嵌入?yún)R編語言庫函數(shù)或者子函數(shù)。根據(jù)BWDSP的VLIW（超長指令字）特性，使用指令級并行的方式，將FFT、IFFT、CZT函數(shù)并行化，提高了FFT、IFFT、CZT函數(shù)的運行效率。實驗結(jié)果顯示，F(xiàn)FT的相對加速比從2.92到3.05；IFFT的相對加速比從2.94到3.08；CZT函數(shù)的相對加速比從2.70到2.74。

（2）針對窗函數(shù)中巴特利特-漢寧窗、巴特利特窗、切比雪夫窗、高斯窗這四個函數(shù)，在結(jié)合使用指令級并行及循環(huán)展開、減少訪存、變量替換等c語言層次的優(yōu)化方式下，使程序性能提升比例從9.49%到68.75%。

2 BWDSP介紹

BWDSP處理器可廣泛地運用于各種高性能計算領(lǐng)域，是一款32位浮點DSP，同時也支持16位和32位定點數(shù)據(jù)格式（本文中定點均指整數(shù)），采用超長指令字架構(gòu)，具備強大的并行處理能力。BWDSP處理器采用16條指令發(fā)射、SIMD（單指令多數(shù)據(jù)流）架構(gòu)，共有11級流水線，分別為取指令3級、指令緩沖池3級、譯碼2級、取操作數(shù)1級、執(zhí)行操作1級和數(shù)據(jù)寫回1級，采用多級取指支持分支預測以減少流水線的性能開銷。

3 FFT算法優(yōu)化介紹

FFT被廣泛地應用于信號處理、圖形圖像、功率譜估計等領(lǐng)域。FFT算法源于研究人員對DFT（離散傅里葉變換）算法運算量的不可容忍性，直接計算DFT可能使得計算機無法承受其運算量。

3.1 FFT串行算法研究現(xiàn)狀

一些算法對逆序過程進行優(yōu)化后，可以使得循環(huán)次數(shù)減少，如張學智等在快速實現(xiàn)FFT的逆序方法中，從逆序數(shù)的生成規(guī)律入手，發(fā)現(xiàn)逆序數(shù)的生成是一個遞歸的形式。該方法生成過程簡單明了，排序速度比標準程序塊，但缺點在于在占用內(nèi)存較多。當點數(shù)規(guī)模較大時，該方法占用的內(nèi)存空間也會非常大?？紤]到BWDSP緩存較小，不便于采用這種方法。

高麗等在文章FFT標準整序算法的優(yōu)化中，構(gòu)思巧妙，將逆序序列分為前后兩部分，然后重新排列，由前面的序列可以分別在每個數(shù)上加1得到后面的序列。但重排過程要多次交換數(shù)據(jù)，會多次產(chǎn)生訪存，并且不利于在BWDSP上進行更進一步的改善。

方志紅等在文章利用逆序循環(huán)實現(xiàn)FFT運算中倒序算法的優(yōu)化中，針對MPC7400硬件提供的128比特浮點矢量[即一次可以取出4個32位浮點數(shù)，采用IQIQ（實部虛部實部虛部）的存儲方式。這種方法理論上能明顯減少循環(huán)次數(shù)，然而在使用c語言程序進行移植后，實驗測試發(fā)現(xiàn)其性能并未達到甚至接近理論值。究其原因在于無論BWDSP或glibc均未擁有類似于MPC7400提供的浮點矢量部件及交換部件。

FFT算法另一優(yōu)化點在于針對蝶形因子的優(yōu)化。王非非等人給出了一種旋轉(zhuǎn)系數(shù)訪存優(yōu)化的FFT算法，該方法根據(jù)旋轉(zhuǎn)系數(shù)的訪存比率統(tǒng)計情況，提出了一種旋轉(zhuǎn)系數(shù)訪問存儲器的優(yōu)化方法。通過僅存儲使用率較高的旋轉(zhuǎn)系數(shù)，而對于其他使用率較低的旋轉(zhuǎn)系數(shù)則采用泰勒插值計算方法生成。這樣做既節(jié)省存儲空間，又提供處理器緩存的命中率，保持計算精確度。

綜上可知，F(xiàn)FT串行算法的優(yōu)化方向主要集中在三個領(lǐng)域：

（1）針對逆序算法進行優(yōu)化，減少循環(huán)的循環(huán)次數(shù)。如n點復數(shù)FFT，共有2n個點，逆序循環(huán)時，按照Cooley-Tukey算法，需要進行n-2次循環(huán)。使用某些特定算法后，可以使得逆序循環(huán)次數(shù)大為減少。

（2）針對計算部分進行優(yōu)化，這部分需要從流水線的角度合理安排訪存操作與計算操作，使得處理器一直處于工作狀態(tài)。這部分工作主要需要通過匯編指令進行。

（3）針對蝶形因子進行優(yōu)化，根據(jù)該系數(shù)的周期性質(zhì)、可約性質(zhì)，使得對蝶形因子的計算減少。

3.2 FFT并行算法研究現(xiàn)狀

張燕燕等利用OpenMp（用于共享內(nèi)存并行系統(tǒng)的多線程程序設(shè)計的編譯方法），將串行FFT修改后，實現(xiàn)了FFT的并行算法。

王剛強等根據(jù)多核體系結(jié)構(gòu)機器擁有多級存儲結(jié)構(gòu)及支持線程級并行程序的特點，將數(shù)據(jù)劃分為滿足二級高速緩存大小的子序列。再將各個子序列進行二次劃分，分批進入一級高速緩存中，然后開始子序列的計算。

Amir A 等人提出了一個可以執(zhí)行于任意個處理器核數(shù)的機器上的并行FFT算法，該算法對一維的傅里葉變換實驗結(jié)果接近線性加速。該算法的特點是實現(xiàn)在共享內(nèi)存MIMD機器上。

汪清等圍繞FFT如何在多核架構(gòu)上高效并行實現(xiàn)這一問題，對并行FFT算法優(yōu)化改進并在SCC、龍芯等多核架構(gòu)上高效并行實現(xiàn)。

劉紅俠等人分析基-2 FFT數(shù)據(jù)流，得出每次蝶形計算的操作數(shù)其結(jié)果按照原讀取地址返回，并且由于蝶形因子地址相同，可以使用一個地址產(chǎn)生器。實現(xiàn)了兩條流水線并行所需的操作數(shù)級旋轉(zhuǎn)系數(shù)的并行訪問，并且減少了蝶形因子的計算次數(shù)。

胡灝等人利用多線程特點，針對多處理器機器，創(chuàng)建與處理器數(shù)目相同的線程，使得每個線程負載均衡，平均分配計算工作，提高了FFT程序的運行效率。缺點是機器需要支持多線程技術(shù)。

綜上可知，國內(nèi)外針對FFT算法的并行化工作主要有三個方向：

（1）針對多核處理器，根據(jù)其硬件特性為FFT算法提供較高的進入緩存的可能，避免因訪存操作造成長時間的處理器等待情況。

（2）針對支持多線程等技術(shù)的機器，使較多的線程均衡地分配任務(wù)，同時計算，達到并行效果。

（3）針對FFT算法自身并行性，如蝶形因子的計算、輸入序列的存取操作，找到其并行操作后，使得算法本身能夠以流水線的方式執(zhí)行。

以上是關(guān)于FFT并行化的部分國內(nèi)外研究成果，這些并行方法分別從不同角度對FFT的運行效率進行改善，對于面向BWDSP的FFT等算法并行化有著重要的參考意義。但由于BWDSP處理器的自身架構(gòu)特性、寄存器使用及所支持的編程環(huán)境自成一格，因此以上方法不適合運用于BWDSP上。這就需要針對BWDSP本身硬件特點，結(jié)合FFT的內(nèi)在并行性，進行并行化程度較高的優(yōu)化。

4 FFT等函數(shù)的指令級并行優(yōu)化

4.1 并行化安排匯編指令

作為一款擁有超長指令字特性的DSP處理器，BWDSP為程序的指令級并行提供了可能。研究發(fā)現(xiàn)串行FFT算法、IFFT算法、CZT算法具備良好的串行特性及函數(shù)調(diào)用關(guān)系。針對這三個函數(shù)，在不造成數(shù)據(jù)相關(guān)的前提下，通過合理地布局不同的指令，進行并行優(yōu)化處理。

作為一種專用的類c匯編，BWDSP不支持x86情況下的嵌入式匯編。它支持如下兩種情況：

第一種情況：

第一種情況是主函數(shù)由c語言編寫，子函數(shù)則由BWDSP匯編語言編寫。第二種情況是主函數(shù)由匯編代碼編寫，子函數(shù)則由c語言編寫。

由于線性調(diào)頻z變換函數(shù)多次調(diào)用基-2 DIT-FFT，基-2 DIT-IFFT程序，可以斷定這兩個程序是本函數(shù)的熱點函數(shù)，將FFT、IFFT兩個函數(shù)改寫為BWDSP匯編程序這種枯燥易錯工作顯得十分必要?？紤]到單純的匯編代碼顯然會有性能上的提升，加之BWDSP的VLIW特點，可以利用這一特性，實現(xiàn)指令級別的FFT并行。

這段代碼較少使用VLIW方式布局代碼，是為了示意，以免因不了解該匯編語言語法而造成困惑。使用VLIW方式安排代碼后，會顯得混亂，更加不易于理解代碼。BWDSP共有4個核，每個核上面有15個部件，其中包括8個算術(shù)邏輯運算部件，4個乘法部件，2個移位部件，1個超算部件。這種在不造成數(shù)據(jù)相關(guān)情況下的并行排放方式，可以使得每一行盡量安排較多的指令，機器一次能夠執(zhí)行多條代碼，極大程度上發(fā)揮BWDSP的并行性能。

VLIW布局代碼：

xr10 = 1 || xfr11 =0.5 || xr39 = [u9 +-27,0]

代碼采用了VLIW方式布局代碼，以第一行代碼為例，對x核上十號、十一號寄存器分別賦值整數(shù)、浮點數(shù)據(jù)，將存儲器中地址寄存器u9-27指向的數(shù)據(jù)取出來并賦給第三十九號寄存器。這一行代碼包括三條指令，其中有兩個賦立即數(shù)指令、一個訪存指令，由于每個核上均有兩個位寬為64比特的讀總線及一個位寬為64比特的寫總線，它們互相之間并不干擾。

4.2 實驗結(jié)果對比

4.2.1 FFT指令級并行化實驗

按照超長指令字思想布局代碼，對基-2 DIT-FFT 及基-2 DIT-IFFT串行程序進行匯編代碼改寫并進行指令級別并行化處理。針對FFT程序，取八組數(shù)據(jù)進行對比。

基-2 FFT串行程序被修改為BWDSP匯編級指令并行化后性能得到了極大程度上的提升，n等于8192點時間上節(jié)省了81739000 ns，n等于4096點時間節(jié)省了37854900 ns，...，n等于64點時間節(jié)省了313282 ns。本例中所選擇各個采樣點的節(jié)省時間均有較好的表現(xiàn)。所選擇的八個樣點的相對加速比也比較理想，平均加速比接近3倍。

當FFT取樣點數(shù)小于1024時，時間性能雖然有提升，但是由于樣點本身數(shù)量較少使得運算量較低。當樣點數(shù)大于1024點時，時間上的差距開始拉開。當取8192個樣點時，時間差達到了一個較大的值。不難得出結(jié)論，隨著取樣點數(shù)的增加，指令級并行FFT算法的優(yōu)勢會愈來愈凸顯出來。

4.2.2 IFFT指令級并行化實驗

基-2逆FFT的算法處理過程類似于基-2 FFT算法，不同之處是需要對輸入序列進行除法操作?？梢钥闯鰞烧邊^(qū)別不大，最終的運算量也是相當?shù)?，其結(jié)果數(shù)據(jù)也近似。取樣點小于1024點時，優(yōu)化效果不是十分的明顯；當取樣點數(shù)大于1024時，優(yōu)化后的并行程序優(yōu)勢十分明顯。

4.2.3 CZT指令級并行化實驗

線性調(diào)頻z變換函數(shù)調(diào)用了基-2 FFT、基-2 IFFT、向量乘法等函數(shù)，采用主干代碼使用c語言編寫，這樣做有利于閱讀與理解，使得用戶迅速熟悉該函數(shù)。將該函數(shù)調(diào)用的基-2 FFT、基-2 IFFT、向量乘法這三個函數(shù)進行匯編代碼改寫。線性調(diào)頻z變換的優(yōu)化效果十分明顯，以2000點取樣結(jié)果為例，節(jié)省時間118574868納秒，相對加速比例為2.721320。取六組數(shù)據(jù)，其平均加速比大于2.70，可以認為該程序得到了較為不錯的性能提升。

5 窗函數(shù)的優(yōu)化

針對BWDSP信號處理庫中的巴特利特-漢寧窗、巴特利特窗、切比雪夫窗、高斯窗進行優(yōu)化。以使用常規(guī)的優(yōu)化方法為主，以使用匯編語言的方式為輔。實驗結(jié)果表明，窗函數(shù)的性能提升從9.49%到68.75%。

5.1 常規(guī)優(yōu)化手段介紹

常規(guī)優(yōu)化手段主要包括：循環(huán)展開、矩陣分塊、減少訪存、指令替換、數(shù)據(jù)預取等操作。

其他優(yōu)化方法如從循環(huán)中提取固定的代碼；用后置條件的循環(huán)替代前置條件的循環(huán)；用自加自減替換加一減一；將多重循環(huán)中循環(huán)次數(shù)較多的循環(huán)體放置在最內(nèi)層以減少處理器跨切循環(huán)層的次數(shù)；將邏輯表達式中為真概率高的子表達式放置在最前方、將邏輯與表達式中為假概率高的子表達式放置在最后面等。

5.1.1 巴特利特-漢寧窗優(yōu)化

巴特利特-漢寧窗，是信號處理領(lǐng)域中常用的基本窗函數(shù)，也稱為廣義余弦窗。在主要程序循環(huán)體外聲明一個浮點型臨時變量temp，賦值為1/(n-1)。然后將循環(huán)體中的除以n-1修改為乘以temp。將函數(shù)調(diào)用fabs修改為增加一個判斷語句，若變量ftmp小于零，則將其賦值為正即可。其性能對比如圖1所示。

圖1：Barthannwin性能優(yōu)化對比

5.1.2 巴特利特窗優(yōu)化

在主要程序循環(huán)體前添加變量聲明并賦值n-1的倒數(shù)。然后在循環(huán)體中替換除以n-1的操作。

其性能提升如圖2所示。

圖2：巴特利特窗性能優(yōu)化對比

5.1.3 切比雪夫窗優(yōu)化

切比雪夫窗主要占用時間的地方有三處循環(huán)體。考慮到第二個主要循環(huán)操作并沒有調(diào)用子函數(shù)，且內(nèi)部表達式較多，不利于匯編實現(xiàn)，選擇第一、第三兩個循環(huán)體進行實現(xiàn)。將第二、第三個循環(huán)體整合為一個匯編接口程序。使用第三部分中介紹的指令并行技術(shù)。優(yōu)化前后切比雪夫窗的性能對比如圖3。

圖3：chebwin優(yōu)化前后性能對比

5.1.4 高斯窗優(yōu)化

在函數(shù)主要循環(huán)體前聲明變量以替換循環(huán)體中的除法，然后將對pow函數(shù)修改為對exp函數(shù)的調(diào)用。

其性能對比如圖4所示。

圖4：高斯窗性能優(yōu)化對比

6 總結(jié)

（1）對FFT、IFFT、CZT函數(shù)進行指令級并行化、對FFT、IFFT使用循環(huán)展開及減少訪存再次優(yōu)化。FFT函數(shù)的指令級并行化結(jié)果與串行結(jié)果對比顯示各個采樣點相對加速比從2.92到3.05；IFFT函數(shù)指令級并行化結(jié)果與串行結(jié)果對比顯示各個采樣點相對加速比從2.94到3.08；CZT函數(shù)的指令級并行化結(jié)果與串行結(jié)果對比相對加速比從2.70到2.74。

（2）對窗函數(shù)部分中的巴特利特-漢寧窗、巴特利特窗、切比雪夫窗、高斯窗這四個函數(shù)進行優(yōu)化。在以使用c語言層次的優(yōu)化為主，以使用嵌入?yún)R編為輔的方式下，性能提升比例從9.49%到68.75%。

本文的工作主要基于BWDSP信號處理庫中的變換、窗函數(shù)的性能優(yōu)化，所使用的優(yōu)化方法主要在指令并行級別及編程語言使用技巧上，未曾涉及到算法層次的優(yōu)化。