李 琨，賈海鵬，曹 婷，張?jiān)迫?/p>

1.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190

2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100190

大規(guī)模集群上多維FFT算法的實(shí)現(xiàn)與優(yōu)化研究*

李 琨1,2+，賈海鵬1，曹 婷1，張?jiān)迫?

1.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190

2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 100190

LI Kun,JIA Haipeng,CAO Ting,et al.Implementation and optimization of multidimensional FFT algorithm on large-scale clusters.Journal of Frontiers of Computer Science and Technology,2017,11(6)：863-874.

快速傅里葉變換（fast Fourier transform，F(xiàn)FT）是用于計(jì)算離散傅里葉變換（discrete Fourier transform，DFT）或其逆運(yùn)算的快速算法，在工程、科學(xué)和數(shù)學(xué)領(lǐng)域的應(yīng)用非常廣泛，例如信號(hào)分解、數(shù)字濾波、圖像處理等。因此，在實(shí)際應(yīng)用中對(duì)FFT算法進(jìn)行細(xì)粒度優(yōu)化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大規(guī)模集群系統(tǒng)上的并行實(shí)現(xiàn)，并提出了相關(guān)的優(yōu)化策略。在此基礎(chǔ)上，對(duì)多種FFT算法在不同平臺(tái)上進(jìn)行了性能評(píng)估，并分析了各算法的實(shí)現(xiàn)、優(yōu)缺點(diǎn)及其在大規(guī)模計(jì)算時(shí)的可擴(kuò)展性。實(shí)驗(yàn)結(jié)果表明，相關(guān)研究有助于對(duì)現(xiàn)有的FFT算法進(jìn)行進(jìn)一步的優(yōu)化，以及指導(dǎo)如何在大規(guī)模CPU+GPU的異構(gòu)系統(tǒng)上根據(jù)不同需求選擇實(shí)現(xiàn)性能更優(yōu)的FFT算法。

集群；快速傅里葉變換（FFT）；消息傳遞接口（MPI）；性能優(yōu)化

1 引言

快速傅里葉變換（fast Fourier transform，F(xiàn)FT），是用于計(jì)算序列的離散傅里葉變換（discrete Fourier transform，DFT）或其逆變換的一種高效算法。FFT被廣泛應(yīng)用于工程、科學(xué)和數(shù)學(xué)領(lǐng)域，如在國(guó)際大科學(xué)工程平方公里陣列射電望遠(yuǎn)鏡（square kilometer array，SKA）[1]的數(shù)據(jù)處理中，F(xiàn)FT占總計(jì)算量的40%，且由于其每秒TB級(jí)的數(shù)據(jù)量及底層高性能計(jì)算機(jī)系統(tǒng)的規(guī)模和復(fù)雜度，對(duì)FFT算法的計(jì)算效能提出了更高的要求，需針對(duì)性地研究相應(yīng)的方法。鑒于此，本文簡(jiǎn)要介紹了FFT的經(jīng)典算法——庫(kù)利圖基算法，針對(duì)集群系統(tǒng)研究了并行FFT算法現(xiàn)存的瓶頸以及相應(yīng)的優(yōu)化策略，最后完整地將FFTW庫(kù)（faster Fourier transform in the West）、PFFT庫(kù)（parallel FFT library）與MPFFT庫(kù)（massive parallel FFT library）3種算法在不同平臺(tái)上進(jìn)行了性能評(píng)估與分析。

本文的主要?jiǎng)?chuàng)新點(diǎn)如下：

（1）分析了PFFT和MPFFT算法的優(yōu)化現(xiàn)狀，指出目前大規(guī)模集群上FFT算法存在的兩點(diǎn)可優(yōu)化方向，一是數(shù)據(jù)在主存和設(shè)備內(nèi)存間的不斷通信，使得PCI-E總線帶寬成為了性能瓶頸；二是在數(shù)據(jù)輸出的同時(shí)可以進(jìn)行細(xì)節(jié)上的處理，以更細(xì)致的劃分方式避免最后數(shù)據(jù)的整體調(diào)整。

（2）在深入分析目前主流的幾種FFT算法基礎(chǔ)上，研究了一維分解、二維分解的優(yōu)化策略，并提出了通信優(yōu)化和輸出優(yōu)化兩種改進(jìn)方案。通信優(yōu)化將數(shù)據(jù)在CPU和GPU間的傳輸進(jìn)行了更細(xì)致的分解，將有效地提高整體的通信效率，減少全局轉(zhuǎn)置所需的時(shí)間；輸出優(yōu)化在每一塊數(shù)據(jù)進(jìn)行FFT計(jì)算的同時(shí)確定好最優(yōu)的內(nèi)存分布位置，便于對(duì)計(jì)算后的數(shù)據(jù)進(jìn)行排列，如此可使得FFT計(jì)算的同時(shí)進(jìn)行數(shù)據(jù)的整理，減少額外進(jìn)行轉(zhuǎn)置的開(kāi)銷。

（3）在單節(jié)點(diǎn)平臺(tái)和天河一號(hào)、天河二號(hào)超級(jí)計(jì)算機(jī)上通過(guò)對(duì)各種規(guī)模輸入數(shù)據(jù)進(jìn)行大量的測(cè)試和統(tǒng)計(jì)，詳細(xì)地評(píng)估與分析了3種主流FFT算法的性能、可擴(kuò)展性以及各算法的最佳適應(yīng)環(huán)境，為FFT在大規(guī)模計(jì)算時(shí)的算法選擇提供了參考。實(shí)驗(yàn)表明，在大多數(shù)情況下PFFT算法與MPFFT算法要優(yōu)于FFTW算法，且當(dāng)輸入數(shù)據(jù)量較小時(shí)，MPFFT算法性能優(yōu)勢(shì)相對(duì)明顯；輸入數(shù)據(jù)量較大時(shí)，PFFT算法性能優(yōu)勢(shì)則相對(duì)明顯。另外，這種性能優(yōu)勢(shì)會(huì)隨著進(jìn)程數(shù)量的增加而更為突出，當(dāng)進(jìn)程數(shù)量較小時(shí)，3種算法的性能優(yōu)劣對(duì)比并不明顯。

本文組織結(jié)構(gòu)如下：第2章介紹了相關(guān)工作；第3章介紹了FFT的庫(kù)利圖基算法；第4章對(duì)FFTW、PFFT、MPFFT算法的分解策略和實(shí)現(xiàn)方法進(jìn)行了分析，針對(duì)3種算法的性能瓶頸提出了兩種優(yōu)化策略；第5章在單節(jié)點(diǎn)和大規(guī)模集群上使用不同的輸入規(guī)模對(duì)3種算法進(jìn)行了性能評(píng)估和性能分析；第6章進(jìn)行了總結(jié)討論。

2 相關(guān)工作

目前常用的FFT庫(kù)有FFTW[2]、PFFT[3]、MPFFT[4]、CUFFT[5]（CUDA fast Fourier transform library）、PKUFFT[6-7]（Peking University fast Fourier transform library）等。Frigo和Johnson開(kāi)發(fā)的FFTW庫(kù)可以計(jì)算一維或者多維實(shí)數(shù)據(jù)、復(fù)數(shù)據(jù)的離散傅里葉變換，其具備自適應(yīng)性，并為各種領(lǐng)域內(nèi)所需的FFT計(jì)算提供了基本的運(yùn)行框架。PFFT算法是在FFTW庫(kù)上的拓展，其加強(qiáng)了FFTW軟件庫(kù)的MPI（message passing interface）部分以適于多維的數(shù)據(jù)分解，即規(guī)模為Nd的d維FFT可以至多被Nd-1個(gè)MPI進(jìn)程并行計(jì)算[8]。中國(guó)科學(xué)院李焱等人提出了FFT針對(duì)GPU平臺(tái)的自適應(yīng)性能優(yōu)化框架和針對(duì)CPU和GPU異構(gòu)集群的MPFFT軟件包，融合了異構(gòu)平臺(tái)的硬件異同和FFT算法的特性，使得FFT在這些平臺(tái)都能取得良好的加速效果[4]。CUFFT是NVIDIA SDK中提供的FFT庫(kù)，它的API接口與FFTW比較相像，包括FFT plan的搜索階段和執(zhí)行階段。另外陳一峯等人通過(guò)將數(shù)據(jù)各維度進(jìn)行細(xì)粒度劃分，利用GPU通信緩沖區(qū)與GPU Pinned Memory之間拷貝的機(jī)會(huì)對(duì)數(shù)據(jù)進(jìn)行粒度上的調(diào)整來(lái)優(yōu)化AlltoAll通信，使得PKUFFT取得了較高的性能[6]。

與以上工作不同，本文分析了各種庫(kù)的并行分解策略以及各自的優(yōu)勢(shì)和不足，從通信、輸出等多方面對(duì)FFTW、PFFT、MPFFT算法提出了可能的改進(jìn)方案，并對(duì)3種算法在大規(guī)模集群上的性能進(jìn)行了全面的評(píng)測(cè)和分析，所得結(jié)果可為3種算法今后的優(yōu)化方向及在大規(guī)模計(jì)算時(shí)FFT算法的選擇提供參考。

3 背景介紹

3.1 快速傅里葉變換

離散傅里葉變換在計(jì)算機(jī)科學(xué)、物理學(xué)等學(xué)科中扮演著非常關(guān)鍵的角色。對(duì)于長(zhǎng)度為N的復(fù)數(shù)序列x，其中x=x0,x1,…,xn-1，DFT的計(jì)算公式[9]為：

根據(jù)式（1），可以發(fā)現(xiàn)Xk共有N次輸出結(jié)果，每一次的輸出都有N次的累加求和運(yùn)算，若按照DFT的定義進(jìn)行計(jì)算求值需O(n2)次運(yùn)算。在實(shí)際應(yīng)用中，F(xiàn)FT算法通常被用于DFT變換。原因有兩點(diǎn)：一是FFT算法在求解過(guò)程中會(huì)有舍入誤差的存在，因此許多FFT算法運(yùn)行后的結(jié)果甚至比用定義進(jìn)行求解的結(jié)果要精確很多；二是FFT算法的運(yùn)算速度更快，所有的FFT算法的復(fù)雜度均可在對(duì)數(shù)時(shí)間復(fù)雜度內(nèi)完成[10]。FFT已經(jīng)有很多成熟的算法，在所有的FFT算法中，庫(kù)利圖基算法應(yīng)用最廣、最流行，是眾多算法庫(kù)實(shí)現(xiàn)的基礎(chǔ)，故下文將簡(jiǎn)要地介紹庫(kù)利圖基算法。

3.2 庫(kù)利圖基快速傅里葉變換算法

庫(kù)利圖基快速傅里葉變換算法（Cooley-Tukey算法）[11]是目前應(yīng)用最廣泛、最流行的FFT算法。利用式（1），將公式中的項(xiàng)目在時(shí)域上進(jìn)行重新分組，并將進(jìn)行替換，其中替換后的被稱為“旋轉(zhuǎn)因子”（twiddle factor），亦稱為“蝶形因子”。根據(jù)旋轉(zhuǎn)因子在計(jì)算過(guò)程中出現(xiàn)的不同位置，可以將FFT算法分為時(shí)域抽?。╠ecimation-in-time，DIT）和頻域抽?。╠ecimation-in-frequency，DIF）兩大類。DIT的旋轉(zhuǎn)因子出現(xiàn)在計(jì)算的輸入端，而DIF的旋轉(zhuǎn)因子則出現(xiàn)在計(jì)算的輸出端。

以DIT為例，將旋轉(zhuǎn)因子替換后，DIT是將長(zhǎng)度為N的復(fù)數(shù)序列x根據(jù)數(shù)據(jù)的偶數(shù)項(xiàng)和奇數(shù)項(xiàng)進(jìn)行分解，分解后的式（1）將成為偶序列與奇序列兩部分。其中偶序列為x0,x2,x4,…,xn-2，奇序列為x1,x3, x5,…,xn-1，運(yùn)算如式（2）：

其中k=0,1,…,N-1。

因?yàn)镚k與Hk具有周期性，WN具有對(duì)稱性和周期性，所以可得：

按照同樣的方式，對(duì)式（3）中的Gk與Hk也繼續(xù)以相同的方式分解，則可將一個(gè)N點(diǎn)的離散傅里葉變換最終用一組兩點(diǎn)的DFT來(lái)計(jì)算。在基數(shù)為2的快速傅里葉變換中，共有l(wèi)bN級(jí)運(yùn)算，而且在每一級(jí)的計(jì)算中有(N/2)個(gè)兩點(diǎn)FFT蝶形運(yùn)算[12]。因此采用該FFT算法的復(fù)雜度將直接降為O(nlbn)。

4 并行FFT優(yōu)化分析及策略

4.1 優(yōu)化分析

對(duì)于許多應(yīng)用，F(xiàn)FT算法的輸入并不能完全只在一個(gè)單節(jié)點(diǎn)上進(jìn)行，因此對(duì)輸入數(shù)據(jù)勢(shì)必要?jiǎng)澐值礁鱾€(gè)節(jié)點(diǎn)上運(yùn)算以提高效率。每個(gè)子任務(wù)計(jì)算自己的FFT部分，之后再將數(shù)據(jù)與其他子任務(wù)進(jìn)行交換。實(shí)現(xiàn)該操作的策略有一維分解和二維分解。

對(duì)于異構(gòu)平臺(tái)上的應(yīng)用，一個(gè)比較普遍的問(wèn)題是哪一種任務(wù)適于使用GPU設(shè)備進(jìn)行加速。GPU適合處理計(jì)算密集型或者訪存密集型的任務(wù)，其他任務(wù)，例如Internet帶寬，存儲(chǔ)設(shè)備的讀、寫(xiě)帶寬以及通信延遲等都是不能被GPU加速的。

對(duì)于小規(guī)模的FFT，如果數(shù)據(jù)能夠被全部地置于GPU設(shè)備上，那么此時(shí)的計(jì)算就會(huì)從設(shè)備內(nèi)存的高帶寬中受益。這種方案是有特定情景的，即大部分的數(shù)據(jù)都置于設(shè)備的內(nèi)存上，并且FFT在這些數(shù)據(jù)上運(yùn)算了多次。這時(shí)數(shù)據(jù)在主存和設(shè)備內(nèi)存間的通信開(kāi)銷與GPU的計(jì)算時(shí)間相比就可以忽略了。

然而，對(duì)于大規(guī)模的FFT，數(shù)據(jù)需要在主存和設(shè)備內(nèi)存間不斷通信，PCI-E總線帶寬就會(huì)成為瓶頸。因?yàn)榇藭r(shí)通過(guò)PCI-E總線的數(shù)據(jù)傳輸時(shí)間要比在GPU的計(jì)算時(shí)間長(zhǎng)得多。這種方案也是有特定情景的，即針對(duì)的是在節(jié)點(diǎn)上計(jì)算大規(guī)模FFT，所有數(shù)據(jù)必須在不同的節(jié)點(diǎn)之間、在主存和設(shè)備內(nèi)存之間來(lái)回傳輸?shù)臅r(shí)候，如果能對(duì)各節(jié)點(diǎn)間的通信、GPU與CPU間的通信進(jìn)行優(yōu)化，將會(huì)大幅提高整體的計(jì)算效率。

4.2 優(yōu)化策略

4.2.1 一維分解

一維分解是基于轉(zhuǎn)置的并行FFT分解策略，該分解策略已在FFTW算法庫(kù)[8]中實(shí)現(xiàn)。以三維輸入數(shù)據(jù)為例，假設(shè)三維的輸入數(shù)據(jù)大小n0×n1×n2，其中n0≥n1≥n2。假定MPI進(jìn)程的數(shù)量為P，則首先沿著n0方向進(jìn)行分解，將數(shù)據(jù)切分到P個(gè)MPI進(jìn)程上，這P個(gè)進(jìn)程并行地計(jì)算n0/P組大小為n1×n2的二維FFT。此時(shí)，n0維的數(shù)據(jù)已被切分分布于所有的P個(gè)進(jìn)程上，故n0維數(shù)據(jù)的計(jì)算需使用AlltoAll的MPI函數(shù)對(duì)數(shù)據(jù)交換轉(zhuǎn)置以完成n0維數(shù)據(jù)的計(jì)算[2]。

MPI_ALLTOALL函數(shù)是對(duì)MPI_ALLGATHER的擴(kuò)展，兩者的區(qū)別是調(diào)用MPI_ALLTOALL時(shí)每個(gè)接收者可接收來(lái)自別的發(fā)送者的數(shù)目不同的數(shù)據(jù)。例如，第m個(gè)進(jìn)程發(fā)送的第n塊數(shù)據(jù)將被第n個(gè)進(jìn)程接收并存放在其接收消息緩沖區(qū)recv_buffer的第m塊上。

一維分解較為簡(jiǎn)單，然而采用該策略進(jìn)行實(shí)現(xiàn)的庫(kù)在可擴(kuò)展性方面存在很大的不足，它要求P=n0，n0=max{n0,n1,n2}。當(dāng)P>n0時(shí)，一維分解將不能被使用。另外當(dāng)P>n1或P>n2時(shí)，數(shù)據(jù)分解所使用的進(jìn)程數(shù)P將受限于n1或n2。數(shù)據(jù)轉(zhuǎn)置之后，多余的進(jìn)程數(shù)將會(huì)空閑得不到利用。因此，對(duì)數(shù)據(jù)的劃分需要采用更多維來(lái)進(jìn)行計(jì)算[4]。圖1為一維分解示意圖。

Fig.1 One-dimension decomposition strategy圖1 一維分解策略

4.2.2 二維分解

二維分解[3]相較于一維分解很好地解決了可擴(kuò)展性不足這一嚴(yán)重的弊端，故在大規(guī)模集群上也應(yīng)用得比較普遍。圖2即為二維分解的效果圖。該分解策略首先由Ding等人提出，后來(lái)Eleftheriou等人引入了體區(qū)域分解（volumetric domain decomposition）的概念，其在本質(zhì)上使用的還是二維分解，即將輸入數(shù)組首先沿n0和n1進(jìn)行分解，因此這種分解策略允許增加的MPI進(jìn)程數(shù)目最多可達(dá)n0×n1。因?yàn)檩斎氲臄?shù)據(jù)僅有一維數(shù)據(jù)位于本地進(jìn)程中，所以每次變換需進(jìn)行多次的數(shù)據(jù)交換轉(zhuǎn)置，包括本地的數(shù)據(jù)轉(zhuǎn)置和全局的數(shù)據(jù)轉(zhuǎn)置。

Fig.2 Tow-dimension decomposition strategy圖2 二維分解策略

對(duì)于規(guī)模為n0×n1×n2的輸入，二維分解會(huì)將其并行地分布于P=P0×P1個(gè)進(jìn)程上，每個(gè)進(jìn)程首先會(huì)得到大小為n2的二維條，圖3表示的就是將輸入數(shù)據(jù)分布到4×4的進(jìn)程網(wǎng)格上。為了計(jì)算三維FFT，算法將沿著n2維進(jìn)行一批FFT計(jì)算，之后進(jìn)行全局轉(zhuǎn)置操作，以使得每個(gè)進(jìn)程在本地得到第二維的數(shù)據(jù)。類似的操作會(huì)再次進(jìn)行以得到第一維的數(shù)據(jù)，最終的輸出分布形式為此時(shí)輸出的內(nèi)存排列與輸入時(shí)是不一致的，差別為輸入數(shù)組沿著第一和第二個(gè)維度分布，而輸出數(shù)組則沿著第二和第三維度分布，如圖4所示。PFFT、MPFFT算法在此之后會(huì)在輸出數(shù)組上進(jìn)行內(nèi)存布局的調(diào)整，以使最后的輸出維度的分布也與輸入時(shí)一致。

Fig.3 Input data distributed on 16 processes initially(4×4 process grid)圖3 初始時(shí)輸入數(shù)據(jù)分布于16個(gè)進(jìn)程上（4×4進(jìn)程網(wǎng)格）

Fig.4 Input data distributed on 16 processes at the end(4×4 process grid)圖4 結(jié)束時(shí)輸入數(shù)據(jù)分布于16個(gè)進(jìn)程上（4×4進(jìn)程網(wǎng)格）

4.2.3 通信優(yōu)化

基于上面的分解策略，F(xiàn)FTW庫(kù)采用了一維分解，PFFT和MPFFT庫(kù)采用了二維分解。FFTW和PFFT算法未進(jìn)行通信方面的優(yōu)化。MPFFT算法在每維FFT計(jì)算時(shí)直接調(diào)用NVIDIA CUFFT庫(kù)，之后進(jìn)行本地轉(zhuǎn)置，由于此時(shí)轉(zhuǎn)置所需的數(shù)據(jù)全部位于GPU中，故其是借助GPU上的矩陣轉(zhuǎn)置函數(shù)來(lái)提高性能。之后與CPU通信時(shí)的全局轉(zhuǎn)置是通過(guò)封裝FFTW中相關(guān)接口直接實(shí)現(xiàn)，并未進(jìn)行更進(jìn)一步的優(yōu)化。而在大規(guī)模計(jì)算FFT時(shí)，顯然這將會(huì)成為一個(gè)限制效率的瓶頸。

基于此可以考慮將需要傳送拷貝的數(shù)據(jù)劃分為相同大小的數(shù)據(jù)塊[13]。通過(guò)異步通信的方式，一次將一個(gè)數(shù)據(jù)塊拷貝到CPU內(nèi)存中，此時(shí)CPU間的通信便可以開(kāi)始，同時(shí)其他的數(shù)據(jù)塊也以異步的方式傳輸?shù)紺PU內(nèi)存。也可以調(diào)用異步接收指令，這樣數(shù)據(jù)接收操作與數(shù)據(jù)塊從設(shè)備向主存的拷貝操作同時(shí)進(jìn)行。同時(shí)，每個(gè)接收的數(shù)據(jù)塊之后可以異步地拷回到GPU設(shè)備中，這樣便可有效地提高通信效率，減少全局轉(zhuǎn)置所需的時(shí)間。圖5展示了對(duì)于P=4時(shí)all-to-all的過(guò)程。4×4矩陣中的每個(gè)元素代表了存儲(chǔ)的數(shù)據(jù)塊。表示從進(jìn)程i到進(jìn)程j的一個(gè)發(fā)送指令，表示進(jìn)程j接收來(lái)自進(jìn)程i的消息。

Fig.5 Communication optimization圖5 通信優(yōu)化示意圖

4.2.4 輸出優(yōu)化

假設(shè)用T0代表本地轉(zhuǎn)置，用T1代表全局轉(zhuǎn)置，以0代表經(jīng)FFT計(jì)算后的n0。在運(yùn)算過(guò)程中，初始的輸入分布可表示為采用二維分解策略，經(jīng)過(guò)一系列計(jì)算后得到的輸出分布為此后，一部分FFT算法，例如PFFT、MPFFT算法，將在此輸出形式上進(jìn)行多次轉(zhuǎn)置計(jì)算以改變其內(nèi)存布局[14-15]，轉(zhuǎn)換過(guò)程可表示如下：

經(jīng)過(guò)多次的本地轉(zhuǎn)置和全局轉(zhuǎn)置，可以將輸出的分布形式完全轉(zhuǎn)化為和初始的輸入分布一致，即為然而這種轉(zhuǎn)化是在已經(jīng)得到正確的輸出結(jié)果之上所做的進(jìn)一步的整理工作，這種額外的數(shù)據(jù)整理又會(huì)增加一些計(jì)算和通信上的開(kāi)銷，而這種開(kāi)銷理論上也可以進(jìn)行進(jìn)一步的分析優(yōu)化。在不可避免使用全局轉(zhuǎn)置的地方盡量以塊劃分的異步通信策略進(jìn)行優(yōu)化，而在每一維度上進(jìn)行轉(zhuǎn)置來(lái)計(jì)算FFT的時(shí)候可以進(jìn)行更為細(xì)致的粒度劃分，即在每一塊數(shù)據(jù)進(jìn)行FFT計(jì)算的同時(shí)確定好最優(yōu)的內(nèi)存分布位置，便于對(duì)計(jì)算后的數(shù)據(jù)進(jìn)行排列。這樣，便可以在FFT計(jì)算的同時(shí)進(jìn)行數(shù)據(jù)整理，減少額外進(jìn)行轉(zhuǎn)置的開(kāi)銷。另外，在某些不需要得到和輸入相同數(shù)據(jù)分布的輸出的情況下，對(duì)輸出數(shù)據(jù)的整理就是一步冗余操作。此時(shí)可以直接取消輸出轉(zhuǎn)化的過(guò)程，輸出計(jì)算后的結(jié)果或按實(shí)際需求相應(yīng)地進(jìn)行小規(guī)模的數(shù)據(jù)整理，這也可以減少算法運(yùn)行的時(shí)間。

5 性能評(píng)估

本文對(duì)FFTW、PFFT和MPFFT庫(kù)在異構(gòu)單節(jié)點(diǎn)、天河一號(hào)和天河二號(hào)3種平臺(tái)上的性能和可擴(kuò)展性進(jìn)行評(píng)估，其中FFTW庫(kù)的版本為3.3.4，具體測(cè)試評(píng)估將分別進(jìn)行介紹。

5.1 單節(jié)點(diǎn)上算法性能分析

本節(jié)將在固定的異構(gòu)平臺(tái)A上分別對(duì)FFTW、PFFT以及MPFFT算法進(jìn)行常規(guī)測(cè)試。

本次實(shí)驗(yàn)平臺(tái)A為CPU和GPU的異構(gòu)平臺(tái)，其中CPU配置的詳細(xì)信息如表1所示。平臺(tái)上共有3塊GPU，分別是一塊GeForce GTX Titan Black，內(nèi)存為6 GB；兩塊Tesla K80，內(nèi)存均為11 GB。使用的CUDA版本為7.5，且運(yùn)行時(shí)調(diào)用了3塊GPU進(jìn)行計(jì)算。

Table 1 CPU configuration表1CPU配置信息

實(shí)驗(yàn)分為兩種輸入：一是1 024×1 024×1 024的規(guī)模下，采用FFTW和PFFT算法得到的性能；二是輸入規(guī)模為256×256×256，采用FFTW、PFFT和MPFFT算法得到的性能。具體實(shí)驗(yàn)所得數(shù)據(jù)如圖6~圖10所示。

圖6和圖7為1 024×1 024×1 024的輸入時(shí)，采用FFTW和PFFT算法得到的性能。從中可以看出PFFT比FFTW算法可擴(kuò)展性更強(qiáng)，當(dāng)輸入為1 024×1 024× 1 024時(shí)，其性能一直優(yōu)于FFTW算法。隨著進(jìn)程數(shù)量的增加，算法性能也在增長(zhǎng)，但由于該平臺(tái)是單節(jié)點(diǎn)服務(wù)器，該測(cè)試并未能真正體現(xiàn)出在大規(guī)模集群上的運(yùn)行情況。另外平臺(tái)中GPU內(nèi)存大小的限制使得MPFFT算法不能夠接收如此大規(guī)模的輸入。

針對(duì)GPU內(nèi)存大小的限制問(wèn)題，本文使用256× 256×256的輸入在該平臺(tái)上進(jìn)行新的測(cè)試，圖8和圖9即為測(cè)試結(jié)果。整體上看，3種算法的運(yùn)算性能大致為MPFFT優(yōu)于PFFT優(yōu)于FFTW算法，且3種算法的運(yùn)算性能隨進(jìn)程數(shù)量的增加都在提升。更確切地說(shuō)，在并行的進(jìn)程數(shù)小于8時(shí)，使用GPU的MPFFT異構(gòu)算法和使用并行計(jì)算的PFFT算法要優(yōu)于FFTW算法，而隨著進(jìn)程數(shù)量的增加，兩種算法相對(duì)于FFTW算法的優(yōu)勢(shì)則不再明顯。主要原因可歸為以下3點(diǎn)：

（1）隨著進(jìn)程數(shù)量的增加，并行算法中進(jìn)程間的通信和數(shù)據(jù)交換將明顯地影響到算法的性能。

Fig.6 Running time comparison of different algorithms when input size is 1 024×1 024×1 024(PlatformA)圖6 數(shù)據(jù)規(guī)模為1 024×1 024×1 024時(shí)不同算法運(yùn)行時(shí)間對(duì)比（平臺(tái)A）

Fig.8 Running time comparison of different algorithms when input size is 256×256×256(PlatformA)圖8 數(shù)據(jù)規(guī)模為256×256×256時(shí)不同算法運(yùn)行時(shí)間對(duì)比（平臺(tái)A）

Fig.7 Performance comparison of different algorithms when input size is 1 024×1 024×1 024(PlatformA)圖7 數(shù)據(jù)規(guī)模為1 024×1 024×1 024時(shí)不同算法運(yùn)行性能對(duì)比（平臺(tái)A）

Fig.9 Performance comparison of different algorithms when input size is 256×256×256(PlatformA)圖9 數(shù)據(jù)規(guī)模為256×256×256時(shí)不同算法運(yùn)行性能對(duì)比（平臺(tái)A）

（2）PFFT與MPFFT算法針對(duì)的都是集群優(yōu)化的算法，平臺(tái)A只是一個(gè)單節(jié)點(diǎn)服務(wù)器，故當(dāng)進(jìn)程數(shù)量、輸入量較小時(shí)，在并行和GPU方面進(jìn)行優(yōu)化的MPFFT算法與PFFT算法會(huì)大幅地改善性能。

（3）當(dāng)進(jìn)程數(shù)量逐漸增加，此時(shí)測(cè)試的數(shù)據(jù)與之前的大規(guī)模輸入相比較小，因此計(jì)算任務(wù)比之前要小，在這種情況下GPU的加速性能并沒(méi)有充分利用，使得優(yōu)化效果減弱，且較小規(guī)模的計(jì)算任務(wù)時(shí)PFFT算法的可擴(kuò)展性將不如FFTW算法，從而當(dāng)進(jìn)程增加時(shí)MPFFT算法與PFFT算法的總體性能將會(huì)出現(xiàn)暫時(shí)不如FFTW算法的現(xiàn)象。

圖10為1 024×1 024×1 024與256×256×256的輸入時(shí)各FFT算法在平臺(tái)A上的加速情況對(duì)比。據(jù)圖可知，各算法在接收大輸入數(shù)據(jù)量時(shí)加速比率要高于接收小輸入數(shù)據(jù)量時(shí)的加速比率，并且FFTW的加速效果較優(yōu)，MPFFT的加速效果較差。原因可歸為兩點(diǎn)：

Fig.10 Speedup comparison of different algorithms when input size is 1 024×1 024×1 024 and 256×256×256(PlatformA)圖10 數(shù)據(jù)規(guī)模為1 024×1 024×1 024與256×256×256時(shí)不同算法加速情況對(duì)比（平臺(tái)A）

（1）各算法在接收大規(guī)模數(shù)據(jù)輸入時(shí)的性能表現(xiàn)能較好地排除接收小規(guī)模數(shù)據(jù)時(shí)所產(chǎn)生的偶然性，更能反映出其真正的性能情況，并且PFFT與MPFFT算法針對(duì)接收大規(guī)模數(shù)據(jù)時(shí)的操作進(jìn)行了相關(guān)的優(yōu)化。

（2）PFFT與MPFFT算法由于進(jìn)行了優(yōu)化，使得其在較小進(jìn)程數(shù)時(shí)已產(chǎn)生相對(duì)FFTW較高的性能，而隨進(jìn)程數(shù)升高，上述分析已說(shuō)明其優(yōu)化效果將受平臺(tái)環(huán)境的制約而減弱，故其加速情況也將受影響而小于FFTW的加速比。

5.2 大規(guī)模集群上算法性能分析

本節(jié)探討的是在大規(guī)模集群上的FFT算法測(cè)試。針對(duì)平臺(tái)A是單節(jié)點(diǎn)服務(wù)器不能進(jìn)行大規(guī)模集群上的運(yùn)算從而無(wú)法獲得算法可擴(kuò)展性的問(wèn)題，本文使用了平臺(tái)B——天河一號(hào)超級(jí)計(jì)算機(jī)（TH-1A）。

TH-1A以持續(xù)性能每秒2 507萬(wàn)億次列世界超級(jí)計(jì)算機(jī)排名第五位，其配備了14 336顆至強(qiáng)X5670處理器、7 168塊基于英偉達(dá)的Tesla M2050計(jì)算卡、2 048顆國(guó)防科大的飛騰處理器以及5 PB存儲(chǔ)設(shè)備。

本文使用了256×256×256、512×512×512、1 024× 1 024×1 024的輸入數(shù)據(jù)分別在TH-1A上進(jìn)行測(cè)試，且每個(gè)節(jié)點(diǎn)進(jìn)行多個(gè)進(jìn)程的并行計(jì)算獲得如下結(jié)果。

由于GPU的內(nèi)存大小限制，MPFFT算法不能在TH-1A上接收輸入數(shù)據(jù)規(guī)模為512×512×512及以上的輸入。圖11、圖12分別是輸入為1 024×1 024× 1 024和512×512×512時(shí)FFTW與PFFT算法運(yùn)行時(shí)間對(duì)比。由圖可以分析出，在大規(guī)模集群上接收512×512×512及以上規(guī)模的輸入數(shù)據(jù)時(shí)，PFFT算法耗時(shí)始終要少于FFTW算法，且進(jìn)程數(shù)量達(dá)到256及以上時(shí)FFTW算法的性能將達(dá)到瓶頸，而PFFT算法至多可擴(kuò)展到2 048個(gè)進(jìn)程上繼續(xù)進(jìn)行計(jì)算，且性能也在不斷提升。

Fig.11 Running time comparison of different algorithms when input size is 1 024×1 024×1 024(TH-1A)圖11 數(shù)據(jù)規(guī)模為1 024×1 024×1 024時(shí)不同算法運(yùn)行時(shí)間對(duì)比（TH-1A）

Fig.12 Running time comparison of different algorithms when input size is 512×512×512(TH-1A)圖12 數(shù)據(jù)規(guī)模為512×512×512時(shí)不同算法運(yùn)行時(shí)間對(duì)比（TH-1A）

圖13展示了FFTW與PFFT算法在接收512× 512×512和1 024×1 024×1 024的輸入數(shù)據(jù)時(shí)的性能對(duì)比。對(duì)比表示，在進(jìn)程數(shù)量較少時(shí)，同一種算法在接收不同規(guī)模的輸入時(shí)性能差異不大，并且PFFT相對(duì)于FFTW算法的優(yōu)勢(shì)也不明顯；然而，PFFT算法的性能在接收1 024×1 024×1 024的輸入反而比接收512×512×512的輸入要高很多，且隨著進(jìn)程數(shù)量的增加性能優(yōu)勢(shì)越明顯。主要原因?yàn)镻FFT算法的設(shè)計(jì)考慮到了多進(jìn)程上的并行優(yōu)化，所以輸入數(shù)據(jù)量越大，使用的進(jìn)程數(shù)量越多，利用PFFT算法進(jìn)行優(yōu)化計(jì)算得到的效果就越明顯。這充分說(shuō)明了PFFT算法在大規(guī)模輸入多進(jìn)程上的可擴(kuò)展性非常強(qiáng)。另外，F(xiàn)FTW算法在使用多進(jìn)程計(jì)算時(shí)優(yōu)化性能至多支持到256個(gè)進(jìn)程，且在接收億級(jí)輸入數(shù)據(jù)時(shí)在256個(gè)進(jìn)程上已經(jīng)開(kāi)始出現(xiàn)明顯的性能下降現(xiàn)象，這也說(shuō)明了FFTW算法在多進(jìn)程上的可擴(kuò)展性不高。

Fig.13 Performance comparison of different algorithms when input size is 1 024×1 024×1 024 and 512×512×512(TH-1A)圖13 數(shù)據(jù)規(guī)模為1 024×1 024×1 024和512×512×512時(shí)不同算法運(yùn)行性能對(duì)比（TH-1A）

圖14與圖15分別是在接收256×256×256輸入數(shù)據(jù)量時(shí)3種算法的運(yùn)算時(shí)間對(duì)比和性能對(duì)比。由圖分析可知，在進(jìn)程數(shù)量較小的情況下，MPFFT算法性能優(yōu)勢(shì)明顯；隨著進(jìn)程數(shù)量的增多，在進(jìn)程數(shù)小于64時(shí)，3種算法的性能相差不大；當(dāng)FFTW算法運(yùn)行的進(jìn)程數(shù)大于32，MPFFT算法運(yùn)行的進(jìn)程數(shù)大于128時(shí)，F(xiàn)FTW與MPFFT算法的性能都開(kāi)始呈下降趨勢(shì)，且這兩種算法隨著進(jìn)程數(shù)的翻倍增長(zhǎng)性能卻沒(méi)有明顯的增長(zhǎng)，而此時(shí)PFFT算法仍有較好的性能。

Fig.14 Running time comparison of different algorithms when input size is 256×256×256(TH-1A)圖14 數(shù)據(jù)規(guī)模為256×256×256時(shí)不同算法運(yùn)行時(shí)間對(duì)比（TH-1A）

Fig.15 Performance comparison of different algorithms when input size is 256×256×256(TH-1A)圖15 數(shù)據(jù)規(guī)模為256×256×256時(shí)不同算法運(yùn)行性能對(duì)比（TH-1A）

綜合分析，MPFFT算法主要是針對(duì)異構(gòu)平臺(tái)上的FFT進(jìn)行優(yōu)化，當(dāng)數(shù)據(jù)量較小，不斷增大進(jìn)程數(shù)時(shí)，計(jì)算時(shí)間上的減小不再明顯，相對(duì)于較小的數(shù)據(jù)計(jì)算時(shí)間，增加的節(jié)點(diǎn)間的通信以及多個(gè)GPU的啟用時(shí)間會(huì)使得整體的性能下降；PFFT算法著重多進(jìn)程上的并行優(yōu)化和改進(jìn)，當(dāng)進(jìn)程數(shù)量增加時(shí)其優(yōu)化效果將會(huì)逐漸顯露；而FFTW算法并未有上述兩種算法的優(yōu)化，故進(jìn)程數(shù)漸增，MPFFT算法優(yōu)化性能開(kāi)始下降而PFFT算法優(yōu)化性能效果還不明顯的時(shí)候，其將會(huì)有稍優(yōu)于MPFFT與PFFT算法的性能表現(xiàn)。

圖16為在接收256×256×256、512×512×512和1 024×1 024×1 024輸入數(shù)據(jù)量時(shí)各FFT算法的加速情況對(duì)比。為了使加速情況對(duì)比更為清晰，圖中橫軸使用的是以2為底進(jìn)程數(shù)的對(duì)數(shù)，縱軸使用的是以2為底加速比的對(duì)數(shù)。在線性加速比的對(duì)比下，各加速算法在接收更大規(guī)模輸入數(shù)據(jù)時(shí)的加速比是相對(duì)更高的，這也印證了之前分析的正確性。未經(jīng)優(yōu)化的FFTW算法隨著進(jìn)程數(shù)增加其加速比呈現(xiàn)了波動(dòng)的趨勢(shì)，而PFFT和MPFFT算法的波動(dòng)相對(duì)要小得多。其中，以接收輸入數(shù)據(jù)量為1 024×1 024×1 024時(shí)PFFT算法加速比最穩(wěn)定且最貼近線性加速比，說(shuō)明PFFT算法在大規(guī)模計(jì)算時(shí)的擴(kuò)展性還是較高的。

Fig.16 Speedup comparison of different algorithms under different input size(TH-1A)圖16 多種輸入數(shù)據(jù)規(guī)模下不同算法加速情況對(duì)比（TH-1A）

之所以出現(xiàn)加速比波動(dòng)的情況，主要原因?yàn)殡S著進(jìn)程數(shù)不斷地呈兩倍提升，額外帶來(lái)的通信開(kāi)銷卻將并行效果相應(yīng)地弱化，兩倍的計(jì)算資源不但不能提供兩倍的加速效果，反而還會(huì)帶來(lái)性能的降低。

圖17為3種FFT算法在TH-1A上的性能評(píng)估。橫軸使用以2為底進(jìn)程數(shù)量的對(duì)數(shù)值來(lái)表示進(jìn)程的規(guī)模，縱軸使用的是以2為底輸入數(shù)據(jù)第一維度的對(duì)數(shù)值來(lái)表示輸入的規(guī)模。氣泡的大小代表在指定的進(jìn)程數(shù)量和指定的輸入規(guī)模下的性能值，氣泡越大，在該環(huán)境下的性能越好，反之則越差。

Fig.17 Performance evaluation of different algorithms on TH-1A圖17 天河1號(hào)不同算法性能評(píng)估

由圖17可分析得知，在大多數(shù)的情況下PFFT算法與MPFFT算法要優(yōu)于FFTW算法，且當(dāng)輸入數(shù)據(jù)量較小時(shí)，MPFFT算法性能優(yōu)勢(shì)相對(duì)明顯；輸入數(shù)據(jù)量較大時(shí)，PFFT算法性能優(yōu)勢(shì)則相對(duì)明顯。另外，這種性能優(yōu)勢(shì)會(huì)隨著進(jìn)程數(shù)量的增加而更為突出，當(dāng)進(jìn)程數(shù)量較小時(shí)，3種算法的性能優(yōu)劣對(duì)比并不明顯。

5.3 大規(guī)模集群上算法性能分析

本節(jié)探討的是單一平臺(tái)（CPU）下的大規(guī)模集群上的FFT算法測(cè)試。在天河一號(hào)上的運(yùn)行環(huán)境是異構(gòu)平臺(tái)多進(jìn)程，而在本節(jié)中將使用天河二號(hào)超級(jí)計(jì)算機(jī)（TH-2）來(lái)重點(diǎn)評(píng)估多節(jié)點(diǎn)上的PFFT算法運(yùn)行情況。

天河二號(hào)是由國(guó)防科技大學(xué)研制的異構(gòu)超級(jí)計(jì)算機(jī)，共有16 000個(gè)運(yùn)算節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)配備兩顆Xeon E5 12核心的中央處理器，3個(gè)Xeon Phi 57核心的協(xié)處理器。本文采用了PFFT算法進(jìn)行測(cè)試以分析其可擴(kuò)展性。實(shí)驗(yàn)中，為了更準(zhǔn)確地對(duì)算法在大規(guī)模集群上的性能進(jìn)行測(cè)量，在每個(gè)節(jié)點(diǎn)上均指定運(yùn)行一個(gè)進(jìn)程，輸入數(shù)據(jù)量為1 024×1 024×1 024。

數(shù)據(jù)結(jié)果如圖18和圖19所示，每個(gè)節(jié)點(diǎn)上運(yùn)行一個(gè)進(jìn)程，申請(qǐng)的最大節(jié)點(diǎn)數(shù)為256，因此該數(shù)據(jù)可以真實(shí)有效地反映在大規(guī)模集群上FFT算法的性能情況。從圖中可以看出，隨著節(jié)點(diǎn)數(shù)的增加，PFFT算法的性能也在逐步地提升，且加速比大致符合線性加速比，實(shí)際的加速情況與理想加速情況的最大差距不超過(guò)16%（16節(jié)點(diǎn)時(shí)）。因此，該數(shù)據(jù)可證明在大規(guī)模集群上（256節(jié)點(diǎn)）PFFT算法有著較為理想的加速實(shí)現(xiàn)，即該算法在多節(jié)點(diǎn)上的優(yōu)化已較為理想。

Fig.18 Performance evaluation of PFFT algorithm when input size is 1 024×1 024×1 024（TH-2）圖18 數(shù)據(jù)規(guī)模為1 024×1 024×1 024時(shí)PFFT算法運(yùn)行性能（TH-2）

Fig.19 Speedup comparison of PFFT algorithm when input size is 1 024×1 024×1 024（TH-2）圖19 數(shù)據(jù)規(guī)模為1 024×1 024×1 024時(shí)PFFT算法加速情況對(duì)比（TH-2）

6 總結(jié)

多維FFT最終都是轉(zhuǎn)換成一維FFT來(lái)計(jì)算，目前分布式FFT算法主要有一維切片分解和二維束分解[14]。前者可擴(kuò)展性比較差，目前只能應(yīng)用于小規(guī)模的集群系統(tǒng)上。而后者需要在計(jì)算中穿插更多的全局轉(zhuǎn)置和本地轉(zhuǎn)置，計(jì)算過(guò)程相對(duì)比較復(fù)雜。

本文針對(duì)CPU和GPU的異構(gòu)集群系統(tǒng)，研究了多維FFT并行算法進(jìn)一步的優(yōu)化方法，從通信和輸出等方面提出的優(yōu)化策略可為現(xiàn)行FFT算法的改進(jìn)提供參考。在此基礎(chǔ)上在不同的平臺(tái)上對(duì)3種FFT算法進(jìn)行了全方位的性能評(píng)估。性能評(píng)估的結(jié)果也可以為FFT算法在大規(guī)模運(yùn)算時(shí)提供可靠和全面的參考。

[1]SKA Telescope.The square kilometre array SKA home[EB/ OL].[2016-09-28].https://www.skatelescope.org/.

[2]Frigo M,Johnson S G.FFTW:an adaptive software architecture for the FFT[C]//Proceedings of the 1998 International Conference on Acoustics,Speech and Signal Processing, Seattle,USA,May 12-15,1998.Piscataway,USA:IEEE, 1998:1381-1384.

[3]Pippig M.PFFT:an extension of FFTW to massively parallel architectures[J].SIAM Journal on Scientific Computing, 2013,35(3):C213-C236.

[4]Li Yan,Zhang Yunquan,Liu Yiqun,et al.MPFFT:an autotuning FFT library for OpenCL GPUs[J].Journal of Computer Science and Technology,2013,28(1):90-105.

[5]Nvidia C.CUFFT library[DB].2010.

[6]Chen Yifeng,Cui Xiang,Mei Hong.Large-scale FFT on GPU clusters[C]//Proceedings of the 24th International Conference on Supercomputing,Tsukuba,Japan,Jun 2-4,2010.New York:ACM,2010:315-324.

[7]Cui Xiang,Chen Yifeng,Mei Hong.Improving performance of matrix multiplication and FFT on GPU[C]//Proceedings of the 15th International Conference on Parallel and Distributed Systems,Shenzhen,China,Dec 8-11,2009.Washington:IEEE Computer Society,2009:42-48.

[8]Pippig M.PFFT user manual.2014.

[9]Frigo M,Johnson S G.The design and implementation of FFTW3[J].Proceedings of the IEEE,2005,93(2):216-231.

[10]Bracewell R N.The Fourier transform and its application[M]. 3rd ed.New York:McGraw-Hill,1999.

[11]Cooley J W,Tukey J W.An algorithm for the machine calculation of complex Fourier series[J].Mathematics of Computation,1965,19(90):297-301.

[12]Cooley J W,Lewis P A W,Welch P D.Historical notes on the fast Fourier transform[J].IEEE Transactions on Audio &Electroacoustics,1967,15(2):76-79.

[13]Gholami A,Hill J,Malhotra D,et al.AccFFT:a library for distributed-memory FFT on CPU and GPU architectures[J]. arXiv:1506.07933v2,2015.

[14]Li Yan,Zhang Yunquan,Jia Haipeng,et al.Automatic FFT performance tuning on OpenCL GPUs[C]//Proceedings of the 17th International Conference on Parallel and Distributed Systems,Tainan,China,Dec 7-9,2011.Washington:IEEE Computer Society,2011:228-235.

[15]Liu Yiqun,Li Yan,Zhang Yunquan,et al.Memory efficient two-pass 3D FFT algorithm for Intel?Xeon PhiTM,coprocessor[J].Journal of Computer Science and Technology, 2014,29(6):989-1002.

LI Kun was born in 1992.He is a Ph.D.candidate at University of Chinese Academy of Sciences.His research interests include high performance computing and parallel software,etc.

李琨（1992—），男，山東青島人，中國(guó)科學(xué)院計(jì)算技術(shù)研究所博士研究生，主要研究領(lǐng)域?yàn)楦咝阅苡?jì)算，并行軟件等。

賈海鵬（1983—），男，山東濰坊人，2013年于中國(guó)海洋大學(xué)獲得博士學(xué)位，現(xiàn)為中國(guó)科學(xué)院計(jì)算技術(shù)研究所助理研究員，主要研究領(lǐng)域?yàn)楫悩?gòu)計(jì)算，多核并行編程方法，多核上的計(jì)算機(jī)視覺(jué)算法等。

CAO Ting was born in 1984.She received the Ph.D.degree in computer system from The Australian National University in 2014.Now she is a post-doctor at Institute of Computing Technology,Chinese Academy of Sciences.Her research interests include high-level language implementation,novel computer architecture design,hybrid memory management and high performance computing,etc.

曹婷（1984—），女，遼寧撫順人，2014年于澳大利亞國(guó)立大學(xué)獲得博士學(xué)位，現(xiàn)為中國(guó)科學(xué)院計(jì)算技術(shù)研究所博士后，主要研究領(lǐng)域?yàn)楦呒?jí)語(yǔ)言實(shí)現(xiàn)，新型計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)，異質(zhì)內(nèi)存管理，高性能計(jì)算等。

ZHANG Yunquan was born in 1973.He received the Ph.D.degree in parallel software from Institute of Software, Chinese Academy of Sciences in 2000.Now he is a professor and Ph.D.supervisor at Institute of Computing Technology,Chinese Academy of Sciences.His research interests include high performance parallel computing,with particular emphasis on large scale parallel computation and programming models,high-performance parallel numerical algorithms,performance modeling and evaluation for parallel programs,etc.

張?jiān)迫?973—），男，山東聊城人，2000年于中國(guó)科學(xué)院軟件研究所獲得博士學(xué)位，現(xiàn)為中國(guó)科學(xué)院計(jì)算技術(shù)研究所研究員、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)楦咝阅懿⑿杏?jì)算，尤其是大規(guī)模并行計(jì)算及編程模型，高性能并行數(shù)值算法，并行程序的性能建模和評(píng)估等。

Implementation and Optimization of Multidimensional FFT Algorithm on Large-Scale Clusters*

LI Kun1,2+,JIAHaipeng1,CAO Ting1,ZHANG Yunquan1
1.State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100190,China
2.School of Computer and Control Engineering,University of ChineseAcademy of Sciences,Beijing 100190,China +Corresponding author:E-mail:likun@ict.ac.cn

Fast Fourier transform(FFT)is a fast algorithm which computes the discrete Fourier transform(DFT)of a sequence,or its inverse.Fast Fourier transform is widely used for many applications in engineering,science and mathematics,such as signal decomposition,digital filter and image processing.As a result,the fine-grained optimization of FFT is extremely important in application.This paper studies the typical decomposition strategies of FFT, the parallel implementation of FFT algorithms on large-scale clusters and proposes some optimization strategies.Onthat basis,this paper also evaluates a variety of FFT algorithms performance on different platforms,then analyzes the implementation,strength and weakness,and the computing scalability on large-scale clusters of these algorithms. The experimental results show that the research of this paper can contribute to the further optimization on existing FFT algorithms,and instruct to choose an FFT algorithm which performance is better on large-scale heterogeneous systems(CPU and GPU)in order to satisfy the specified requirements.

cluster;fast Fourier transforms(FFT);message passing interface(MPI);performance optimization

ng was born in 1983.He

the Ph.D.degree in parallel software from Ocean University of China in 2013.Now he is an assistant professor at Institute of Computing Technology,Chinese Academy of Sciences.His research interests include heterogeneous computing,many-core parallel programming method and computer vision algorithms on multi-/many-core processors,etc.

A

TP302.7

*The National Natural Science Foundation of China under Grant Nos.61432018,61133005,61272136,61521092,61502450(國(guó)家自然科學(xué)基金);the National Key Research and Development Program of China under Grant No.2016YFB0200803(國(guó)家重點(diǎn)研發(fā)計(jì)劃);the Postdoctoral Science Foundation of China under Grant No.2015T80139(中國(guó)博士后科學(xué)基金);the National High Technology Research and Development Program of China under Grant Nos.2015AA01A303,2015AA011505(國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃));the Key Technology Research and Development Programs of Guangdong Province under Grant No.2015B010108006 (廣東省科技計(jì)劃項(xiàng)目);the CAS Interdisciplinary Innovation Team of Efficient Space Weather Forecast Models(中科院高效空間天氣預(yù)報(bào)模式科技創(chuàng)新交叉與合作團(tuán)隊(duì)項(xiàng)目).

Received 2016-11,Accepted 2017-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-01-05,http://www.cnki.net/kcms/detail/11.5602.TP.20170105.0828.006.html