王 璐，梁 濤，王文義

（中原工學(xué)院，鄭州450007）

FFT算法的并行化性能分析

王 璐，梁 濤，王文義

（中原工學(xué)院，鄭州450007）

以串行FFTW為基準(zhǔn)，從程序運(yùn)行時(shí)間、通信開(kāi)銷兩方面分析了基于消息傳遞型（MPI－FFT）和共享內(nèi)存型（CUFFT）并行FFT實(shí)現(xiàn)的性能.實(shí)驗(yàn)表明，并行FFT都可以提升計(jì)算速度至FFTW的30～80倍，對(duì)于中等規(guī)模的數(shù)據(jù)，CUFFT的計(jì)算速度略優(yōu)于MPI－FFT，且其通信開(kāi)銷明顯較低，具有較高性價(jià)比和較好的應(yīng)用前景.

并行性能；CUFFT；MPI；FFTW

離散傅里葉變換（DFT）是數(shù)字信號(hào)處理中最基本、最重要的運(yùn)算，許多算法，例如卷積、濾波、波譜分析等都可以化為DFT來(lái)實(shí)現(xiàn).但是DFT的計(jì)算量相當(dāng)大，1965年Cooley和Tukey提出了快速傅里葉變換算法（FFT），大大提高了DFT的計(jì)算速度.此后，有很多研究者不斷改進(jìn)算法.美國(guó)麻省理工學(xué)院計(jì)算機(jī)科學(xué)實(shí)驗(yàn)室超級(jí)計(jì)算技術(shù)組開(kāi)發(fā)的FFTW（Fastest Fourier Transform in the West）是目前世界上公認(rèn)的運(yùn)算較快、使用廣泛的串行C程序FFT，支持一維和多維的實(shí)數(shù)及復(fù)數(shù)DFT［1］.

隨著高性能科學(xué)計(jì)算的要求和嵌入式技術(shù)的發(fā)展，不僅產(chǎn)生了多種基于DSP或FPGA的并行FFT實(shí)現(xiàn)［2］，而且還出現(xiàn)了多種適于不同并行體系結(jié)構(gòu)及編程模型的并行FFT算法［3－5］.文獻(xiàn)［6］對(duì)FFT并行化思想進(jìn)行了簡(jiǎn)要的總結(jié)與分析，面向集群設(shè)備給出了基于消息傳遞接口（MPI）的典型并行FFT算法，是目前針對(duì)因高性價(jià)比而受到用戶青睞的集群并行設(shè)備實(shí)現(xiàn)并行FFT的重要參考.

目前，基于圖形硬件（GPU）的通用計(jì)算正成為并行領(lǐng)域的研究熱點(diǎn).特別是NVidia公司于2007年推出統(tǒng)一計(jì)算設(shè)備架構(gòu)（CUDA）后，極大增強(qiáng)了GPU的通用計(jì)算能力，在編程、優(yōu)化等方面都得到了顯著的提升.同時(shí)，NVidia公司基于CUDA也推出了面向GPU的并行FFT算法，即CUFFT.肖江等針對(duì)矩陣乘法以及CUFFT進(jìn)行了計(jì)算性能測(cè)試［7］.但是更詳盡的性能分析，以及與其他典型并行體系結(jié)構(gòu)下的并行FFT算法的比較還很少見(jiàn).

本文以串行FFTW作為基準(zhǔn)，對(duì)CUFFT、基于集群與MPI的典型并行FFT算法進(jìn)行了計(jì)算能力以及通信開(kāi)銷的詳細(xì)比較，以期為各種算法的性能特點(diǎn)及適用場(chǎng)合提供更翔實(shí)的應(yīng)用參考.

1 FFT的并行性分析

FFT的基－2并行計(jì)算過(guò)程如圖1所示［5］.節(jié)點(diǎn)｛i，0｝（N／2≤i≤N－1）將接受直線邊傳來(lái)的數(shù)據(jù)與交叉邊傳來(lái)的數(shù)據(jù)，通過(guò)兩點(diǎn)FFT蝶形計(jì)算方法可求出下一列向量.以此類推，直到第logN列才變?yōu)橛迷枷蛄窟M(jìn)行計(jì)算.所以，經(jīng)過(guò)logN步并行計(jì)算后，即可計(jì)算出一個(gè)N點(diǎn)一維FFT.

圖1中數(shù)據(jù)量為8，并行節(jié)點(diǎn)數(shù)為4.一般地，若數(shù)據(jù)量為DataSize，并行處理機(jī)節(jié)點(diǎn)數(shù)為T(mén)askNum，則log2DataSize至log2TaskNum列都是單機(jī)的串行處理，從log2TaskNum列至0列是并行處理.經(jīng)過(guò)這樣的遞歸計(jì)算，最終把結(jié)果數(shù)據(jù)計(jì)算出來(lái).在此過(guò)程中，并行計(jì)算節(jié)點(diǎn)之間需要進(jìn)行數(shù)據(jù)傳遞，且在每一個(gè)循環(huán)階段，都要進(jìn)行同步，才可以進(jìn)行下一步.

圖1 FFT并行計(jì)算蝶形示意圖

在具體實(shí)現(xiàn)FFT并行計(jì)算過(guò)程時(shí)，集群設(shè)備通常采用消息傳遞機(jī)制，通過(guò)普通以太網(wǎng)絡(luò)或?qū)Ｓ肐nfiniband網(wǎng)絡(luò)在各計(jì)算節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)傳輸，因此需要較多的通信開(kāi)銷.而圖形設(shè)備（顯卡）在進(jìn)行并行計(jì)算時(shí)，采用共享內(nèi)存型的計(jì)算模式.特別地，CUDA還提供了全局存儲(chǔ)器、共享存儲(chǔ)器、本地存儲(chǔ)器等多種存儲(chǔ)器方案，便于性能調(diào)節(jié)與優(yōu)化.與消息傳遞型相比，GPU的通信主要在圖形硬件（顯卡）的板級(jí)，因此通信更可靠且更快速.

2 并行FFT的性能測(cè)試及分析

2.1 測(cè)試方案

2.1.1 測(cè)試環(huán)境

單計(jì)算機(jī)硬件環(huán)境為CPU Intel Pentium Dual E2160 1.80GHZ，內(nèi)存1G；軟件環(huán)境為 WinXP操作系統(tǒng)；顯卡為NVIDIA公司的GeForce 8400GT，支持CUDA技術(shù)；集群環(huán)境為22個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)由2個(gè)2.8GHz處理器組成，內(nèi)存總量為22G，Infiniband專用網(wǎng)絡(luò)；分別選用了FFTW庫(kù)與CUFFT庫(kù)；編譯環(huán)境為Micorsoft Visul Studio 2005.

由于當(dāng)數(shù)據(jù)量為2的冪次方時(shí)，F(xiàn)FT的速度最快，本文對(duì)4組二維實(shí)驗(yàn)數(shù)據(jù)進(jìn)行FFT運(yùn)算，通過(guò)對(duì)給定同樣大小的數(shù)組數(shù)據(jù)進(jìn)行處理的時(shí)間來(lái)進(jìn)行比較.

2.1.2 測(cè)試對(duì)象

本文對(duì)目前比較重要的并行FFT算法進(jìn)行測(cè)試.因此，選擇面向集群及MPI實(shí)現(xiàn)的典型FFT算法和面向GPU的CUFFT進(jìn)行比較測(cè)試，代表了目前高性能計(jì)算領(lǐng)域2種非?；钴S而且通用的并行體系結(jié)構(gòu).為更好地分析并行性能，仍以串行FFTW算法作為測(cè)試基準(zhǔn).

（1）FFTW庫(kù)程序.FFTW是世界上公認(rèn)的運(yùn)算較快的FFT，也是使用很廣泛的傅立葉變換程序.具體實(shí)現(xiàn)如下：

首先載入數(shù)組數(shù)據(jù)，再建立二維FFTW plan進(jìn)行數(shù)據(jù)處理.主要程序如下：

in＝ （fftw＿complex＊）fftw＿malloc（sizeof（fftw＿real）＊Nx＊Ny）；

out＝ （fftw＿complex＊）fftw＿malloc（sizeof（fftw＿complex）＊Nx＊Ny）；

給輸入和輸出的數(shù)據(jù)申請(qǐng)內(nèi)存，這里Nx和Ny分別表示數(shù)組的行和列的大小，執(zhí)行plan，完成FFT；

p＝fftw＿plan＿dft＿2d（NNx，NNy，in，out，F(xiàn)FTW＿FORWARD，F(xiàn)FTW＿ESTIMATE）.

這里，F(xiàn)FTW＿ESTIMATE也可換為FFTW＿M(jìn)EASRUE，F(xiàn)FTW＿ESTIMATE會(huì)更快一些.但如果要處理很多同樣大小的數(shù)據(jù)，用FFTW＿M(jìn)EASRUE會(huì)更好一些，因?yàn)槿绻肍FTW＿M(jìn)EASRUE模式創(chuàng)建一個(gè)最優(yōu)方案后，只要數(shù)據(jù)大小不變，在下一次啟用時(shí)會(huì)啟動(dòng)之前創(chuàng)建好的plan，這同樣是最優(yōu)方案.

當(dāng)數(shù)據(jù)大小為1024＊1024時(shí)，F(xiàn)FTW＿M(jìn)EASRUE和FFTW＿ESTIMATE運(yùn)行結(jié)果如圖2所示.

圖2 FFTW＿ESTIMATE與FFTW＿M(jìn)EASRUE運(yùn)行結(jié)果比較

（2）CUFFT.CUFFT是由NVIDIA提供的基于GPU的快速傅里葉變換（FFT）函數(shù)庫(kù).它采用分治的算法，對(duì)數(shù)據(jù)能夠在實(shí)數(shù)與復(fù)數(shù)域進(jìn)行FFT運(yùn)算.CUFFT提供了以下功能：

可以對(duì)實(shí)數(shù)或復(fù)數(shù)進(jìn)行一維或多維的DFT，可以同時(shí)處理一批一維DFT；

對(duì)二位和三維的傅里葉變換，每個(gè)維度長(zhǎng)度在［2，16384］中取值.

具體實(shí)現(xiàn)如下：

首先，需要將文檔中的數(shù)據(jù)載入GPU內(nèi)存中，分別對(duì)＊idata和＊odata定義并申請(qǐng)存儲(chǔ)空間：

cufftReal＊idata；cufftComplex＊odata；

cudaMalloc（（void＊＊）＆idata，sizeof（cufftReal）＊Nx＊Ny）；

cufftMalloc（（void＊ ＊）＆odata，sizeof（cufft－Complex）＊Nx＊Ny）；

定義plan，創(chuàng)建plan：

cufftHandle plan；cufftPlan2d（＆plan，Nx，Ny，CURRT＿R2C）；

完成FFT變換：

cufftExecR2C（plan，idata，odata，CUFFT＿FORWARD）；

當(dāng)數(shù)據(jù)大小為1024＊1024時(shí)，運(yùn)行結(jié)果如圖3所示.

圖3 CUFFT運(yùn)行結(jié)果

（3）基于 MPI的并行FFT.MPI（Message Passing Interface）是一個(gè)庫(kù)，F(xiàn)FTW3支持基于MPI的并行編程.具體實(shí)現(xiàn)如下：

調(diào)用頭文件＜fftw＿mpi.h＞，創(chuàng)建計(jì)劃：

fftw＿mpi＿plan fftw＿mpi＿create＿plan（MPI＿Comm comm，int n，F(xiàn)FTW＿FORWARD，F(xiàn)FTW＿ESTIMATE）；

通過(guò)調(diào)用函數(shù)來(lái)進(jìn)行變換，調(diào)用的函數(shù)為：void fftw＿mpi（fftw＿mpi＿plan p，int n＿fields，fftw＿complex＊local＿data，fftw＿complex＊work）；

返回時(shí)調(diào)用函數(shù)：void fftw＿mpi＿local＿sizes（fftw＿mpi＿plan p，int＊local＿n，int＊local＿start，int＊local＿n＿after＿transform，int＊local＿start＿after＿transform，int＊total＿local＿size）.

2.2 計(jì)算能力比較

測(cè)試結(jié)果如圖4所示.

從圖4可以看出，隨著數(shù)據(jù)量的增大（矩陣的行列分別為256，512，1024，2048），并行計(jì)算的優(yōu)勢(shì)越發(fā)明顯，MPI－FFT和CUFFT一般比FFTW的運(yùn)算速度提高30～80倍；MPI和GPU的計(jì)算時(shí)耗在數(shù)據(jù)規(guī)模較小時(shí)相差不大，隨著數(shù)據(jù)規(guī)模的增加，GPU計(jì)算要稍快.但對(duì)于超大規(guī)模數(shù)據(jù)，GPU由于受到硬件容量限制，其并行性能落后于集群設(shè)備.由于GPU的造價(jià)相對(duì)于集群設(shè)備MPI更加低廉，普通用戶也可以享用多節(jié)點(diǎn)并行的技術(shù)優(yōu)勢(shì)，因此對(duì)于中小規(guī)模計(jì)算具有更高的性價(jià)比.但對(duì)于超大數(shù)據(jù)量計(jì)算時(shí)，一般會(huì)選擇基于MPI的集群設(shè)備.

圖43種FFT測(cè)試結(jié)果

2.3 通信開(kāi)銷

通信開(kāi)銷對(duì)比如圖5所示.在追求減少計(jì)算用時(shí)的算法研究的同時(shí)，用于計(jì)算過(guò)程中的數(shù)據(jù)傳遞所用的時(shí)間，即通信開(kāi)銷，也是必須要重視的因素.在CUDA的GPU運(yùn)算中，通信的時(shí)間主要是發(fā)生在從內(nèi)存拷貝數(shù)據(jù)到GPU的全局存儲(chǔ)器上；基于MPI的并行計(jì)算，它的通信時(shí)間是在每一級(jí)運(yùn)算完畢后，再把數(shù)據(jù)分別傳遞給既定的下一級(jí)節(jié)點(diǎn)上用的時(shí)間.

圖5 通信開(kāi)銷

本文MPI選取的處理節(jié)點(diǎn)數(shù)為16，通過(guò)圖5可以看出（處理節(jié)點(diǎn)個(gè)數(shù)n＝16），MPI的通信開(kāi)銷是比較大的，這也影響了MPI并行計(jì)算的效率.而GPU計(jì)算的通信時(shí)間相對(duì)地要少得多，GPU計(jì)算在通信開(kāi)銷方面有很大優(yōu)勢(shì).

3 結(jié) 語(yǔ)

本文對(duì)FFTW、CUFFT以及 MPI－FFT等3種FFT實(shí)現(xiàn)方案進(jìn)行了性能測(cè)試.通過(guò)計(jì)算用時(shí)和通信開(kāi)銷兩方面的比較可以看出，基于GPU的CUFFT性能在中小數(shù)據(jù)規(guī)模情況下略高于基于MPI的FFT，具有較高的性價(jià)比.目前國(guó)內(nèi)CUDA技術(shù)的發(fā)展研究正逐漸興盛起來(lái)，相比較于大型計(jì)算機(jī)，CUDA技術(shù)使得人們?cè)趥€(gè)人PC機(jī)上也能高效地實(shí)現(xiàn)大量數(shù)據(jù)運(yùn)算，這也將吸引人們投入更多的精力致力于CUDA技術(shù)的研究發(fā)展.從這個(gè)意義上說(shuō)，CUFFT具有更好的應(yīng)用前景.

［1］ Matteo Frigo，Steven G Johnson.The Design and Implementation of FFTW3［J］.Proceedings of the IEEE，2005，93（2）：216－231.

［2］ 朱林，王志凌，黃天戍.基于DSP并行系統(tǒng)的FFT算法實(shí)現(xiàn)［J］.武漢理工大學(xué)學(xué)報(bào)，2009，31（20）：102－104，120.

［3］ 于澤德.基于SIMD－MC2的并行FFT算法［J］.現(xiàn)代計(jì)算機(jī)（專業(yè)版），2008（10）：57－58.

［4］ 劉文輝.基于SIMD－BF的并行FFT算法［J］.商丘師范學(xué)院學(xué)報(bào)，2003，19（5）：63－63.

［5］ 孫世新，盧光輝，張艷，等.并行算法及其應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2005.

［6］ 張林波，遲學(xué)斌，莫?jiǎng)t堯，等.并行計(jì)算導(dǎo)論［M］.北京：清華大學(xué)出版社，2006.

［7］ 肖江，胡柯良，鄧元勇.基于CUDA的矩陣乘法和FFT性能測(cè)試.［J］計(jì)算機(jī)工程，2009，35（10）：7－10.

［8］ 張舒，褚艷利，趙開(kāi)勇，等.GPU高性能運(yùn)算之CUDA［M］.北京：中國(guó)水利水電出版社，2009：10.

Parallel Performance Analysis of FFT Algorithm

WANG Lu，LIANG Tao，WANG Wen－yi
（Zhongyuan University of Technology，Zhengzhou 450007，China）

Performance analysis is the basis of parallel program before applied practically.This paper compares a set of parallel Fast Fourier Transform （FFT）algorithm including FFTW，CUFFT Library and MPI－FFT.Experiments show that parallel program can achieve 30to 80times than serial program （FFTW）in speed.And CUFFT is better than FFT based on MPI in large scale data computing.It has less communication overhead distinctively.

parallel performance analysis；CUFFT；MPI；FFTW

TP391

A

10.3969／j.issn.1671－6906.2010.05.008

1671－6906（2010）05－0030－03

2010－09－29

河南省教育廳自然科學(xué)研究項(xiàng)目（2009A520034）

王 璐（1972－），男，遼寧清原人，副教授，博士.