馬麗萍， 張驍煜， 白雨鑫， 陳 鑫， 張 穎

(南京航空航天大學 電子信息工程學院，南京 210016)

目前, 移動設備的計算需求越來越多地側重在音視頻處理、模式識別及數(shù)據(jù)挖掘等方面.這些應用場景都具備一個共同特征, 最終結果無需是一個精確值，只需產(chǎn)生一個能夠滿足需求的近似結果即可.在圖像處理中，一定的銳度損失或分辨率損失在人眼看來都是可接受的, 因而這類系統(tǒng)能容忍在一定范圍內的誤差[1].針對這些應用場景的芯片設計可以通過人為引入誤差來降低電路的復雜度，進而提升芯片的其他性能.

快速Fourier變換 (FFT) 處理器是數(shù)字信號處理系統(tǒng)中必不可少的模塊之一[2]，有關高速與高精度FFT處理器的研究已進入了相對成熟的狀態(tài)[3-5]，而近似FFT處理器的相關研究仍處在起步階段.文獻[6]將電壓縮放調節(jié)技術應用于FFT處理器，并通過窮舉法選取了FFT處理器中最優(yōu)的近似加法器及近似乘法器類型，但是這種設計缺乏理論上的分析論證，沒有充分利用FFT算法的容錯特性.同時，對基本近似計算單元的建模會消耗大量時間，具有一定的局限性.文獻[7]討論了FFT計算中削減每一級數(shù)據(jù)處理位寬的近似方式，同時給出了多種FFT處理器結構在不同精度需求下各級數(shù)據(jù)處理位寬的最優(yōu)配置，但是無法進行精度動態(tài)調整, 只適用于特定的場景.

在不同的應用場景下，F(xiàn)FT處理器對于精度、性能與功耗的需求都有一定的差別，精度可調的FFT處理器能夠根據(jù)不同場景的需求動態(tài)調節(jié)處理器的精度、性能和功耗，具有很強的實際應用價值.圖片處理中，在進行圖片預覽時，采用近似程度較大的模式，快速得到圖片的整體信息而不追求精確的細節(jié)；需要查看原圖時，就需要調整至精確模式；對于存儲空間有限或者功耗有限制時，就需要多種近似模式來滿足不同的需求，獲取不同精確程度的信息，從而實現(xiàn)功耗和速度的最優(yōu)，且相比于采用多個只能用于固定場景的FFT處理器，精度動態(tài)可調FFT的面積開銷最小.因此，本文以512點基23單路徑延時反饋(SDF) FFT處理器作為設計目標.精度可調FFT處理器可工作在精確計算模式與4種近似計算模式下，可實現(xiàn)精度、速度、功耗的動態(tài)調節(jié).所提設計基于180 nm互補金屬氧化物半導體 (CMOS)技術實現(xiàn)，通過專業(yè)電子自動化設計(EDA)工具評估性能，相對于精確模式，處理器在近似模式下的最高工作頻率提升約14.33%；工作頻率為60 MHz時，功耗降低約15.61%.本文提出了一種基于近似計算的精度可調FFT處理器設計思路，證明所提出的設計具有良好的實用價值.

1 精度可調FFT處理器設計

假設x[n]為時域中長度為N的序列(n為每個元素的序號，0≤n≤N-1)，其離散Fourier變換的定義形式如下式所示：

(1)

式中：X[k]為變換域中一個長度為N的序列；k為每個元素的序號.常用記號WN的表達式可以表示為

WN=e-j2π/N

(2)

則將WN代入式(1)后，可改寫為

(3)

若長度為N的序列滿足N=2l，其中l(wèi)為3的倍數(shù)，即長度N為8的冪，則可以將經(jīng)過變換后的X[k]按照先后順序分為8個子序列，定義為Xm[k]，其中m為子序列的序號，0≤m≤7.xm[n]為Xm[k]變換前的序列.按頻率抽取的基23FFT算法流圖與硬件結構實現(xiàn)的對照圖如圖1所示.

圖1 按頻率抽取的基23 FFT算法Fig.1 Decimation in frequency radix-23 FFT algorithm

精度動態(tài)可調FFT處理器的整體硬件結構中共需9個蝶形計算單元，2個非常系數(shù)復數(shù)乘法器和6個常系數(shù)乘法器.其中：本文在蝶形節(jié)點和旋轉因子乘法節(jié)點上分別提出了一種截斷進位鏈的可配置近似蝶形計算單元和一種位寬可調的乘法模塊，在此基礎上完成了精度動態(tài)可調FFT處理器的設計.

1.1 可配置近似蝶形計算單元

對于L位二進制加法，若A與B為加法的兩個加數(shù)，Cin為加法的進位輸入.則加法中的傳播信號和生成信號可以表示為

(4)

式中：0≤i≤L-1；ai為A的第i位；bi為B的第i位；pi為加法第i位的傳播信號；gi為加法第i位的生成信號.

精確加法的邏輯表達式可表示為

(5)

式中：si,e為第i位的精確和；ci,e為第i位產(chǎn)生的精確進位信號.

隨著輸入信號位寬的增加，精確加法器的關鍵路徑為加法器的進位鏈.截斷進位的近似加法將某一位的進位輸出信號截斷，減少關鍵路徑的長度和降低翻轉率.本文采用預測進位的截斷進位加法邏輯為

si,a=pi+ci-1,ci,a=gi

(6)

式中：si,a為第i位的近似和；ci,a為第i位產(chǎn)生的近似進位信號.

通過比較可知，式(5)和(6)具有相同的部分，因此，本文設計一種可配置近似蝶形計算單元，通過雙路選擇器使其可工作在精確及近似兩種模式，其邏輯表達為

(7)

此外，F(xiàn)FT處理器中的定點數(shù)都是以二進制補碼的形式存儲與計算的，當式(6)中的近似加法應用于二進制補碼計算時，可能因截斷進位而引起符號位的錯誤.經(jīng)分析得，符號位發(fā)生錯誤只在A與B符號相反，且正數(shù)的絕對值大于或等于負數(shù)的絕對值時發(fā)生的.因此通過引入符號糾錯單元，解決近似蝶形計算單元符號位發(fā)生錯誤的問題.其邏輯表達式為

(8)

1.2 位寬可調的乘法模塊

由旋轉因子近似計算分析可知，旋轉因子量化至14位即可認為是精確計算的結果，而蝶形模塊的計算結果均為16位，因此本文設計的是 16×14位乘法器.

復數(shù)乘法器用于實現(xiàn)復數(shù)乘法.為了提高乘法器的工作頻率，本文設計的乘法器采用流水線結構.第1級流水采用Booth編碼生成部分積并完成部分積壓縮，第2級流水進行加法與截位操作.

由于FFT的數(shù)據(jù)位寬是16位，乘法器得到的結果為30位，需要將結果截去14位.旋轉因子的實部與虛部范圍均在[-1, 1]之間，所以乘法器的結果不會大于被乘數(shù)的大小，據(jù)此可知乘法器輸出數(shù)據(jù)的符號位后兩位必與符號位相同.根據(jù)這一特性，可選擇截去乘法器符號位的后兩位及低12位的數(shù)據(jù)，并且在截去低12位數(shù)據(jù)時將數(shù)據(jù)進行四舍五入以降低誤差.

值得指出的是，由Booth算法可知，若想通過將乘數(shù)低z位復位為0的方式減少部分積，則z為 [0,8] 之間的偶數(shù).

改革開放釋放了科研設計院所和科技人員的所有潛力，也釋放了人的生產(chǎn)力，將設計成果推到了產(chǎn)業(yè)發(fā)展的第一線。市場經(jīng)濟的規(guī)律，對設計提出了更高的要求。產(chǎn)品設計不僅要解決工程設計的結構、功能等問題，還要解決其形態(tài)、色彩、造型等問題。中國的設計發(fā)展要在產(chǎn)品與商品、生產(chǎn)與市場、科技與文化之間重新找到平衡點，才能走得更遠。因此，中國的工業(yè)設計應運而生。

2 基23 FFT的近似計算分析

通過MATLAB搭建誤差分析平臺，以量化信噪比(SQNR)作為指標[7-8]，評估在不同節(jié)點進行近似計算對FFT運算的影響.

2.1 蝶形計算節(jié)點的近似計算分析

將近似FFT模塊中的9個蝶形單元視作9個計算節(jié)點，第1級蝶形為節(jié)點1，依次類推.對其中1個蝶形節(jié)點進行近似計算，剩余8個蝶形節(jié)點采用精確計算，從而分析每個蝶形節(jié)點對最終輸出結果的影響.分別對蝶形節(jié)點1～9中的第j位采用式(3)的近似運算，在誤差分析平臺對9個蝶形節(jié)點采用近似計算后FFT輸出的SQNR如圖2所示.其中：Ssqnr為FFT的輸出的SQNR.

圖2 單節(jié)點近似蝶形的SQNRFig.2 SQNR of single approximate butterfly node

基于分析的結果，可得出以下結論：

(1) 近似計算位j越接近高位，引入的平均誤差就越大.FFT位置越靠前的蝶形節(jié)點對誤差的容忍度越高.

(2) 每一個蝶形節(jié)點都存在一個閾值jth，當j小于jth時，近似計算對最終結果產(chǎn)生的影響非常小.從蝶形節(jié)點1～9各個節(jié)點jth排列為(4, 3, 3, 3, 2, 2, 1, 1, 0).

根據(jù)MATLAB誤差分析結果可知，蝶形節(jié)點9對輸出結果的影響最大，因此在對9個蝶形節(jié)點進行近似設計時應該從后向前考慮，首先確定蝶形節(jié)點9的j值，再依次決定靠前蝶形節(jié)點的j值.當某一蝶形節(jié)點的jth大于蝶形節(jié)點9的j值時，選取jth作為該蝶形節(jié)點第j位的截斷進位值；當該蝶形節(jié)點的jth小于蝶形節(jié)點9的j值時，考慮到蝶形節(jié)點9會截取該蝶形節(jié)點所保留的位寬，保留更多的位寬不會帶來精度上非常明顯的提高，所以選取蝶形節(jié)點9的j值作為該節(jié)點的j值.遵循這種思路，可以獲得蝶形節(jié)點9的j值從0～7變化時所有蝶形節(jié)點的j值，如表1所示.

表1 512點FFT近似蝶形配置Tab.1 Approximate butterfly configuration of 512 FFT

通過MATLAB對上述配置仿真得到的FFT輸出精度如圖3所示，其中：j9為蝶形節(jié)點9的j值.當?shù)喂?jié)點9的j值逐漸增大時，SQNR仍然呈線性下降，蝶形節(jié)點9的j值每增加1，輸出結果的SQNR下降約6 dB.

圖3 蝶形計算不同近似配置下的精度Fig.3 Accuracy of butterfly computation at different configurations

2.2 旋轉因子乘法節(jié)點的近似計算分析

在512點基23FFT計算中共有8次旋轉因子乘法，將這8次旋轉因子乘法按先后順序分別視作乘法節(jié)點1～8，則8個乘法節(jié)點的旋轉因子范圍如表2所示.

表2 各個乘法節(jié)點的旋轉因子范圍Tab.2 Rotation factor ranges of each multiplication node

乘法節(jié)點3與6的旋轉因子采用對低于量化后最低位的數(shù)據(jù)進行四舍五入的量化方式.經(jīng)過仿真驗證發(fā)現(xiàn)，旋轉因子乘法中每個節(jié)點對最終結果的影響程度是基本相同的.且當旋轉因子量化至14位定點數(shù)時即可認為是精確計算，因此可對每個節(jié)點進行同樣大小的位寬縮減.將乘法節(jié)點3與6的旋轉因子位寬同時從16位縮減至6位時輸出結果的SQNR如圖4所示，其中：w為乘法節(jié)點3與6的旋轉因子位寬.

圖4 同時調整乘法節(jié)點3與6時的SQNRFig.4 SQNR of adjusting multiplication nodes 3 and 6

2.3 兩類節(jié)點同時近似計算的效果

現(xiàn)考慮對蝶形節(jié)點與旋轉因子乘法節(jié)點這同時采用近似計算，圖5為兩類節(jié)點同時近似計算時輸出結果的SQNR，9個蝶形計算單元采用表1中節(jié)點9的j值從1～6的近似配置，旋轉因子乘法節(jié)點3與節(jié)點6的量化位寬w范圍為6～14位.

圖5 兩類節(jié)點同時近似模式的SQNRFig.5 SQNR of two types of nodes with approximate modes

由分析結果可知，當節(jié)點9的j值較小時，SQNR的變化趨勢與精確蝶形運算的結果基本相同.當節(jié)點9取較大j值時，由于蝶形節(jié)點的近似計算已經(jīng)引入了較大誤差，縮減旋轉因子位寬對輸出結果的SQNR的影響已變得不明顯.

2.4 精度可調FFT處理器的近似方案選擇

近似蝶形模塊的近似計算主要影響蝶形計算單元的延時，即FFT處理器的最大工作頻率，而位寬可調的乘法模塊的近似計算主要影響16×14位乘法器的功耗，即主要影響FFT處理器的功耗.QPDP為精度歸一化后的功耗延時積，根據(jù)QPDP可評估不同配置的近似效果，可表示為

(9)

式中：tbf為蝶形計算單元的延時；Pmul為16×14位乘法器的功耗.

由圖3和5中的數(shù)據(jù)可得出，SQNR大于35 dB的16種配置方案的QPDP，在近似方案中有13種近似配置的QPDP小于精確配置，將QPDP優(yōu)于精確配置的13種方案的SQNR分為55±3、50±3、45±3、40±3 dB這4個區(qū)間，在4個區(qū)間中分別選取QPDP最小的配置作為精度可調FFT處理器的近似計算模式.精度可調FFT處理器的5種計算模式如表3所示，其中：wmul為乘法位寬.

表3 FFT處理器的5種計算模式Tab.3 Five computation modes of FFT processer

3 實現(xiàn)與驗證

3.1 功能仿真

功能仿真驗證平臺的結構如圖6所示.將FFT處理器的輸入設置為范圍在[-1, 1]中的隨機數(shù)，利用MATLAB的軟件計算結果及ModelSim軟件中的硬件計算結果計算FFT處理器在5種模式下輸出的SQNR，結果與MATLAB誤差仿真平臺結果的SQNR基本一致，符合設計預期.

圖6 功能仿真驗證平臺Fig.6 Function simulation verification platform

3.2 后端實現(xiàn)

最終采用臺積電TSMC 180 nm CMOS工藝基于超大規(guī)模數(shù)字集成電路標準設計流程對FFT處理器完成后端實現(xiàn)，設計中的隨機存取存儲器(RAM)與ROM采用ARM Artisan公司的知識產(chǎn)權(IP)核.

最終通過設計規(guī)則檢查和版圖與原理圖一致性檢查的芯片版圖如圖7所示，尺寸為 1.44 mm×1.44 mm，面積為2.07 mm2.為了進一步獲取電路設計的功耗信息，本文基于超大規(guī)模數(shù)字集成電路功耗評估的標準流程，結合Synopsys VCS仿真后的翻轉率文件，Synopsys ICC的布局布線后所抽取的寄生參數(shù)，在Synopsys PT中獲取功耗評估結果.

圖7 精度可調FFT處理器芯片版圖Fig.7 Chip layout of accuracy configurable FFT processor

3.3 性能比較

由于不同 FFT 處理器的最大處理點數(shù)、實現(xiàn)工藝及電壓等參數(shù)均不相同，因此需要將參數(shù)歸一化后對比.FFT處理器的歸一化計算時間tnm、能耗Enm及面積Anm的計算方法為[9]

(10)

(11)

(12)

式中：P為處理器的功耗；tcyc為完成一輪FFT計算所需的時間；M為數(shù)據(jù)的通路；U為芯片的電壓；A為芯片面積；Y為最大計算點數(shù)；τ為處理器所用工藝.

精度可調FFT處理器與已發(fā)表精確FFT處理器的對比結果如表5所示.在近似模式3下處理器的最大工作頻率提升約14.33%，當工作頻率為 60 MHz 時，功耗降低約15.61%.其余3個近似模式的功耗平均降低了約9%.

精度可調FFT處理器分別針對乘法器與蝶形計算單元進行了優(yōu)化，因此面積相較其余3種處理器均具有一定優(yōu)勢.文獻[8]與[10]采用的數(shù)據(jù)處理位寬分別為10位與8位，使得計算單元的關鍵路徑長度小于精度可調FFT處理器，因此具有更高的最大工作頻率.

文獻[9]與精度可調FFT處理器采用相同的16位數(shù)據(jù)處理位寬，在近似模式3下精度可調FFT處理器的最大工作頻率相較于文獻[9]增大了17.44%，性能方面有明顯提升.精度可調FFT處理器在計算模式為精確模式、近似模式0、近似模式3時的SQNR分別與文獻[8-10]中處理器的SQNR相近，差值均在3 dB以內，但歸一化后的能耗分別為文獻[8-10]的84.87%、52.96%、65.80%.雖然本文的功耗結果是EDA工具功耗評估獲得的，但是產(chǎn)業(yè)界普遍認為該流程獲得功耗信息在數(shù)量級上是可信的；且經(jīng)過歸一化計算之后，本次提出的FFT處理器在不同近似模式下相比已有的FFT處理器功耗下降均超過15%，因此本設計和其他文獻相比，在能耗方面具有一定優(yōu)勢.

3.4 圖像處理中的驗證

由表5可知，在近似模式3下處理器的SQNR降低了約31.9%，其余3個近似模式的SQNR分別降低了9%、15.6%、17.17%.本小節(jié)將精度可調FFT處理器應用于圖像的頻率域處理中來驗證處理器在實際應用中的表現(xiàn)，使用Butterworth高通濾波器對圖像進行平滑處理的結果如圖8所示.其中：Qssim為圖形結構相似性.

表5 不同F(xiàn)FT處理器對比結果Tab.5 Comparison of different FFT processors

圖8 圖像平滑處理結果Fig.8 Results of image smoothing

圖像結構相似性(SSIM)能夠有效地衡量兩幅圖像的相似度，通常用于評估圖像的失真程度，其取值范圍為0～1.Qssim越大表示失真程度越小，當Qssim為1時，表示兩張圖像完全相同.

FFT處理器在4種近似模式下圖像平滑后的圖像結構相似性的Qssim均大于0.95.在近似模式0的場景下，圖像質量是最好的，功耗相對于精確模式略有下降；近似模式1與近似模式0處理后圖像與精確模式處理后圖像無明顯差別，但是最大工作頻率有所提高，提高了數(shù)據(jù)吞吐率；近似模式2最大工作頻率進一步提高，但是圖像清晰度也略有下降；近似模式3下，圖像質量進一步下降，但是工作率達到最大且功耗降到最低，比較適用于“圖像預覽”這樣的工作場景，不需要非常清晰的畫質，但是需要低功耗以及較大的吞吐量.

近似模式2與近似模式3處理后的圖像存在一定的畫質劣化，但仍可清晰分辨出圖像內容，說明處理器的所有計算模式在圖像平滑時有較好的表現(xiàn)，具有良好的實用價值.

4 結語

本文在國內外近似電路的現(xiàn)有研究進展基礎上提出了一種基于近似計算的精度可調FFT處理器.通過對FFT算法進行建模仿真確定了FFT的容錯特性，在此基礎上將近似加法器及可調節(jié)位寬的乘法器應用在FFT處理器的設計中，并根據(jù)性能與精度等參數(shù)的對比確定了FFT處理器的計算模式.精度可調FFT處理器能夠在精確模式及4種近似模式下切換，實現(xiàn)精度、速度與功耗的動態(tài)調整，從而滿足不同場景的需求.將精度可調FFT處理器應用于圖像邊緣提取及圖像平滑處理中，處理結果表明在近似程度最大的計算模式下精度可調FFT處理器的結果仍具有一定的可用性，表明精度動態(tài)可調FFT處理在圖像處理中具有良好的應用前景.由于條件限制，本文設計的性能指標均是通過專業(yè)EDA工具的標準評估流程得到的，未來該設計改進后將盡量進行流片實測.