高立寧 馬 瀟劉騰飛 吳 金

(北京理工大學(xué)信息與電子學(xué)院 北京 100081)

1 引言

快速傅里葉變換(FFT)在雷達(dá)、數(shù)字通信和圖像處理等科學(xué)技術(shù)領(lǐng)域有著廣泛的應(yīng)用，這使得FFT的工程實(shí)現(xiàn)具有十分重要的意義。隨著現(xiàn)代數(shù)字信號處理技術(shù)的發(fā)展，應(yīng)用系統(tǒng)中對實(shí)現(xiàn)超大點(diǎn)數(shù)FFT的需求越來越高，這也意味著對數(shù)字信號處理器(DSP)的處理性能和內(nèi)存資源都提出了更高的要求和挑戰(zhàn)[1]。

在雷達(dá)系統(tǒng)中，高分辨大測繪帶寬的合成孔徑雷達(dá)的飛速發(fā)展，對信號處理系統(tǒng)中實(shí)現(xiàn)超大點(diǎn)數(shù)FFT提出了更高的要求。然而，超大點(diǎn)數(shù)FFT的實(shí)現(xiàn)對資源的消耗隨著點(diǎn)數(shù)的增加而增大，且對超大點(diǎn)數(shù) FFT的優(yōu)化效率往往和資源開銷的程度直接相關(guān)，這都說明處理器資源已經(jīng)成為制約大點(diǎn)數(shù)FFT實(shí)現(xiàn)的關(guān)鍵因素。因此，如何在節(jié)約現(xiàn)有平臺資源開銷并保證執(zhí)行效率的條件下實(shí)現(xiàn)超大點(diǎn)數(shù)FFT，成為當(dāng)前研究的重要方向。

很多文獻(xiàn)對大點(diǎn)數(shù) FFT的實(shí)現(xiàn)進(jìn)行了深入的研究，對其性能的優(yōu)化主要采用了兩種方式：一種是通過算法的優(yōu)化，使FFT處理更加適合處理器架構(gòu)；另一種是增加系統(tǒng)資源，達(dá)到并行處理。例如，文獻(xiàn)[2,3]中給出了 SingLeton結(jié)構(gòu)實(shí)現(xiàn)定點(diǎn)/浮點(diǎn)FFT的方法，采用該結(jié)構(gòu)對蝶形進(jìn)行重排，使除了第1級外的其它級數(shù)據(jù)都是順序讀取，具有較高運(yùn)算效率，但是這種方法要采用乒乓緩存，浪費(fèi)了一倍的存儲器；文獻(xiàn)[4]采用多片DSP分級并行處理一個(gè)大點(diǎn)數(shù)FFT，將蝶形運(yùn)算分配到多個(gè)DSP分級并行計(jì)算，進(jìn)而提高FFT的執(zhí)行效率，但是該處理方法需要多片DSP并行計(jì)算，造成了資源浪費(fèi)，在實(shí)際工程應(yīng)用中成本較高，且增加了開發(fā)難度；文獻(xiàn)[5]提出了一種基于FPGA的高性能并行FFT處理方案，其采用4個(gè)蝶形運(yùn)算單元進(jìn)行并行處理，優(yōu)化了處理效率，其缺點(diǎn)是增加了4倍的資源消耗；文獻(xiàn)[6]采用Winograd算法將大點(diǎn)數(shù)FFT拆成小點(diǎn)數(shù)進(jìn)行處理，雖然在處理中引入了額外的鉸鏈因子相乘運(yùn)算和3次顯性轉(zhuǎn)置操作，但是該算法能夠有效地降低資源的消耗，能夠在現(xiàn)有平臺上實(shí)現(xiàn)更大點(diǎn)數(shù)的FFT運(yùn)算。

本文針對處理器硬件資源對實(shí)現(xiàn)超大點(diǎn)數(shù)FFT的制約，提出一種優(yōu)化的 Winograd算法實(shí)現(xiàn)超大點(diǎn)數(shù)FFT的方法。相比傳統(tǒng)的Winograd處理方法，該實(shí)現(xiàn)方法通過優(yōu)化鉸鏈因子存儲，改變矩陣訪問方式和限制行列劃分等手段使 FFT處理能夠更好的適應(yīng)處理器的架構(gòu)，使其在現(xiàn)有平臺上可以實(shí)現(xiàn)更大點(diǎn)數(shù)的FFT運(yùn)算。

2 資源優(yōu)化分析

文獻(xiàn)[6]中Winograd算法實(shí)現(xiàn)FFT的主要流程為：(1)將1維序列拆分成2維矩陣并轉(zhuǎn)置；(2)行方向FFT處理；(3)乘以鉸鏈因子；(4)對(3)的結(jié)果轉(zhuǎn)置存儲；(5)列方向FFT處理；(6)將處理結(jié)果轉(zhuǎn)置存儲，得到序列的FFT結(jié)果。該處理算法將大點(diǎn)數(shù)FFT拆成小點(diǎn)數(shù)運(yùn)算，但是該算法在實(shí)現(xiàn)過程中存在兩個(gè)問題：一是引入的鉸鏈因子需要額外的存儲空間，同時(shí)增加了乘法運(yùn)算次數(shù)；二是3次顯性轉(zhuǎn)置需要較多額外的內(nèi)存空間，且存儲轉(zhuǎn)置處理引起的Cache丟失對時(shí)間影響很大。針對上述問題，本節(jié)給出具體的優(yōu)化方案。

2.1 鉸鏈因子存儲優(yōu)化

為了便于說明，這里重設(shè)2維序列N=ML×,M為列數(shù)，L為行數(shù)，并設(shè)1n和0n分別表示時(shí)域行列序號，0k和1k分別表示頻域的行列序號。由文獻(xiàn)[6]中給出的處理步驟可知，在第(3)步時(shí)對行方向FFT的處理結(jié)果乘以鉸鏈因子，其值如式(1)：

由式(1)可推導(dǎo)：

由式(2)可以看出，鉸鏈因子與0n和k兩個(gè)變量有關(guān)，且可以將第k行的鉸鏈因子分解為k個(gè)相乘，因此，在存儲鉸鏈因子時(shí)可以只存儲第1行的鉸鏈因子，而其它行的鉸鏈因子可由第1行的鉸鏈因子計(jì)算得出。雖然采用計(jì)算得出鉸鏈因子會引入新的額外乘法運(yùn)算，但該處理方式可以大大節(jié)省內(nèi)存資源，這對在資源有限的情況下實(shí)現(xiàn)超大點(diǎn)數(shù)FFT十分重要。為了得出新的額外乘法運(yùn)算對超大點(diǎn)數(shù) FFT執(zhí)行效率的影響，下面對該運(yùn)算時(shí)間在FFT總運(yùn)算時(shí)間中所占的比重作進(jìn)一步分析[7]。

Winograd算法實(shí)現(xiàn)FFT運(yùn)算所需運(yùn)算量為

采用節(jié)省內(nèi)存空間的方式存儲鉸鏈因子會額外引入N次乘法運(yùn)算，又由于處理器進(jìn)行乘法運(yùn)算的時(shí)間比加法多得多，因此，如果只考慮FFT計(jì)算時(shí)間與乘法次數(shù)成正比，則新引入的額外乘法運(yùn)算時(shí)間占FFT運(yùn)算時(shí)間的比例為

由柯西不等式可以得

由式(6)和圖1可見，新引入的額外乘法運(yùn)算隨著FFT點(diǎn)數(shù)的增加逐步減小，其對FFT的執(zhí)行效率的影響也在逐漸減低。例如，按照理論分析在256k點(diǎn)時(shí)，額外乘法運(yùn)算只占 FFT乘法總運(yùn)算時(shí)間的18.49%；然而，該處理方法可以節(jié)約的內(nèi)存空間，這為在現(xiàn)有處理器資源不變的情況下實(shí)現(xiàn)更大點(diǎn)數(shù)的FFT提供了可能。

經(jīng)以上推導(dǎo)分析，為了節(jié)省處理器內(nèi)存資源，本文采取只存儲第1行的方法來存儲鉸鏈因子，且由此引入的新的額外乘法運(yùn)算對 FFT執(zhí)行時(shí)間的影響隨點(diǎn)數(shù)的增加而逐漸減?。凰?，對于超大點(diǎn)數(shù)FFT的實(shí)現(xiàn)來說，該部分的時(shí)間開銷可以忽略不計(jì)。

2.2 矩陣訪問優(yōu)化

圖1 隨點(diǎn)數(shù)增加額外乘法運(yùn)算時(shí)間/FFT乘法總運(yùn)算時(shí)間曲線圖

相對于 1維序列的處理，文獻(xiàn)[6]的 Winograd算法將序列映射成2維序列處理，對2維矩陣的行列訪問采用轉(zhuǎn)置成正常順序后連續(xù)讀取的方式，對于FFT處理，該方法引入了3次顯性轉(zhuǎn)置，而轉(zhuǎn)置處理需要大量的額外轉(zhuǎn)置內(nèi)存空間，且矩陣轉(zhuǎn)置會對FFT的執(zhí)行速度產(chǎn)生嚴(yán)重的影響。目前主流DSP處理器都采用分級存儲結(jié)構(gòu)，一級緩存(Cache)會對數(shù)據(jù)進(jìn)行預(yù)處理來協(xié)助對矩陣數(shù)據(jù)的訪問，從而減少直接對DRAM的訪問次數(shù)；當(dāng)數(shù)據(jù)在Cache中命中，可以直接從Cache中讀取所需數(shù)據(jù)，否則需要重新到DRAM中讀取新的數(shù)據(jù)頁面，此時(shí)會引起數(shù)據(jù)訪問時(shí)延[8]。文獻(xiàn)[9]采用變換行列號方式實(shí)現(xiàn)對2維矩陣的訪問，即通過行列號來計(jì)算數(shù)據(jù)首地址和訪問步長，然后進(jìn)行數(shù)據(jù)訪問。但其帶來的問題是，讀取一列數(shù)據(jù)時(shí)，需要每讀一個(gè)數(shù)據(jù)均進(jìn)行行切換，而行切換需要切換時(shí)間；讀取一行數(shù)據(jù)時(shí)，行數(shù)據(jù)不能太長，如果超出一級Cache的容量，在行FFT處理過程中，則會出現(xiàn)因無法從Cache命中數(shù)據(jù)帶來的各種問題。因此，需要通過優(yōu)化行列的拆分規(guī)則來最大發(fā)揮Cache協(xié)助數(shù)據(jù)訪問的特點(diǎn)，實(shí)現(xiàn)對2維矩陣高效訪問。

為了盡量減少行切換，可以在列處理時(shí)一次讀取幾列數(shù)據(jù)，讀取列數(shù)的多少以及每列含數(shù)據(jù)量大小均需要根據(jù)Cache的容納量計(jì)算，以實(shí)現(xiàn)對Cache的充分利用，但要保證讀取列的總數(shù)據(jù)小于 Cache大小，否則在列FFT處理時(shí)會出現(xiàn)Cache頻繁丟失的情況；圖2所示為在進(jìn)行一次列數(shù)據(jù)訪問讀取第i列的數(shù)據(jù)時(shí)，數(shù)據(jù)在Cache中的布局圖。

在行FFT處理時(shí)為了充分利用Cache，只有當(dāng)讀一行的數(shù)據(jù)盡可能填充Cache空間時(shí)才能充分利用Cache的優(yōu)勢來協(xié)助數(shù)據(jù)訪問。矩陣行處理訪問內(nèi)存后數(shù)據(jù)在Cache中分布如圖3所示。

圖2 矩陣列方向訪問后的緩存布局

圖3 矩陣行方向訪問后的緩存布局

由此，采用行列號方式訪問2維矩陣，節(jié)省了額外的轉(zhuǎn)置存儲空間，解決了3次顯性轉(zhuǎn)置引起時(shí)間開銷對FFT執(zhí)行效率影響的問題，并結(jié)合處理器分級存儲的特點(diǎn)對 2維矩陣行列劃分規(guī)則進(jìn)行優(yōu)化，最大限度發(fā)揮Cache的優(yōu)點(diǎn)來提高矩陣訪問速度。

上述兩小節(jié)分別從鉸鏈因子和矩陣轉(zhuǎn)置兩個(gè)方面對資源及效率進(jìn)行優(yōu)化：一是依據(jù)鉸鏈因子的規(guī)律，采取減少存儲鉸鏈因子的數(shù)據(jù)量來節(jié)省內(nèi)存空間，該方法引入了額外的乘法運(yùn)算，但經(jīng)過理論分析該額外運(yùn)算引起的時(shí)間開銷對超大點(diǎn)數(shù) FFT的執(zhí)行效率影響較?。欢歉淖兙仃嚨脑L問方式，節(jié)省了顯性轉(zhuǎn)置增加的額外存儲空間，同時(shí)通過限制行列劃分規(guī)則，在一定程度上提高了數(shù)據(jù)訪問的速度。表1給出了本文方法采用Winograd算法的優(yōu)化方法，實(shí)現(xiàn)超大點(diǎn)數(shù)FFT時(shí)對內(nèi)存資源的需求。其中表示取其中最大的緩沖區(qū)，該緩沖區(qū)行列可復(fù)用。下面通過工程實(shí)例來具體說明采用Winograd算法的優(yōu)化方法對超大點(diǎn)FFT的實(shí)現(xiàn)流程。

3 工程實(shí)例

TS201是ADI公司的TigerSHARC系列DSP，其采用超級哈佛結(jié)構(gòu)，最高可支持600 MHz的內(nèi)核時(shí)鐘，具有雙運(yùn)算單元和雙整數(shù)ALU，其內(nèi)部集成24M bit的DRAM存儲器，整個(gè)DRAM劃分為6個(gè)分區(qū)(BANK)，每個(gè) DRAM 存儲器塊帶有一個(gè)128k bit的 Cache，用來協(xié)助數(shù)據(jù)訪問。它的靜態(tài)超標(biāo)量結(jié)構(gòu)使其能夠在1個(gè)周期內(nèi)執(zhí)行4條指令，完成24次16 bit定點(diǎn)運(yùn)算，12次32 bit定點(diǎn)運(yùn)算6次浮點(diǎn)運(yùn)算[10]。

表1 本文方法實(shí)現(xiàn)FFT對資源的需求

由于在一個(gè)BANK里面只能存儲128k復(fù)數(shù)點(diǎn)的數(shù)據(jù)量，因此考慮將原始數(shù)據(jù)存儲在兩個(gè)不同的BANK中，采用J和K總線同時(shí)訪問兩個(gè)BANK的數(shù)據(jù)；另外，TS201的雙運(yùn)算單元可以一次讀取4列8個(gè)復(fù)數(shù)點(diǎn)的數(shù)據(jù)，Cache的大小為128k bit，按照第2節(jié)所述的行列劃分規(guī)則對1維矩陣進(jìn)行劃分：M=2048, L=64, i=8；即行處理時(shí)，每次讀取一行的數(shù)據(jù)是 2048個(gè)復(fù)數(shù)點(diǎn)可以剛好填充 Cache的空間，在每次列處理時(shí)，分8次讀取數(shù)據(jù)，一次讀取4列，也剛好可以填充一個(gè)Cache的空間。因此，在行列FFT處理時(shí)，只在蝶形運(yùn)算第1級和最后一級存在Cache丟失的情況下，其它級運(yùn)算因?yàn)閿?shù)據(jù)都緩存在Cache中而提高了數(shù)據(jù)命中概率。圖4為128k復(fù)數(shù)浮點(diǎn)FFT的程序設(shè)計(jì)流程圖。

本文主要從指令優(yōu)化和匯編優(yōu)化兩個(gè)方面對128k復(fù)數(shù)浮點(diǎn)FFT的程序設(shè)計(jì)進(jìn)行優(yōu)化：在指令優(yōu)化方面，TS201提供了合適復(fù)數(shù)運(yùn)算的指令集，其內(nèi)部有4條128 bit寬度的內(nèi)部總線，通過J和K總線可以同時(shí)實(shí)現(xiàn)一個(gè)周期內(nèi)4個(gè)32 bit數(shù)據(jù)的讀和寫操作，且其存在兩個(gè)完全對稱的X/Y計(jì)算單元和指令對齊緩沖器(IAB)為單個(gè)時(shí)鐘周期內(nèi)運(yùn)行 4條指令提供了硬件基礎(chǔ)，所以，理論上一個(gè)周期內(nèi)可以完成兩個(gè)蝶形運(yùn)算；在匯編優(yōu)化方面，TS201采用并行的超標(biāo)量流水線技術(shù)，通過合理安排指令流水，使程序進(jìn)入核循環(huán)時(shí)內(nèi)核運(yùn)算單元(乘法運(yùn)算、加減法運(yùn)算)的操作與內(nèi)存訪問的IO操作均并行起來，使程序只在填充和排空時(shí)存在一定的串行操作，保證了算法的高效運(yùn)算[11]。

4 資源開銷及速度對比

驗(yàn)證實(shí)驗(yàn)采用北京理工大學(xué)雷達(dá)所研制的8TS201通用信號處理板卡進(jìn)行實(shí)測，即通過在FFT函數(shù)運(yùn)行前后分別讀取TS201 內(nèi)部的時(shí)鐘計(jì)數(shù)器，計(jì)算二者差值并除以TS201的處理器主頻可以來得到運(yùn)行時(shí)間，運(yùn)行時(shí)間見表2。

由表 2可以看出，相對與文獻(xiàn)[6]的 Winograd算法實(shí)現(xiàn)FFT，采用本文的方法對Winograd算法實(shí)現(xiàn)進(jìn)行優(yōu)化，其在小點(diǎn)數(shù)時(shí)因引入了額外的乘法運(yùn)算致使執(zhí)行效率大概降低16%；但是，在大點(diǎn)數(shù)時(shí)FFT的執(zhí)行效率卻得到了提升，這主要是因?yàn)樵撎幚矸椒ú捎眯辛刑柗绞絻?yōu)化矩陣訪問使其省去了3次顯性轉(zhuǎn)置，并通過限制行列劃分規(guī)則來減少Cache的丟失對執(zhí)行效率的影響。另外，由表3可以看出，在超大點(diǎn)數(shù)時(shí)，本文 Winograd算法的實(shí)現(xiàn)方法比傳統(tǒng)方法節(jié)省了近一半的內(nèi)存資源，較其它算法也有巨大優(yōu)勢，這為同一處理器平臺上實(shí)現(xiàn)更大點(diǎn)數(shù)的FFT提供了一種可行的方法。

5 結(jié)束語

本文針對現(xiàn)有處理器硬件平臺對實(shí)現(xiàn)超大點(diǎn)數(shù)FFT的限制因素進(jìn)行了深入分析，對Winograd算法的實(shí)現(xiàn)方法進(jìn)行了資源優(yōu)化處理，并依據(jù)處理器分級存儲結(jié)構(gòu)的特點(diǎn)優(yōu)化了行列劃分規(guī)則，從而提高了FFT處理過程中的行列訪問效率；同時(shí)，給出了在TS201上實(shí)現(xiàn)了128k復(fù)數(shù)浮點(diǎn)FFT的實(shí)現(xiàn)流程。實(shí)驗(yàn)驗(yàn)證及資源對比表明，在超大點(diǎn)數(shù)FFT時(shí)，本文的處理方法能夠節(jié)約一半的處理器資源開銷，明顯提升了大點(diǎn)數(shù)FFT處理的處理效率，該處理方法實(shí)現(xiàn)的超大點(diǎn)數(shù)FFT具有很高的工程應(yīng)用價(jià)值。

圖4 128k復(fù)數(shù)浮點(diǎn)FFT程序?qū)崿F(xiàn)流程圖

表2 FFT運(yùn)行時(shí)間對比(s)μ

表3 FFT內(nèi)存開銷對比(kB)

[1] 李斌, 田素雷, 孫雪晶. 大點(diǎn)數(shù) FFT 設(shè)計(jì)中提高資源利用率的方法[J]. 無線電工程, 2011, 41(1): 54-57.Li Bin, Tian Su-lei, and Sun Xue-jing. Method of improving resource utilization for large point FFT design[J]. Radio Engineering, 2011, 41(1): 54-57.

[2] Boris Lerner. Writing efficient floating-point FFTs for ADSP-TS201 TigerSHARC[OL]. http://www.Analog.com/dsp, 2012.

[3] 李欣, 劉峰, 龍騰. 定點(diǎn)FFT在TS201上的高效實(shí)現(xiàn)[J]. 北京理工大學(xué)學(xué)報(bào), 2010, 30(1): 88-91.Li Xin, Liu Feng, and Long Teng. Efficient implementation of fixed-point FFT on TS201[J]. Transactions of Beijing Institute of Technology, 2010, 30(1): 88-91.

[4] 劉莉, 高梅國, 周閏, 等. 大點(diǎn)數(shù)FFT的多DSPs并行處理算法及實(shí)現(xiàn)[J]. 系統(tǒng)工程與電子技術(shù), 2003, 25(10): 1193-1197.Liu Li, Gao Mei-guo, Zhou Run, et al.. Algorithm and implementation of a large-point FFT under the master-slave parallel multi-processor architecture[J]. Systems Engineering and Electronics, 2003, 25(10): 1193-1197.

[5] 石長振, 楊雪, 王貞松. 高性能并行 FFT 處理器的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2012, 38(2): 242-245.Shi Chang-zhen, Yang Xue, and Wang Zhen-song. Design and realization of high performance parallel FFT processor[J].Computer Engineering, 2012, 38(2): 242-245.

[6] Boris Lerner. Parallel implementation of fixed-point FFTs on TigerSHARC processors[OL]. http://www.Analog.com/dsp,2012.

[7] 王世一. 數(shù)字信號處理[M]. 北京: 北京理工大學(xué)出版社, 1997:123-131.

[8] 李浩, 謝倫國. 片上多處理器末級Cache優(yōu)化技術(shù)研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(增刊): 172-179.Li Hao and Xie Lun-guo. Research development of optimization technology on last level cache in chip multiprocessors[J]. Journal of Computer Research and Development, 2012, 49(Suppl.): 172-179.

[9] 周永彬, 張軍超. 基于軟硬件的協(xié)同支持在眾核上對 1-DFT算法的優(yōu)化研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(11): 2005-2014.Zhou Yong-bin and Zhang Jun-chao. Software ＆amp; hardware co-design for 1-D FFT optimization on many-core architecture[J]. Chinese Journal of Computers, 2008, 31(11):2005-2014.

[10] 劉書明, 羅勇江. ADSP TS20XS系列 DSP原理與應(yīng)用設(shè)計(jì)[M]. 北京: 電子工業(yè)出版社, 2007: 6-7.

[11] Analog Device Inc. ADSP-TS201 TigerSHARC Processor Programming Reference[M]. Norwood: Mass, US, Analog Device Incorporation, 2004: 172-199.

[12] 劉志哲, 仲順安. 基于分級存儲并行運(yùn)算的 FFT處理器設(shè)計(jì)[J]. 北京理工大學(xué)學(xué)報(bào), 2011, 32(6): 691-684.Liu Zhi-zhe and Zhong Shun-an. Design of FFT processor based on grade-memory and parallel-computation[J].Transactions of Beijing Institute of Technology, 2011, 32(6):691-694.

[13] 蘇濤, 莊德靖. 大點(diǎn)數(shù) FFT 算法的改進(jìn)及其實(shí)現(xiàn)[J]. 現(xiàn)代雷達(dá), 2005, 27(7): 23-27.Su Tao and Zhuang De-jing. Improvement and implementation of FFT algorithm for long sequences[J].Modern Radar, 2005, 27(7): 23-27.

[14] Analog Device Inc. TigerSHARC DSP 32 bit REAL/COMPL EX FFT example [EB/OL]. http://www.Analog.com/dsp,2012.

[15] Analog Device Inc. TigerSHARC DSP complex fixed point FFT example for TS201 and TS101[EB/OL]. http://www.Analog.com/dsp, 2012.

[16] Bailey D H. FFTs in external or hierarchical memory[J].Journal of Supercomputing, 1990, 4(1): 23-35.