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

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

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

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

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

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

信號處理；高層次綜合工具；專用微處理器；SIMD

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

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

1.1 FIR濾波算法

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

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

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

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

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

表1 寄存器FIR3濾波算法

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

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

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

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

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

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

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

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

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

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

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

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

2.1 VECx擴展

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

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

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

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

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

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

圖2 FIRk的SIMD非對齊向量計算

3 實驗分析與評估

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

3.1 CatapultC實驗結(jié)果與分析

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

圖3 單個FIR3濾波、2xFIR3與FIR5的面積

圖4 單個FIR3濾波、2xFIR3與FIR5的能耗

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

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

3.2 STxP70實驗結(jié)果分析

圖5 標量版非遞歸型FIR濾波器的性能

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

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

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

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

4 結(jié) 論

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

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

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

[11]趙岸，顏毅華，陳林杰，等.基于FPGA的高速FIR數(shù)字濾波器設(shè)計的改進方法[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]解慶春，張云泉，王可，等.SIMD技術(shù)與向量數(shù)學(xué)庫研究[J].計算機科學(xué)，2011，38（7）:298-301.

[15]鄧豹，劉照青.基于AltiVec技術(shù)的PowerPC處理器矢量運算性能測試[J].計算機測量與控制，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稿件編號：201609227

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

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