文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2017.03.003
中文引用格式: 張多利,,沈休壘,,宋宇鯤,等. 基于異構(gòu)多核可編程系統(tǒng)的大點(diǎn)FFT卷積設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用,,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ù)字信號(hào)處理領(lǐng)域,長(zhǎng)沖激響應(yīng)的數(shù)據(jù)流卷積運(yùn)算廣泛地應(yīng)用在雷達(dá)接收匹配濾波器,、數(shù)字通信,、圖像處理和信號(hào)接收帶通濾波器等中。FFT卷積方法將線性卷積轉(zhuǎn)換到頻域,,通過(guò)使用有效的FFT處理器,,對(duì)于數(shù)據(jù)流處理是有效算法,具有很高數(shù)據(jù)處理速度,,但數(shù)據(jù)吞吐率很低,。為了使用FFT卷積方法處理數(shù)據(jù)流,F(xiàn)FT處理器必須多路復(fù)用,,以保持處理速度和吞吐率同步,。
隨著半導(dǎo)體技術(shù)的高速發(fā)展,HMPS已經(jīng)成為IC主流趨勢(shì),,并且在很多應(yīng)用領(lǐng)域成為最具有發(fā)展前景的硬件處理技術(shù)[1,,2]。因此,,在處理零點(diǎn)填充數(shù)據(jù)流,,大點(diǎn)FFT卷積運(yùn)算中,HMPS成為這種數(shù)據(jù)密集型和計(jì)算密集型任務(wù)的最佳解決方法,。為了獲得高吞吐率和處理速度,,研究基于NoC[3]互聯(lián)的HMPS,充分利用其并行計(jì)算處理能力,,具有良好的可拓展性和低功耗等,。
大點(diǎn)FFT卷積實(shí)現(xiàn)需要大量復(fù)雜計(jì)算,成為濾波器設(shè)計(jì)的瓶頸,。本文首先介紹并總結(jié)大點(diǎn)FFT卷積運(yùn)算原理以及推導(dǎo)方法,;其次,展示HMPS系統(tǒng)架構(gòu)和詳細(xì)的算法映射方案,;最后,,給出系統(tǒng)性能參數(shù),包括結(jié)果誤差比較,、系統(tǒng)任務(wù)并行度,、硬件資源消耗和針對(duì)系統(tǒng)性能的改進(jìn)目標(biāo)和方向等[4,,5]。
1 重疊相加算法原理
如圖1所示,,重疊相加FFT卷積方法是將采樣序列劃分成具有L等長(zhǎng)度的數(shù)據(jù)片段,。假設(shè)抽頭系數(shù)h(n)長(zhǎng)度為N,采樣序列x(n)為無(wú)限長(zhǎng),,將x(n)序列等分成長(zhǎng)為L(zhǎng)的數(shù)據(jù)片段,,如式(1)所示:
那么,序列h(n)和x(n)的FFT卷積為濾波結(jié)果,,定義如下:
由式(2)和式(3)推導(dǎo)可知,,當(dāng)計(jì)算大點(diǎn)FFT卷積時(shí),首先,,計(jì)算分段片段的線性卷積yk(n),,然后將分段片段的卷積結(jié)果重疊部分相加,則為最終濾波結(jié)果y(n),。
為了避免混疊效應(yīng),,對(duì)于長(zhǎng)度為M的濾波沖激響應(yīng),將各個(gè)分段序列后追加M-1個(gè)0,,同時(shí)將時(shí)域卷積轉(zhuǎn)換成頻域相乘,,在采樣序列為N的DFT中,其中N≥L+M-1,,由式(4)可得頻域?yàn)V波結(jié)果:
其中H(k)為濾波器的頻域響應(yīng),,X(k)和Y(k)分別代表采樣序列和濾波結(jié)果的頻域響應(yīng)。在零點(diǎn)填充的沖激響應(yīng)序列和分段序列轉(zhuǎn)換成頻域相乘之后,,將各分段濾波結(jié)果求逆FFT運(yùn)算,,最后在時(shí)域中,將上一份段的后M-1點(diǎn)與下一分段的前M-1點(diǎn)重疊相加即為最終濾波結(jié)果,。
2 基于NoC平臺(tái)的HMPS
異構(gòu)多核可編程系統(tǒng)HMPS主要應(yīng)用在高密度計(jì)算中,,該系統(tǒng)設(shè)計(jì)不僅能滿足某些特殊類型操作,而且還具有一定的通用性,。
如圖2所示,,基于7×6 2D mesh網(wǎng)絡(luò)結(jié)構(gòu)的HMPS系統(tǒng)架構(gòu)具有22個(gè)資源節(jié)點(diǎn),所有的操作數(shù)和狀態(tài)控制信息等通過(guò)該通信網(wǎng)絡(luò)進(jìn)行傳遞,。同時(shí),,該多核系統(tǒng)集成的資源節(jié)點(diǎn)類型主要有:Flash簇、主控制器簇(Main Controller Cluster),、以太網(wǎng)口簇(Ethernet Port Cluster),、三層網(wǎng)絡(luò)、4GB的DDR3簇以及3種浮點(diǎn)運(yùn)算單元簇,。該系統(tǒng)的32 bit浮點(diǎn)運(yùn)算單元主要有協(xié)處理器簇(COP Cluster),、可重構(gòu)運(yùn)算單元簇(RCU Cluster)和FFT/IFFT簇,滿足IEEE-754單精度浮點(diǎn)標(biāo)準(zhǔn),。在NoC平臺(tái)下的每個(gè)資源節(jié)點(diǎn)分別具有轉(zhuǎn)發(fā)狀態(tài)請(qǐng)求包的狀態(tài)網(wǎng)絡(luò),、下發(fā)配置信息的配置網(wǎng)絡(luò)和數(shù)據(jù)傳輸?shù)陌娐方粨Q網(wǎng)絡(luò)(PCC)。在任務(wù)運(yùn)行時(shí),,所有的資源節(jié)點(diǎn)必須滿足片上網(wǎng)絡(luò)通信機(jī)制和主控制器任務(wù)調(diào)度管理來(lái)協(xié)同處理,,發(fā)揮系統(tǒng)高性能優(yōu)勢(shì)。
2.1 Flash簇
系統(tǒng)進(jìn)行上電復(fù)位之后,,由Flash簇中固化的配置引導(dǎo)信息完成HMPS系統(tǒng)任務(wù)初始化工作,。
2.2 主控制器簇
通過(guò)向DDR請(qǐng)求配置信息,對(duì)參與任務(wù)的簇配置,,轉(zhuǎn)發(fā)數(shù)據(jù)請(qǐng)求/應(yīng)答信息,,接收DDR發(fā)出的任務(wù)切換信息,進(jìn)行任務(wù)切換, 完成系統(tǒng)任務(wù)調(diào)度,。
2.3 以太網(wǎng)口簇
實(shí)現(xiàn)上位機(jī)軟件與FPGA芯片之間的數(shù)據(jù)交換,,下發(fā)系統(tǒng)任務(wù)運(yùn)算的配置信息和原數(shù)據(jù)以及回傳運(yùn)算結(jié)果數(shù)據(jù),網(wǎng)口簇是HMPS調(diào)試的必要手段,。
2.4 三層網(wǎng)絡(luò)
由PCC網(wǎng)絡(luò),、配置網(wǎng)絡(luò)和狀態(tài)網(wǎng)絡(luò)組成7×6 2D mesh網(wǎng)絡(luò)結(jié)構(gòu),完成系統(tǒng)中的數(shù)據(jù)以及控制信息傳輸,。數(shù)據(jù)傳輸網(wǎng)由PCC路由節(jié)點(diǎn)連接而成的PCC網(wǎng)絡(luò),,是數(shù)據(jù)傳輸?shù)奈ㄒ宦窂健E渲镁W(wǎng)絡(luò)是下發(fā)配置信息和轉(zhuǎn)發(fā)數(shù)據(jù)請(qǐng)求的唯一路徑,。狀態(tài)網(wǎng)絡(luò)是上傳數(shù)據(jù)請(qǐng)求/應(yīng)答信息的唯一路徑,。
2.5 DDR3簇
DDR3控制器能夠同時(shí)處理資源節(jié)點(diǎn)的讀寫(xiě)控制請(qǐng)求,并且將參與系統(tǒng)任務(wù)的相關(guān)配置信息,、原始數(shù)據(jù),、中間立即數(shù)和結(jié)果數(shù)據(jù)等存儲(chǔ)在4 GB DDR3中。
2.6 FFT/IFFT簇
32 bit浮點(diǎn)運(yùn)算能力的FFT/IFFT簇能夠支持16K點(diǎn)FFT和逆FFT,,具有兩個(gè)蝶形運(yùn)算器的特殊架構(gòu)設(shè)計(jì)能夠同時(shí)運(yùn)算,,因此,16K點(diǎn)FFT和逆FFT僅需要56.3K系統(tǒng)時(shí)鐘周期,。
2.7 RCU簇
32 bit浮點(diǎn)運(yùn)算能力的RCU簇主要處理復(fù)數(shù)和實(shí)數(shù)的規(guī)整運(yùn)算,,主要包括復(fù)、實(shí)數(shù)間的批量乘法,、加法和減法等[6],。該處理單元由兩個(gè)乘法器和兩個(gè)加法器構(gòu)成,具有可重構(gòu)特性,,因此能夠處理大批量的數(shù)據(jù)運(yùn)算,。同時(shí),,能夠支持兩種數(shù)據(jù)運(yùn)算模式:存儲(chǔ)模式和流模式。
2.8 COP簇
滿足IEEE-754單精度浮點(diǎn)運(yùn)算標(biāo)準(zhǔn)的COP簇主要通過(guò)軟件編程來(lái)控制無(wú)規(guī)律的浮點(diǎn)復(fù),、實(shí)數(shù)操作運(yùn)算,,主要包括復(fù)、實(shí)數(shù)間的加法,、減法,、乘法、除法,、開(kāi)方運(yùn)算等[7],。基于SIMD架構(gòu)的協(xié)處理器采用Micro blaze作為控制單元,,通過(guò)FSL總線控制硬件浮點(diǎn)協(xié)處理器IP,。參與系統(tǒng)任務(wù)的COP簇主要通過(guò)SDK軟件編程來(lái)控制數(shù)據(jù)接收、相關(guān)運(yùn)算以及傳送結(jié)果到相應(yīng)的處理單元中,。
3 大點(diǎn)FFT卷積算法映射
本文采用抽頭系數(shù)1K+1點(diǎn)的h(n)和采樣點(diǎn)數(shù)為16K點(diǎn)的x(n)為例來(lái)驗(yàn)證零點(diǎn)填充和重疊相加方法,,如圖3所示。
通過(guò)零點(diǎn)填充和流水重疊相加方法,,將16K采樣點(diǎn)劃分成16組1K等長(zhǎng)的分段,,為了避免混疊效應(yīng),將所有的分段片段和抽頭系數(shù)分別追加1K和1K-1點(diǎn)的零序列,,轉(zhuǎn)換成具有2K統(tǒng)一長(zhǎng)度,,由系統(tǒng)資源節(jié)點(diǎn)來(lái)完成各個(gè)分段片段的FFT卷積運(yùn)算。為了提高處理速度和充分利用HMPS高性能優(yōu)勢(shì),,將所有的采樣點(diǎn)通過(guò)時(shí)域到頻域再到時(shí)域的轉(zhuǎn)換,,使得系統(tǒng)所有運(yùn)算簇能夠參與流水并行運(yùn)算,提高系統(tǒng)任務(wù)并行度,。
如圖4(a),、圖4(b)和圖4(c)所示,16K采樣點(diǎn)FFT卷積算法映射成4個(gè)子任務(wù)(Task0,、Task1,、Task2和Task3)。在如下的數(shù)據(jù)流圖(DFG)中,,系統(tǒng)的18個(gè)浮點(diǎn)運(yùn)算單元參與任務(wù)執(zhí)行,。
如圖4(a)所示,特殊任務(wù)Task0通過(guò)FFT0,、FFT1和FFT2簇來(lái)計(jì)算抽頭系數(shù)的頻率響應(yīng),,并存儲(chǔ)在COP0、COP1和COP2簇的片上存儲(chǔ)單元中。在接下來(lái)的任務(wù)中,,分別發(fā)送給RCU0,、RCU1和RCU2簇,與零點(diǎn)添加分段片段序列在頻域上做批量乘法運(yùn)算,。
Task1主要計(jì)算前2K采樣點(diǎn),,得到前2K點(diǎn)濾波結(jié)果,COP3簇的片上存儲(chǔ)單元存儲(chǔ)來(lái)自COP5簇的中間1K濾波結(jié)果來(lái)進(jìn)行接下來(lái)流水重疊相加運(yùn)算,。
如圖4(b)所示,Task2采用了4次并行循環(huán)運(yùn)算流水架構(gòu),,所有的資源節(jié)點(diǎn)均參與任務(wù)執(zhí)行,,達(dá)到理論上最大值。FFT0,、FFT1和FFT2簇分別計(jì)算每次流水各2K點(diǎn)的頻域響應(yīng),,RCU0、RCU1和RCU2簇分別實(shí)現(xiàn)抽頭系數(shù)和各采樣點(diǎn)在頻域上的批量乘運(yùn)算,,F(xiàn)FT3,、FFT4和FFT5簇通過(guò)逆FFT運(yùn)算將頻域?yàn)V波結(jié)果轉(zhuǎn)換成時(shí)域,分別發(fā)送給COP3,、COP4和COP5簇,,最后通過(guò)RCU3、RCU4和RCU5簇實(shí)現(xiàn)前后兩個(gè)分段片段濾波結(jié)果的1K點(diǎn)重疊相加,,得到最終濾波結(jié)果,,并且存儲(chǔ)在DDR3簇中。
在最后一個(gè)任務(wù)Task3中,,主要實(shí)現(xiàn)最后2K采樣點(diǎn)濾波,,將3K濾波結(jié)果寫(xiě)入DDR3簇中去,如圖4(c)所示,。至此,,通過(guò)4個(gè)任務(wù)在HMPS中實(shí)現(xiàn)了16K點(diǎn)的FFT卷積運(yùn)算。
在以上的算法映射方案中,,通過(guò)DDR3簇來(lái)存儲(chǔ)了參與任務(wù)執(zhí)行的配置信息,、原始采樣數(shù)據(jù)和濾波結(jié)果,節(jié)點(diǎn)FFT和RCU簇參與過(guò)程計(jì)算,,利用COP0,、COP1和COP2簇的片上存儲(chǔ)單元存儲(chǔ)濾波系數(shù)的頻域響應(yīng),利用COP3,、COP4和COP5簇來(lái)接收和發(fā)送中間結(jié)果數(shù)據(jù)到相應(yīng)的RCU3,、RCU4和RCU5簇實(shí)現(xiàn)重疊相加。由DFG可以看出,參與任務(wù)執(zhí)行的COP簇僅僅用來(lái)實(shí)現(xiàn)中間數(shù)據(jù)的接收和發(fā)送,,并不參與實(shí)際任務(wù)運(yùn)算,,而所有的FFT和RCU簇參與整個(gè)任務(wù)的相關(guān)運(yùn)算,因此,,系統(tǒng)理論上最大的任務(wù)并行度為12,。
根據(jù)片上網(wǎng)絡(luò)的通信機(jī)制和HMPS中的高效浮點(diǎn)運(yùn)算簇,該系統(tǒng)的大點(diǎn)FFT卷積映射方案比傳統(tǒng)的設(shè)計(jì)架構(gòu)更加方便,,靈活而且運(yùn)算效率更高,。
4 實(shí)驗(yàn)結(jié)果和系統(tǒng)性能分析
在Xilinx XC7V2000T FPGA開(kāi)發(fā)板上,將系統(tǒng)時(shí)鐘頻率設(shè)置為100 MHz,,進(jìn)行測(cè)試驗(yàn)證,,并且通過(guò)網(wǎng)口簇和上位機(jī)軟件將結(jié)果數(shù)據(jù)傳回至本地PC。
通過(guò)將MATLAB軟件的計(jì)算結(jié)果與HMPS處理結(jié)果進(jìn)行誤差比較可知,,由于大點(diǎn)FFT卷積的累加運(yùn)算,,相對(duì)誤差趨近于0,因此,,給出系統(tǒng)的絕對(duì)誤差方法,,如式(5)所示:
表1給出了采樣點(diǎn)為64 K和1 M時(shí),相應(yīng)的系統(tǒng)時(shí)鐘消耗和系統(tǒng)平均任務(wù)并行度,,其中,,Aerr_imagmax和Aerr_realmax分別代表虛部和實(shí)部的絕對(duì)誤差最大值。平均任務(wù)并行度計(jì)算方法如下:
式中,,clusters表示并行度,,Tclusters表示在并行度clusters下的時(shí)鐘消耗,T表示整個(gè)任務(wù)的時(shí)鐘消耗,。
在以上的映射方案中,,64K和1M采樣點(diǎn)僅需要改變Task2的循環(huán)次數(shù),其他保持不變,。零點(diǎn)填充和重疊相加的16K點(diǎn) FFT卷積平均需要5次流水循環(huán)運(yùn)算,,而64K和1M采用點(diǎn)分別需要21次和341次流水循環(huán)運(yùn)算。
從表1實(shí)驗(yàn)結(jié)果可以推導(dǎo)出,,參與系統(tǒng)運(yùn)算的采樣點(diǎn)越大,,系統(tǒng)平均任務(wù)并行度就越高,而且最大絕對(duì)誤差接近10-4,,相較于文獻(xiàn)[8]中的異構(gòu)多核處理單元的10-3相對(duì)誤差,,本系統(tǒng)具有更高的計(jì)算精度。與文獻(xiàn)[9]中的異構(gòu)多核SoC相比(其ATP最大達(dá)到3.88),,本設(shè)計(jì)能達(dá)到5.33,,因而具有更高的處理速度和系統(tǒng)平均任務(wù)并行度,,采樣點(diǎn)數(shù)越大,效果越明顯,。
HMPS在Xilinx XC7V2000T開(kāi)發(fā)板上的硬件資源消耗如表2所示,。
5 結(jié)論
在很多應(yīng)用領(lǐng)域,大點(diǎn)FFT卷積實(shí)現(xiàn)是一個(gè)需要突破的技術(shù)瓶頸,,減少運(yùn)算時(shí)間,,提高運(yùn)算效率和濾波結(jié)果正確性等具有重要意義。本文實(shí)現(xiàn)了基于HMPS的大點(diǎn)FFT卷積高效映射方案,,對(duì)于2M,、4M,甚至更大的采樣點(diǎn)都可以很容易地通過(guò)以上映射方法增加流水循環(huán)次數(shù)進(jìn)行實(shí)現(xiàn),,而且不需要增加額外的硬件資源消耗,。
另外需要注意的是,系統(tǒng)性能和任務(wù)并行度的提高需要同一時(shí)刻所有運(yùn)算簇參與任務(wù)計(jì)算,。本文實(shí)現(xiàn)了抽頭系數(shù)為1K+1點(diǎn),也可以采用其他合適長(zhǎng)度的抽頭系數(shù),。作為通用目的處理器系統(tǒng),,HMPS主要運(yùn)用在高密度計(jì)算領(lǐng)域,也可以實(shí)現(xiàn)其它復(fù)雜計(jì)算,。
通過(guò)實(shí)驗(yàn)分析可知,,系統(tǒng)性能有很大的提升空間,為了獲得更高的數(shù)據(jù)吞吐率,、處理速度和任務(wù)并行度,,可以通過(guò)改善片上網(wǎng)絡(luò)來(lái)減少通信時(shí)間和增加DDR的有效帶寬來(lái)提高數(shù)據(jù)吞吐量等,具有十分重要的意義,。
參考文獻(xiàn)
[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è)大學(xué) 微電子設(shè)計(jì)研究所,安徽 合肥230009)