鐘旭陽(yáng) ，徐 云

（1.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230026；2.安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽 合肥230026）

0 引言

快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）是實(shí)現(xiàn)離散傅里葉變換及其逆變換的算法。FFT使用分而治之的主要思想，其主要目的是將一個(gè)復(fù)雜的大問(wèn)題分解成多個(gè)簡(jiǎn)單的小問(wèn)題，然后分別解決這些小問(wèn)題[1]。FFT在科學(xué)計(jì)算領(lǐng)域具有極其重要的地位[2]。利用FFT能夠在計(jì)算離散傅里葉變換時(shí)大大減少所需要的乘法次數(shù)，并且FFT點(diǎn)數(shù)規(guī)模越大，F(xiàn)FT算法所能夠節(jié)省的計(jì)算量就越顯著，因此FFT廣泛應(yīng)用于數(shù)據(jù)信號(hào)處理、地震預(yù)報(bào)、石油勘探等領(lǐng)域。

已有的FFT分布式計(jì)算方法大多基于MapReduce批處理系統(tǒng)[1，3-5]，其中 FFT計(jì)算作為一個(gè)整體，在某一個(gè)轉(zhuǎn)換操作中直接計(jì)算來(lái)自上一個(gè)操作的整個(gè)輸出數(shù)據(jù)，忽視了FFT計(jì)算特性的同時(shí)，還需要等待較長(zhǎng)時(shí)間才能延遲得到處理結(jié)果。目前并未有成熟的、基于流粒度的對(duì)FFT的流處理分布式算法并行優(yōu)化相關(guān)研究。且現(xiàn)如今Flink分布式流處理框架大都用于社交網(wǎng)絡(luò)等領(lǐng)域中簡(jiǎn)單的數(shù)據(jù)項(xiàng)統(tǒng)計(jì)應(yīng)用，對(duì)于FFT此類耗時(shí)大、數(shù)據(jù)量大的科學(xué)計(jì)算問(wèn)題并不適用，因此需要對(duì)Flink相關(guān)的機(jī)制進(jìn)行應(yīng)用和改造，使得其符合FFT計(jì)算的要求。

在Flink流處理框架中設(shè)計(jì)實(shí)現(xiàn)良好的FFT算法并行化流程及優(yōu)化，不僅可以將FFT計(jì)算中的源數(shù)據(jù)流的特征表現(xiàn)得非常突出，推動(dòng)了FFT計(jì)算在高精度、大寬帶和實(shí)時(shí)性的要求上更進(jìn)一步；而且為傳統(tǒng)科學(xué)計(jì)算任務(wù)在大數(shù)據(jù)時(shí)代背景下，提供了一種基于分布式流處理平臺(tái)的并行流程新思路。

1 相關(guān)研究

1.1 單機(jī)FFT算法優(yōu)化現(xiàn)狀

目前在單機(jī)上進(jìn)行FFT并行設(shè)計(jì)、提高FFT計(jì)算速度的方法主要有兩類。

一類主要優(yōu)化FFT算法本身。1995年Varkonyi-Koczy[6]提出了新的遞歸FFT算法，力圖提高處理時(shí)間。在生物醫(yī)學(xué)方面，Brünger[7]等人提出了基于覆蓋晶體晶胞的子網(wǎng)格的FFT變種算法，嘗試使用自網(wǎng)格減少計(jì)算的內(nèi)存消耗。郭金鑫[8]等人重構(gòu)蝶形網(wǎng)絡(luò)，在ARMV8及X86-64架構(gòu)上構(gòu)建了一個(gè)高性能FFT算法庫(kù)。FFT高性能程序庫(kù)、基于C的 FFTW[9]，通過(guò)高度優(yōu)化的多線程代碼和緩沖區(qū)優(yōu)化等手段，成為目前行業(yè)內(nèi)頂尖的單機(jī)并行FFT程序庫(kù)。與此類似的包括基于GPU的cuFFT[10]和基于Java的Jtransform[11]等。

另一類主要在集中式的硬件平臺(tái)上進(jìn)行并行化優(yōu)化。例如文獻(xiàn)[12]將多塊DSP芯片集成在一片信號(hào)處理器中，輔以多種硬件加速器，對(duì)一個(gè)FFT輸入數(shù)據(jù)進(jìn)行計(jì)算。文獻(xiàn)[13]采用DSP芯片實(shí)現(xiàn)高速信號(hào)采集和FFT的實(shí)時(shí)運(yùn)算。這種平臺(tái)已有成熟的產(chǎn)品，例如TMS320C6678多核DSP公司的雷達(dá)信號(hào)處理系統(tǒng)等。

但是由于單機(jī)的資源有限，單機(jī)和集中式環(huán)境擴(kuò)展性不高，前端傳感器輸入數(shù)據(jù)量大、數(shù)據(jù)速率快，雖然已經(jīng)有相當(dāng)多的對(duì)FFT算法本身和對(duì)單機(jī)并行FFT程序庫(kù)的優(yōu)化研究，但是處理大規(guī)模數(shù)據(jù)仍然效率不高，且無(wú)法充分發(fā)揮集群機(jī)器CPU和內(nèi)存資源在解決此類大規(guī)模問(wèn)題上的優(yōu)勢(shì)[14]。因此使用大數(shù)據(jù)分布式框架成為目前FFT并行處理的重要手段。

1.2 分布式FFT算法并行流程及優(yōu)化現(xiàn)狀

目前已有很多在分布式框架上搭建FFT應(yīng)用的研究工作。Duc[3]在 Hadoop和 Spark系統(tǒng)上設(shè)計(jì)了一種可擴(kuò)展的FFT計(jì)算系統(tǒng)，以提供給聲學(xué)進(jìn)行分析和使用。王菊[15]等人基于MapReduce改進(jìn)了FFT算法，設(shè)計(jì)不同的組件按順序提交數(shù)據(jù)補(bǔ)零、變址運(yùn)算、蝶式計(jì)算、格式化四個(gè)階段，使得以時(shí)間為基準(zhǔn)的基-2 FFT算法能在框架上并行執(zhí)行，并應(yīng)用于風(fēng)電機(jī)組的發(fā)電場(chǎng)景上。趙鑫[16]等人設(shè)計(jì)了一種非遞歸的增量式FFT方法，在計(jì)算過(guò)程中加入隊(duì)列結(jié)構(gòu)緩沖數(shù)據(jù)以解決數(shù)據(jù)傳輸過(guò)程中丟失和亂序問(wèn)題，并應(yīng)用于轉(zhuǎn)子合成軸心軌跡監(jiān)測(cè)中。

但目前FFT分布式設(shè)計(jì)大多本質(zhì)都是批量處理，要求先存儲(chǔ)后計(jì)算，這種方法一方面有較多的時(shí)間花費(fèi)在IO讀寫上，需要對(duì)大批量的數(shù)據(jù)進(jìn)行存儲(chǔ)復(fù)制，另一方面無(wú)法實(shí)現(xiàn)實(shí)時(shí)的數(shù)據(jù)處理，數(shù)據(jù)延遲高。

由于單機(jī)環(huán)境和分布式環(huán)境有本質(zhì)區(qū)別，單機(jī)FFT算法并未考慮其在分布式環(huán)境下的多機(jī)并行等問(wèn)題。本文根據(jù) FFT算法本身的特點(diǎn)，設(shè)計(jì)了FFT在流式引擎Flink中的并行流程。將每幀數(shù)據(jù)并行拆分，在多級(jí)并行實(shí)例間構(gòu)建蝶式變換，隨后逐級(jí)合并，同時(shí)在多幀數(shù)據(jù)間實(shí)現(xiàn)流水線計(jì)算。本文設(shè)計(jì)了蝶式計(jì)算遞歸深度的自動(dòng)調(diào)優(yōu)，以自動(dòng)設(shè)置在不同點(diǎn)數(shù)、不同集群中的最優(yōu)深度，將計(jì)算時(shí)間降至最低。另外，本文對(duì)Flink原有窗口進(jìn)行了改造，實(shí)現(xiàn)以數(shù)據(jù)空間信息為觸發(fā)條件的窗口機(jī)制，使得蝶式計(jì)算數(shù)據(jù)全部到達(dá)時(shí)觸發(fā)窗口計(jì)算。同時(shí)在窗口內(nèi)設(shè)計(jì)了多幀緩沖隊(duì)列，以防出現(xiàn)位置覆蓋、亂序、計(jì)算錯(cuò)誤等問(wèn)題。

2 方法設(shè)計(jì)

2.1 FFT流處理并行流程設(shè)計(jì)及優(yōu)化

本文參考了1965年Cooley和Tukey提出的經(jīng)典遞歸基 2-FFT算法[17]，將其稍加改造，使得其適用于分布式流處理場(chǎng)景。

本文提出的基于Flink的FFT并行算法整體流程如圖1所示。該并行流程主要分為四個(gè)部分，分別為蝶式計(jì)算數(shù)據(jù)劃分、位置窗口觸發(fā)計(jì)算、小數(shù)據(jù)塊FFT計(jì)算和蝶式計(jì)算多級(jí)合并。

圖1 FFT并行算法整體流程圖

FFT數(shù)據(jù)的輸入流實(shí)質(zhì)為每幀雷達(dá)數(shù)據(jù)中的每個(gè)點(diǎn)。蝶式計(jì)算數(shù)據(jù)劃分時(shí)，根據(jù)下游計(jì)算并行實(shí)例個(gè)數(shù)，將數(shù)據(jù)流按在整幀中的位置信息分發(fā)到對(duì)應(yīng)的計(jì)算并行實(shí)例中，映射關(guān)系示例圖如圖2所示。某個(gè)位置的數(shù)據(jù)與計(jì)算并行實(shí)例編號(hào)的對(duì)應(yīng)關(guān)系在初始化時(shí)計(jì)算并存于映射表中，在運(yùn)行中可以直接從中取值，無(wú)需消耗額外的時(shí)間進(jìn)行多次遞歸計(jì)算匹配。

圖2 基2-FFT點(diǎn)數(shù)為8時(shí)遞歸兩次后的位置映射圖

數(shù)據(jù)合并部分按蝶式計(jì)算遞歸合并的原則，將奇偶項(xiàng)劃分開并將單獨(dú)計(jì)算的兩塊數(shù)據(jù)塊重新合并。計(jì)算公式如式（1）所示。式中o為將要合并后的數(shù)組，u與v分別為上游處理偶數(shù)項(xiàng)和奇數(shù)項(xiàng)數(shù)據(jù)的并行實(shí)例的輸出數(shù)組，w為旋轉(zhuǎn)因子。

圖3為Flink中蝶式計(jì)算遞歸次數(shù)為2時(shí)FFT并行流程方法示意圖，Map算子主要負(fù)責(zé)將流元素進(jìn)行位置編號(hào)，記錄一幀數(shù)據(jù)的最大點(diǎn)數(shù)和當(dāng)前位置，將其位置標(biāo)簽貼在每一個(gè)流動(dòng)的數(shù)據(jù)項(xiàng)中。Partition算子負(fù)責(zé)將流元素實(shí)時(shí)拆分到不同的FFT計(jì)算算子中。在FFT計(jì)算算子中，符合要求的流數(shù)據(jù)全部到達(dá)后會(huì)觸發(fā)新設(shè)計(jì)的緩存窗口，對(duì)到達(dá)的數(shù)據(jù)直接進(jìn)行FFT計(jì)算。Union算子負(fù)責(zé)將計(jì)算算子的輸出數(shù)據(jù)進(jìn)行匯總合并。

圖3 蝶式計(jì)算遞歸深度為2時(shí)FFT并行流程示意圖

本文結(jié)合流式數(shù)據(jù)持續(xù)流動(dòng)的特性，將流水線的并行思想應(yīng)用于FFT并行流程方法中，實(shí)現(xiàn)處理時(shí)間重疊，從而降低每幀數(shù)據(jù)處理的時(shí)間。計(jì)算算子和同一深度的合并算子可以同時(shí)處理一幀的數(shù)據(jù)，而每一層深度之間可以流水線處理連續(xù)幀的數(shù)據(jù)。

由于集群性能不同和環(huán)境不同，為了讓分布式流處理中的FFT并行流程具備在各個(gè)不同集群環(huán)境主動(dòng)適應(yīng)、自動(dòng)調(diào)優(yōu)的能力，需要通過(guò)試運(yùn)行，確定FFT算法蝶式計(jì)算的最優(yōu)遞歸次數(shù)，從而將每幀的處理時(shí)間降至最低。

圖4是蝶式計(jì)算遞歸次數(shù)為1和2時(shí)FFT計(jì)算并行流程方法樣例。當(dāng)深度為1時(shí)，F(xiàn)FT計(jì)算并行實(shí)例數(shù)量為2，將整個(gè)幀中的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)分別交給第一個(gè)和第二個(gè)計(jì)算并行實(shí)例獨(dú)立計(jì)算。當(dāng)深度為0時(shí)，整幀數(shù)據(jù)都交給一個(gè)并行實(shí)例計(jì)算，其本質(zhì)上為Flink上的串行計(jì)算。深度最大為log（n），n為FFT點(diǎn)數(shù)。

圖4 深度為1和2時(shí)FFT并行流程示意圖

2.2 適用于FFT計(jì)算的緩存窗口設(shè)計(jì)

Flink現(xiàn)有窗口機(jī)制包括應(yīng)用于事件時(shí)間的時(shí)間窗口、應(yīng)用于流元素本身的計(jì)數(shù)窗口和應(yīng)用于時(shí)間段數(shù)據(jù)活躍度的會(huì)話窗口，對(duì)于FFT此類高通量?jī)x器的數(shù)據(jù)流來(lái)說(shuō)，會(huì)在很短甚至相同的時(shí)間內(nèi)產(chǎn)生大量的數(shù)據(jù)，這些雙精度浮點(diǎn)數(shù)的數(shù)據(jù)具有極其相近甚至相同的時(shí)間戳，因此無(wú)法借助事件時(shí)間戳信息的時(shí)間窗口。而又因?yàn)?FFT計(jì)算不允許數(shù)據(jù)亂序，因此無(wú)法保障數(shù)據(jù)有序到達(dá)計(jì)數(shù)窗口。

因此，需要針對(duì)FFT這類科學(xué)計(jì)算問(wèn)題，在Flink上設(shè)計(jì)特殊的緩存窗口，使其能夠依據(jù)當(dāng)前數(shù)據(jù)項(xiàng)在幀中的位置信息，在計(jì)算并行實(shí)例所要求的小塊數(shù)據(jù)全部到達(dá)后觸發(fā)窗口邏輯，將數(shù)據(jù)交給并行實(shí)例來(lái)進(jìn)行計(jì)算。而對(duì)于負(fù)責(zé)合并的并行實(shí)例來(lái)說(shuō)，由于其數(shù)據(jù)流來(lái)源為上游的兩個(gè)并行實(shí)例，輸出數(shù)據(jù)塊必須嚴(yán)格遵守位置順序以防亂序，也需要此類緩存窗口。

由于數(shù)據(jù)流可能流速過(guò)快，在負(fù)責(zé)合并的并行實(shí)例緩存窗口中，本文設(shè)有對(duì)多幀數(shù)據(jù)的緩沖隊(duì)列，能夠在一定程度上解決流速過(guò)快而產(chǎn)生如多幀數(shù)據(jù)覆蓋后計(jì)算錯(cuò)誤等問(wèn)題，同時(shí)也能夠在各并行實(shí)例計(jì)算速度不均衡的情況下提前將計(jì)算速度快的并行實(shí)例所產(chǎn)生的數(shù)據(jù)進(jìn)行保存，從而節(jié)約部分通信時(shí)間。

本文緩存窗口實(shí)現(xiàn)方式如下，表1是其中設(shè)計(jì)的部分字段。

表1 適用于FFT的緩存窗口中部分字段設(shè)計(jì)

unionId表明了在當(dāng)前這一深度中此緩存窗口所在并行實(shí)例的索引，此字段是對(duì)應(yīng)所負(fù)責(zé)上一級(jí)兩個(gè)并行實(shí)例的索引，例如0號(hào)并行實(shí)例主要負(fù)責(zé)合并上一級(jí)0號(hào)和1號(hào)并行實(shí)例的數(shù)據(jù)塊。size字段表示負(fù)責(zé)合并的數(shù)據(jù)數(shù)量，在基2-FFT計(jì)算中，始終是兩兩合并，因此默認(rèn)為2。isInit是判斷初始化的標(biāo)簽。miniData是上一級(jí)并行實(shí)例所輸出的小數(shù)據(jù)塊。cacheQueue是多緩沖隊(duì)列，隊(duì)列內(nèi)的每項(xiàng)數(shù)據(jù)以映射表的形式保存，映射表的鍵為所負(fù)責(zé)合并的上一級(jí)并行實(shí)例索引，映射表的值為上一級(jí)對(duì)應(yīng)索引并行實(shí)例的輸出數(shù)據(jù)塊miniData。hasNum實(shí)時(shí)統(tǒng)計(jì)多緩沖隊(duì)列中頭部的映射表中已就緒的數(shù)據(jù)塊數(shù)量。

圖5是負(fù)責(zé)合并的并行實(shí)例中緩存窗口觸發(fā)樣例圖，該并行實(shí)例主要負(fù)責(zé)上游索引為0和1的并行實(shí)例的輸出數(shù)據(jù)塊。階段1時(shí)，窗口內(nèi)多緩沖隊(duì)列為空。在階段2時(shí)，該并行實(shí)例接收上游輸出數(shù)據(jù)＜1，data＞。＜1，data＞中的 1，表明數(shù)據(jù)流中此數(shù)據(jù)項(xiàng)來(lái)自上游索引為1的并行實(shí)例，data是處理后的數(shù)據(jù)塊。將此data存儲(chǔ)于隊(duì)列的第一個(gè)映射表的鍵1所對(duì)應(yīng)的值上。鍵0的值暫且空缺，表明未有完整匹配的數(shù)據(jù)到達(dá)。階段3時(shí)，接收到了一項(xiàng)數(shù)據(jù)項(xiàng)＜1，data＞，依然來(lái)源于上游索引為 1的并行實(shí)例，繼續(xù)緩存此數(shù)據(jù)塊。階段4時(shí)，接收來(lái)自上游索引為 0的并行實(shí)例所處理后的數(shù)據(jù)項(xiàng)＜0，data＞。此時(shí)隊(duì)列頭部映射表中的兩項(xiàng)數(shù)據(jù)項(xiàng)已全部出現(xiàn)，彈出隊(duì)列頭，并將彈出后的兩塊數(shù)據(jù)塊在此并行實(shí)例中進(jìn)行合并。

圖5 合并算子中緩存窗口觸發(fā)樣例圖

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)配置與測(cè)試樣例

由于本文主要測(cè)試的是Flink中FFT算法的各并行度時(shí)間性能和容錯(cuò)性能，應(yīng)盡量避免帶寬等因素給本實(shí)驗(yàn)帶來(lái)的影響，因此本文主要使用Flink的Standalone模式，一個(gè)節(jié)點(diǎn)中設(shè)置了28個(gè)slot給不同的并行實(shí)例運(yùn)行任務(wù)。具體實(shí)驗(yàn)節(jié)點(diǎn)配置情況如表2所示。

表2 實(shí)驗(yàn)節(jié)點(diǎn)配置情況

本文使用隨機(jī)生成雙精度浮點(diǎn)數(shù)作為FFT的輸入數(shù)據(jù)，每組數(shù)據(jù)點(diǎn)數(shù)不同，均為1 000幀。本文實(shí)驗(yàn)所用的Flink作業(yè)拓?fù)鋱D由一個(gè)Source數(shù)據(jù)源輸入算子、一個(gè) Map算子、一個(gè) Partition算子、多個(gè)計(jì)算算子、多個(gè)合并算子和一個(gè)Sink輸出算子組成。Source算子和Sink算子分別是Kafka的消費(fèi)端和生產(chǎn)端。

3.2 實(shí)驗(yàn)結(jié)果與分析

該實(shí)驗(yàn)主要是測(cè)試FFT并行流程中處理每幀數(shù)據(jù)所需要的時(shí)間。在FFT并行流程中，多幀數(shù)據(jù)以流水線的形式在作業(yè)拓?fù)鋱D中進(jìn)行計(jì)算，因此每幀數(shù)據(jù)處理時(shí)間的統(tǒng)計(jì)均是流水線時(shí)間。

實(shí)驗(yàn)結(jié)果如表3所示，表中是對(duì)于不同點(diǎn)數(shù)的FFT數(shù)據(jù)在不同F(xiàn)FT計(jì)算并行度的情況下處理每幀數(shù)據(jù)的流水線時(shí)間。

表3 不同點(diǎn)數(shù)、不同并行度下處理每幀數(shù)據(jù)的流水線時(shí)間

表3中，按行觀察，即從同一個(gè)FFT數(shù)據(jù)點(diǎn)數(shù)來(lái)看，隨著并行度的逐漸增大，處理每幀數(shù)據(jù)的流水線時(shí)間先是逐漸減少，后來(lái)又逐漸增大。計(jì)算時(shí)間減少是由于隨著計(jì)算并行度的增加，并行的算法帶來(lái)了時(shí)間上的優(yōu)化。但是隨著并行度越來(lái)越大，F(xiàn)FT并行流程所自動(dòng)形成的作業(yè)拓?fù)鋱D越加龐大，拉長(zhǎng)了整個(gè)計(jì)算流程，作業(yè)拓?fù)鋱D中的各項(xiàng)并行實(shí)例、對(duì)應(yīng)的窗口和流管道等組件越來(lái)越多，其本身的開銷占比越來(lái)越高，因此導(dǎo)致處理每幀數(shù)據(jù)的流水線時(shí)間有所提高。

按列觀察，即從不同的FFT數(shù)據(jù)點(diǎn)數(shù)來(lái)看，隨著點(diǎn)數(shù)的逐漸增大，處理每幀數(shù)據(jù)的流水線時(shí)間基本都會(huì)成倍增加，一方面因?yàn)镕FT算法的復(fù)雜度是O（nlogn），在 FFT點(diǎn)數(shù)總量 n翻倍的情況下，計(jì)算時(shí)間也因此會(huì)同步增加；另一方面是由于數(shù)據(jù)量的提高，在整個(gè)并行流程中傳輸一幀數(shù)據(jù)所需要的時(shí)間大大增加，特別是各并行實(shí)例窗口的觸發(fā)延時(shí)和并行實(shí)例之間的傳輸也需要更多時(shí)間，增加了時(shí)間的損耗。

從整體來(lái)看，隨著點(diǎn)數(shù)的逐漸增大，時(shí)間消耗最小的最優(yōu)并行度先增大后減小。在點(diǎn)數(shù)為16 384時(shí)，并行度為2的情況下處理每幀數(shù)據(jù)的流水線時(shí)間最小，成為所有并行度下的最優(yōu)并行度；在點(diǎn)數(shù)分別為 65 536、131 072、262 144時(shí)，最優(yōu)的并行度向后推移為8；在點(diǎn)數(shù)更大時(shí)，最優(yōu)的并行度反而減小。并行度逐漸增大的原因?yàn)樵邳c(diǎn)數(shù)較小的情況下，每幀的數(shù)據(jù)量較小，使用并行算法的必要性不高，因?yàn)椴⑿兴惴〞?huì)帶來(lái)一定的開銷，對(duì)時(shí)間的優(yōu)化不明顯。但在點(diǎn)數(shù)增加、每幀的數(shù)據(jù)量提高時(shí)，使用并行計(jì)算帶來(lái)的時(shí)間優(yōu)化越來(lái)越明顯，因此計(jì)算所需要的時(shí)間也越來(lái)越少。在點(diǎn)數(shù)增加到一定規(guī)模如1 048 576后，最優(yōu)并行度反而下降。本文探究最優(yōu)并行度變化的原因如下。

本文統(tǒng)計(jì)了并行度為1時(shí)不同點(diǎn)數(shù)下每幀數(shù)據(jù)完整的計(jì)算時(shí)間和通信時(shí)間，如表4所示，以及點(diǎn)數(shù)為131 072時(shí)不同并行度下每幀數(shù)據(jù)的計(jì)算時(shí)間和通信時(shí)間，如表5所示。此處總時(shí)間為整幀數(shù)據(jù)全部的時(shí)間，計(jì)算時(shí)間包括FFT計(jì)算時(shí)間、多級(jí)合并時(shí)間，通信時(shí)間包含序列化反序列化時(shí)間、流通道數(shù)據(jù)傳輸時(shí)間、并行實(shí)例輸入緩沖區(qū)和輸出緩沖區(qū)等待時(shí)間等。

如表4所示，在并行度不變、點(diǎn)數(shù)逐漸增加到巨大規(guī)模時(shí)，計(jì)算每幀數(shù)據(jù)所需的通信時(shí)間增加幅度遠(yuǎn)大于FFT點(diǎn)數(shù)規(guī)模增加所導(dǎo)致的計(jì)算時(shí)間增加的幅度。因此表3中最佳并行度會(huì)隨著點(diǎn)數(shù)增加到一定程度時(shí)降低，是因?yàn)榇藭r(shí)通信時(shí)間逐漸占據(jù)了主要部分。如表5所示，在點(diǎn)數(shù)不變的情況下，并行度逐漸增加會(huì)使一幀的總時(shí)間增加。其中并行度增加時(shí)，由于每個(gè)并行實(shí)例處理的數(shù)據(jù)減少，因此小份數(shù)據(jù)的計(jì)算時(shí)間會(huì)急劇降低，但是并行度增加時(shí)會(huì)拉長(zhǎng)整個(gè)作業(yè)拓?fù)鋱D，F(xiàn)FT計(jì)算的深度會(huì)增加，帶來(lái)更多的通信階段，通信時(shí)間也會(huì)因此增加。因此需要試運(yùn)行來(lái)自動(dòng)決定不同F(xiàn)FT點(diǎn)數(shù)的最佳并行度，從而將每幀數(shù)據(jù)的流水線計(jì)算時(shí)間降至最低。

表4 并行度為1（Flink中串行）時(shí)不同點(diǎn)數(shù)每幀數(shù)據(jù)計(jì)算時(shí)間和通信時(shí)間

表5 點(diǎn)數(shù)為131 072時(shí)不同并行度每幀數(shù)據(jù)計(jì)算時(shí)間和通信時(shí)間

圖6所示是FFT不同點(diǎn)數(shù)下，F(xiàn)link中串行的計(jì)算時(shí)間和對(duì)應(yīng)最優(yōu)并行度的計(jì)算時(shí)間對(duì)比圖。從實(shí)驗(yàn)結(jié)果中可以看出，本文設(shè)計(jì)出的FFT并行流程在不同點(diǎn)數(shù)的最優(yōu)并行度下與Flink上串行的FFT算法相比，處理每幀數(shù)據(jù)的流水線時(shí)間大大降低。

圖6 Flink中串行計(jì)算時(shí)間和最優(yōu)并行度計(jì)算時(shí)間對(duì)比圖

4 結(jié)論

本文將FFT的計(jì)算特點(diǎn)與分布式流處理相結(jié)合，提出了一種基于Flink的FFT并行流程方法，同時(shí)在Flink中設(shè)計(jì)了適用于FFT的緩存窗口，使得通信時(shí)間和計(jì)算時(shí)間有部分時(shí)間重疊，加快FFT處理時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文在Flink上FFT并行流程中降低了每幀的處理時(shí)間，提高了計(jì)算效率。下一步的工作重點(diǎn)是對(duì)FFT并行流程中的流水線進(jìn)行進(jìn)一步的優(yōu)化。