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

ALL時每個接收者可接收來自別的發(fā)送者的數(shù)目不同的數(shù)據(jù)。例如，第m個進(jìn)程發(fā)送的第n塊數(shù)據(jù)將被第n個進(jìn)程接收并存放在其接收消息緩沖區(qū)recv_buffer的第m塊上。一維分解較為簡單，然而采用該策略進(jìn)行實現(xiàn)的庫在可擴展性方面存在很大的不足，它要求P=n0，n0=max{n0,n1,n2}。當(dāng)P>n0時，一維分解將不能被使用。另外當(dāng)P>n1或P>n2時，數(shù)據(jù)分解所使用的進(jìn)程數(shù)P將受限于n1或n2。數(shù)據(jù)轉(zhuǎn)置之后，多余的進(jìn)程數(shù)將會空閑得不到利用。因此，，對數(shù)據(jù)的劃分需要采用更多維來進(jìn)行計算[4]。圖1為一維分解示意圖。4.2.2二維分解二維分解[3]相較于一維分解很好地解決了可擴展性不足這一嚴(yán)重的弊端，故在大規(guī)模集群上也應(yīng)用得比較普遍。圖2即為二維分解的效果圖。該分Fig.1One-dimensiondecompositionstrategy圖1一維分解策略866

鍪

本文編號：2583320