硬件與軟件對(duì)實(shí)現(xiàn)非遞歸濾波算法影響的研究

葉海雄 ，陶寧蓉 ，王世明 ，Laurent Cabaret，Lionel Lacassagne

（1.上海海洋大學(xué) 工程學(xué)院，上海201306；2.巴黎南大學(xué) 計(jì)算機(jī)學(xué)院，埃松 奧賽91405；3.巴黎皮埃爾和瑪麗居里大學(xué) 計(jì)算機(jī)學(xué)院，巴黎 朱西厄75006）

硬件與軟件對(duì)實(shí)現(xiàn)非遞歸濾波算法影響的研究

葉海雄1,2，陶寧蓉1，王世明1，Laurent Cabaret2，Lionel Lacassagne3

（1.上海海洋大學(xué) 工程學(xué)院，上海201306；2.巴黎南大學(xué) 計(jì)算機(jī)學(xué)院，埃松 奧賽91405；3.巴黎皮埃爾和瑪麗居里大學(xué) 計(jì)算機(jī)學(xué)院，巴黎 朱西厄75006）

以信號(hào)處理中非遞歸型Finite Impulse Response（FIR）濾波器作為研究對(duì)象，針對(duì)硬件電路設(shè)計(jì)中存在的面積、功耗和計(jì)算性能的問題，通過利用Catapult C高層次綜合工具先優(yōu)化單個(gè)FIR濾波，再級(jí)聯(lián)濾波算法的方法以改善濾波的能耗。同時(shí)FIR濾波算法在STxP70專用微處理器中采用單指令多數(shù)據(jù)Single Instruction Multiple Data（SIMD）VECx技術(shù)以加速電路的計(jì)算性能，分析與評(píng)估硬件與軟件對(duì)實(shí)現(xiàn)FIR濾波算法的影響。實(shí)驗(yàn)結(jié)果表明，采用硬件等效替代的方法能使單個(gè)FIR濾波能耗降低6倍，級(jí)聯(lián)濾波能耗降低7倍，滿足了綠色環(huán)保的電路設(shè)計(jì)理念。采用軟件的SIMD技術(shù)可實(shí)現(xiàn)數(shù)據(jù)向量化加速計(jì)算，計(jì)算加速比提高4倍以上。

信號(hào)處理；高層次綜合工具；專用微處理器；SIMD

設(shè)計(jì)大規(guī)模集成電路領(lǐng)域中高層次綜合設(shè)計(jì)方法從算法抽象描述層面到物理行為實(shí)現(xiàn)層面減少中間步驟，在保證電路的性能的前提下能夠縮短產(chǎn)品開發(fā)周期。最新推出的高層次綜合工具的編譯器具備操作展開循環(huán)、軟件流水線和使用多面體模型安排循環(huán)體的時(shí)序等軟件優(yōu)化功能[1]。此外工具還能分析多媒體應(yīng)用領(lǐng)域的計(jì)算機(jī)語義[2]。文獻(xiàn)[3-5]描述了Compann、Paro、MMAlpha等高層次綜合工具使用多面體模型分析并轉(zhuǎn)換循環(huán)體的能力。文獻(xiàn)[6]描述了Array-OL工具操作數(shù)組并生成VHDL語言以快速評(píng)估電路性能。輸入語言為C或C++語言的Catapult C高層次綜合工具[7]，通過浮點(diǎn)型到定點(diǎn)型的轉(zhuǎn)換，接口定義、元器件庫(kù)資源調(diào)用、時(shí)序安排等，最后生成RTL級(jí)VHDL或Verilog硬件語言，利用Design Compiler[8]軟件在門級(jí)層面評(píng)估電路的特征，Scverify軟件能在C語言和VHDL語言上協(xié)同仿真以確保電路功能的準(zhǔn)確性。另外Catapult C工具中間距啟動(dòng)ii值可改變電路特性，ii值越大，表示電路面積大、功耗高。反之亦然。

1 非遞歸型FIR濾波算法及優(yōu)化方法

1.1 FIR濾波算法

非遞歸型FIR濾波器[9-11]在信號(hào)處理、多媒體、圖像處理、模式識(shí)別等方面得到廣泛應(yīng)用。輸入信號(hào)x（k）與沖擊響應(yīng)（系數(shù) bk），階數(shù)為n-1的FIR濾波器的數(shù)學(xué)表達(dá)式如下：

在式（1）中，若系數(shù) bk與數(shù)據(jù) x（n-k）的類型為浮點(diǎn)型，可以保證計(jì)算結(jié)果y（n）精確度，但會(huì)導(dǎo)致硬件電路設(shè)計(jì)的面積和功耗額外開銷。本文假設(shè)編碼位數(shù)長(zhǎng)度足夠并希望計(jì)算的結(jié)果與專用微處理器的結(jié)果作對(duì)比，故采用長(zhǎng)度分別為8位的定點(diǎn)型系數(shù)和數(shù)據(jù)[12]，用Q8表示。式（1）中加入r項(xiàng)以修正由于截取操作帶來的計(jì)算誤差，系數(shù)需要左移8位，即乘以28，最后的結(jié)果y（n）右移8位，即除以28。本文以3個(gè)系數(shù)的濾波為例，其數(shù)學(xué)表達(dá)式展開如下：

式（2）所對(duì)應(yīng)的算法分別為寄存器FIR3濾波算法（Reg版）和循環(huán)使用寄存器FIR3濾波算法（Rot版）。為了防止循環(huán)中邊界溢出，本文采用的濾波器計(jì)數(shù)都從i=2開始。對(duì)于循環(huán)中邊界問題，假設(shè)信號(hào)x（n）是無限信號(hào)的一部分，前兩個(gè)輸出信號(hào)值復(fù)制輸入信號(hào)的值。讀取與寫入數(shù)據(jù)分別在兩個(gè)不同的內(nèi)存中以避免同時(shí)訪問內(nèi)存地址引起沖突。Reg版是指從單門輸入內(nèi)存中讀取數(shù)據(jù)與系數(shù)進(jìn)行乘加運(yùn)算，計(jì)算結(jié)果寫入輸出內(nèi)存。Rot版與Reg版相比，增加了兩個(gè)移位寄存器以保存兩個(gè)數(shù)據(jù)用于下次計(jì)算。

1.2 硬件資源調(diào)用

增加數(shù)據(jù)通路的方法可以增加讀取數(shù)據(jù)量間接提升計(jì)算性能。在Catapult C高層次綜合工具中，可調(diào)用的硬件資源有單門內(nèi)存：做一次FIR3計(jì)算需要3個(gè)時(shí)鐘周期完成數(shù)據(jù)的讀??；雙門內(nèi)存可同時(shí)在內(nèi)存中讀寫數(shù)據(jù)，需要3/2=2個(gè)時(shí)鐘周期完成FIR3數(shù)據(jù)的讀取；3個(gè)交錯(cuò)單門內(nèi)存：可以同時(shí)從3個(gè)單門內(nèi)存分別讀取FIR3的數(shù)據(jù)，做一次計(jì)算只需要1個(gè)時(shí)鐘周期。如果總數(shù)據(jù)量與交錯(cuò)單門內(nèi)存非整數(shù)倍，狀態(tài)機(jī)將被創(chuàng)建以管理和分配內(nèi)存數(shù)據(jù)。該狀態(tài)機(jī)將增大硬件電路面積和功耗。

表1 寄存器FIR3濾波算法

表2 循環(huán)使用寄存器FIR3濾波算法

1.3 級(jí)聯(lián)FIR濾波算法的優(yōu)化方法

單個(gè)濾波器有時(shí)未能完全滿足過濾的要求，級(jí)聯(lián)濾波方法的使用為了進(jìn)一步去除噪聲。級(jí)聯(lián)兩個(gè)非遞歸型濾波器，有以下3種情況:

1）如果兩個(gè)濾波器數(shù)據(jù)相互獨(dú)立，只需要一個(gè)中間內(nèi)存T保存第一個(gè)濾波器所有的計(jì)算結(jié)果并用于第二個(gè)濾波的計(jì)算，如圖1中第一行。

2）兩個(gè)濾波器中間只需加入一個(gè)First In First Out（FIFO）寄存器，如圖1中間行。

3）一個(gè)新的濾波器等效替代兩個(gè)濾波器，如圖1最后一行。

根據(jù)離散卷積公式

如果把式（2）代入式（3）中，可以得到 5個(gè)系數(shù)c0、c1、c2、c3和 c4的值。

從編譯的角度，編譯器能夠合并多個(gè)循環(huán)體，即合并一個(gè)濾波器可以看成合并一個(gè)操作。合并的關(guān)鍵是為了節(jié)約中間內(nèi)存的使用。由式（4）看，兩個(gè)2階的FIR3濾波器串聯(lián)，可以用1個(gè)4階的FIR5濾波器以等效替代。擴(kuò)展到n階與m階FIR濾波器級(jí)聯(lián)，可以得到p階新濾波器，其系數(shù)個(gè)數(shù)為m+n+1。

圖1 級(jí)聯(lián)2xFIR3濾波算法的優(yōu)化方法

2 STxP70專用微處理器與算法轉(zhuǎn)換

STxP70[13]是ST公司自主研發(fā)的具有32位精簡(jiǎn)指令集低功耗專用微處理器。在CMOS 65納米工藝下，最高工作頻率為450兆赫，面積約為40千門。它帶有緊密耦合程序存儲(chǔ)器（TCPM）和緊密耦合數(shù)據(jù)存儲(chǔ)器（TCDM），訪問內(nèi)存延遲時(shí)間可設(shè)置為1、2和10時(shí)鐘周期，還有64/128位矢量擴(kuò)展用于單指令多數(shù)據(jù)流結(jié)構(gòu)（SIMD）[14]等多個(gè)硬件擴(kuò)展模式。

2.1 VECx擴(kuò)展

VECx擴(kuò)展模式是ST公司針對(duì)信號(hào)處理中低功耗多媒體嵌入式應(yīng)用領(lǐng)域設(shè)計(jì)的。它的基本指令有讀取/保存指令、算術(shù)指令、比較指令和混合數(shù)據(jù)指令，還有16位累加指令、求平均值指令等。當(dāng)需要濾波時(shí)，專用指令用于完成16位乘加運(yùn)算、進(jìn)位并輸出8位的計(jì)算結(jié)果：acc16＜--h8 x h8+acc16，y8=（acc16+128） ＞＞ 8，以高效化數(shù)據(jù)計(jì)算，

在CMOS 65納米工藝下，它的最高工作頻率為420兆赫，面積約為190千門，或?yàn)?.42 mm2。直接測(cè)量VECx功耗的任務(wù)是艱巨困難的，結(jié)合ST公司的經(jīng)驗(yàn)數(shù)據(jù)，本文假設(shè)STxP70微處理器與VECx擴(kuò)展的面積的比值與其功耗的比值相關(guān)聯(lián)，即功耗的比值為190/40=4.75倍。

2.2 單指令多數(shù)據(jù)結(jié)構(gòu)（SIMD）算法

本文評(píng)估濾波算法轉(zhuǎn)換在標(biāo)量和SIMD向量版本上的性能。采用K階濾波器，用FIRk表示，k取奇數(shù)，其范圍為1～9。FIRk濾波器標(biāo)量版的算法與高層次綜合的算法相一致。向量化算法采用Motorola公司Altivec[15]的設(shè)計(jì)模式，對(duì)非對(duì)齊的向量進(jìn)行計(jì)算避免因非對(duì)齊訪問造成的性能損失。

在精簡(jiǎn)指令微處理器中，加速計(jì)算性能的難點(diǎn)在于大部分信號(hào)處理算法存在內(nèi)存容量問題。其原因是算術(shù)強(qiáng)度，即計(jì)算操作次數(shù)與訪問內(nèi)存次數(shù)的比值是很弱的，訪問內(nèi)存的延遲時(shí)間在算術(shù)計(jì)算時(shí)間面前常常被隱藏。FIRk濾波器一共需要2k+1次算術(shù)操作和2k+1次訪問內(nèi)存次數(shù)，故算術(shù)強(qiáng)度為1。當(dāng)濾波器的系數(shù)是固定，可在循環(huán)體外預(yù)先讀取系數(shù)，則訪問內(nèi)存次數(shù)縮減到k次，算術(shù)強(qiáng)度為2。但對(duì)系數(shù)的保存需要更多的寄存器可能會(huì)導(dǎo)致編譯器在編譯時(shí)代碼溢出。設(shè)計(jì)模式是針對(duì)因訪問內(nèi)存而引起的低計(jì)算強(qiáng)度的問題而使用的。它能夠重新組織計(jì)算以最大化平行計(jì)算為目的，在寄存器中創(chuàng)建非對(duì)齊向量用于加載操作。

圖2展示了VECx結(jié)構(gòu)：內(nèi)存被劃分為64位的塊（即8小方塊x8位）。當(dāng)從一個(gè)64位塊讀取數(shù)據(jù)，加載指令進(jìn)行8小方塊x8位轉(zhuǎn)換成8小方塊x16位的強(qiáng)行轉(zhuǎn)換。在兩個(gè)加載數(shù)據(jù)的向量寄存器v0與v1。非對(duì)齊向量u1與u2使用SIMD指令VECx_VSHLUIH在v0與v1中計(jì)算。在此之后，只需要計(jì)算寄存器中每個(gè)系數(shù)與數(shù)據(jù)的乘加。在VECx中，2次64位數(shù)據(jù)加載可計(jì)算濾波器的大小最大為FIR9。保存指令的方式與加載指令相反。

圖2 FIRk的SIMD非對(duì)齊向量計(jì)算

3 實(shí)驗(yàn)分析與評(píng)估

為了測(cè)試硬件與軟件算法優(yōu)化方法，實(shí)驗(yàn)在Intel多核CPU 3.2 GHz、Solaris Sun平臺(tái)上，使用ST公司的CMOS 65納米工藝庫(kù)和Synopsys公司Design Compile工具進(jìn)行仿真實(shí)驗(yàn)。得到電路面積、靜態(tài)功耗、動(dòng)態(tài)功耗、時(shí)間等結(jié)果。通過計(jì)算總時(shí)間與總功耗的乘積再除以濾波長(zhǎng)度，得到單位能耗，用cpp表示。

3.1 CatapultC實(shí)驗(yàn)結(jié)果與分析

圖表3、4的實(shí)驗(yàn)條件是在工作頻率為200兆赫到800兆赫下，每200兆赫采樣并顯示平均值。ST公司相同工藝的1024x8字節(jié)的內(nèi)存的面積為15 000μm2，能耗為14 pJ/point。換而言之，一個(gè)內(nèi)存的面積2倍大于濾波器本身的面積。這也是取消級(jí)聯(lián)濾波器中間內(nèi)存的原因所在。

圖3 單個(gè)FIR3濾波、2xFIR3與FIR5的面積

圖4 單個(gè)FIR3濾波、2xFIR3與FIR5的能耗

算法版本編號(hào)為1-4所對(duì)應(yīng)的版本為SP+Reg、DP+Reg、3xSP+Reg、SP+Rot。

從圖3、4中可以看出，單個(gè)FIR3濾波器下，相比Reg算法，SP Rot和3xSP Reg算法在能耗方面優(yōu)勢(shì)明顯。Rot算法采用移位操作且間距啟動(dòng)值ii為1，使能耗節(jié)省5.87倍，而為此付出是是面積只增大19%。2xFIR3在FIFO寄存器濾波下，調(diào)用硬件資源的方式，3個(gè)交錯(cuò)內(nèi)存能使能耗降低3.61倍。而軟件Rot版能在此基礎(chǔ)上，再節(jié)省1.5倍，總共節(jié)省5.55倍，而面積增加58%。FIR5濾波下，調(diào)用硬件資源的方式，5個(gè)交錯(cuò)內(nèi)存能使能耗降低2.25倍。而軟件Rot版能在此基礎(chǔ)上，再節(jié)省1.75倍，總共節(jié)省6.39倍，而面積增加47%。

等效替代的SP Rot版與FIFO的SP Rot版相比，面積和能耗都節(jié)省14%。最后，SP Rot版比3xSP Reg優(yōu)勢(shì)明顯。

3.2 STxP70實(shí)驗(yàn)結(jié)果分析

圖5 標(biāo)量版非遞歸型FIR濾波器的性能

圖6 向量版非遞歸型FIR濾波器的性能

圖5、6顯示了非遞歸FIR濾波器在STxP70的標(biāo)量和向量版上的性能。比較所有標(biāo)量版，當(dāng)TCDM為1個(gè)時(shí)鐘周期，即內(nèi)存讀取數(shù)據(jù)速度短，Rot版比Reg版速度快30%；當(dāng)內(nèi)存為2個(gè)時(shí)鐘周期，Rot版比Reg版速度快一倍；當(dāng)內(nèi)存為10個(gè)時(shí)鐘周期，Reg版速度一直較慢。比較所有向量版，當(dāng)內(nèi)存為1個(gè)時(shí)鐘周期，Reg版比Rot版的速度更快，因?yàn)樵赗ot算法中從一個(gè)寄存器中復(fù)制數(shù)據(jù)到另一個(gè)寄存器的時(shí)間開銷很長(zhǎng)；當(dāng)內(nèi)存為2個(gè)時(shí)鐘周期，Rot版比Reg版速度快20%以上；當(dāng)內(nèi)存為10個(gè)時(shí)鐘周期，Rot版與Reg版速度相近。相比Rot標(biāo)量版與SIMD版，它們的比值取決于內(nèi)存速度。當(dāng)TCDM為1個(gè)時(shí)鐘周期，F(xiàn)IR3、FIR5的標(biāo)量版與SIMD版的比值分別為5.4和4.69。當(dāng)內(nèi)存為10個(gè)時(shí)鐘周期，比值分別為7.4和7.0。當(dāng)內(nèi)存為1個(gè)時(shí)鐘周期中，VECx中的計(jì)算非對(duì)齊寄存器混合指令丟失加速度的現(xiàn)象是不可忽略的。

表3 在執(zhí)行時(shí)間和能耗上比較算法在Catapult C與STxP70影響

從表3中可以看出，在執(zhí)行時(shí)間方面，F(xiàn)IR3與FIR5，Catapult C是STxP70微處理器的2.95倍、3.87倍。在能耗方面相差61倍與50倍。但是STxP70微處理器讓設(shè)計(jì)者重復(fù)使用碼可，提高設(shè)計(jì)靈活性。

4 結(jié) 論

文中針對(duì)非遞歸型FIR濾波器，基于Catapult C與STxP70微處理器，研究了不同版本的算法以評(píng)估算法優(yōu)化對(duì)ASIC設(shè)計(jì)能耗的影響和算法轉(zhuǎn)換對(duì)微處理器性能的影響。實(shí)驗(yàn)表明，通過算法優(yōu)化與算法轉(zhuǎn)換，電路在能耗和性能方面有顯著提高，達(dá)到了綠色環(huán)保設(shè)計(jì)效果。下一步工作將采用元函數(shù)的宏定義，通過先手工、后讓編譯器自動(dòng)轉(zhuǎn)換信號(hào)處理中硬件與軟件算法以提高電路設(shè)計(jì)效率。

[1]Kennedy K，Allen J R.Optimizing compilers for modern architectures:a dependence-based approach[M].Optimizing compilers for modern architectures:Morgan Kaufmann Publishers，2002.

[2]Beux S L，Moss L，Marquet P，et al.A high level synthesis flow using model driven engineering[M].Algorithm-Architecture Matching for Signal and Image Processing.Springer Netherlands，2011.

[3]Stefanov T，Zissulescu C，Turjan A，et al.System design using Khan process networks:the Compaan/Laura approach[J].2004（1）:340-345.

[4]Bednara M，Teich，J&#，rgen.Automatic synthesis of FPGA processor arrays from loop algorithms[J].Journal of Supercomputing，2003，26（2）:149-165.

[5]Mozipo A，Massicotte D，Quinton P，et al.Automatic synthesis of parallel architecture for kalman filtering using MMAlpha[C]//International Conference on Parallel Computing in Electrical Engineering.1998:1081-1083.

[6]Amar A，Boulet P，Dumont P.Projection of the Array-OL specification language onto the Kahn process network computation model[J].Proceedings of the International Symposium on Parallel Architectures，Algorithmsand Networks，ISPAN，2006（5）:496-503.

[7]Fingeroff M.High-Level Synthesis Blue Book[M].Xlibris Corporation，2010.

[8] Сурков А В，Surkov A V.Synthesis of burstmode asynchronous schemes using Synopsys Design Compiler[J].2014，44:24-30.

[9]徐遠(yuǎn)澤，戴立新，高曉蓉，等.FIR濾波器的FPGA實(shí)現(xiàn)方法[J].現(xiàn)代電子技術(shù)，2010，33（22）:64-67.

[10]李偉，武鵬飛，陳宏霖.基于DSP Builder的分布式算法的FIR數(shù)字低通濾波器設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2015（s2）:335-338.

[11]趙岸，顏毅華，陳林杰，等.基于FPGA的高速FIR數(shù)字濾波器設(shè)計(jì)的改進(jìn)方法[J].天文研究與技術(shù)，2015，12（1）:109-116.

[12]Menard D，Serizel R，Rocher R，et al.Accuracy constraint determination in fixed-point system design[J].Eurasip Journal on Embedded Systems，2008（1）:1-12.

[13]Janin Y，Bertin V，Chauvet H，et al.Designing tightly-coupled extension units for the STxP70 processor[J].2013（1）:1052-1053.

[14]解慶春，張?jiān)迫蹩?，?SIMD技術(shù)與向量數(shù)學(xué)庫(kù)研究[J].計(jì)算機(jī)科學(xué)，2011，38（7）:298-301.

[15]鄧豹，劉照青.基于AltiVec技術(shù)的PowerPC處理器矢量運(yùn)算性能測(cè)試[J].計(jì)算機(jī)測(cè)量與控制，2015，23（6）:2113-2115.

Research on the hardware and software impact on the non-recursive FIR filter algorithm implementation

YE Hai-xiong1，2，TAO Ning-rong1，WANG Shi-ming1，Laurent Cabaret2，Lionel Lacassagne3
（1.School of Engineering Science and Technology，Shanghai Ocean University，Shanghai 201306，China；2.Laboratire Recherche d’informatique，Paris Sud University，Orsay 91405，F(xiàn)rance；3.Laboratiore d’Informatique de Paris，Pierre et Marie Curie University，Jussieu 75006，F(xiàn)rance）

This paper discussed the non-recursive FIR filter in signal processing，the face to the problems on area，power consumption of the electronic circuit.Through the use of Catapult C High-Level synthesis tool,we optimized a single non-recursive FIR filter algorithm,then cascade filter algorithm,in order to achieve improving the energy consumption.Through the use of dedicated microprocessor STxP70,we used the SIMD VECx technique to improve the computing performance.Finally we analyzed and evaluated the impacts of the FIR filter algorithms implementation.The experimental results showed the optimizations algorithms are very efficient,it can be reduced 6 times for the single filter and 7 times for the fusion filter on energy consumption.The circuit is ecologic.And software optimizations algorithms with SIMD technique can be increased 4 times for the computation acceleration.

signal processing； high-level synthesis tool；microprocessor；SIMD

TN4

A

1674－6236（2017）16-0001-05

2016-09-25稿件編號(hào)：201609227

國(guó)家自然科學(xué)基金項(xiàng)目（71501125）；上海市青年教師高校新進(jìn)教師培訓(xùn)及科研啟動(dòng)基金(ZZHY14033)；上海海洋大學(xué)博士科研啟動(dòng)基金（2030214300082）

葉海雄（1982—），男，浙江萬象人，博士，講師。研究方向：信號(hào)、圖像處理、嵌入式系統(tǒng)、ASIC和SOC。