基于MPI的并行大數(shù)據(jù)集生成器*

葛旭冉，劉 洋，陳志廣，肖 儂

(1.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073;2.中山大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

1 引言

大數(shù)據(jù)時(shí)代大量企業(yè)需要處理的數(shù)據(jù)規(guī)模高達(dá)PB級(jí)甚至EB級(jí)，海量數(shù)據(jù)帶來(lái)了海量?jī)r(jià)值，人們的生活方式越來(lái)越智能化。但是，數(shù)據(jù)規(guī)模的劇增也為傳統(tǒng)的大數(shù)據(jù)處理平臺(tái)和大數(shù)據(jù)處理分析算法帶來(lái)了新的挑戰(zhàn)，不斷推動(dòng)著技術(shù)改進(jìn)和平臺(tái)優(yōu)化。另一方面，科技的高速發(fā)展使互聯(lián)網(wǎng)用戶(hù)對(duì)數(shù)據(jù)查詢(xún)、分析、處理和響應(yīng)的延遲要求越來(lái)越高，網(wǎng)絡(luò)的實(shí)時(shí)性需求也持續(xù)增加。這些都導(dǎo)致傳統(tǒng)大數(shù)據(jù)分析平臺(tái)的處理能力與用戶(hù)需求之間的鴻溝不斷增大。例如，淘寶在“雙十一”等重大節(jié)日時(shí)，經(jīng)常會(huì)有頁(yè)面卡頓、服務(wù)器崩潰等現(xiàn)象發(fā)生。對(duì)于這些企業(yè)而言，數(shù)據(jù)量大并不可怕，問(wèn)題是如何實(shí)時(shí)處理海量數(shù)據(jù)，因?yàn)槿魏螘r(shí)延都可能會(huì)失去服務(wù)優(yōu)勢(shì)，進(jìn)而引發(fā)企業(yè)用戶(hù)的大量流失，從而導(dǎo)致商業(yè)經(jīng)濟(jì)下降。

為了解決上述問(wèn)題，企業(yè)需要不斷創(chuàng)新、研發(fā)新技術(shù)。在這個(gè)過(guò)程中，傳統(tǒng)的大數(shù)據(jù)處理平臺(tái)和大數(shù)據(jù)處理分析算法不斷更新演進(jìn)。然而，在這些大數(shù)據(jù)處理分析算法的優(yōu)化研究過(guò)程中，速度常常受限于數(shù)據(jù)集規(guī)模。尤其是涉及到并行通信時(shí)，在數(shù)據(jù)集體量不足的情況下，算法的通信時(shí)間往往要高于真正的計(jì)算時(shí)間，進(jìn)而難以驗(yàn)證算法本身的優(yōu)化效果。因此，大規(guī)模集成數(shù)據(jù)是大數(shù)據(jù)處理優(yōu)化研究的必要前提。但在現(xiàn)實(shí)生活中，往往難以找到適用于測(cè)試的大體量數(shù)據(jù)。為幫助其他大數(shù)據(jù)處理分析算法合理地測(cè)試性能和發(fā)現(xiàn)問(wèn)題，需要自動(dòng)生成一些滿(mǎn)足分布條件的大規(guī)模隨機(jī)數(shù)，并在此基礎(chǔ)上建立可以控制數(shù)據(jù)規(guī)模和復(fù)雜性的人工測(cè)試數(shù)據(jù)集。

目前，國(guó)內(nèi)外紛紛研究了應(yīng)用于不同場(chǎng)合、不同環(huán)境的數(shù)據(jù)生成器[1]。在國(guó)外，Lo等人[2]提出了DBMS測(cè)試套件MyBenchmark和數(shù)據(jù)生成工具，以一組查詢(xún)操作作為輸入，生成數(shù)據(jù)庫(kù)實(shí)例，同時(shí)用戶(hù)還可以控制生成負(fù)載的特征； Houkj?r等人[3]將數(shù)據(jù)表的生成轉(zhuǎn)換成圖的遍歷過(guò)程，能夠保證比較好的屬性依賴(lài)和概率分布，但由于重點(diǎn)保持屬性依賴(lài)，導(dǎo)致數(shù)據(jù)的并行化程度不高，降低了數(shù)據(jù)表的生成速度。在國(guó)內(nèi)，中國(guó)科學(xué)院計(jì)算技術(shù)研究所的詹劍鋒等人[4]提出了大數(shù)據(jù)測(cè)試基準(zhǔn)BigDataBench，使用一個(gè)或多個(gè)數(shù)據(jù)模序組合來(lái)表示大數(shù)據(jù)和人工智能工作負(fù)載的多樣性，其基準(zhǔn)測(cè)試程序覆蓋了多個(gè)大數(shù)據(jù)應(yīng)用領(lǐng)域；顧伶等人[5]開(kāi)發(fā)了一個(gè)流數(shù)據(jù)的分布式在線生成系統(tǒng)Chronos，可以由用戶(hù)控制生成速度和吞吐量，并且在數(shù)據(jù)生成過(guò)程中能夠保持屬性之間的關(guān)聯(lián)和時(shí)間依賴(lài)，生成滿(mǎn)足流數(shù)據(jù)庫(kù)測(cè)試套件的數(shù)據(jù)。

眾所周知，大規(guī)模隨機(jī)數(shù)生成器是產(chǎn)生復(fù)雜數(shù)據(jù)集的基礎(chǔ)。目前，最常見(jiàn)的隨機(jī)數(shù)生成器是基于線性同余算法LCG(Linear Congruential Generat- or)[6]實(shí)現(xiàn)的，被包含在大多數(shù)編程語(yǔ)言的隨機(jī)數(shù)生成庫(kù)中。LCG算法實(shí)現(xiàn)較為簡(jiǎn)單，但是產(chǎn)生數(shù)據(jù)的最低位具有相關(guān)性且序列周期相對(duì)較短。近年，MT(Mersenne Twister)方法逐漸流行起來(lái)，它可以產(chǎn)生周期較長(zhǎng)的隨機(jī)數(shù)序列，其MT19937變體可以產(chǎn)生周期為219937-1的離散型均勻分布隨機(jī)數(shù)。但是，該方法實(shí)現(xiàn)較為復(fù)雜，并行化效率低且需要大量的緩沖器。因此，本文主要采用了線性同余算法生成均勻分布的偽隨機(jī)數(shù)，然后通過(guò)各種函數(shù)變換及映射關(guān)系得到任意概率分布[7]的偽隨機(jī)數(shù)，并在此基礎(chǔ)上構(gòu)造了并行偽隨機(jī)數(shù)生成器。

本文將傳統(tǒng)的隨機(jī)數(shù)生成算法并行化，將整個(gè)任務(wù)分解成許多子任務(wù)在多個(gè)進(jìn)程中并行運(yùn)算，既要保證各處理器生成自己所需要的隨機(jī)數(shù)子序列，又要減少處理器之間的通信負(fù)擔(dān)，從而大大提高數(shù)據(jù)集生成規(guī)模和生成速度，幫助大數(shù)據(jù)處理分析算法進(jìn)行性能測(cè)試和優(yōu)化研究。

本文的主要貢獻(xiàn)包括3個(gè)方面:

(1) 將LCG算法并行化生成符合均勻分布的偽隨機(jī)數(shù)，然后通過(guò)各種函數(shù)變換及映射關(guān)系并行生成任意概率分布的隨機(jī)數(shù)。

(2) 設(shè)計(jì)實(shí)現(xiàn)了不同用途的可以控制數(shù)據(jù)規(guī)模和統(tǒng)計(jì)屬性的人工數(shù)據(jù)集生成算法，構(gòu)造了一個(gè)通用的并行大數(shù)據(jù)集生成器，為運(yùn)行在超級(jí)計(jì)算機(jī)上的并行大數(shù)據(jù)處理分析算法提供基準(zhǔn)測(cè)試數(shù)據(jù)集。

(3) 研究實(shí)現(xiàn)了一個(gè)I/O系統(tǒng)，包括數(shù)據(jù)集的讀、寫(xiě)操作，MPI-I/O讀、寫(xiě)文件，生成不同數(shù)據(jù)格式的文件，分割數(shù)據(jù)集并將其分配到不同進(jìn)程，以及設(shè)置映射規(guī)則使得所有節(jié)點(diǎn)之間都可以進(jìn)行數(shù)據(jù)交互。

最后的實(shí)驗(yàn)結(jié)果表明，并行大數(shù)據(jù)集生成器有效提高了數(shù)據(jù)生成效率和生成規(guī)模，能夠?yàn)榇髷?shù)據(jù)處理分析算法提供高質(zhì)量、大體量的測(cè)試數(shù)據(jù)集。

2 背景

MPI并行編程是實(shí)現(xiàn)大數(shù)據(jù)集生成器的核心技術(shù)，生成滿(mǎn)足不同概率分布條件的隨機(jī)數(shù)是實(shí)現(xiàn)復(fù)雜人工數(shù)據(jù)集的前提。本節(jié)主要介紹MPI并行編程模型,以及生成均勻分布隨機(jī)數(shù)的線性同余LCG算法和其他生成正態(tài)分布、泊松分布、多維正態(tài)分布、二項(xiàng)分布和多項(xiàng)分布等復(fù)雜分布隨機(jī)數(shù)的算法。

2.1 MPI消息傳遞模型

MPI消息傳遞模型[8]面向分布式內(nèi)存的單程序多數(shù)據(jù)并行計(jì)算機(jī)進(jìn)行編程。常用的通信接口包括：MPI_Bast、MPI_Satter、MPI_Gather、MPI_Allgather、MPI_Allgatherall、MPI_Send、MPI_Recv和MPI_Barrier等。其基本思想是將一個(gè)大任務(wù)按照任務(wù)量或數(shù)據(jù)劃分為若干個(gè)元任務(wù)，為了減少進(jìn)程間的通信，合并適量的元任務(wù)，然后設(shè)置特定的映射規(guī)則將其分發(fā)到多個(gè)獨(dú)立的進(jìn)程中并行執(zhí)行。在同一個(gè)通信器內(nèi)，每個(gè)進(jìn)程都有唯一的標(biāo)識(shí)符rankID，通常，根據(jù)rankID編程控制各個(gè)進(jìn)程運(yùn)行相同或不同的代碼塊。根據(jù)程序的實(shí)際數(shù)據(jù)需要，調(diào)用MPI通信接口進(jìn)行消息傳遞。通常的MPI程序結(jié)構(gòu)如圖1所示。

Figure 1 Framework of MPI parallel programming圖1 MPI并行程序設(shè)計(jì)框架圖

2.2 線性同余算法

線性同余算法是目前最流行的偽隨機(jī)數(shù)[9 - 11]生成算法，其過(guò)程主要基于如式(1)所示的迭代公式：

Xi+1=(aXi+c) modm,i=0,1,…n，

m>0，0≤a

(1)

其中，X0為隨機(jī)數(shù)發(fā)生器的初始種子，a為乘數(shù)，c為增量，m為模數(shù)。由式(1)產(chǎn)生的隨機(jī)序列并不總是隨機(jī)的，它實(shí)際上是一個(gè)周期性序列。如果對(duì)于任意正整數(shù)i具有Xi+T=Xi，符合該條件的最小整數(shù)T為L(zhǎng)CG序列的最大周期。但是，在實(shí)際情況下，它的周期要比m小。

c等于0時(shí)該隨機(jī)數(shù)發(fā)生器的生成速度要比c不等于0時(shí)快。盡管c等于0時(shí)看起來(lái)縮短了隨機(jī)數(shù)序列的周期長(zhǎng)度，但它有很大概率獲得較長(zhǎng)的周期。起初，Lehmer[12]只提出了c等于0的情況，后來(lái)Thomson[13]和Rotenberg[14]發(fā)現(xiàn)：當(dāng)c不等于0時(shí)，可以得到更長(zhǎng)的周期。稱(chēng)c不等于0時(shí)的生成器為乘同余生成器；c等于0時(shí)的生成器為混合同余生成器。

2.3 復(fù)雜分布隨機(jī)數(shù)的生成

(1)正態(tài)分布。Box-Muller變換的基本思想是使用2個(gè)符合均勻分布的隨機(jī)變量構(gòu)造符合高斯分布的隨機(jī)變量。具體可以描述為：選取2個(gè)相互獨(dú)立的在[0,1]上均勻分布的隨機(jī)變量U和V，則符合均值為0、標(biāo)準(zhǔn)差為1的高斯分布隨機(jī)變量X和Y如式(2)所示：

(2)

(2)多維正態(tài)分布。多維正態(tài)分布[15]的邊緣分布仍然是正態(tài)分布，給定每個(gè)維度上邊緣正態(tài)分布的均值mean和方差s，再加上相關(guān)系數(shù)矩陣cov，就可以得到它的聯(lián)合概率分布P。算法具體步驟如下：

①根據(jù)邊緣分布的均值mean和方差s，獨(dú)立生成各個(gè)維度上的符合標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)。將各個(gè)維度的隨機(jī)數(shù)序列組合成一個(gè)向量X；

②將相關(guān)系數(shù)矩陣cov進(jìn)行Cholesky分解得到下三角矩陣L；

③用分解得到的下三角矩陣L與向量X相乘，即可得到滿(mǎn)足多維標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)序列S。

(3)泊松分布。泊松分布[16]表示任意時(shí)刻都可能出現(xiàn)的一個(gè)事件在每個(gè)單位時(shí)間里出現(xiàn)的次數(shù)。假設(shè)離散隨機(jī)變量X服從泊松分布，其概率密度函數(shù)如式(3)所示:

(3)

其中，l等于離散隨機(jī)變量X的均值和方差，k為隨機(jī)事件發(fā)生的次數(shù)。

(4)二項(xiàng)分布。假設(shè)在n次伯努利實(shí)驗(yàn)中，每次實(shí)驗(yàn)成功的概率為p(0

0

(4)

其中，n為實(shí)驗(yàn)總次數(shù)，p為實(shí)驗(yàn)成功的概率，q為實(shí)驗(yàn)失敗的概率。在實(shí)際模擬過(guò)程中，可以生成n個(gè)在[0,1]的隨機(jī)數(shù)，統(tǒng)計(jì)其中大于p的數(shù)目即可得到符合二項(xiàng)分布的隨機(jī)數(shù)。

(5)多項(xiàng)分布。多項(xiàng)分布是將二項(xiàng)分布的結(jié)果推廣到多種狀態(tài)得到的。如果把二項(xiàng)分布比作擲硬幣，多項(xiàng)分布就類(lèi)似于投骰子，骰子的6個(gè)面對(duì)應(yīng)6個(gè)不同的點(diǎn)數(shù)，單次擲骰子每個(gè)點(diǎn)數(shù)朝上的概率都是1/6，重復(fù)扔n次。

假設(shè)某隨機(jī)實(shí)驗(yàn)有r個(gè)可能結(jié)果A1,A2,…,Ar，每個(gè)結(jié)果出現(xiàn)的次數(shù)記為隨機(jī)變量X1,X2,…,Xr，概率分布分別是p1,p2,…,pr，那么在t次采樣的總結(jié)果中，A1出現(xiàn)t1次、A2出現(xiàn)t2次、…、Ar出現(xiàn)tr次的這種事件的出現(xiàn)概率P如式(5)所示：

P(X1=t1,…,Xr=tr)=

(5)

Figure 2 Datasets for different purposes 圖2 Dataset庫(kù)中不同用途數(shù)據(jù)集

3 并行大數(shù)據(jù)集生成器的構(gòu)造

3.1 線性同余算法并行設(shè)計(jì)

并行產(chǎn)生隨機(jī)數(shù)的主要思路是使用同一個(gè)隨機(jī)數(shù)生成器，各個(gè)進(jìn)程分別產(chǎn)生隨機(jī)數(shù)序列中不同的子序列。采用跳躍法將LCG算法并行化。

假設(shè)長(zhǎng)度為L(zhǎng)的原始序列為{X0,X1,…,Xi,…}，總共有N個(gè)進(jìn)程，進(jìn)程i從Xi開(kāi)始，每隔N個(gè)數(shù)取走1個(gè)數(shù)，進(jìn)程i生成的序列為{Xi,Xi+N,Xi+2N,…},該序列中的下標(biāo)代表進(jìn)程i生成的隨機(jī)數(shù)在原始序列中的位置。對(duì)于進(jìn)程i來(lái)講，可以構(gòu)造該進(jìn)程的混合同余遞推公式，如式(6)所示：

Yi,sub_i+1=(AYi,sub_i+C) modm

(6)

其中,i=0,1,…,N-1,sub_i=0,1,2,…,各個(gè)進(jìn)程的初始值{Y0,0,Y1,0,…,Yi,0,…,YN-1,0}為原始序列中的{X0,X1,…,Xi,…,XN-1}。A稱(chēng)為廣義乘子，C稱(chēng)為廣義增量,推導(dǎo)如式(7)所示：

(7)

其中，a為乘子，c為增量，m為模數(shù)。

在實(shí)際計(jì)算中，可以采用式(8)來(lái)計(jì)算A：

A=(…((a×amodm)×

amodm)…×a) modm

(8)

與分段并行方法相比，跳躍并行方法使用起來(lái)更加靈活，且各進(jìn)程的初始種子容易計(jì)算。

3.2 人工大數(shù)據(jù)集生成算法并行設(shè)計(jì)

人工大數(shù)據(jù)集的生成主要依賴(lài)于滿(mǎn)足特定分布條件的隨機(jī)數(shù)。這些數(shù)據(jù)集主要用于為運(yùn)行在超級(jí)計(jì)算機(jī)上的并行大數(shù)據(jù)處理分析算法提供基準(zhǔn)測(cè)試。通過(guò)調(diào)研大數(shù)據(jù)處理分析算法的實(shí)際需求，本文主要實(shí)現(xiàn)以下幾類(lèi)數(shù)據(jù)集：分類(lèi)和聚類(lèi)數(shù)據(jù)集、回歸數(shù)據(jù)集、流形學(xué)習(xí)數(shù)據(jù)集和因子分解數(shù)據(jù)集，如圖2所示。

將算法并行化的關(guān)鍵思路是拆解算法的循環(huán)部分，對(duì)其進(jìn)行域分解，按照待生成數(shù)據(jù)集的樣本總數(shù)為每個(gè)進(jìn)程分配任務(wù)量。圖2中17個(gè)數(shù)據(jù)集的生成算法雖各不相同，但其并行化思路相似。下面主要對(duì)聚類(lèi)數(shù)據(jù)集make_gaussian_quantiles和因子分解數(shù)據(jù)集make_sparse__spd_matrix的生成算法并行化進(jìn)行詳細(xì)說(shuō)明。

Figure 3 Parallel diagram of make_gaussian_quantiles algorithm圖3 make_gaussian_quantiles算法并行示意圖

3.2.1 make_gaussian_quantiles算法

make_gaussian_quantiles算法生成符合多維標(biāo)準(zhǔn)正態(tài)分布的各向同性單高斯簇，通過(guò)分位點(diǎn)定義由嵌套的同心多維球體分隔的類(lèi)，以使每個(gè)類(lèi)中的樣本數(shù)量大致相等。用戶(hù)根據(jù)實(shí)際需求設(shè)置樣本數(shù)目n_samples、樣本特征數(shù)目n_features、類(lèi)別數(shù)目n_class、均值mean[]和標(biāo)準(zhǔn)協(xié)方差cov等。算法偽代碼如算法1所示。

算法1make_gaussian_quantiles算法

Init：

(1)輸入樣本數(shù)n_samples、特征數(shù)n_features、均值mean[]、標(biāo)準(zhǔn)協(xié)方差cov、類(lèi)別數(shù)n_classes；

(2)初始化隨機(jī)數(shù)種子myseed；

(3)生成n_samples×n_features維符合多維標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)數(shù)據(jù)集samples[][]；

(4)samples[][]←samples[][]×mean[]+cov；

(5)for(每個(gè)樣本點(diǎn)i)do

計(jì)算該樣本點(diǎn)序列的方差：

endfor

(6)對(duì)樣本集中每個(gè)樣本的方差進(jìn)行排序；

(7)按照排序后的樣本方差找出n_classese-1分位點(diǎn)quantile[]；

(8)for(每個(gè)樣本點(diǎn)i)do

判斷該樣本點(diǎn)在quantile[]上的區(qū)間位置，設(shè)置樣本標(biāo)簽；

endfor

end

3.2.2 make_gaussian_quantiles算法并行化

通過(guò)分析算法1，可以對(duì)需要生成的數(shù)據(jù)集進(jìn)行劃分，每個(gè)進(jìn)程生成一個(gè)符合多維標(biāo)準(zhǔn)正態(tài)分布的子數(shù)據(jù)集，分別計(jì)算各自產(chǎn)生的樣本方差并進(jìn)行排序，并按照排序結(jié)果分別設(shè)置樣本標(biāo)簽。假設(shè)有N個(gè)進(jìn)程，共需生成n_samples個(gè)樣本，每個(gè)樣本有n_features個(gè)特征。并行過(guò)程如圖3所示。

各個(gè)從進(jìn)程生成子數(shù)據(jù)集并按照樣本方差排序，此時(shí)，從進(jìn)程內(nèi)的樣本是局部有序的，本文使用PSRS( Parallel Sorting by Regular Sampling)算法對(duì)整個(gè)數(shù)據(jù)集進(jìn)行全局排序，最后聚集到主進(jìn)程。

make_gaussian_quantiles算法并行化的具體如下所示：

步驟1主進(jìn)程設(shè)置隨機(jī)數(shù)發(fā)生器初始種子，計(jì)算出前N個(gè)隨機(jī)數(shù)并隨機(jī)生成高斯簇中心點(diǎn)坐標(biāo)centerbuffer，然后將其廣播到從進(jìn)程。

步驟2主進(jìn)程計(jì)算各個(gè)進(jìn)程需要生成的樣本數(shù)。進(jìn)程i生成的樣本數(shù)目n_samples_per_procs[i]如式(9)所示：

n_samples_per_proc[i]=n_samples/N+left[i],

(9)

將式(9)計(jì)算得到的n_samples_per_procs[i]分發(fā)到從進(jìn)程。

步驟3從進(jìn)程隨機(jī)生成n_samples_per_procsi個(gè)符合多維標(biāo)準(zhǔn)正態(tài)分布的樣本點(diǎn)，然后計(jì)算每個(gè)樣本點(diǎn)到中心點(diǎn)的距離dis[]。

步驟4各個(gè)進(jìn)程按照從小到大的順序?qū)ζ渖傻拿總€(gè)樣本點(diǎn)到中心點(diǎn)的距離進(jìn)行局部排序。

步驟6此時(shí)選取的N個(gè)數(shù)也是有序的，然后將總共N×N個(gè)數(shù)聚集到主進(jìn)程。

步驟7主進(jìn)程對(duì)N×N數(shù)據(jù)進(jìn)行排序，此時(shí)的數(shù)據(jù)都是局部有序的，使用歸并算法排序可以降低時(shí)間復(fù)雜度。

步驟8主進(jìn)程從排序好的N×N個(gè)數(shù)據(jù)中等間隔選取N-1個(gè)主元,并將其廣播到從進(jìn)程中。

步驟9從進(jìn)程根據(jù)N-1個(gè)主元將dis[]數(shù)組劃分為N段。

步驟10進(jìn)程i(i=0,1,2,…,N-1)將第j(j=0,1,2,…,N-1)段發(fā)送給進(jìn)程j，即每個(gè)進(jìn)程都要給其它所有進(jìn)程發(fā)送相應(yīng)的數(shù)據(jù)段，并且從其它所有進(jìn)程中接收數(shù)據(jù)段，此過(guò)程稱(chēng)為全局交換。

步驟11此時(shí)，各個(gè)進(jìn)程中的N個(gè)數(shù)據(jù)段都是局部有序的，使用歸并算法對(duì)其進(jìn)行最終排序。然后，將排序好的dis[]數(shù)組聚集到主進(jìn)程，就得到了每個(gè)樣本點(diǎn)到中心點(diǎn)距離的全局排序結(jié)果。

步驟12主進(jìn)程在全局dis[]數(shù)組中尋找n_class個(gè)分位點(diǎn)quantile[]，第j個(gè)分位點(diǎn)quantile[j]=j×(n_samples/n_class),j=0,1,2,…,n_class-1。然后將quantile[]廣播到從進(jìn)程。

步驟13從進(jìn)程依次判斷每個(gè)樣本點(diǎn)到中心點(diǎn)的距離在quantile[]中的區(qū)間位置，設(shè)置樣本標(biāo)簽。各個(gè)進(jìn)程利用shuffle函數(shù)打亂樣本集的順序。

并行大數(shù)據(jù)集生成器[17 - 19]集成了若干并行生成數(shù)據(jù)集的算法，可以生成分類(lèi)和聚類(lèi)數(shù)據(jù)集、回歸數(shù)據(jù)集、流形學(xué)習(xí)數(shù)據(jù)集和因子分解數(shù)據(jù)集等。用戶(hù)可以根據(jù)自身需求高效地生成GB級(jí)數(shù)據(jù)集。

4 I/O系統(tǒng)

大數(shù)據(jù)集生成器的I/O系統(tǒng)的主要功能可以分為2部分：一是提供數(shù)據(jù)集讀、寫(xiě)操作的函數(shù)接口；二是實(shí)現(xiàn)數(shù)據(jù)集在各進(jìn)程之間的分發(fā)映射、數(shù)據(jù)交互等。

4.1 MPI-I/O并行讀寫(xiě)文件

(1)多視口并行讀取文件。本文在MPI-I/O系統(tǒng)[20 - 22]中實(shí)現(xiàn)了多視口并行讀取文件的接口。每個(gè)進(jìn)程對(duì)應(yīng)一個(gè)文件視口，每個(gè)視口擁有獨(dú)立的文件指針對(duì)視口進(jìn)行讀寫(xiě)。一個(gè)視口在物理位置上對(duì)應(yīng)原始文件中連續(xù)或不連續(xù)的部分。文件與視口的關(guān)系如圖4所示。

Figure 4 File and viewport mapping圖4 文件與視口對(duì)應(yīng)圖

假設(shè)有N個(gè)進(jìn)程，計(jì)算出每個(gè)進(jìn)程需要讀取的文件大?。篵ufsize=filesize/N。首先，使用MPI_FILE_OPEN并行打開(kāi)文件;然后,根據(jù)每個(gè)進(jìn)程的編號(hào)設(shè)置各進(jìn)程的文件視口，通過(guò)調(diào)用MPI_FILE_SEEK將每個(gè)視口的文件指針移動(dòng)到特定位置；最后，使用MPI_FILE_READ以阻塞方式將各個(gè)文件視口中的數(shù)據(jù)讀入該節(jié)點(diǎn)的內(nèi)存buffer中，并調(diào)用MPI_FILE_CLOSE關(guān)閉文件。

(2)共享指針寫(xiě)入文件。共享文件內(nèi)有且僅有一個(gè)文件指針，任何一個(gè)進(jìn)程對(duì)文件進(jìn)行讀寫(xiě)操作都會(huì)影響其他進(jìn)程。共享文件的寫(xiě)入過(guò)程如圖5所示。

Figure 5 Schematic diagram of writing shared files圖5 共享文件寫(xiě)入示意圖

假設(shè)有N個(gè)進(jìn)程，首先，使用MPI_FILE_OPEN并行打開(kāi)文件，調(diào)用MPI_FILE_WRITE_ORDERED使同一進(jìn)程組內(nèi)的所有進(jìn)程以共享文件指針的方式按順序?qū)懭霐?shù)據(jù)；然后，根據(jù)各個(gè)進(jìn)程的rankID標(biāo)識(shí)，第0,1,…,N-1號(hào)進(jìn)程依次對(duì)文件進(jìn)行寫(xiě)入,當(dāng)一個(gè)進(jìn)程寫(xiě)入后，文件指針自動(dòng)指向下一個(gè)數(shù)據(jù)單元，每個(gè)進(jìn)程都向共同的文件視口中寫(xiě)入存放在各自buffer中的數(shù)據(jù)；最后，調(diào)用MPI_FILE_CLOSE接口關(guān)閉文件。

4.2 數(shù)據(jù)集分發(fā)映射

本文還提供了數(shù)據(jù)集分發(fā)、映射的接口。由主進(jìn)程將文件讀取到自己的緩沖區(qū)dataBuffer內(nèi)，設(shè)置映射規(guī)則將文件分塊發(fā)送到所有其他進(jìn)程。假設(shè)將數(shù)據(jù)集分發(fā)到N個(gè)進(jìn)程，數(shù)據(jù)集中共包含datasize個(gè)樣本，各進(jìn)程接收的樣本數(shù)n_samples_per_proc[i]如式(10)所示：

n_samples_per_proc[i]=datasize/N+left[i],

(10)

文件到各進(jìn)程的映射規(guī)則為連續(xù)分塊放置，即每個(gè)進(jìn)程接收文件中某一塊連續(xù)數(shù)據(jù),如圖6所示。

已知某樣本在原始文件中的全局索引globalIndex，根據(jù)文件塊映射規(guī)則，需要尋找該樣本點(diǎn)在并行節(jié)點(diǎn)上的位置，即獲取樣本點(diǎn)所在的進(jìn)程號(hào)sendID和局部索引localIndex。首先，根據(jù)n_samples_per_proc[]數(shù)組計(jì)算出從進(jìn)程0開(kāi)始的累積樣本數(shù)目accum_local_array[](數(shù)組元素升序排列)。然后，循環(huán)比較找到globalIndex應(yīng)該插入accum_local_array[]中的位置下標(biāo)，該下標(biāo)即為樣本點(diǎn)所在進(jìn)程號(hào)sendID。樣本點(diǎn)在sendID號(hào)進(jìn)程的局部索引為：localIndex=globalIndex-accum_loaca_array[sendID-1]。為獲取樣本點(diǎn)，本文使用了MPI_Send和MPI_Recv接口以阻塞方式實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)通信。由進(jìn)程sendID分別發(fā)送樣本點(diǎn)的特征和標(biāo)簽，進(jìn)程recvID接收數(shù)據(jù)。

5 實(shí)驗(yàn)與評(píng)估

5.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證并行大數(shù)據(jù)集的生成器對(duì)數(shù)據(jù)集生成速度和規(guī)模的有效提高，在天河二號(hào)計(jì)算機(jī)上進(jìn)行測(cè)試，GPU(V100)集群中每個(gè)計(jì)算結(jié)點(diǎn)包含 2 個(gè) Intel(R) Xeon(R) Gold 6132 、14核心的多核中央處理器(CPU)和 4 個(gè) GPU 卡。每個(gè)計(jì)算結(jié)點(diǎn)擁有 256 GB 內(nèi)存(2 個(gè) CPU 共用)。GPU(V100)集群操作系統(tǒng)為 Red Hat 7.3。MPI編譯環(huán)境為mvapich2/2.3rc2-gcc-4.8.5-CUDA-9.2.88。

5.2 數(shù)據(jù)集功能測(cè)試

為了測(cè)試人工數(shù)據(jù)集[23，24]是否滿(mǎn)足大數(shù)據(jù)處理分析算法的測(cè)試需求，本文將MPI并行生成的數(shù)據(jù)集通過(guò)I/O系統(tǒng)的并行接口以.csv格式輸出到同一個(gè)文件，然后調(diào)用并行大數(shù)據(jù)處理分析算法對(duì)生成的不同用途的數(shù)據(jù)集進(jìn)行測(cè)試。以下測(cè)試過(guò)程中均使用原始生成的數(shù)據(jù)集，并未對(duì)其進(jìn)行數(shù)據(jù)預(yù)處理。

(1)單標(biāo)簽聚類(lèi)：make_blob數(shù)據(jù)集和make_gaussian_quantiles數(shù)據(jù)集，使用dbscan和GaussianNB算法進(jìn)行功能驗(yàn)證；

(2)雙向聚類(lèi)：make_biclusters數(shù)據(jù)集和make_checkerboard數(shù)據(jù)集，使用Spectral Biclustering算法進(jìn)行功能驗(yàn)證；

(3)單標(biāo)簽分類(lèi)：make_circles數(shù)據(jù)集和make_moons數(shù)據(jù)集，使用dbscan和k-means算法進(jìn)行功能驗(yàn)證；

(4)多標(biāo)簽分類(lèi)：make_multilabel_classification數(shù)據(jù)集，通過(guò)PCA (Principal Component Analysis)和CCA (Canonical Correlation Analysis)對(duì)數(shù)據(jù)集進(jìn)行分析，抽取了數(shù)據(jù)集的前2個(gè)主成分進(jìn)行分類(lèi)，然后使用sklearn.multiclass.OneVsRestClassifier中帶有線性核的C-SVC(Support Vector Classification) 的分類(lèi)器學(xué)習(xí)每個(gè)類(lèi)的判別模型。

(5)回歸：make_regression數(shù)據(jù)集，使用隨機(jī)抽樣一致性算法RANSAC(RANdom SAmple Consensus)和線性回歸算法LINEAR(LINEAR regression)進(jìn)行功能驗(yàn)證；

(6)流形學(xué)習(xí)：make_swiss_roll數(shù)據(jù)集和make_s_curve數(shù)據(jù)集，使用ISOMAP(ISOmetric MAPping)、 LLE(Locally Linear Embedding)、LE(Laplacian Eigenmaps)、LTSA (Local Tangent Space Alignment)和SE(Spline Embedding)等算法對(duì)數(shù)據(jù)集進(jìn)行降維。

不同用途數(shù)據(jù)集的功能驗(yàn)證測(cè)試結(jié)果如圖7所示。由圖7可以看出，并行大數(shù)據(jù)集生成器生成的不同用途的數(shù)據(jù)集可以滿(mǎn)足大數(shù)據(jù)處理分析算法的性能測(cè)試需求，可以用來(lái)作為基準(zhǔn)測(cè)試數(shù)據(jù)集[25 - 29]，其功能性得到了驗(yàn)證。

Figure 7 Functional verification of different datasets圖7 不同數(shù)據(jù)集的功能驗(yàn)證

5.3 算法性能分析

為了展示數(shù)據(jù)集生成器的數(shù)據(jù)生成速度以及不同數(shù)據(jù)集生成算法的生成速度是否一致，本文從中選取了5個(gè)有代表性的數(shù)據(jù)集生成器，測(cè)試了它們?cè)?0,50,100,200,500,1 000個(gè)進(jìn)程下生成1e8個(gè)樣本的程序運(yùn)行時(shí)間,結(jié)果如圖8所示。

Figure 8 Running time of different algorithms with different numbers of processes圖8 不同算法在不同進(jìn)程數(shù)目下的運(yùn)行時(shí)間

從圖8可以看出，隨著進(jìn)程數(shù)目的不斷增加，各類(lèi)數(shù)據(jù)集生成算法的運(yùn)行時(shí)間不斷縮短，符合預(yù)期效果。盡管不同算法的時(shí)間復(fù)雜度和并行設(shè)計(jì)不盡相同，但是它們生成數(shù)據(jù)集的速度是相對(duì)一致的。隨著進(jìn)程數(shù)目的不斷增加，各類(lèi)算法運(yùn)行時(shí)間的差距不斷減小。在1 000個(gè)進(jìn)程下并行執(zhí)行時(shí)，各類(lèi)算法的運(yùn)行時(shí)間基本相同。

為了測(cè)試算法并行后的性能，本文設(shè)置樣本規(guī)模分別為106,107,108,109，測(cè)試算法在1,20,50,100,200,500,1 000個(gè)進(jìn)程并行工作時(shí)的執(zhí)行時(shí)間。主要的評(píng)估指標(biāo)為加速比和效率，加速比用于評(píng)估并行算法的執(zhí)行速度，效率用于度量各進(jìn)程的資源利用率。并行程序的效率計(jì)算公式如式(11)所示：

(11)

限于篇幅，本文只給出生成make_regression數(shù)據(jù)集算法的加速比和效率示意圖(其他數(shù)據(jù)集算法的評(píng)測(cè)與make_regression類(lèi)似)，如圖9和圖10所示。

Figure 9 Speedup of make_regression algorithm after parallelling圖9 make_regression算法并行加速比

Figure 10 Efficiency of make_regression algorithm after parallelling 圖10 make_regression算法并行效率

由圖9可以看出，當(dāng)樣本規(guī)模比較大時(shí)，隨著分配進(jìn)程數(shù)目(1 000以?xún)?nèi))的增加，算法的加速比不斷增大，但是增加的速度越來(lái)越慢；當(dāng)樣本規(guī)模較小時(shí)，隨著進(jìn)程數(shù)目(1 000以?xún)?nèi))的增加，算法加速比先增加后減小。當(dāng)進(jìn)程數(shù)目不變時(shí)，樣本規(guī)模越大，算法加速比越高。這說(shuō)明多進(jìn)程并行帶來(lái)的算法加速效果是有局限性的，這不僅取決于算法的并行部分占整個(gè)算法的比例，而且還取決于各進(jìn)程之間的通信開(kāi)銷(xiāo)。樣本規(guī)模較小時(shí)，各進(jìn)程的任務(wù)量也很小，進(jìn)程間通信所消耗的時(shí)間抵消了一部分并行計(jì)算節(jié)省的時(shí)間，極端情況下，甚至?xí)霈F(xiàn)加速比小于1的情況，此時(shí)，參與并行計(jì)算的進(jìn)程越多，算法的運(yùn)行速度越慢。

由圖10可知，樣本規(guī)模一定時(shí)，隨著進(jìn)程數(shù)目的增加，算法效率不斷降低，且降低的速率越來(lái)越慢；進(jìn)程數(shù)目一定時(shí)，隨著樣本規(guī)模的增加，算法效率不斷提高。效率主要用于度量各進(jìn)程的資源利用率。任務(wù)量一定，進(jìn)程數(shù)目越多，平均每個(gè)進(jìn)程的利用率就越低；進(jìn)程數(shù)目一定時(shí)，算法任務(wù)量越大，每個(gè)進(jìn)程的資源利用率越高。在樣本規(guī)模達(dá)到1e9時(shí)，在1 000個(gè)進(jìn)程下運(yùn)行并行程序，效率可達(dá)到80%以上。

6 結(jié)束語(yǔ)

本文面向超級(jí)計(jì)算機(jī)實(shí)現(xiàn)了一個(gè)大數(shù)據(jù)集生成器，主要用于解決大數(shù)據(jù)處理分析算法中的數(shù)據(jù)集體量不足問(wèn)題，幫助測(cè)試大數(shù)據(jù)分析算法性能。在并行生成各種復(fù)雜分布隨機(jī)數(shù)的基礎(chǔ)上，利用MPI并行編程技術(shù)設(shè)計(jì)實(shí)現(xiàn)多種數(shù)據(jù)集(如單標(biāo)簽聚類(lèi)數(shù)據(jù)集、分類(lèi)數(shù)據(jù)集、回歸數(shù)據(jù)集、流形學(xué)習(xí)數(shù)據(jù)集、因子分解數(shù)據(jù)集)的并行生成算法，以生成GB級(jí)數(shù)據(jù)。為大數(shù)據(jù)處理分析算法設(shè)置數(shù)據(jù)集在不同進(jìn)程間的分發(fā)、映射規(guī)則，利用點(diǎn)對(duì)點(diǎn)通信實(shí)現(xiàn)不同節(jié)點(diǎn)上的數(shù)據(jù)交互訪問(wèn)功能?；緦?shí)現(xiàn)了大數(shù)據(jù)集從產(chǎn)生、讀寫(xiě)、分發(fā)、映射再到樣本點(diǎn)索引的全過(guò)程。