二維快速傅里葉變換在眾核處理器上的實(shí)現(xiàn)

肖風(fēng)玉　張德學(xué)

摘 要 本文研究了開放式平鋪結(jié)構(gòu)的眾核片上系統(tǒng)（Open Tiled Manycore System-on-Chip，簡(jiǎn)稱OPTIMSOC）上的一款眾核處理器，在該處理器上實(shí)現(xiàn)了二維快速傅里葉變換（two dimensional Fast Fourier transform，簡(jiǎn)稱2D FFT）。實(shí)驗(yàn)結(jié)果表明，相較于單核處理器，眾核處理器有較明顯的加速效果。

關(guān)鍵詞 二維快速傅里葉變換 眾核處理器 OPTIMSOC 加速比

中圖分類號(hào)：TN929.53；TP332 文獻(xiàn)標(biāo)識(shí)碼：A

所謂多核處理器是指在同一個(gè)芯片上集成多個(gè)處理器核心。根據(jù)處理器核心的結(jié)構(gòu)是否相同又可進(jìn)一步劃分為同構(gòu)多核處理器和異構(gòu)多核處理器。相比傳統(tǒng)的單核處理器，多核處理器最大的優(yōu)勢(shì)在于其并行性，由于在一個(gè)芯片內(nèi)集成了多個(gè)核心，因此在同一時(shí)間內(nèi)每個(gè)核心都可以并發(fā)的執(zhí)行計(jì)算任務(wù)，且互不干擾，這使得多核處理器的計(jì)算性能得到大幅度提升。此外由于多核處理器的并行性使得其不必工作在較高的工作頻率也能完成與單核處理器相同的任務(wù)，降低了處理器的工作頻率，延長(zhǎng)了芯片的使用壽命。

本文首先分析了二維快速傅里葉變換（two dimensional Fast Fourier Transform，簡(jiǎn)稱2D FFT）的基本原理，然后利用開放式平鋪結(jié)構(gòu)的眾核片上系統(tǒng)（Open Tiled Manycore System-on-Chip，簡(jiǎn)稱OPTIMSOC）上的一款眾核處理器對(duì)2D FFT進(jìn)行了實(shí)現(xiàn)。

1 2D FFT的基本原理

計(jì)算2D FFT可分為3步。第一步，對(duì)矩陣的每一列進(jìn)行一維快速傅里葉變換（簡(jiǎn)稱1D FFT），由于列變換之間無(wú)相關(guān)性，因此其并行性是顯著的；第二步處理2D FFT的旋轉(zhuǎn)因子，由于旋轉(zhuǎn)因子的處理之間無(wú)相關(guān)性，因此其并行性是顯著的；第三步，對(duì)矩陣的每一行進(jìn)行1D FFT，由于行變換之間無(wú)相關(guān)性，因此其并行性是顯著的。

2 眾核處理器介紹

OPTIMSOC是一個(gè)基于庫(kù)的框架平臺(tái)，它允許用戶構(gòu)建屬于自己的眾核處理器。該平臺(tái)基于開源規(guī)則的片上網(wǎng)絡(luò)結(jié)構(gòu)LISNOC和其它一些開源的硬件組件構(gòu)成。這些硬件組件包括處理單元、存儲(chǔ)器和輸入輸出設(shè)備等等。與傳統(tǒng)的基于總線互聯(lián)方式的多核處理器相比，眾核處理器的一大顯著特點(diǎn)是引入了片上網(wǎng)絡(luò)的概念。片上網(wǎng)絡(luò)的成功引入，解決了總線互聯(lián)方式中的瓶頸，包括功耗、面積和復(fù)雜度等。使用OPTIMSOC平臺(tái)構(gòu)建的眾核系統(tǒng)可以在電腦上進(jìn)行仿真或者綜合之后下載到FPGA開發(fā)板上進(jìn)行實(shí)現(xiàn)。OPTIMSOC平臺(tái)的出現(xiàn)，使得對(duì)眾核處理器研究不只是停留在建模與仿真階段，而是真正進(jìn)入了設(shè)計(jì)階段，加速了眾核處理器產(chǎn)品的設(shè)計(jì)與開發(fā)。

OPTIMSOC平臺(tái)設(shè)計(jì)者建議使用Ubuntu 12.04或14.04 LTS作為開發(fā)系統(tǒng)。本文在Centos 7.1系統(tǒng)上對(duì)OPTIMSOC平臺(tái)進(jìn)行了安裝與配置并對(duì)平臺(tái)上存在的一款眾核處理器進(jìn)行了分析。通過分析，該眾核處理器由獨(dú)立的計(jì)算單元組成，每個(gè)計(jì)算單元包含一個(gè)計(jì)算核心和一個(gè)本地存儲(chǔ)器。計(jì)算核心采用的是OpenRisc架構(gòu)的處理器，本地存儲(chǔ)器的容量是8MB，核與核之間的通信通過LISNOC完成。值得注意的是，OPTIMSOC的安裝包中已包含了單核處理器。

3 2D FFT在眾核處理器上的測(cè)試

對(duì)于單核處理器的編程，可按照第一部分中介紹的2D FFT的計(jì)算步驟進(jìn)行編程，即將3個(gè)計(jì)算步驟看作是三個(gè)順序執(zhí)行的任務(wù)進(jìn)行編程。對(duì)于眾核處理器而言，由于其核心數(shù)較多，各核心需要協(xié)同工作才能完成計(jì)算任務(wù)，因此與單核處理器相比，眾核處理器的編程較為復(fù)雜。在該眾核處理器中，將0核作為主核，其它核作為輔核。主核負(fù)責(zé)向其它核傳送計(jì)算指令與運(yùn)算數(shù)據(jù)并回收來(lái)自輔核的計(jì)算結(jié)果，輔核負(fù)責(zé)進(jìn)行計(jì)算并將計(jì)算后的結(jié)果返回至主核。根據(jù)該原則，編寫了在眾核處理器上運(yùn)行的2D FFT程序。本文在單核處理器和眾核處理器上分別對(duì)256點(diǎn)、1024點(diǎn)和4096點(diǎn)下的2D FFT進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果表明，眾核處理器對(duì)2D FFT有較明顯的加速效果。

4 結(jié)論

本文分析了OPTIMSOC平臺(tái)上的一款眾核處理器，在該眾核處理器上運(yùn)行了2D FFT。實(shí)驗(yàn)結(jié)果表明，相比單核處理器，眾核處理器對(duì)2D FFT有較明顯的加速效果。

但仍有一些問題需要進(jìn)行深度的挖掘，包括算法并行度的進(jìn)一步分析，眾核處理器的共享存儲(chǔ)問題。如果算法的并行程度分析不夠，很容易造成眾核處理器資源的浪費(fèi)。由于本文中的眾核處理器未采用共享存儲(chǔ)，大點(diǎn)數(shù)情況下，核間數(shù)據(jù)交換將會(huì)占據(jù)較大部分比重，影響眾核處理器的性能。因此今后的研究重點(diǎn)將在這兩方面進(jìn)行。

參考文獻(xiàn)

[1] 黃國(guó)睿，張平，魏廣博.多核處理器的關(guān)鍵技術(shù)及其發(fā)展趨勢(shì)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（10）：2414-2418.

[2] 李曉明，王韜，劉東等.走進(jìn)多核時(shí)代[J].計(jì)算機(jī)科學(xué)與探索，2008（6）：561-570.

[3] 張麗君.大點(diǎn)數(shù)FFT的二維算法FPGA并行實(shí)現(xiàn)[J].無(wú)線電通信技術(shù)，2013（3）：86-88.

[4] 李麗，許居衍.片上網(wǎng)絡(luò)發(fā)展現(xiàn)狀及趨勢(shì)淺析[J].電子產(chǎn)品世界，2009（1）：32-37.