高燕軍,,,,2
(1.太原理工大學(xué) 信息工程學(xué)院,山西 晉中 030600;2.昆士蘭科技大學(xué) 電機(jī)工程及計(jì)算機(jī)科學(xué)學(xué)院,澳大利亞 布里斯班4001)
全比較是一類特殊的計(jì)算問題,廣泛存在于生物信息學(xué)、生物測(cè)定學(xué)和數(shù)據(jù)挖掘等領(lǐng)域[1]。在生物信息學(xué)中,通過比較不同物種的基因序列對(duì)譜系關(guān)系進(jìn)行推斷[2]。在生物測(cè)定學(xué)的研究中,一個(gè)典型的全比較問題是通過對(duì)生物測(cè)定學(xué)數(shù)據(jù)庫中的大量數(shù)據(jù)進(jìn)行成對(duì)比較來識(shí)別人的生理特征的,如面部識(shí)別、指形判斷、手掌掃描[3]。在數(shù)據(jù)挖掘中,相似矩陣的計(jì)算是分類和聚類分析中的一個(gè)關(guān)鍵步驟,它表示被考慮對(duì)象之間的相似度[4-5]。序列比對(duì)、聚類分析[6]以及當(dāng)前的研究熱點(diǎn)全局網(wǎng)絡(luò)比對(duì)均屬于計(jì)算生物學(xué)和生物信息學(xué)中典型的全比較計(jì)算問題[7]。
全比較計(jì)算代表了一種典型的計(jì)算模式,即數(shù)據(jù)集中的每個(gè)數(shù)據(jù)都要和該數(shù)據(jù)集中的其他所有的數(shù)據(jù)做一次比較計(jì)算[8-9]。當(dāng)數(shù)據(jù)集中的文件個(gè)數(shù)或者文件所包含的數(shù)據(jù)變大時(shí),全比較計(jì)算的規(guī)模隨之變大[10]。當(dāng)前,針對(duì)一些特定領(lǐng)域的全比較問題已有解決方法被提出,如著名的BLAST[11]和ClustalW[12]。然而,這些方法要求在系統(tǒng)中的每個(gè)節(jié)點(diǎn)上存儲(chǔ)所有的數(shù)據(jù)文件,增加了時(shí)間開銷和通信成本,而且需要巨大的存儲(chǔ)空間。此外,分布式系統(tǒng)(如開源的分布式處理框架Hadoop[13])被廣泛地用于解決大規(guī)模的數(shù)據(jù)密集型的計(jì)算問題,包括全比較計(jì)算[14]。然而,由于沒有考慮比較任務(wù)和數(shù)據(jù)之間的依賴關(guān)系,基于Hadoop的數(shù)據(jù)分配策略對(duì)于全比較計(jì)算是低效的[15]。由此可以得出,數(shù)據(jù)分配的結(jié)果將直接影響全比較計(jì)算的整體性能。文獻(xiàn)[10]將全比較計(jì)算的數(shù)據(jù)分配問題抽象為帶約束條件的組合優(yōu)化問題,并利用啟發(fā)式算法求最優(yōu)解。與Hadoop相比,該方法提高了整體的計(jì)算性能,但是隨著數(shù)據(jù)量的增大,解空間變大,問題規(guī)模呈指數(shù)級(jí)增長(zhǎng)[16]。此外,啟發(fā)式算法也無法保證解的全局最優(yōu)性[17]。
針對(duì)上述問題,本文提出基于圖覆蓋的數(shù)據(jù)分配算法(Data Allocation Algorithm Based on Graph Covering,DAABGC)。首先對(duì)全比較計(jì)算問題進(jìn)行理論分析,將其歸納為圖覆蓋問題,然后構(gòu)造最優(yōu)圖覆蓋的解,根據(jù)特解設(shè)計(jì)相應(yīng)的數(shù)據(jù)分配算法,以確保所有比較任務(wù)都包含本地?cái)?shù)據(jù),使節(jié)點(diǎn)之間達(dá)到負(fù)載均衡,從而在保證存儲(chǔ)節(jié)約率的前提下,提高計(jì)算性能。
一個(gè)典型的全比較計(jì)算步驟如下:1)通過主節(jié)點(diǎn)管理和分配數(shù)據(jù)到各節(jié)點(diǎn)上;2)通過任務(wù)調(diào)度器生成計(jì)算任務(wù),然后把任務(wù)分配到各節(jié)點(diǎn)上;3)各節(jié)點(diǎn)執(zhí)行全比較計(jì)算,處理和任務(wù)相關(guān)的數(shù)據(jù)。各階段示意圖如圖1所示。從中可以看出,數(shù)據(jù)分配和任務(wù)執(zhí)行是大數(shù)據(jù)全比較計(jì)算的2個(gè)關(guān)鍵階段。
圖1 大數(shù)據(jù)全比較計(jì)算各階段示意圖
為更高效地解決大數(shù)據(jù)全比較問題,首先提出2個(gè)假設(shè):1)數(shù)據(jù)文件的大小相同或近似相同;2)比較任務(wù)的執(zhí)行時(shí)間相同或近似相同。在真實(shí)的場(chǎng)景中,很多應(yīng)用滿足這2個(gè)特性,如協(xié)方差矩陣的計(jì)算、聚類分析中相似矩陣的計(jì)算等。本文研究的正是這類應(yīng)用。其次,本文將從存儲(chǔ)的使用和計(jì)算性能2個(gè)方面對(duì)該問題進(jìn)行深入剖析。
1)減少存儲(chǔ)使用
對(duì)于存儲(chǔ)的使用,需要考慮2個(gè)問題:(1)每個(gè)節(jié)點(diǎn)的存儲(chǔ)使用必須在其范圍之內(nèi);(2)分配數(shù)據(jù)到各個(gè)節(jié)點(diǎn)上所花費(fèi)的時(shí)間應(yīng)該在可接受的程度之內(nèi)。令|Di|為節(jié)點(diǎn)i上存儲(chǔ)的文件數(shù),則在考慮到上述2個(gè)條件的情況下,數(shù)據(jù)分配算法需要滿足:
Minimize max{|D1|,|D2|,…,|Dk|}
(1)
最小化節(jié)點(diǎn)中最大的文件數(shù)可以使每個(gè)節(jié)點(diǎn)存儲(chǔ)相似數(shù)量的文件并包含相似數(shù)量的可執(zhí)行比較任務(wù),原因是可執(zhí)行任務(wù)的數(shù)量和節(jié)點(diǎn)上的文件數(shù)是成比例增長(zhǎng)的。
2)提高計(jì)算性能
在全比較問題的分布式計(jì)算中,任務(wù)執(zhí)行的總時(shí)間是由最后一個(gè)完成任務(wù)的節(jié)點(diǎn)決定的。為了完成每個(gè)比較任務(wù),對(duì)應(yīng)的節(jié)點(diǎn)必須訪問和處理所需的數(shù)據(jù)。令K、tcom(k)和tacc(k)分別代表分配給最后一個(gè)完成任務(wù)的節(jié)點(diǎn)的任務(wù)數(shù)、任務(wù)k的計(jì)算時(shí)間和訪問任務(wù)k所需數(shù)據(jù)的時(shí)間。那么,執(zhí)行任務(wù)的總時(shí)間可以表示為:
(2)
為了減少式(2)中總的執(zhí)行時(shí)間,數(shù)據(jù)分配算法需要滿足2個(gè)條件:(1)任務(wù)分配均衡;(2)所有的比較任務(wù)都具有好的數(shù)據(jù)本地性。
令Ti為節(jié)點(diǎn)i執(zhí)行的比較任務(wù)數(shù),則對(duì)于N個(gè)節(jié)點(diǎn)、M個(gè)文件的全比較問題,共有M(M-1)/2個(gè)比較任務(wù)需要分配,那么任務(wù)分配均衡可以表示為:
(3)
好的數(shù)據(jù)本地性也可以公式化。如果一個(gè)比較任務(wù)所需的數(shù)據(jù)都存儲(chǔ)在本地,那么該任務(wù)不需要通過網(wǎng)絡(luò)來遠(yuǎn)程訪問數(shù)據(jù),因此,好的數(shù)據(jù)本地性意味著tacc(k)的最小值可以為0。令(x,y)、T、Ti、Di分別代表數(shù)據(jù)x和y之間的比較任務(wù)、所有比較任務(wù)的集合、由節(jié)點(diǎn)i執(zhí)行的任務(wù)集合以及節(jié)點(diǎn)i上存儲(chǔ)的數(shù)據(jù)集合,則好的數(shù)據(jù)本地性可以表示為:
?(x,y)∈T,?i∈{1,2,…,N}
x∈Di∧y∈Di∧(x,y)∈Ti
(4)
經(jīng)上述討論,將式(1)、式(3)、式(4)作為本文數(shù)據(jù)分配算法的優(yōu)化目標(biāo)。
1.2.1 圖覆蓋的基本概念
定義1完全圖是每對(duì)頂點(diǎn)之間都恰好連有一條邊的簡(jiǎn)單圖,n個(gè)頂點(diǎn)的完全圖有n(n-1)/2條邊,記為Gn。
定義2假設(shè)G(V,E)代表一個(gè)圖,其中,V表示頂點(diǎn)集合,E表示邊集合。從集合V取若干個(gè)頂點(diǎn)組成集合V′,構(gòu)成一個(gè)誘導(dǎo)子圖,用G[V′]表示。
定義32個(gè)圖G1(V1,E1)和G2(V2,E2)的聯(lián)合為分別對(duì)頂點(diǎn)和邊求并集,即G=(V1∪V2,E1∪E2)。如果存在n個(gè)誘導(dǎo)子圖G(V1),G(V2),…,G(Vn)的聯(lián)合G覆蓋圖G′,當(dāng)且僅當(dāng)G′的任何一條邊存在于某個(gè)子圖G(Vi)。
定義4給定一個(gè)圖G=(V,E)和一個(gè)正整數(shù)k,把G劃分為k個(gè)誘導(dǎo)子圖G(V1),G(V2),…,G(Vk),如果滿足2個(gè)條件:1)該k個(gè)子圖的聯(lián)合覆蓋G;2)各子圖中最大的頂點(diǎn)數(shù)最小,即minmax{|V1|,|V2|,…,|Vk|},其中|Vi|代表第i個(gè)子圖中的頂點(diǎn)數(shù),則稱其為圖覆蓋問題。
定義5若某一個(gè)Gn的一些子圖Gp、Gp之間無公共邊,且Gn中的任意一邊必定在某個(gè)Gp中,則稱這些圖Gp的聯(lián)合為Gn的最優(yōu)圖覆蓋,若不滿足則稱這些Gp不是Gn的最優(yōu)圖覆蓋。
1.2.2 全比較問題到圖覆蓋問題的轉(zhuǎn)化
把全比較計(jì)算映射為一個(gè)完全圖,圖中的頂點(diǎn)代表數(shù)據(jù)文件,邊代表比較任務(wù),如圖2所示,其中,8個(gè)頂點(diǎn)代表8個(gè)數(shù)據(jù)文件,28條邊代表28個(gè)比較任務(wù),如C(3,8)、C(4,8)、C(4,7)分別表示3個(gè)不同的比較任務(wù)。因此,M個(gè)文件、N個(gè)節(jié)點(diǎn)全比較數(shù)據(jù)分配問題可以類比為把一個(gè)完全圖GM劃分為N個(gè)子圖,且該N個(gè)子圖的聯(lián)合能夠覆蓋圖GM??紤]到1.1節(jié)提出的優(yōu)化目標(biāo),式(1)數(shù)據(jù)均衡意味著每個(gè)子圖有相似數(shù)量的頂點(diǎn),式(2)任務(wù)均衡意味著每個(gè)子圖有相似數(shù)量的邊,而式(3)數(shù)據(jù)本地性,按照最優(yōu)圖覆蓋的子圖劃分方式,任意2個(gè)子圖之間沒有公共邊,每個(gè)子圖都自成一個(gè)完全圖,所有的邊都連著2個(gè)頂點(diǎn),因此,可以確保比較任務(wù)具有100%的數(shù)據(jù)本地性。由此可以得出,全比較問題可以轉(zhuǎn)化為最優(yōu)圖覆蓋的求解問題。文獻(xiàn)[18]證明最優(yōu)圖覆蓋問題是NP完全問題。NP完全問題是非確定性問題,無法直接通過計(jì)算得到解,解決NP完全問題的一般方法是采用啟發(fā)式算法。然而,隨著M和N的增大,解的空間呈指數(shù)級(jí)增長(zhǎng)。
圖2 8個(gè)文件的全比較計(jì)算示意圖
通過研究可以發(fā)現(xiàn),相同頂點(diǎn)數(shù)的子圖Gp覆蓋Gn的必要條件是n-1≥p(p-1)。
M=N=p(p-1)+1,p>2,其中M為文件數(shù),N為節(jié)點(diǎn)數(shù),當(dāng)p=2,3時(shí),問題相對(duì)簡(jiǎn)單,通過枚舉法構(gòu)造出最優(yōu)解,如表1、表2所示,最優(yōu)解可以表示為集合S={Ni(Vi1,Vi2,…,Vip)|i=1,2,…,n},其中n為節(jié)點(diǎn)數(shù),Ni為節(jié)點(diǎn)i的編號(hào),Vip為頂點(diǎn)p(即數(shù)據(jù)文件p)的編號(hào)。
表1 p=2時(shí)圖覆蓋最優(yōu)解
表2 p=3時(shí)圖覆蓋最優(yōu)解
由表1、表2可以歸納出以下規(guī)律:
1)如果存在最優(yōu)解,則每個(gè)節(jié)點(diǎn)上的文件個(gè)數(shù)為p。
2)相鄰節(jié)點(diǎn)之間的解組合差1,如表2的N1(1,2,4),然后對(duì)組合中的各元素遞增1,即為下一個(gè)節(jié)點(diǎn)上的頂點(diǎn)組合。當(dāng)Vip遞增為N+1時(shí),將Vip置為1,然后對(duì)這p個(gè)點(diǎn)從小到大重新排列,繼續(xù)遞增,結(jié)果發(fā)現(xiàn)是一個(gè)循環(huán)。
3)在這p個(gè)點(diǎn)中,1和2是可以首先確定的2個(gè)點(diǎn),在確定1和2的情況下,3是可以排除的,例如(1,2,3)遞增1,則為(2,3,4),顯然(2,3)為公共邊,不滿足最優(yōu)圖覆蓋的條件。因此,第3個(gè)點(diǎn)從4開始。
4)由于這p個(gè)點(diǎn)是循環(huán)遞增的,因此任意2個(gè)點(diǎn)之間的差值不能相同。如p=4,M=N=13,取4個(gè)點(diǎn)為(1,2,4,7),當(dāng)遞增到(4,5,7,10)時(shí),將出現(xiàn)一條公共邊,直到第4個(gè)數(shù)遞增到13都會(huì)有公共邊存在。
5)在滿足規(guī)律1)和規(guī)律2)之后,在(Vi1,Vi2,…,Vip)的第p個(gè)點(diǎn)Vip遞增到N+1之前都不會(huì)有公共邊存在。當(dāng)Vip=N+1時(shí),將其置為1,此時(shí),節(jié)點(diǎn)i上的解為(1,Vi2,Vi3,…,Vip),重新計(jì)算1和其他各點(diǎn)之間的差,且不能和之前的差相同。
從第2節(jié)的分析中可以得到以下結(jié)論:
1)假設(shè)M=N=p(p-1)+1,p>2時(shí)存在圖覆蓋的最優(yōu)解,則可以通過上文5條規(guī)律來構(gòu)造該解。
2)在構(gòu)造出最優(yōu)解之后,數(shù)據(jù)和任務(wù)的分配可以根據(jù)最優(yōu)解來進(jìn)行。
3)由于之前所討論的構(gòu)造特殊解的前提是M=N,因此本文討論M>N的情況。當(dāng)M>N時(shí),可以將文件均勻分成N個(gè)Block,每個(gè)Block中的文件個(gè)數(shù)差別不大于1,然后按照M=N的情況來構(gòu)造解,并進(jìn)行相應(yīng)的數(shù)據(jù)分配和任務(wù)調(diào)度。如表3所示,N=7,M=9時(shí)可以構(gòu)造7個(gè)Block。
表3 N=7,M=9時(shí)Block的構(gòu)造
根據(jù)上述內(nèi)容,本文提出基于圖覆蓋的數(shù)據(jù)分配算法(DAABGC)。該算法分為2個(gè)步驟:
步驟1構(gòu)造最優(yōu)解。首先定義5個(gè)集合變量:L1用于存放已經(jīng)找到的特解元素;L2存放特解中任意兩點(diǎn)之間的差;L3存放L1和L2中元素的和;L4存放新找到的頂點(diǎn)和已有頂點(diǎn)的差;L5存放當(dāng)Vi遞增到N+1時(shí),Vj,j=1,2,…,i-1和1的差,其中Vi表示第i個(gè)頂點(diǎn),然后進(jìn)行特解的構(gòu)造。
步驟2分配數(shù)據(jù)和調(diào)度任務(wù)。當(dāng)M=N時(shí),根據(jù)步驟1得到特解進(jìn)行數(shù)據(jù)分配;當(dāng)M>N時(shí),將數(shù)據(jù)文件均勻打包為N個(gè)Block,然后根據(jù)特解進(jìn)行數(shù)據(jù)分配。
通過DAABGC算法,構(gòu)造出當(dāng)M=N=13,21,31時(shí)的最優(yōu)解,加上手動(dòng)構(gòu)造p=2,3時(shí)的解,M=N=3,7,13,21,31時(shí)的特解如表4所示。
表4 M=N=3,7,13,21,31時(shí)的特解
DAABGC算法描述如下:
//構(gòu)造最優(yōu)解
定義變量:L1、L2、L3、L4、L5為5個(gè)集合變量
構(gòu)造最優(yōu)解S中組合N1(V1,V2,…,Vp)
V1=1,V2=2,V3從4開始
把V1、V2、V3存到L1,把V1、V2、V3之間任意2個(gè)元素之間的差無重復(fù)地存到L2
while V3 for i=4 to p do for x in L1do for y in L2do 把x+y無重復(fù)地放入L3 end for end for 對(duì)L3進(jìn)行升序排序,在L3中搜索第一個(gè)在Vi-1和L3[last]之間沒有的自然數(shù),如果存在將其賦給Vi,否則把L3[last]++賦給Vi while Vi for z in L1do L4.add(Vi-z); end for 計(jì)算當(dāng)Vi遞增到N+1時(shí),Vj,j=1,2…,i-1和1的差,并放入L5 if L2或L4包含的L5任意一個(gè)元素then Vi++; if Vi是Vi-1和L3[last]之間某個(gè)元素then L3[last]賦給Vi Continue end if else 把Vi放入L1,把L4,L5的元素拷貝到L2,清空L4、L5 break; end if end while if最優(yōu)解的所有元素Vi全部找到then 保存最優(yōu)解,并退出循環(huán) else V3++; end for end while //根據(jù)最優(yōu)解分配數(shù)據(jù)和任務(wù)調(diào)度 當(dāng)M=N時(shí),按特解來分配數(shù)據(jù);當(dāng)M>N時(shí),將文件均勻地打包為N個(gè)Block,然后按照特解分配數(shù)據(jù),最后根據(jù)數(shù)據(jù)分配的結(jié)果來調(diào)度任務(wù) 本節(jié)將通過實(shí)驗(yàn)來驗(yàn)證算法的有效性。首先介紹評(píng)價(jià)指標(biāo),然后根據(jù)每個(gè)指標(biāo)依次對(duì)算法進(jìn)行評(píng)估。 本文提出了4個(gè)評(píng)價(jià)指標(biāo)來評(píng)估算法,分別為存儲(chǔ)節(jié)約率、數(shù)據(jù)本地性、計(jì)算性能和可擴(kuò)展性。 1)存儲(chǔ)節(jié)約率。存儲(chǔ)節(jié)約率是數(shù)據(jù)分配算法的目標(biāo)之一,反映了算法對(duì)硬盤的節(jié)約情況,可有效度量存儲(chǔ)效率。 2)數(shù)據(jù)本地性。數(shù)據(jù)本地性能夠反映數(shù)據(jù)分配算法和計(jì)算性能的好壞。因?yàn)樵诒疚牡乃惴ㄖ?任務(wù)的分配是基于數(shù)據(jù)分配的結(jié)果,所以具有數(shù)據(jù)本地性的任務(wù)在數(shù)據(jù)分配完成之后可以統(tǒng)計(jì)出來。 3)計(jì)算性能。相對(duì)于存儲(chǔ)節(jié)約率和數(shù)據(jù)本地性,計(jì)算性能能夠更加直觀地反映算法的性能。 4)可擴(kuò)展性。可擴(kuò)展性對(duì)于大數(shù)據(jù)全比較問題的大規(guī)模分布式計(jì)算是非常重要的。本文將對(duì)分布式系統(tǒng)中節(jié)點(diǎn)上不同數(shù)量的處理進(jìn)行測(cè)試。 存儲(chǔ)節(jié)約率的計(jì)算以每個(gè)節(jié)點(diǎn)上存儲(chǔ)所有數(shù)據(jù)文件作為基準(zhǔn),以節(jié)點(diǎn)上的最大文件數(shù)Vmax為衡量標(biāo)準(zhǔn),即max{|V1|,|V2|,…,|VN|}。存儲(chǔ)節(jié)約率的計(jì)算式如下: (5) 在最理想的數(shù)據(jù)分配和任務(wù)調(diào)度情況下,Vmax存在理論下界。令M為文件數(shù),N為節(jié)點(diǎn)數(shù),則共有M(M-1)/2個(gè)比較任務(wù),每個(gè)節(jié)點(diǎn)分配的比較任務(wù)不超過下式: (6) 為了完成比較任務(wù)所需的最少的文件,由于每個(gè)任務(wù)對(duì)應(yīng)2個(gè)不同的數(shù)據(jù)文件,因此可以得到式(7)。 (7) 對(duì)式(7)進(jìn)行計(jì)算得到: (8) 令M=256,對(duì)DAABGC算法和Hadoop進(jìn)行對(duì)比。如表5所示,與在每個(gè)節(jié)點(diǎn)上存儲(chǔ)所有的數(shù)據(jù)文件相比,DAABGC算法和Hadoop都具有很高的存儲(chǔ)節(jié)約率,其中,Hadoop更高一些。當(dāng)節(jié)點(diǎn)數(shù)為31時(shí),DAABGC算法的存儲(chǔ)節(jié)約率達(dá)到了80%,而Hadoop則為90%。雖然DAABGC的存儲(chǔ)節(jié)約率相對(duì)較低,但是對(duì)于所有的比較任務(wù),數(shù)據(jù)本地性都為100%,而Hadoop的高存儲(chǔ)節(jié)約率是以犧牲數(shù)據(jù)本地性為代價(jià)的。例如,當(dāng)節(jié)點(diǎn)數(shù)為31時(shí),Hadoop的數(shù)據(jù)本地性只有14%。數(shù)據(jù)本地性對(duì)于大規(guī)模的全比較計(jì)算問題十分重要,好的數(shù)據(jù)本地性能夠極大地減少任務(wù)執(zhí)行時(shí)節(jié)點(diǎn)間的數(shù)據(jù)移動(dòng),因此,DAABGC算法在高存儲(chǔ)節(jié)約率的情況下,數(shù)據(jù)本地性更好。 表5 不同數(shù)據(jù)分配策略的對(duì)比 計(jì)算性能由全比較問題總的執(zhí)行時(shí)間來表征。下文對(duì)Hadoop和DAABGC算法進(jìn)行比較。實(shí)驗(yàn)的設(shè)計(jì)如下: 1)實(shí)驗(yàn)的軟硬件環(huán)境。如表6所示,為了測(cè)試算法在真實(shí)的集群環(huán)境下的性能,筆者搭建了Hadoop集群,操作系統(tǒng)采用Centos7,將其中一個(gè)管理節(jié)點(diǎn)作為主節(jié)點(diǎn),另外一個(gè)管理節(jié)點(diǎn)作為主節(jié)點(diǎn)的備用節(jié)點(diǎn),其他節(jié)點(diǎn)作為數(shù)據(jù)節(jié)點(diǎn)。主節(jié)點(diǎn)和備用節(jié)點(diǎn),以及數(shù)據(jù)節(jié)點(diǎn)之間通過2個(gè)交換機(jī)冗余連接。 表6 集群的硬件配置 2)實(shí)驗(yàn)應(yīng)用。作為生物信息學(xué)中典型的全比較問題,CVTree被選為測(cè)試計(jì)算性能的應(yīng)用。CVTree在單機(jī)平臺(tái)的計(jì)算已經(jīng)實(shí)現(xiàn)[19],本文將在分布式的環(huán)境下來測(cè)試CVTree。 3)實(shí)驗(yàn)數(shù)據(jù)。本文選擇國(guó)家技術(shù)生物中心的一組dsDNA文件作為實(shí)驗(yàn)數(shù)據(jù),其中,每個(gè)文件的大小約為150 MB,總的數(shù)據(jù)量為20 GB。 本文對(duì)節(jié)點(diǎn)數(shù)為7時(shí)不同的數(shù)據(jù)文件做了測(cè)試。如圖3所示,當(dāng)M分別為93、109、124時(shí),DAABGC的總運(yùn)行時(shí)間都低于Hadoop,說明DAABGC算法對(duì)于解決CVTree來說具有更好的性能。 圖3 2種算法的計(jì)算效率對(duì)比 為了更好地驗(yàn)證DAABGC算法的性能,對(duì)不同數(shù)量的文件,在節(jié)點(diǎn)數(shù)為7的情況下計(jì)算總的運(yùn)行時(shí)間。如圖4所示,對(duì)于相同的文件個(gè)數(shù)M,每個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間是非常相似的,很好地滿足了式(3)所表達(dá)的負(fù)載均衡。每個(gè)節(jié)點(diǎn)上的比較任務(wù)在執(zhí)行時(shí)都訪問了本地?cái)?shù)據(jù),因?yàn)楣?jié)點(diǎn)之間不存在數(shù)據(jù)移動(dòng)。 圖4 7個(gè)節(jié)點(diǎn)的任務(wù)均衡性 可擴(kuò)展性對(duì)于大數(shù)據(jù)集全比較問題的處理很重要。可擴(kuò)展性的評(píng)估指標(biāo)為加速比。 如圖5所示,實(shí)驗(yàn)對(duì)處理器個(gè)數(shù)從1~7的情況進(jìn)行測(cè)試。從中可知DAABGC算法獲得了約6.335/7=90.5%的理想性能,由此可得,和Hadoop相比,DAABGC算法雖然占用了更多的存儲(chǔ)空間,但是也獲得了更好的性能,隨著處理器數(shù)量的增加,獲得了較好的加速比,因此,DAABGC算法具有良好的可擴(kuò)展性,能夠適應(yīng)大數(shù)據(jù)全比較問題的大規(guī)模分布式計(jì)算的要求。 圖5 本文算法獲得的加速比 本文從存儲(chǔ)使用和計(jì)算性能2個(gè)方面探討如何高效解決大數(shù)據(jù)全比較問題,并基于圖覆蓋理論提出DAABGC算法。實(shí)驗(yàn)結(jié)果表明,該算法可構(gòu)造出最優(yōu)解,得到比Hadoop更好的性能。下一步將深入研究圖覆蓋問題最優(yōu)解產(chǎn)生的理論依據(jù),并針對(duì)更多領(lǐng)域的大數(shù)據(jù)全比較問題對(duì)DAABGC算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。 [1] ZHANG Y F,TIAN Y C,KELLY W,et al.Application of simulated annealing to data distribution for all-to-all comparison problems in homogeneous systems[C]//Proceedings of ICONIP’15.Berlin,Germany:Springer,2015:683-691. [2] HAO B,QI J,WANG B.Prokaryotic phylogeny based on complete genomes without sequence alignment[J].Modern Physics Letters B,2011,17(3):91-94. [3] PHILLIPS P J,FLYNN P J,SCRUGGS T,et al.Overview of the face recognition grand challenge[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Computer Society,2005:947-954. [4] SKABAR A,ABDALGADER K.Clustering sentence-level text using a novel fuzzy relational clustering algorithm[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(1):62-75. [5] 丁三軍,薛 宇,王朝霞,等.基于模糊數(shù)據(jù)挖掘的虛擬環(huán)境主機(jī)故障預(yù)測(cè)[J].計(jì)算機(jī)工程,2015,41(11):202-206. [6] WONG A K,LEE E S.Aligning and clustering patterns to reveal the protein functionality of sequences[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2014,11(3):548-560. [7] FAISAL F E,ZHAO H,MILENKOVIC T,et al.Global network alignment in the context of aging[J].IEEE/ACM Transations on Computational Biology and Bioinformatics,2015,12(1):40-52. [8] KRISHNAJITH A P D,KELLY W,HAYWARD R,et al.Managing memory and reducing I/O cost for correlation matrix calculation in bioinformatics[C]//Proceedings of IEEE Symposium on Computational Intelligence in Bioinfor-matics and Computational Biology.Washington D.C.,USA:IEEE Press,2013:36-43. [9] ANATHTHA P D K,KELLY W,TIAN Y C.Optimizing I/O cost and managing memory for composition vector method based on correlation matrix calculation in bioinformatics[J].Current Bioinformatics,2014,9(3):234-245. [10] ZHANG Y F,TIAN Y C,KELLY W,et al.A distributed com-puting framework for all-to-all comparison problems[C]//Proceedings of IECON’14.Washington D.C.,USA:IEEE Press,2014:2499-2505. [11] ALTSCHUL S F,GISH W,MILLER W,et al.Basic local alignment search tool[J].Journal of Molecular Biology,1990,215(3):403-410. [12] THOMPSON J D,GIBSON T J,HIGGINS D G.Multiple sequence alignment using ClustalW and ClustalX[EB/J].Current Protocols in Bioinformatics,2002,2(3). [13] 欒亞建,黃翀民,龔高晟,等.Hadoop平臺(tái)的性能優(yōu)化研究[J].計(jì)算機(jī)工程,2010,36(14):262-263. [14] CHEN Q,WANG L,SHANG Z.MRGIS:a MapReduce-enabled high performance workflow system for GIS[C]//Proceedings of the 4th IEEE International Conference on e-science.Washington D.C.,USA:IEEE Computer Society,2008:646-651. [15] 程 苗,陳華平.基于Hadoop的Web日志挖掘[J].計(jì)算機(jī)工程,2011,37(11):37-39. [16] GILLETT B E,MILLER L R.A heuristic algorithm for the vehicle-dispatch problem[J].Operations Research,1974,22(2):340-349. [17] LIN S,KERNIGHAN B W.An effective heuristic algorithm for the TSP[J].Operations Research,1973,21(2):498-516. [18] THITE S.On covering a graph optimally with induced subgraphs[J].Computing,2006,44(1):1-6. [19] KRISHNAJITH A P D,KELLY W,HAYWARD R,et al.Managing memory and reducing I/O cost for correlation matrix calculation in bioinformatics[C]//Proceedings of IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology.Washington D.C.,USA:IEEE Press,2013:36-43.4 實(shí)驗(yàn)
4.1 評(píng)價(jià)指標(biāo)
4.2 存儲(chǔ)節(jié)約率和數(shù)據(jù)本地性
4.3 計(jì)算性能
4.4 可擴(kuò)展性
5 結(jié)束語