【摘要】：快速傅里葉變換(fast Fourier transform,FFT)是用于計(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算法。
【圖文】：

ALL時(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為一維分解示意圖。4.2.2二維分解二維分解[3]相較于一維分解很好地解決了可擴(kuò)展性不足這一嚴(yán)重的弊端，故在大規(guī)模集群上也應(yīng)用得比較普遍。圖2即為二維分解的效果圖。該分Fig.1One-dimensiondecompositionstrategy圖1一維分解策略866

鍪

本文編號(hào)：2583320