文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.03.003
中文引用格式： 張多利，沈休壘，宋宇鯤，等. 基于異構多核可編程系統(tǒng)的大點FFT卷積設計與實現(xiàn)[J].電子技術應用，2017，43(3)：16-20.
英文引用格式： Zhang Duoli，Shen Xiulei，Song Yukun，et al. Design and implementation of large FFT convolution on heterogeneous multicore programmable system[J].Application of Electronic Technique，2017，43(3)：16-20.
0 引言
在數(shù)字信號處理領域，長沖激響應的數(shù)據(jù)流卷積運算廣泛地應用在雷達接收匹配濾波器、數(shù)字通信、圖像處理和信號接收帶通濾波器等中。FFT卷積方法將線性卷積轉換到頻域，通過使用有效的FFT處理器，對于數(shù)據(jù)流處理是有效算法，具有很高數(shù)據(jù)處理速度，但數(shù)據(jù)吞吐率很低。為了使用FFT卷積方法處理數(shù)據(jù)流，F(xiàn)FT處理器必須多路復用，以保持處理速度和吞吐率同步。
隨著半導體技術的高速發(fā)展，HMPS已經(jīng)成為IC主流趨勢，并且在很多應用領域成為最具有發(fā)展前景的硬件處理技術[1，2]。因此，在處理零點填充數(shù)據(jù)流，大點FFT卷積運算中，HMPS成為這種數(shù)據(jù)密集型和計算密集型任務的最佳解決方法。為了獲得高吞吐率和處理速度，研究基于NoC[3]互聯(lián)的HMPS，充分利用其并行計算處理能力，具有良好的可拓展性和低功耗等。
大點FFT卷積實現(xiàn)需要大量復雜計算，成為濾波器設計的瓶頸。本文首先介紹并總結大點FFT卷積運算原理以及推導方法；其次，展示HMPS系統(tǒng)架構和詳細的算法映射方案；最后，給出系統(tǒng)性能參數(shù)，包括結果誤差比較、系統(tǒng)任務并行度、硬件資源消耗和針對系統(tǒng)性能的改進目標和方向等[4，5]。
1 重疊相加算法原理
如圖1所示，重疊相加FFT卷積方法是將采樣序列劃分成具有L等長度的數(shù)據(jù)片段。假設抽頭系數(shù)h(n)長度為N，采樣序列x(n)為無限長，將x(n)序列等分成長為L的數(shù)據(jù)片段，如式(1)所示：
那么，序列h(n)和x(n)的FFT卷積為濾波結果，定義如下：
由式(2)和式(3)推導可知，當計算大點FFT卷積時，首先，計算分段片段的線性卷積yk(n)，然后將分段片段的卷積結果重疊部分相加，則為最終濾波結果y(n)。
為了避免混疊效應，對于長度為M的濾波沖激響應，將各個分段序列后追加M-1個0，同時將時域卷積轉換成頻域相乘，在采樣序列為N的DFT中，其中N≥L+M-1，由式(4)可得頻域濾波結果：
其中H(k)為濾波器的頻域響應，X(k)和Y(k)分別代表采樣序列和濾波結果的頻域響應。在零點填充的沖激響應序列和分段序列轉換成頻域相乘之后，將各分段濾波結果求逆FFT運算，最后在時域中，將上一份段的后M-1點與下一分段的前M-1點重疊相加即為最終濾波結果。
2 基于NoC平臺的HMPS
異構多核可編程系統(tǒng)HMPS主要應用在高密度計算中，該系統(tǒng)設計不僅能滿足某些特殊類型操作，而且還具有一定的通用性。
如圖2所示，基于7×6 2D mesh網(wǎng)絡結構的HMPS系統(tǒng)架構具有22個資源節(jié)點，所有的操作數(shù)和狀態(tài)控制信息等通過該通信網(wǎng)絡進行傳遞。同時，該多核系統(tǒng)集成的資源節(jié)點類型主要有：Flash簇、主控制器簇（Main Controller Cluster）、以太網(wǎng)口簇（Ethernet Port Cluster）、三層網(wǎng)絡、4GB的DDR3簇以及3種浮點運算單元簇。該系統(tǒng)的32 bit浮點運算單元主要有協(xié)處理器簇（COP Cluster）、可重構運算單元簇（RCU Cluster）和FFT/IFFT簇，滿足IEEE-754單精度浮點標準。在NoC平臺下的每個資源節(jié)點分別具有轉發(fā)狀態(tài)請求包的狀態(tài)網(wǎng)絡、下發(fā)配置信息的配置網(wǎng)絡和數(shù)據(jù)傳輸?shù)陌娐方粨Q網(wǎng)絡（PCC）。在任務運行時，所有的資源節(jié)點必須滿足片上網(wǎng)絡通信機制和主控制器任務調度管理來協(xié)同處理，發(fā)揮系統(tǒng)高性能優(yōu)勢。
2.1 Flash簇
系統(tǒng)進行上電復位之后，由Flash簇中固化的配置引導信息完成HMPS系統(tǒng)任務初始化工作。
2.2 主控制器簇
通過向DDR請求配置信息，對參與任務的簇配置，轉發(fā)數(shù)據(jù)請求/應答信息，接收DDR發(fā)出的任務切換信息，進行任務切換, 完成系統(tǒng)任務調度。
2.3 以太網(wǎng)口簇
實現(xiàn)上位機軟件與FPGA芯片之間的數(shù)據(jù)交換，下發(fā)系統(tǒng)任務運算的配置信息和原數(shù)據(jù)以及回傳運算結果數(shù)據(jù)，網(wǎng)口簇是HMPS調試的必要手段。
2.4 三層網(wǎng)絡
由PCC網(wǎng)絡、配置網(wǎng)絡和狀態(tài)網(wǎng)絡組成7×6 2D mesh網(wǎng)絡結構，完成系統(tǒng)中的數(shù)據(jù)以及控制信息傳輸。數(shù)據(jù)傳輸網(wǎng)由PCC路由節(jié)點連接而成的PCC網(wǎng)絡，是數(shù)據(jù)傳輸?shù)奈ㄒ宦窂健Ｅ渲镁W(wǎng)絡是下發(fā)配置信息和轉發(fā)數(shù)據(jù)請求的唯一路徑。狀態(tài)網(wǎng)絡是上傳數(shù)據(jù)請求/應答信息的唯一路徑。
2.5 DDR3簇
DDR3控制器能夠同時處理資源節(jié)點的讀寫控制請求，并且將參與系統(tǒng)任務的相關配置信息、原始數(shù)據(jù)、中間立即數(shù)和結果數(shù)據(jù)等存儲在4 GB DDR3中。
2.6 FFT/IFFT簇
32 bit浮點運算能力的FFT/IFFT簇能夠支持16K點FFT和逆FFT，具有兩個蝶形運算器的特殊架構設計能夠同時運算，因此，16K點FFT和逆FFT僅需要56.3K系統(tǒng)時鐘周期。
2.7 RCU簇
32 bit浮點運算能力的RCU簇主要處理復數(shù)和實數(shù)的規(guī)整運算，主要包括復、實數(shù)間的批量乘法、加法和減法等[6]。該處理單元由兩個乘法器和兩個加法器構成，具有可重構特性，因此能夠處理大批量的數(shù)據(jù)運算。同時，能夠支持兩種數(shù)據(jù)運算模式：存儲模式和流模式。
2.8 COP簇
滿足IEEE-754單精度浮點運算標準的COP簇主要通過軟件編程來控制無規(guī)律的浮點復、實數(shù)操作運算，主要包括復、實數(shù)間的加法、減法、乘法、除法、開方運算等[7]。基于SIMD架構的協(xié)處理器采用Micro blaze作為控制單元，通過FSL總線控制硬件浮點協(xié)處理器IP。參與系統(tǒng)任務的COP簇主要通過SDK軟件編程來控制數(shù)據(jù)接收、相關運算以及傳送結果到相應的處理單元中。
3 大點FFT卷積算法映射
本文采用抽頭系數(shù)1K+1點的h(n)和采樣點數(shù)為16K點的x(n)為例來驗證零點填充和重疊相加方法，如圖3所示。
通過零點填充和流水重疊相加方法，將16K采樣點劃分成16組1K等長的分段，為了避免混疊效應，將所有的分段片段和抽頭系數(shù)分別追加1K和1K-1點的零序列，轉換成具有2K統(tǒng)一長度，由系統(tǒng)資源節(jié)點來完成各個分段片段的FFT卷積運算。為了提高處理速度和充分利用HMPS高性能優(yōu)勢，將所有的采樣點通過時域到頻域再到時域的轉換，使得系統(tǒng)所有運算簇能夠參與流水并行運算，提高系統(tǒng)任務并行度。
如圖4(a)、圖4(b)和圖4(c)所示，16K采樣點FFT卷積算法映射成4個子任務(Task0、Task1、Task2和Task3)。在如下的數(shù)據(jù)流圖（DFG）中，系統(tǒng)的18個浮點運算單元參與任務執(zhí)行。
如圖4(a)所示，特殊任務Task0通過FFT0、FFT1和FFT2簇來計算抽頭系數(shù)的頻率響應，并存儲在COP0、COP1和COP2簇的片上存儲單元中。在接下來的任務中，分別發(fā)送給RCU0、RCU1和RCU2簇，與零點添加分段片段序列在頻域上做批量乘法運算。
Task1主要計算前2K采樣點，得到前2K點濾波結果，COP3簇的片上存儲單元存儲來自COP5簇的中間1K濾波結果來進行接下來流水重疊相加運算。
如圖4(b)所示，Task2采用了4次并行循環(huán)運算流水架構，所有的資源節(jié)點均參與任務執(zhí)行，達到理論上最大值。FFT0、FFT1和FFT2簇分別計算每次流水各2K點的頻域響應，RCU0、RCU1和RCU2簇分別實現(xiàn)抽頭系數(shù)和各采樣點在頻域上的批量乘運算，F(xiàn)FT3、FFT4和FFT5簇通過逆FFT運算將頻域濾波結果轉換成時域，分別發(fā)送給COP3、COP4和COP5簇，最后通過RCU3、RCU4和RCU5簇實現(xiàn)前后兩個分段片段濾波結果的1K點重疊相加，得到最終濾波結果，并且存儲在DDR3簇中。
在最后一個任務Task3中，主要實現(xiàn)最后2K采樣點濾波，將3K濾波結果寫入DDR3簇中去，如圖4(c)所示。至此，通過4個任務在HMPS中實現(xiàn)了16K點的FFT卷積運算。
在以上的算法映射方案中，通過DDR3簇來存儲了參與任務執(zhí)行的配置信息、原始采樣數(shù)據(jù)和濾波結果，節(jié)點FFT和RCU簇參與過程計算，利用COP0、COP1和COP2簇的片上存儲單元存儲濾波系數(shù)的頻域響應，利用COP3、COP4和COP5簇來接收和發(fā)送中間結果數(shù)據(jù)到相應的RCU3、RCU4和RCU5簇實現(xiàn)重疊相加。由DFG可以看出，參與任務執(zhí)行的COP簇僅僅用來實現(xiàn)中間數(shù)據(jù)的接收和發(fā)送，并不參與實際任務運算，而所有的FFT和RCU簇參與整個任務的相關運算，因此，系統(tǒng)理論上最大的任務并行度為12。
根據(jù)片上網(wǎng)絡的通信機制和HMPS中的高效浮點運算簇，該系統(tǒng)的大點FFT卷積映射方案比傳統(tǒng)的設計架構更加方便，靈活而且運算效率更高。
4 實驗結果和系統(tǒng)性能分析
在Xilinx XC7V2000T FPGA開發(fā)板上，將系統(tǒng)時鐘頻率設置為100 MHz，進行測試驗證，并且通過網(wǎng)口簇和上位機軟件將結果數(shù)據(jù)傳回至本地PC。
通過將MATLAB軟件的計算結果與HMPS處理結果進行誤差比較可知，由于大點FFT卷積的累加運算，相對誤差趨近于0，因此，給出系統(tǒng)的絕對誤差方法，如式(5)所示：
表1給出了采樣點為64 K和1 M時，相應的系統(tǒng)時鐘消耗和系統(tǒng)平均任務并行度，其中，Aerr_imagmax和Aerr_realmax分別代表虛部和實部的絕對誤差最大值。平均任務并行度計算方法如下：
式中，clusters表示并行度，Tclusters表示在并行度clusters下的時鐘消耗，T表示整個任務的時鐘消耗。
在以上的映射方案中，64K和1M采樣點僅需要改變Task2的循環(huán)次數(shù)，其他保持不變。零點填充和重疊相加的16K點 FFT卷積平均需要5次流水循環(huán)運算，而64K和1M采用點分別需要21次和341次流水循環(huán)運算。
從表1實驗結果可以推導出，參與系統(tǒng)運算的采樣點越大，系統(tǒng)平均任務并行度就越高，而且最大絕對誤差接近10-4，相較于文獻[8]中的異構多核處理單元的10-3相對誤差，本系統(tǒng)具有更高的計算精度。與文獻[9]中的異構多核SoC相比(其ATP最大達到3.88)，本設計能達到5.33，因而具有更高的處理速度和系統(tǒng)平均任務并行度，采樣點數(shù)越大，效果越明顯。
HMPS在Xilinx XC7V2000T開發(fā)板上的硬件資源消耗如表2所示。
5 結論
在很多應用領域，大點FFT卷積實現(xiàn)是一個需要突破的技術瓶頸，減少運算時間，提高運算效率和濾波結果正確性等具有重要意義。本文實現(xiàn)了基于HMPS的大點FFT卷積高效映射方案，對于2M、4M，甚至更大的采樣點都可以很容易地通過以上映射方法增加流水循環(huán)次數(shù)進行實現(xiàn)，而且不需要增加額外的硬件資源消耗。
另外需要注意的是，系統(tǒng)性能和任務并行度的提高需要同一時刻所有運算簇參與任務計算。本文實現(xiàn)了抽頭系數(shù)為1K+1點，也可以采用其他合適長度的抽頭系數(shù)。作為通用目的處理器系統(tǒng)，HMPS主要運用在高密度計算領域，也可以實現(xiàn)其它復雜計算。
通過實驗分析可知，系統(tǒng)性能有很大的提升空間，為了獲得更高的數(shù)據(jù)吞吐率、處理速度和任務并行度，可以通過改善片上網(wǎng)絡來減少通信時間和增加DDR的有效帶寬來提高數(shù)據(jù)吞吐量等，具有十分重要的意義。
參考文獻
[1] CHEN F Y，ZHANG D S，WANG Z Y.Research of the heterogeneous multi-core processor architecture design[J].Computer Engineering & Science，2011，33(12)：27-36.
[2] REN J，HE Y，XUN C Q，et al.A hardware/software method for heterogeneous cores cooperating on stream architecture[J].Chinese Journal of Computers，2008，31(11)：2038-2046.
[3] Hou Ning，Lu Yapeng，Zhang Duoli.Communication solution of multi-core chipset based on NoC[J].Computer Era，2014(10)：17-18.
[4] LEI W，XIAO M，RUI X.Study on a parallel test system based on multicore[J].Journal of Xian Jiaotong University，2008，42(6)：683-687.
[5] LI J，MARTINEZ J F.Power-performance considerations of parallel computing on chip multiprocessors[J].ACM Transactions on Architecture and Code Optimization(TACO)，2005，2(4)：397-422.
[6] Wang Xing，Zhang Duoli，Song Yukun，et al.Design and implementation of a reduced floating-point reconfigruable computing unit[C].International Conference on Computer，Network Security and Communication Engineering(CNSCE)，2014.
[7] HAN Z F，LI J S，PAN H B，et al.Design of Floating-point vector coprocessor based on FPGA[J].Computer Engineering，2012，38(5)：251-254.
[8] ZHANG D，ZHANG Y，SONG Y.The implementation of large FFT on homogeneous multi-core system[C].Solid-State and Integrated Circuit Technology(ICSICT)，2014 12th IEEE International Conference on.IEEE，2014：1-4.
[9] SONG Y，JIAO R，ZHANG D，et al.Performance analysis for matrix-multiplication based on an heterogeneous multicore SoC[C].ASIC(ASICON)，2015 IEEE 11th International Conference on.IEEE，2015：1-4.
作者信息:
張多利，沈休壘，宋宇鯤，杜高明
(合肥工業(yè)大學 微電子設計研究所，安徽 合肥230009）