二維快速傅里葉變換在眾核處理器上的實現

肖風玉　張德學

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

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

中圖分類號：TN929.53；TP332 文獻標識碼：A

所謂多核處理器是指在同一個芯片上集成多個處理器核心。根據處理器核心的結構是否相同又可進一步劃分為同構多核處理器和異構多核處理器。相比傳統的單核處理器，多核處理器最大的優勢在于其并行性，由于在一個芯片內集成了多個核心，因此在同一時間內每個核心都可以并發的執行計算任務，且互不干擾，這使得多核處理器的計算性能得到大幅度提升。此外由于多核處理器的并行性使得其不必工作在較高的工作頻率也能完成與單核處理器相同的任務，降低了處理器的工作頻率，延長了芯片的使用壽命。

本文首先分析了二維快速傅里葉變換（two dimensional Fast Fourier Transform，簡稱2D FFT）的基本原理，然后利用開放式平鋪結構的眾核片上系統（Open Tiled Manycore System-on-Chip，簡稱OPTIMSOC）上的一款眾核處理器對2D FFT進行了實現。

1 2D FFT的基本原理

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

2 眾核處理器介紹

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

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

3 2D FFT在眾核處理器上的測試

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

4 結論

本文分析了OPTIMSOC平臺上的一款眾核處理器，在該眾核處理器上運行了2D FFT。實驗結果表明，相比單核處理器，眾核處理器對2D FFT有較明顯的加速效果。

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

參考文獻

[1] 黃國睿，張平，魏廣博.多核處理器的關鍵技術及其發展趨勢[J].計算機工程與設計，2009，30（10）：2414-2418.

[2] 李曉明，王韜，劉東等.走進多核時代[J].計算機科學與探索，2008（6）：561-570.

[3] 張麗君.大點數FFT的二維算法FPGA并行實現[J].無線電通信技術，2013（3）：86-88.

[4] 李麗，許居衍.片上網絡發展現狀及趨勢淺析[J].電子產品世界，2009（1）：32-37.