硬件與軟件對實現非遞歸濾波算法影響的研究

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

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

硬件與軟件對實現非遞歸濾波算法影響的研究

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

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

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

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

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

1 非遞歸型FIR濾波算法及優化方法

1.1 FIR濾波算法

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

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

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

1.2 硬件資源調用

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

表1 寄存器FIR3濾波算法

表2 循環使用寄存器FIR3濾波算法

1.3 級聯FIR濾波算法的優化方法

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

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

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

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

根據離散卷積公式

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

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

圖1 級聯2xFIR3濾波算法的優化方法

2 STxP70專用微處理器與算法轉換

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

2.1 VECx擴展

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

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

2.2 單指令多數據結構（SIMD）算法

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

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

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

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

3 實驗分析與評估

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

3.1 CatapultC實驗結果與分析

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

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

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

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

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

等效替代的SP Rot版與FIFO的SP Rot版相比，面積和能耗都節省14%。最后，SP Rot版比3xSP Reg優勢明顯。

3.2 STxP70實驗結果分析

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

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

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

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

從表3中可以看出，在執行時間方面，FIR3與FIR5，Catapult C是STxP70微處理器的2.95倍、3.87倍。在能耗方面相差61倍與50倍。但是STxP70微處理器讓設計者重復使用碼可，提高設計靈活性。

4 結 論

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

[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實現方法[J].現代電子技術，2010，33（22）:64-67.

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

[11]趙岸，顏毅華，陳林杰，等.基于FPGA的高速FIR數字濾波器設計的改進方法[J].天文研究與技術，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技術與向量數學庫研究[J].計算機科學，2011，38（7）:298-301.

[15]鄧豹，劉照青.基于AltiVec技術的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，France；3.Laboratiore d’Informatique de Paris，Pierre et Marie Curie University，Jussieu 75006，France）

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

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

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