顧志威，李　麗，傅傳張，傅玉祥，李　偉

（南京大學(xué)電子科學(xué)與工程學(xué)院，南京210093）

電路設(shè)計(jì)

FIR算法在可重構(gòu)專用處理器中的并行化實(shí)現(xiàn)*

顧志威，李麗，傅傳張，傅玉祥，李偉

（南京大學(xué)電子科學(xué)與工程學(xué)院，南京210093）

基于FIR算法在數(shù)字信號處理系統(tǒng)中的重要性以及當(dāng)前對于高性能實(shí)時(shí)處理的需求，在一款可重構(gòu)專用處理器平臺上實(shí)現(xiàn)了FIR算法的并行化。并且對傳統(tǒng)的直接型乘累加器進(jìn)行了改進(jìn)，提出了一種效率更高、延時(shí)更低的乘累加器，提高了FIR算法的性能。實(shí)驗(yàn)結(jié)果表明，設(shè)計(jì)的并行FIR濾波器誤差在10-8量級，對大于1 k點(diǎn)的FIR運(yùn)算并行化效率達(dá)95%以上，加速比達(dá)3.85以上。

FIR；并行化；乘累加器；乒乓操作

1　引言

現(xiàn)代電子計(jì)算機(jī)和信息技術(shù)的迅猛發(fā)展，帶動(dòng)了一系列相關(guān)產(chǎn)業(yè)的出現(xiàn)和發(fā)展，數(shù)字信號處理技術(shù)就是其中之一，至今已經(jīng)在通信、語音、圖像等領(lǐng)域取得了極為廣泛的應(yīng)用。有限脈沖響應(yīng)（Finite Impulse Response，F(xiàn)IR）數(shù)字濾波器作為數(shù)字信號處理的基本模塊之一，其性能的優(yōu)劣直接影響到數(shù)字信號處理系統(tǒng)的實(shí)時(shí)處理能力。如何優(yōu)化FIR數(shù)字濾波器的性能一直是人們研究并關(guān)注的熱點(diǎn)問題。與此同時(shí)，在進(jìn)入21世紀(jì)后，隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)的運(yùn)算量迅速增加，傳統(tǒng)的串行化數(shù)據(jù)運(yùn)算模式已經(jīng)無法滿足越來越龐大的數(shù)據(jù)運(yùn)算量的需求，因此將算法并行化成為了不可避免的發(fā)展趨勢。另一方面，在摩爾定律的作用下，硬件資源成本越來越低，單位面積能夠集成的硬件資源越來越多，這使得通過使用更多的硬件資源來實(shí)現(xiàn)算法并行化成為了可能。

在此之前，有些人已經(jīng)做過相關(guān)的研究工作，例如文獻(xiàn)［1］提出基于CUDA平臺的FIR濾波算法［1］，利用GPU強(qiáng)大的計(jì)算能力，將CUDA用于FIR濾波器輸入輸出關(guān)系計(jì)算，采用矩陣乘法的并行計(jì)算技術(shù)，在GPU上建立了FIR并行計(jì)算模型。文獻(xiàn)［2］在FPGA上實(shí)現(xiàn)了FIR濾波器的并行化［2］，并且提出了基于最小沖擊響應(yīng)系數(shù)按等比例量化的方法，使沖擊響應(yīng)系數(shù)的生成更加準(zhǔn)確和簡單。

本文所實(shí)現(xiàn)的并行FIR濾波器是整個(gè)可重構(gòu)專用處理器的一個(gè)組成部分。文章在第二節(jié)介紹了可重構(gòu)專用處理器，第三節(jié)介紹了FIR濾波算法的基本原理，第四節(jié)介紹了實(shí)現(xiàn)FIR濾波算法并行化的硬件架構(gòu)，第五節(jié)給出了在UVM和FPGA環(huán)境下模擬仿真的結(jié)果，第六節(jié)對全文進(jìn)行了總結(jié)。

2　可重構(gòu)專用處理器

正如引言中所述，人們對高性能計(jì)算的要求越來越高，現(xiàn)有的通用處理器，包括 CPU（Central Processing Unit，中央處理器）和DSP（Digital Signal Processing，數(shù)字信號處理器），雖然可以完成高性能信號處理算法的實(shí)現(xiàn)，但是依然存在一些問題。一方面通用處理器為了實(shí)現(xiàn)通用性，結(jié)構(gòu)較為復(fù)雜，對于很多數(shù)據(jù)密集型運(yùn)算需要付出較大的功耗和面積代價(jià)；另一方面，通用處理器基于指令流執(zhí)行任務(wù)的特點(diǎn)使其在密集型算法實(shí)現(xiàn)上消耗過長的時(shí)間。本文所述的可重構(gòu)專用處理器（以下統(tǒng)一簡稱RASP）的目的在于提供一種基于可重構(gòu)硬件的協(xié)處理器，使用固定的硬件運(yùn)算資源，通過配置信息的改變可實(shí)現(xiàn)不同算法的加速。RASP的核心在于其可重構(gòu)性，通過不同的配置信息改變可重構(gòu)計(jì)算陣列的拓?fù)浣Y(jié)構(gòu)，RASP可以支持多種不同的算法，圖1是RASP的結(jié)構(gòu)示意圖。

圖1　RASP模塊示意圖

RASP主要包括5個(gè)部分，分別是主控制器、重構(gòu)控制器、可重構(gòu)計(jì)算陣列、存儲器和DMA。主控制器用于接收外部通用處理器發(fā)出的控制信息，再對其進(jìn)行解析，并發(fā)出相應(yīng)的配置指令，配置指令包括傳輸參數(shù)與算法參數(shù)。重構(gòu)控制器根據(jù)配置指令中的算法參數(shù)，發(fā)出配置信息，配置信息包括用于選擇和組織運(yùn)算核心單元中的邏輯算法的執(zhí)行信號與內(nèi)部網(wǎng)絡(luò)選通信號。可重構(gòu)計(jì)算陣列接收配置信息，根據(jù)配置信息完成復(fù)乘、復(fù)加、實(shí)乘等基本運(yùn)算。DMA單元，接收配置指令的傳輸參數(shù)，進(jìn)行外部DDR與內(nèi)部存儲模塊、主控制器間的數(shù)據(jù)搬運(yùn)。存儲器，用于存儲運(yùn)算所需的源數(shù)據(jù)和結(jié)果數(shù)據(jù)。

3　FIR算法原理

FIR算法是濾波器中經(jīng)常使用的一種算法，對于N點(diǎn)M階FIR濾波器，假設(shè)濾波系數(shù)為h（i），i=1，2，3，…，M，現(xiàn)有一組輸入信號x（j），j=1，2，3，…，N，那么FIR算法的輸出為：

這里算法的系數(shù)h（i），操作數(shù)x（j）和結(jié)果y（n）都是實(shí)數(shù)。需要注意的是，點(diǎn)數(shù)N不能小于階數(shù)M，否則算法無意義。從FIR算法的公式中可以看出，該算法的核心是乘累加運(yùn)算。同時(shí)也可以看出FIR算法是一種典型的滑窗算法，如果把操作數(shù)x（j）的前后分別補(bǔ)M-1個(gè)0，那么系數(shù)h（i）從左到右共滑動(dòng)N+M-1次即可得到結(jié)果y（n），由此可見，輸出結(jié)果y（n）比輸入的操作數(shù)x（j）多出M-1個(gè)值。

以1024點(diǎn)16階為例，算法過程如圖2所示。

圖2　FIR算法示意圖（1024點(diǎn)16階）

4　基于RASP的FIR濾波器并行化實(shí)現(xiàn)

FIR濾波器有兩個(gè)重要的參數(shù)，分別是該濾波器能夠支持的最大點(diǎn)數(shù)N和階數(shù)M。在并行FIR濾波器中，還有一個(gè)重要參數(shù)是并行路數(shù)Q，圖3描述了Q路并行的FIR濾波器的模塊結(jié)構(gòu)圖。

在不考慮使用乒乓操作的前提下，假設(shè)每個(gè)bank大小為S×32 bit，即每個(gè)bank能夠存儲S個(gè)32位的實(shí)數(shù)，那么，濾波器所能支持的最大點(diǎn)數(shù)N、最大階數(shù)M、并行路數(shù)Q和bank大小S之間有如下定量關(guān)系：

S和Q的乘積代表操作數(shù)bank最多能夠存儲的操作數(shù)個(gè)數(shù)，然而由于每個(gè)bank存儲的數(shù)據(jù)有小部分冗余，上一個(gè)bank最后的M-1個(gè)數(shù)和下一個(gè)bank開頭的M-1個(gè)數(shù)是相同的，另外為了算法的一致性，在第一個(gè)bank開頭和最后一個(gè)bank結(jié)尾均補(bǔ)齊M-1 個(gè)0，這就是公式中被減數(shù)的由來。

圖3　Q路并行FIR濾波器模塊結(jié)構(gòu)圖

在RASP項(xiàng)目中，這些參數(shù)具體表現(xiàn)為最大點(diǎn)數(shù)N=128k，最大階數(shù)M=128，并行路數(shù)Q=16，每個(gè)bank大小S=16k。

當(dāng)所需計(jì)算的點(diǎn)數(shù)正好是并行路數(shù)16的倍數(shù)時(shí)，每一路分擔(dān)的點(diǎn)數(shù)均相同，但是當(dāng)所需計(jì)算的點(diǎn)數(shù)不是16的倍數(shù)時(shí)，需要考慮到多余點(diǎn)數(shù)的分配問題，本設(shè)計(jì)將多余的點(diǎn)數(shù)依次分配到每個(gè)bank中，也就是當(dāng)階數(shù)n不能被16整除時(shí)，若n/16余1，那么把這1點(diǎn)分配到bank1中；若n/16余2，那么把這2點(diǎn)分配到bank1和bank2中；依此類推。

4.1新型乘累加器

傳統(tǒng)的FIR濾波器中，采用的是直接型乘累加結(jié)構(gòu)，圖4為直接型FIR濾波器結(jié)構(gòu)框圖，這種乘累加結(jié)構(gòu)的時(shí)延為Tm+（M-1）Ta，其中M是濾波器階數(shù)，Tm是乘法器時(shí)延，Ta是加法器時(shí)延，因此這種結(jié)構(gòu)的濾波延時(shí)會隨著濾波器階數(shù)的增加而增加。

圖4　直接型FIR濾波器結(jié)構(gòu)框圖

本文設(shè)計(jì)了一種新型的運(yùn)算單元，其結(jié)構(gòu)如圖5所示，該乘累加器由1個(gè)乘法器、2個(gè)加法器和一些控制結(jié)構(gòu)組成，支持單精度浮點(diǎn)數(shù)操作，其中乘法器和加法器的延時(shí)都是4個(gè)周期，累加器由2個(gè)加法器組成。第一個(gè)加法器負(fù)責(zé)累加乘法器的流水結(jié)果，由于加法器有4個(gè)周期的延時(shí)，所以第一個(gè)加法器會多出4個(gè)數(shù)據(jù)無法累加，這4個(gè)數(shù)由第二個(gè)加法器完成累加功能并輸出。該乘累加器可以支持階數(shù)M≥8的乘累加流水操作，其中第一個(gè)數(shù)延時(shí)為2（M+4）個(gè)周期，后續(xù)每個(gè)數(shù)的延時(shí)為M個(gè)周期，結(jié)果數(shù)據(jù)延時(shí)與乘法器和加法器的延時(shí)是無關(guān)的。因此相對于直接型乘累加器，本文設(shè)計(jì)的乘累加器運(yùn)算效率提升了Ta倍，在本例中即為4倍。

圖5　乘累加器結(jié)構(gòu)圖

4.2乒乓操作

前文設(shè)計(jì)的FIR濾波器只進(jìn)行一次數(shù)據(jù)搬運(yùn)（將操作數(shù)搬運(yùn)至bank中）即可得到結(jié)果，這種一次搬運(yùn)的模式會導(dǎo)致FIR濾波器所需的硬件資源與它能支持的最大點(diǎn)數(shù)呈線性關(guān)系。因此，我們有必要考慮可以進(jìn)行多次數(shù)據(jù)搬運(yùn)的情況，換句話說，濾波器的設(shè)計(jì)需要允許將計(jì)算分為多次進(jìn)行。在這種情況下，理論上來說該FIR濾波器就突破了最大點(diǎn)數(shù)的限制，也就是在時(shí)間允許的條件下，它可以支持任意點(diǎn)數(shù)的FIR運(yùn)算。

在實(shí)現(xiàn)濾波器的這一改進(jìn)時(shí)，需要引入乒乓操作的概念。仍舊以前文RASP中的FIR濾波器為例，我們把16個(gè)操作數(shù)bank分成兩組，每組8個(gè)bank；同樣16個(gè)結(jié)果數(shù)bank也分成兩組，每組8個(gè)bank。此時(shí)仍然是16路并行，并且每一路所需運(yùn)算的點(diǎn)數(shù)分配方式和原來相同，差別在于搬數(shù)至bank時(shí)，首先只搬上面8個(gè)bank的操作數(shù)，當(dāng)搬完上面8個(gè)bank的操作數(shù)時(shí)，這8路可以先啟動(dòng)運(yùn)算，在這8路運(yùn)算的同時(shí)，再把下面8路的操作數(shù)搬運(yùn)至bank中，這樣相比于原來16路的搬數(shù)時(shí)間減少了一半，這對于需要進(jìn)行多次搬數(shù)過程（濾波器所進(jìn)行的運(yùn)算點(diǎn)數(shù)遠(yuǎn)大于128k點(diǎn)或者硬件資源有限導(dǎo)致bank數(shù)不到16個(gè)）的FIR運(yùn)算來說，可以節(jié)省的時(shí)間將很可觀。另一方面，乒乓操作的引入可以將運(yùn)算模塊從原來的16個(gè)縮減至8個(gè)，也就是讓兩組bank復(fù)用運(yùn)算單元，一組bank在運(yùn)算，同時(shí)另一組bank在搬數(shù)，任務(wù)結(jié)束之后切換角色，原來在運(yùn)算的bank組進(jìn)行搬數(shù)，原來在搬數(shù)的bank組進(jìn)行運(yùn)算。改進(jìn)后的FIR濾波器硬件架構(gòu)如圖6所示。

圖6　采用乒乓操作的FIR濾波器

5　實(shí)驗(yàn)結(jié)果

本設(shè)計(jì)采用UVM和FPGA兩種驗(yàn)證平臺給出實(shí)驗(yàn)結(jié)果。設(shè)計(jì)采用UVM1.0，編程語言是System Verilog，仿真工具是VCS（Version F-2011.12-SP1），其總體驗(yàn)證環(huán)境的結(jié)構(gòu)圖如圖7所示。

圖7 UVM驗(yàn)證環(huán)境組成示意圖

圖8為UVM驗(yàn)證報(bào)告，隨機(jī)選取了16組點(diǎn)數(shù)與階數(shù)的組合，從圖8中可以看出硬件運(yùn)算結(jié)果與C模型一致。

圖8　UVM驗(yàn)證報(bào)告圖

本設(shè)計(jì)同時(shí)也進(jìn)行了FPGA驗(yàn)證，所使用的驗(yàn)證平臺是 HAPS62開發(fā)板，此開發(fā)板包含兩片Virtex6-760 FPGA。由于RASP占用邏輯資源比較大，一片Vertex6-760 FPGA版中資源不夠，故整個(gè)系統(tǒng)通過Certify軟件劃分成2部分，分別下載到2片F(xiàn)PGA中，按2片F(xiàn)PGA間通信最小的原則劃分，劃分示意圖如圖9所示。

圖9　FPGA劃分示意圖

每片F(xiàn)PGA占用資源如表1所示。

表1　兩片F(xiàn)PGA資源占用比例表

圖10為FIR算法在FPGA平臺下的運(yùn)算平均誤差，選取的點(diǎn)數(shù)固定為1k，從圖中可以看出運(yùn)算誤差隨著階數(shù)的增大而增大，這是由于階數(shù)的增加導(dǎo)致累加誤差增大，但其誤差都維持在10-8數(shù)量級。

圖10　FIR算法平均誤差

在前文中介紹了乘累加器結(jié)構(gòu)，它支持階數(shù)M≥8的乘累加流水操作，其中第一個(gè)結(jié)果數(shù)據(jù)延時(shí)為2 （M+4）個(gè)周期，后續(xù)每個(gè)數(shù)的延時(shí)為M個(gè)周期，因此對于FIR算法，計(jì)算N點(diǎn)M階理論上的運(yùn)算周期為2 （M+4）+（N+M-2）×M。定義算法并行化效率=理論時(shí)間/實(shí)際時(shí)間/并行化路數(shù)，對于本文中的16路并行FIR濾波器，其并行化效率為理論時(shí)間/（16×實(shí)際時(shí)間）。另一方面，為了定量描述新型乘累加器相對于傳統(tǒng)的直接型乘累加器在性能上的提高，定義加速比=采用直接型乘累加器所用時(shí)間/采用新型乘累加器所用時(shí)間。并行化效率和加速比結(jié)果如表2所示。

從表2中可以看出，F(xiàn)IR算法的并行化效率和加速比都隨著點(diǎn)數(shù)的增加而遞增。在點(diǎn)數(shù)較小時(shí)，其并行化效率和加速比處于較低水平，但當(dāng)點(diǎn)數(shù)大于1k時(shí)，其并行化效率達(dá)到95%以上，并逐漸趨近于極限值100%；加速比也達(dá)到3.85以上，并逐漸趨于4，這和4.1小節(jié)中的理論分析結(jié)果一致。出現(xiàn)這種現(xiàn)象的原因在于：當(dāng)點(diǎn)數(shù)較小時(shí)，F(xiàn)IR算法的計(jì)算量很小，這時(shí)并行化過程中的其他時(shí)間花費(fèi)（如確定每一路的點(diǎn)數(shù)分配）與計(jì)算時(shí)間相比不能忽略，導(dǎo)致并行化效率和加速比較低；而隨著點(diǎn)數(shù)的增加，計(jì)算時(shí)間占比越來越大，所以并行化效率和加速比逐漸增加。

表2　FIR算法并行化效率和加速比（階數(shù)M=16）

6　總結(jié)

隨著數(shù)字信號處理技術(shù)的飛速發(fā)展和大數(shù)據(jù)時(shí)代的到來，人們對各種算法的高性能實(shí)時(shí)處理要求越來越高，在這一背景下，本文在可重構(gòu)專用處理器的平臺上實(shí)現(xiàn)了FIR算法的并行化。FIR算法的核心是乘累加操作，然而傳統(tǒng)的直接型乘累加器延時(shí)過高，導(dǎo)致FIR算法運(yùn)行效率低下，本文提出了一種效率更高、延時(shí)更低的新型乘累加器，能有效提高FIR算法的性能。本文在FPGA和UVM兩個(gè)平臺上實(shí)現(xiàn)了模擬仿真，F(xiàn)PGA硬件仿真的結(jié)果給出了FIR濾波器的誤差，UVM軟件仿真的結(jié)果給出了并行化效率和加速比。實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的并行FIR濾波器誤差小，并行化效率高，加速比可觀。文中提及的設(shè)計(jì)思路對同類產(chǎn)品的研發(fā)有一定的參考意義。

［1］郭海鳳，李莉.基于CUDA平臺的FIR濾波算法的設(shè)計(jì)與優(yōu)化［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（3）:102-105，167.

［2］王英喆，王振宇，嚴(yán)偉，時(shí)廣軼.全并行FIR濾波器的FPGA實(shí)現(xiàn)與優(yōu)化［J］.電子設(shè)計(jì)工程，2015，23（22）:94-97.

［3］趙文兵，楊建寧.FIR濾波器的FPGA實(shí)現(xiàn)及其仿真研究［J］.微計(jì)算機(jī)信息，2005，21（7）:108-109.

［4］虞希清.專用集成電路設(shè)計(jì)實(shí)用教程［M］.杭州：浙江大學(xué)出版社，2007:1-4.

［5］Tian J，Li G，Li Q.Hardware-efficient parallel structures for linear-phase FIR digital filter［C］.Circuits and Systems （MWSCAS），2013IEEE56thInternationalMidwest Symposium on.IEEE，2013:995-998.

［6］Tsao Y C，Choi K.Hardware-efficient parallel FIR digital filter structures for symmetric convolutions［C］.Circuits and Systems（ISCAS），2011 IEEE International Symposium on. IEEE，2011:2301-2304.

［7］Tsao Y C，Choi K.Area-efficient parallel FIR digital filter structures for symmetric convolutions based on fast FIR algorithm［J］.Very Large Scale Integration（VLSI）Systems，IEEE Transactions on，2012，20（2）:366-371.

［8］Nikolaos S Voros，等編著.可重構(gòu)片上系統(tǒng)的系統(tǒng)級設(shè)計(jì)System Level Design of Reconfiguable System-on-Chip（影印版）［M］.北京：科學(xué)出版社，2007.

［9］Sudan K，Rajamani K，Huang W，et al.Tiered memory:an iso-power memory architecture to address the memory power wall［J］.Computers，IEEE Transactions on，2012，61 （12）:1697-1710.

［10］Selvakumar J，Bhaskar V，Narendran S.FPGA Based Efficient Fast FIR Algorithm for Higher Oreder Digital FIR Filter［C］.Electronic System Design（ISED），2012 International Symposium on IEEE，2012:43-47.

Parallel FIR Filter Based on Reconfigurable Processor

GU Zhiwei，LI Li，F(xiàn)U Chuanzhang，F(xiàn)U Yuxiang，LI Wei
（School of Electronic Science and Engineering，Nanjing University，Nanjing 210093，China）

The significance of FIR algorithm in digital signal processing system and demand for high-performance real-time processing facilitates the realization of a parallel FIR filter on the reconfigurable processor and a new kind of multiply-accumulator featuring higherefficiency and lower time delay. Experiment shows that the error of the FIR filter is within 10-8and the parallel efficiency reaches 95%and higher for FIR algorithm with over 1k point.

FIR；parallel；multiply-accumulator；ping-pong operation

TN402

A

1681-1070（2016）08-0014-05

2016-5-11

高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目（20120091110029）；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究項(xiàng)目（BY2015069-05）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目（021014380030）。

顧志威（1992—），男，江蘇蘇州人，碩士研究生，研究方向?yàn)榧呻娐吩O(shè)計(jì)。