季 朋，李 暉，陳 梅，戴震宇

(1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025;2.貴州省先進(jìn)計(jì)算與醫(yī)療信息服務(wù)工程實(shí)驗(yàn)室，貴州 貴陽 550025)

0 引 言

快速傅里葉變換(FFT)[1]算法是數(shù)字信號(hào)處理中的核心算法，在頻譜分析、數(shù)字通信、圖像處理中有著重要的應(yīng)用?？焖俑道锶~變換在天文學(xué)方面也有大量應(yīng)用，一個(gè)典型的應(yīng)用場(chǎng)景是對(duì)脈沖星信號(hào)進(jìn)行相干消色散處理[2]。脈沖星輻射的電磁波在傳播過程中，由于受到星際介質(zhì)的干擾，不同頻率的電磁波經(jīng)過星際介質(zhì)后，會(huì)引起觀測(cè)到的脈沖星輪廓展寬，所以需要進(jìn)行消色散處理。消色散處理通常使用相干消色散算法。相干消色散算法的基本原理[3]是將基帶脈沖星數(shù)字信號(hào)進(jìn)行快速傅里葉變換，然后將頻域上各頻點(diǎn)的信號(hào)乘以星際介質(zhì)函數(shù)CHIRP即頻率的響應(yīng)函數(shù)，最終逆傅里葉變換到時(shí)域，從而實(shí)現(xiàn)將不同頻率成分的脈沖星型號(hào)對(duì)齊到某一頻點(diǎn)。傅里葉變換的快慢直接決定相關(guān)消色散的處理效率。

為了滿足海量信號(hào)數(shù)據(jù)的存儲(chǔ)與分析需求，本文采用Greenplum分布式數(shù)據(jù)庫(kù)[4-5]存儲(chǔ)脈沖星信號(hào)。在數(shù)據(jù)庫(kù)中對(duì)數(shù)據(jù)計(jì)算分析通常使用SQL語句，但SQL語句不便于實(shí)現(xiàn)復(fù)雜的算法，例如快速傅里葉變換等科學(xué)分析算法，而用戶自定義函數(shù)(UDF)可以滿足這一需求。本文實(shí)現(xiàn)了UDF形式的快速傅里葉變換算法，為了提高算法效率，對(duì)算法的執(zhí)行做了進(jìn)一步的優(yōu)化。

在Greenplum數(shù)據(jù)庫(kù)集群中有多個(gè)segment實(shí)例，每個(gè)實(shí)例能夠并行執(zhí)行一部分任務(wù)。文獻(xiàn)[6]設(shè)計(jì)了并行結(jié)構(gòu)的FFT算法，本文同樣對(duì)FFT進(jìn)行了并行化設(shè)計(jì)，使每個(gè)實(shí)例能夠并行計(jì)算并得到一部分結(jié)果，從而提高算法執(zhí)行效率。另一方面，集群中數(shù)據(jù)分布[7]也可能影響算法性能。Greenplum將數(shù)據(jù)分布到各個(gè)節(jié)點(diǎn)中，當(dāng)在某個(gè)節(jié)點(diǎn)上執(zhí)行UDF時(shí)，由于節(jié)點(diǎn)的負(fù)載等不同，會(huì)導(dǎo)致不同的性能。為了使UDF算法執(zhí)行性能達(dá)到最優(yōu)，本文做數(shù)據(jù)重分布。文獻(xiàn)[8]根據(jù)網(wǎng)絡(luò)傳播元組數(shù)目，重分布節(jié)點(diǎn)元組，從而提高表連接性能。本文是根據(jù)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)分片大小、負(fù)載等因素重分布元組數(shù)據(jù)，能夠較大地提高FFT的執(zhí)行效率。

1 預(yù)備知識(shí)

1.1 Greenplum分布式數(shù)據(jù)庫(kù)

分布式數(shù)據(jù)庫(kù)[9-10]是通過網(wǎng)絡(luò)將物理上分散的多個(gè)數(shù)據(jù)庫(kù)單元連接起來組成的一個(gè)邏輯上統(tǒng)一的數(shù)據(jù)庫(kù)。每個(gè)數(shù)據(jù)庫(kù)單元相當(dāng)于一個(gè)數(shù)據(jù)庫(kù)實(shí)例，它存儲(chǔ)數(shù)據(jù)且并行執(zhí)行查詢。在查詢時(shí)[11]，集群中的各數(shù)據(jù)庫(kù)實(shí)例能夠并行執(zhí)行一部分查詢?nèi)蝿?wù)，從而提高查詢效率。

圖1 Greenplum架構(gòu)

Greenplum是基于PostgreSQL 8.X的MPP分布式數(shù)據(jù)庫(kù)。MPP[12](shared nothing架構(gòu))指有2個(gè)或更多個(gè)處理器協(xié)同執(zhí)行一個(gè)操作的系統(tǒng)。每個(gè)處理器都有自己的內(nèi)存、操作系統(tǒng)和磁盤。圖1是Geenplum的架構(gòu)圖。

Greenplum集群中的節(jié)點(diǎn)分為2類，一類是master節(jié)點(diǎn)，一類是node節(jié)點(diǎn)，node節(jié)點(diǎn)為物理節(jié)點(diǎn)，每一個(gè)node節(jié)點(diǎn)上都有多個(gè)數(shù)據(jù)庫(kù)實(shí)例segment，負(fù)責(zé)存儲(chǔ)與查詢數(shù)據(jù)。當(dāng)一個(gè)查詢到來時(shí)，master節(jié)點(diǎn)上的優(yōu)化器(optimizer)負(fù)責(zé)生成查詢計(jì)劃，而查詢調(diào)度器(QD)會(huì)以slice的形式下發(fā)查詢?nèi)蝿?wù)到每個(gè)數(shù)據(jù)節(jié)點(diǎn)，數(shù)據(jù)節(jié)點(diǎn)收到查詢?nèi)蝿?wù)后，創(chuàng)建查詢執(zhí)行器(QE)進(jìn)程執(zhí)行任務(wù)。Greenplum將一個(gè)查詢計(jì)劃切分成多個(gè)slice來執(zhí)行，多個(gè)查詢計(jì)劃并行執(zhí)行。本文的UDF通過QE執(zhí)行。

1.2 UDF技術(shù)

在編寫應(yīng)用程序的時(shí)候，傳統(tǒng)的方法是讓服務(wù)器應(yīng)用程序的處理邏輯盡可能地被推送到客戶端,而程序處理的數(shù)據(jù)也需要通過外部網(wǎng)絡(luò)從數(shù)據(jù)庫(kù)中讀取然后推送到客戶端。本文的方法是把計(jì)算、數(shù)據(jù)操作全部轉(zhuǎn)移到一個(gè)位于服務(wù)器上的UDF里面，然后直接在數(shù)據(jù)庫(kù)服務(wù)器中執(zhí)行該UDF。UDF不僅便于設(shè)計(jì)更加復(fù)雜的算法，同時(shí)還消除了數(shù)據(jù)在客戶端與服務(wù)器之間傳輸?shù)倪^程，減少了算法執(zhí)行的時(shí)間。

Greenplum中的UDF能夠提供強(qiáng)大的擴(kuò)展能力，比如能夠添加數(shù)據(jù)類型、創(chuàng)建新的索引等。用戶可以使用UDF實(shí)現(xiàn)內(nèi)置函數(shù)不提供的功能和完成復(fù)雜算法。UDF可以用多種語言實(shí)現(xiàn)，比如Python、Perl等一些插件式的腳本語言。但腳本語言在某些情況下存在缺陷，一方面，當(dāng)執(zhí)行相同的算法時(shí)，大多數(shù)腳本語言會(huì)比C代碼運(yùn)行得慢；另一方面，當(dāng)遇到函數(shù)要被每個(gè)查詢調(diào)用成千上萬次的情況，那么運(yùn)行過程會(huì)出現(xiàn)各種超負(fù)荷運(yùn)作，如函數(shù)調(diào)用、參數(shù)與返回值在腳本語言間的轉(zhuǎn)化等?；诖耍疚牟捎肅語言實(shí)現(xiàn)UDF形式的快速傅里葉變換算法。

2 數(shù)據(jù)重分布

Greenplum在進(jìn)行數(shù)據(jù)分布[13]時(shí)是根據(jù)表的分布鍵按照分布策略把表數(shù)據(jù)分散到不同的segment實(shí)例。常見的分布策略包括哈希分布和隨機(jī)分布。哈希分布[14]是根據(jù)指定的分布列計(jì)算該列對(duì)應(yīng)的每一行數(shù)據(jù)的哈希值，并映射行數(shù)據(jù)至相應(yīng)的segment實(shí)例。隨機(jī)分布指記錄隨機(jī)分散數(shù)據(jù)，相同的記錄可能分布到不同的segment。本文采用的數(shù)據(jù)分布策略為哈希分布。但哈希分布僅考慮了數(shù)據(jù)的分布存儲(chǔ)，沒有考慮分布對(duì)查詢的影響。例如當(dāng)一個(gè)節(jié)點(diǎn)的CPU利用率很高時(shí)，位于該節(jié)點(diǎn)上的segment的查詢執(zhí)行效率會(huì)極大地下降?；诖耍趫?zhí)行查詢前，本文對(duì)數(shù)據(jù)重分布，即根據(jù)當(dāng)前各segment的負(fù)載和數(shù)據(jù)分布情況對(duì)表記錄重新調(diào)整分散，從而加快后續(xù)查詢的執(zhí)行速度。

2.1 數(shù)據(jù)重分布方案

在調(diào)整數(shù)據(jù)分布前，需要確定當(dāng)前數(shù)據(jù)分布的狀態(tài)，一個(gè)表的數(shù)據(jù)分布通常有如圖2所示的幾種情況。

圖2 數(shù)據(jù)分片

在圖2中，node1、node2、node3、node4為Greenplum的4個(gè)物理節(jié)點(diǎn)，與圖1的node1和node2類似。seg0，seg1，…，seg15為16個(gè)segment，與圖1中的segment類似，圖2中的a1～a16、b1～b4、c1～c4、d1～d3分別為表a、b、c、d的數(shù)據(jù)分片，例如表b有4個(gè)數(shù)據(jù)分片b1、b2、b3、b4，分別分布在seg2、seg6、seg10、seg14。數(shù)據(jù)分布分為以下2種情況：

1)數(shù)據(jù)均勻分布在各個(gè)segment上。

數(shù)據(jù)表a的記錄分布在集群中的所有segment中，這種情況不做處理，直接運(yùn)行查詢。

2)數(shù)據(jù)分布在多個(gè)segment上。

如圖2中的表b、c、d，數(shù)據(jù)分布在16個(gè)segment中的少數(shù)幾個(gè)segment中。例如表c的數(shù)據(jù)分布在seg4、seg5、seg8和seg12，這種情況需要根據(jù)代價(jià)判斷是否需要做數(shù)據(jù)重分布。以數(shù)據(jù)表d為例，表d的數(shù)據(jù)分片為d1、d2、d3，分別位于seg4、seg8、seg12上。首先分析數(shù)據(jù)分片d1，d1位于seg4上，則需要計(jì)算d1均勻分布到除seg8、seg12外的其他14個(gè)segment的代價(jià)，一共有n種情況：

(1)

2.2 計(jì)算代價(jià)

C=負(fù)載+時(shí)間

(2)

代價(jià)可根據(jù)節(jié)點(diǎn)當(dāng)前的負(fù)載[15]和預(yù)計(jì)所需時(shí)間得到，比如在計(jì)算I/O代價(jià)時(shí)候，需要評(píng)估節(jié)點(diǎn)的I/O負(fù)載，還需要估算數(shù)據(jù)從磁盤讀出和寫入磁盤的時(shí)間，然后根據(jù)這2個(gè)維度的值得出代價(jià)。

2.2.1 計(jì)算CPU代價(jià)

計(jì)算CPU代價(jià)時(shí)，首先需要得到系統(tǒng)當(dāng)前的負(fù)載，負(fù)載越高，代價(jià)越大，估算負(fù)載的公式如下：

(3)

公式(3)對(duì)CPU當(dāng)前的負(fù)載做歸一化處理，LCPU表示系統(tǒng)當(dāng)前的負(fù)載，利用uptimie命令得到，φmin表示系統(tǒng)的最小負(fù)載，φmax表示系統(tǒng)的最大負(fù)載，由于本文的實(shí)驗(yàn)環(huán)境中的機(jī)器的CPU為4核，所以φmax一般大于4。由于φmin可以為0，所以能夠得到公式(3)的右半部分。

在得到CPU的負(fù)載后，還需要估算CPU處理記錄的代價(jià)，計(jì)算公式如下：

(4)

公式(4)做歸一化處理，α為當(dāng)前segment的記錄條數(shù)。βmin表示segment的最小記錄條數(shù)，βmax表示segment的最大記錄條數(shù)，對(duì)于d1來說，這個(gè)值為2個(gè)segment上存儲(chǔ)的記錄總數(shù)，同樣由于βmin可以為0，所以，能夠推導(dǎo)出等式的右半部分。

在得到負(fù)載和耗時(shí)的值之后，便可以計(jì)算CPU的代價(jià)：

(5)

由于負(fù)載對(duì)CPU代價(jià)影響較大，所以負(fù)載乘以100。從上述公式可以看出CPU的負(fù)載越大，CPU代價(jià)越大，同樣待處理的記錄條數(shù)越多，CPU的代價(jià)也越大。

2.2.2 計(jì)算I/O代價(jià)

計(jì)算I/O代價(jià)同樣需要得到負(fù)載和時(shí)間2個(gè)維度的值。負(fù)載能夠直接通過iostat命令得到，磁盤的使用率越高表示I/O的負(fù)載越大，I/O的代價(jià)LIO也就越高。假設(shè)從磁盤讀取的數(shù)據(jù)量為γr，向磁盤寫入的數(shù)據(jù)量為γw，讀磁盤的速率為δr，寫磁盤的速率為δw，則可得到代價(jià)為：

(6)

在得到2個(gè)維度的代價(jià)以后，則可計(jì)算I/O的代價(jià)：

(7)

上述公式中的100，同樣是為擴(kuò)大負(fù)載對(duì)代價(jià)的影響。公式(7)表示當(dāng)負(fù)載越大，讀寫磁盤的數(shù)據(jù)越多，I/O代價(jià)越大，反之，越小。

2.2.3 計(jì)算網(wǎng)絡(luò)代價(jià)

計(jì)算網(wǎng)絡(luò)代價(jià)與計(jì)算I/O代價(jià)類似，首先通過命令netstat得到網(wǎng)絡(luò)負(fù)載的代價(jià)Lnet，接著計(jì)算通過網(wǎng)絡(luò)傳輸數(shù)據(jù)的代價(jià)。假設(shè)傳輸?shù)臄?shù)據(jù)量為n×m kB，網(wǎng)絡(luò)的帶寬為ξ，對(duì)于傳輸數(shù)據(jù)的代價(jià)為：

(8)

由此得到網(wǎng)絡(luò)總代價(jià)為：

(9)

可見，網(wǎng)絡(luò)負(fù)載越高，傳輸?shù)臄?shù)據(jù)量越多，則網(wǎng)絡(luò)代價(jià)越大。

2.2.4 計(jì)算平均等待時(shí)間

在得到了CPU、I/O和網(wǎng)絡(luò)的代價(jià)，總代價(jià)為上述3個(gè)代價(jià)之和，如果對(duì)于2種不同的方案，總代價(jià)C相同或者相差不大時(shí)，還需要判斷每個(gè)segment的任務(wù)平均等待時(shí)間Tavg。該值通過公式(10)計(jì)算得到：

Tavg=(Q1+Q2+Q3+…+QZ)/z

(10)

公式(10)中的Q1，Q2，…，Qz為segment中在等待隊(duì)列中的查詢的等待時(shí)間，而z表示等待任務(wù)的個(gè)數(shù)。

2.2.5 計(jì)算總代價(jià)

一種方案的總代價(jià)為：

C=CCPU+CIO+Cnet

(11)

總代價(jià)即為CPU、I/O和網(wǎng)絡(luò)代價(jià)之和。在得到每種方案的總代價(jià)以后，比較所有方案的代價(jià)，采用代價(jià)最小的方案。如果待比較的2種方案的代價(jià)之差小于σ，則比較2種方案中待遷移到的segment上任務(wù)的平均等待時(shí)間Tavg，其中σ通過實(shí)驗(yàn)根據(jù)經(jīng)驗(yàn)得到。下面是對(duì)于方案τ1和τ2，判斷采用哪種方案的算法，C1、C2表示2種方案的代價(jià)，T1、T2表示2種方案中segment的總平均等待時(shí)間。算法1為選擇方案算法。

算法1選擇方案算法

if(C1=C2or abs(C1-C2<σ){

if(T1

use τ1

}else{

use τ2

}

}else if(C1

use τ1

}else{

use τ2

}

上述算法能夠得到一種代價(jià)最小或代價(jià)與平均等待時(shí)間都較小的方案，該方案能夠最大程度地提高快速傅里葉變換執(zhí)行效率。

3 快速傅里葉變換的并行實(shí)現(xiàn)

根據(jù)第2章得到的數(shù)據(jù)分布方案對(duì)數(shù)據(jù)進(jìn)行重分布后，還需要設(shè)計(jì)并行化的快速傅里葉變換算法。

3.1 快速傅里葉變換

快速傅里葉變換是對(duì)離散傅里葉變換(DFT)的改進(jìn)，DFT的計(jì)算過程如下。

給定向量A=(a0,a1,…,an-1)，DFT將A變換為B=(b0,b1,…,bn-1)，變換的過程為：

(12)

式(12)中的w=e2πi/n，式(12)表示的含義寫成矩陣形式為：

DFT的另外一種形式為：

(13)

舉一個(gè)具體的例子：對(duì)于一個(gè)4點(diǎn)的向量X=[2,3,3,2]，DFT的計(jì)算過程如下：

圖3 FFT算法

從圖3可以看到，對(duì)于一個(gè)初始向量X[n]，可以分段得到結(jié)果x[k]，因此，可以通過在Greenplum中的各個(gè)segment并行執(zhí)行得到部分結(jié)果，然后在master上匯總結(jié)果并返回。

3.2 分布式并行執(zhí)行

根據(jù)快速傅里葉變換的算法原理，能夠設(shè)計(jì)多進(jìn)程并行執(zhí)行的FFT[16-18]。由于數(shù)據(jù)存儲(chǔ)在Greenplum中，可以利用Greenplum的分布式特性，通過讓多個(gè)segment并行運(yùn)行來實(shí)現(xiàn)多進(jìn)程執(zhí)行的效果。利用Greenplum的UDF實(shí)現(xiàn)快速傅里葉變換的算法設(shè)計(jì)見算法2。

算法2快速傅里葉變換的分布式并行執(zhí)行

master:

get_situation();

for(i=0;i

{

w[i].r=cos(i*2*PI/wLength);

w[i].i=sin(i*2*PI/wLength);

}

parallel segment:

cal_partial();

send_partial();

master:

recv_gather();

上述算法共分為3個(gè)步驟：

1)在master上執(zhí)行準(zhǔn)備工作，例如得到數(shù)據(jù)分布情況、初始化旋轉(zhuǎn)因子數(shù)組等。

2)在segment上執(zhí)行快速傅里葉變換。

3)在master節(jié)點(diǎn)上匯總各并行的segment結(jié)果并返回給客戶端。

算法的主要函數(shù)說明如下：

1)get_situation()。得到數(shù)據(jù)的分布情況，包括：數(shù)據(jù)分布在幾個(gè)segment上，每個(gè)segment有多少條記錄等。在得到數(shù)據(jù)的分布情況后，接著初始化旋轉(zhuǎn)因子數(shù)組，并把該數(shù)組發(fā)送給各segment。

2)cal_partial()。每個(gè)segment執(zhí)行具體的快速傅里葉變換，該函數(shù)能夠得到最終結(jié)果的一部分。

3)send_partial()。每個(gè)segment得到一部分結(jié)果以后，把結(jié)果送給master節(jié)點(diǎn)。

4)recv_gather()。接收各segment的結(jié)果并匯總，返回給客戶端。

4 實(shí)驗(yàn)及結(jié)果分析

本文工作中采用的Greenplum版本為5.0.0-alpha+79a3598。集群共有5個(gè)節(jié)點(diǎn)，1個(gè)主節(jié)點(diǎn)和4個(gè)從節(jié)點(diǎn)，從節(jié)點(diǎn)主要用來存放數(shù)據(jù)并執(zhí)行查詢，主節(jié)點(diǎn)則負(fù)責(zé)分配查詢和匯總結(jié)果。主節(jié)點(diǎn)的硬件配置為32 GB的內(nèi)存，CPU為4核Intel(R) Xeon(R) CPU E5-2630 v2@2.60 GHz，從節(jié)點(diǎn)的內(nèi)存16 GB，CPU的核數(shù)和型號(hào)與主節(jié)點(diǎn)相同，在每個(gè)從節(jié)點(diǎn)中有4個(gè)數(shù)據(jù)庫(kù)實(shí)例。主節(jié)點(diǎn)和從節(jié)點(diǎn)的操作系統(tǒng)均為CentOS 7.4，Linux內(nèi)核版本為3.10。

本文的測(cè)試數(shù)據(jù)為用Python模擬生成的脈沖信號(hào)，數(shù)據(jù)量最大為10 GB，在數(shù)據(jù)庫(kù)中使用列存儲(chǔ)方式存儲(chǔ)數(shù)據(jù)。使用列存儲(chǔ)有利于數(shù)據(jù)壓縮，并且能減少查詢的數(shù)據(jù)量。

4.1 并行化執(zhí)行對(duì)效率的影響

為了驗(yàn)證DoFFT算法并行執(zhí)行的效果，實(shí)驗(yàn)比較當(dāng)所有數(shù)據(jù)存儲(chǔ)于集群中的一個(gè)segment中與均勻存儲(chǔ)于所有segment時(shí)的FFT執(zhí)行效率。數(shù)據(jù)量范圍為1 GB～10 GB。性能結(jié)果如圖4所示。

圖4 并行FFT效率對(duì)比

從圖4可以看出，DoFFT算法能夠極大提升FFT的效率，并且隨著數(shù)據(jù)量的增多，提升效果也更明顯。

4.2 執(zhí)行環(huán)境對(duì)效率的影響

上節(jié)比較了DoFFT并行化算法對(duì)FFT效率的提升，本節(jié)比較DoFFT對(duì)于不同的環(huán)境負(fù)載的優(yōu)化效果。

4.2.1 CPU

CPU對(duì)執(zhí)行效率的影響主要在于，若某個(gè)segment的CPU負(fù)載很高，則會(huì)降低該segment上FFT的執(zhí)行效率。本實(shí)驗(yàn)中創(chuàng)建一個(gè)高負(fù)載的環(huán)境，使CPU的平均負(fù)載高于4，對(duì)比該執(zhí)行環(huán)境下，直接執(zhí)行FFT所用時(shí)間與使用DoFFT算法后的時(shí)間，如圖5所示。

圖5 CPU影響

從圖5可以看出，在每個(gè)數(shù)據(jù)量級(jí)別下，DoFFT算法對(duì)FFT性能都有2倍左右的性能提升。

4.2.2 I/O

I/O對(duì)FFT執(zhí)行效率的影響主要來自于節(jié)點(diǎn)的I/O負(fù)載和I/O帶寬。由于集群中的節(jié)點(diǎn)具有相近的I/O帶寬，所以主要比較DoFFT算法對(duì)I/O負(fù)載的優(yōu)化效果。結(jié)果如圖6所示。

圖6 I/O影響

從圖6可以看出，在小數(shù)據(jù)量時(shí)，DoFFT算法提升效果并不明顯，但隨著數(shù)據(jù)量的增加，效果越來越明顯。

4.2.3 網(wǎng)絡(luò)

Greenplum在執(zhí)行FFT時(shí)，數(shù)據(jù)會(huì)在網(wǎng)絡(luò)中傳輸，網(wǎng)絡(luò)的負(fù)載和帶寬對(duì)性能會(huì)產(chǎn)生一定影響。圖7展示了DoFFT基于網(wǎng)絡(luò)因素對(duì)FFT的優(yōu)化效果。

圖7 網(wǎng)絡(luò)影響

從圖7可以看出，DoFFT算法能夠小幅度地提高性能，但較CPU和I/O，對(duì)網(wǎng)路的提升效果不明顯。

4.2.4 平均等待時(shí)間

分布式數(shù)據(jù)庫(kù)中的segment執(zhí)行的任務(wù)數(shù)會(huì)不同，任務(wù)平均等待時(shí)間也會(huì)不同，平均等待時(shí)間越長(zhǎng)，處于等待隊(duì)列中的查詢被調(diào)度執(zhí)行所需的時(shí)間也就越長(zhǎng)。圖8展示了當(dāng)某些segment中執(zhí)行較多任務(wù)時(shí)，DoFFT的優(yōu)化效果。

圖8 平均等待時(shí)間影響

從圖8可以看到，平均等待時(shí)間同樣能夠小幅地提升效率。

4.2.5 實(shí)驗(yàn)總結(jié)

上述的實(shí)驗(yàn)結(jié)果表明，DoFFT算法能夠不同程度提高算法的執(zhí)行效率。DoFFT的并行化對(duì)FFT執(zhí)行提升效果最明顯。在各影響因素中，對(duì)CPU和I/O優(yōu)化的的提升效果較明顯，對(duì)網(wǎng)絡(luò)和平均等待時(shí)間優(yōu)化的提升較小。

5 結(jié)束語

為提高快速傅里葉變換算法在分布式數(shù)據(jù)庫(kù)中執(zhí)行的效率，本文提出了DoFFT算法。算法首先對(duì)Greenplum中的數(shù)據(jù)進(jìn)行重分布。Greenplum在存儲(chǔ)數(shù)據(jù)時(shí)，會(huì)使用哈希分布或隨機(jī)分布策略分散表數(shù)據(jù)至各個(gè)segment實(shí)例，而在實(shí)際環(huán)境中，每個(gè)segment的CPU、I/O等負(fù)載不同，硬件配置環(huán)境不同，會(huì)造成UDF形式的FFT算法在執(zhí)行時(shí)達(dá)不到最優(yōu)性能。DoFFT算法以每個(gè)segment的負(fù)載、處理時(shí)間等量化為代價(jià)，采用一種代價(jià)最小的方案對(duì)數(shù)據(jù)做重分布。并且，為進(jìn)一步提升FFT執(zhí)行效率，DoFFT算法還利用Greenplum中各個(gè)segment實(shí)例并行地執(zhí)行FFT。實(shí)驗(yàn)結(jié)果表明，DoFFT算法能夠較好地提升FFT在分布式數(shù)據(jù)庫(kù)中執(zhí)行的性能。

參考文獻(xiàn)：

[1] Cochran W, Cooley J, Favin D, et al. What is the fast Fourier transform?[J]. Proceedings of the IEEE, 1967,15(10):1664-1674.

[2] 劉東亮, Demorest P, 南仁東. 基于CUDA的相干消色散算法實(shí)現(xiàn)與測(cè)試[J]. 科學(xué)技術(shù)與工程, 2010,10(8):1947-1950.

[3] 徐永華,李紀(jì)云,張穎倩,等. 相干消色散脈沖星觀測(cè)系統(tǒng)的研究[J]. 天文研究與技術(shù), 2015,12(4):480-486.

[4] Caragea G C, Garciaalvarado C, Petropoulos M, et al. Total operator state recall—Cost-effective reuse of results in Greenplum Database[C]// IEEE International Conference on Data Engineering Workshops. 2013:44-49.

[5] Antova L, El-Helw A, Soliman M A, et al. Optimizing queries over partitioned tables in MPP systems[C]// Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. 2014:373-384.

[6] 丁順英. 基于并行結(jié)構(gòu)的FFT算法的軟硬件設(shè)計(jì)與實(shí)現(xiàn)[D]. 哈爾濱:哈爾濱工業(yè)大學(xué), 2012.

[7] Cheng Long, Li Tao. Efficient data redistribution to speedup big data analytics in large systems[C]// IEEE International Conference on High Performance Computing. 2017:91-100.

[8] Polychroniou O, Sen R, Ross K A. Track join: Distributed joins with minimal network traffic[C]// Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. 20141483-1494.

[9] ?zsu M T, Valduriez P. Distributed database systems: Where are we now?[J]. Computer, 2002,24(8):68-78.

[10] Rothnie J B, Goodman N. A survey of research and development in distributed database management[C]// International Conference on Very Large Data Bases.1977:48-62.

[11] Yu C T, Chang C C. Distributed query processing[J]. ACM Computing Surveys, 1989,16(4):399-433.

[12] Dewitt D J, Gray J. Parallel database systems:The future of database processing or a passing fad?[J]. ACM Sigmod Record, 1990,19(4):104-112.

[13] Garcia-Alvarado C, Raghavan V, Narayanan S, et al. Automatic data placement in MPP databases[C]// IEEE International Conference on Data Engineering Workshops. 2012:322-327.

[14] Shen Yuxia. Distributed storage system model design in Internet of things based on hash distribution[J]. International Journal of Security & Networks, 2017,12(3):141..

[15] Curino C, Jones E P C, Madden S, et al. Workload-aware database monitoring and consolidation[C]// ACM SIGMOD International Conference on Management of Data. 2011:313-324.

[16] Gro?e P, May N, Lehner W. A Study of Partitioning and Parallel UDF Execution with the SAP HANA Database[EB/OL]. https://www.researchgate.net/publication/266660040_A_study_of_partitioning_and_parallel_UDF_execution_with_the_SAP_HANA_database, 2018-03-13.

[17] Taboada J M, Araujo M G, Basteiro F O, et al. MLFMA-FFT parallel algorithm for the solution of extremely large problems in electromagnetics[J]. Progress in Electromagnetics Research. 2010,101(2):350-363.

[18] Chu E, George A. FFT algorithms and their adaptation to parallel processing[J]. Linear Algebra & Its Applications, 1998,284(1):95-124.