一種基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)策略

鄧 丹，李雷孝，高 靜，楊艷艷，王永生

1(內(nèi)蒙古工業(yè)大學 數(shù)據(jù)科學與應用學院，呼和浩特 010080)2(內(nèi)蒙古農(nóng)業(yè)大學 計算機與信息工程學院，呼和浩特 010011)

1 引 言

全比較問題(All-To-All Comparison，ATAC)源于在分布式系統(tǒng)中求解多序列比對任務時的數(shù)據(jù)分發(fā)和任務調(diào)度工作.通過求解全比較問題，能夠得到一個數(shù)據(jù)分發(fā)策略，該策略包含一個數(shù)據(jù)分發(fā)方案和一個任務調(diào)度方案.求解全比較問題的分布式系統(tǒng)根據(jù)得到的數(shù)據(jù)分發(fā)方案進行文件分發(fā)，一對一的比對任務依據(jù)任務調(diào)度方案在節(jié)點間進行調(diào)度.之所以說一對一的比對任務是因為多序列比對工作的原子性操作是兩個不相同文件間的比對.全比較計算頻繁出現(xiàn)在眾多學科領域，如生物信息學、自然語言處理、網(wǎng)絡工程等.在生物信息學中，典型的全比較計算應用如基因序列比對[1]、組裝[2]和蛋白質(zhì)序列比對[3]時數(shù)據(jù)文件的分發(fā).自然語言處理領域的語義相似度的計算[4]的數(shù)據(jù)分發(fā)同樣是全比較計算的應用場景.點對點網(wǎng)絡作為當前研究熱點，其數(shù)據(jù)發(fā)送問題同樣是全比較計算的應用之一[5].

在生物信息學領域全比較計算數(shù)據(jù)分發(fā)工作的研究在此之前主要分為3類.分別是全量分發(fā)、使用Hadoop的分布式文件系統(tǒng)(Hadoop Distributed File System，HDFS)進行分發(fā)以及基于全比較數(shù)據(jù)分發(fā)算法進行分發(fā).

Fumihik等人在研究利用空閑GPU來加速生物序列比對時，將需要比對的數(shù)據(jù)往每個計算節(jié)點上都發(fā)送一份[6].這種分發(fā)方式適合于數(shù)據(jù)量較小的場景，當面對海量數(shù)據(jù)時，將造成嚴重的存儲資源浪費.全量分發(fā)的方式?jīng)]有專門的負載均衡調(diào)度器，使得任務的調(diào)度需要第三方框架的支持.

鄒全等人在構建系統(tǒng)發(fā)育樹時，使用了HDFS來進行分布式存儲[7].HDFS默認采用副本數(shù)為3的分布式存儲方案，這種存儲方式能節(jié)約存儲空間.能夠隨著節(jié)點數(shù)量的增加，不斷提高存儲節(jié)約率.HDFS存儲有兩個問題.一個是副本數(shù)為3的存儲方案，不一定是最佳的，有時需要調(diào)整副本數(shù)量以適應任務的計算速度.官方?jīng)]有給出調(diào)整方案，因此用戶無法進行有效的調(diào)整.另一個問題是，節(jié)點數(shù)量通常是大于副本數(shù)的，無法實現(xiàn)完全數(shù)據(jù)本地化.HDFS是一個塊存儲的分布式存儲系統(tǒng)，當文件小于塊大小時將占用整個塊，從而造成存儲浪費.當文件大于塊時，將被拆分成多個塊進行存儲.在這種情況下，同樣無法實現(xiàn)數(shù)據(jù)文件的完全本地化.Eun-Kyu等人使用Lustre軟件平臺對HDFS進行了優(yōu)化，消除了HDFS數(shù)據(jù)傳輸產(chǎn)生的開銷，但還是存在數(shù)據(jù)不能完全本地化的問題[8].

針對全量分發(fā)和使用HDFS存儲存在的問題，自2014年就有學者專門研究全比較計算的數(shù)據(jù)分發(fā)問題.表1對現(xiàn)有的全比較數(shù)據(jù)分發(fā)算法的優(yōu)點與不足做了分析.

表1 現(xiàn)有的全比較計算數(shù)據(jù)分發(fā)算法分析

針對全量分發(fā)方式存在的存儲空間浪費問題，使用HDFS存儲無法實現(xiàn)完全數(shù)據(jù)本地化.使用啟發(fā)式解決方案、分支定界法存在的解空間較大以及計算耗時等問題.提出了基于禁忌搜索優(yōu)化[15]的全比較計算數(shù)據(jù)分發(fā)模型(Data Distribution model of All-to-All comparison computation Based on Tabu Search optimization，DDBTS)，為求解DDBTS模型設計了基于禁忌搜索優(yōu)化的負載均衡全比較數(shù)據(jù)分發(fā)算法(All-to-all Comparison Data Distribution for Load Balancing Based on Tabu Search optimization，DDLBBTS)和基于禁忌搜索優(yōu)化的最小化存儲全比較數(shù)據(jù)分發(fā)算法(All-to-all Comparison Data Distribution for Minimum Storage Based on Tabu Search optimization，DDMSBTS).其中，DDMSBTS算法依賴DDLBBTS算法的計算結果.在實驗部分將對DDBTS模型的負載均衡、存儲節(jié)約能力、數(shù)據(jù)本地化率、計算速度以及存儲優(yōu)化效果進行驗證，并與現(xiàn)有的主流全比較數(shù)據(jù)分發(fā)策略進行比較.

2 全比較計算數(shù)據(jù)分發(fā)模型構建

2.1 形式化描述

現(xiàn)有m個數(shù)據(jù)文件，文件大小完全相等或近似相等.使用具有n個節(jié)點的分布式系統(tǒng)來計算任意兩個文件的相似度.則全比較計算的形式化表述如公式(1)所示.

Mi,j={C(i,j)|i

(1)

其中Mi,j為任務C(i,j)的計算結果，i與j是文件編號，所有的Mi,j組成了全比較計算的解.在構建全比較數(shù)據(jù)分發(fā)模型之前，先提出兩個基本假設.

假設1.全比較計算任務的執(zhí)行環(huán)境為同構分布式系統(tǒng).本文研究的是在同構分布式系統(tǒng)[16]中進行的全比較計算數(shù)據(jù)分發(fā)方案，節(jié)點具有相同的計算速度與存儲能力.

假設2.數(shù)據(jù)文件大小完全相等或近似相等.全比較計算涉及的數(shù)據(jù)文件的存儲單位均為MB，文件大小數(shù)值差異不超過2.

2.2 負載均衡

有一組基因序列文件S={s1,s2,…,sm}，S中的m個文件的大小近似相等.現(xiàn)要將這m個基因序列文件在分布式系統(tǒng)中進行兩兩文件的比對，令比對的總?cè)蝿諗?shù)為k，根據(jù)組合數(shù)計算公式可得k的數(shù)學表達形式如公式(2)所示[17].

(2)

某個序列比對任務的任務量和參與比對的數(shù)據(jù)文件大小成正比.令ct表示由文件i與文件j組成的任務t的任務量，第i個文件的大小用si來表示.則ct為：

ct=si+sj,t={1，2，…，k},i

i=1,2,…,m-1,j=2,3,…,m

(3)

(4)

(5)

要獲得全比較計算在分布式系統(tǒng)下負載均衡的數(shù)據(jù)分發(fā)方案，先要得到節(jié)點p所需承擔的計算量wp，wp的形式化描述如公式(6)所示.

(6)

使用wavg來表示在進行本次全比較計算時，分布式系統(tǒng)中的節(jié)點平均計算量.由于wp是在尋優(yōu)的過程中動態(tài)生成的，因此不能通過公式(6)來進行求解.但是能夠通過公式(2)與公式(3)以及節(jié)點個數(shù)n來獲取wavg.計算方法如公式(7)所示.

(7)

本文所述的負載均衡是指分布式系統(tǒng)中各個節(jié)點上的計算量負載要盡可能相同.負載均衡狀態(tài)能通過累加wp與wavg差值的絕對值來表征.完全負載均衡時，該絕對值為0.但初始值一般是大于零的值，尋優(yōu)過程實質(zhì)上是不斷縮小這個絕對值，使得這個絕對值的右極限為0.由公式(2)、公式(6)、公式(7)能求出負載均衡模型目標函數(shù)的形式化描述如公式(8).

(8)

硬盤資源是計算機的重要資源之一，是DDBTS模型中必須要考慮的一個因素.為了保證全比較計算的性能，需要讓所有節(jié)點都能存儲全部的數(shù)據(jù)文件.令同構分布式系統(tǒng)中節(jié)點的硬盤剩余容量為U，則負載均衡模型的存儲約束能夠形式化地描述為：

(9)

公式(2)-公式(9)能得出m個序列數(shù)據(jù)文件在由n個節(jié)點組成的同構分布式系統(tǒng)中的全比較計算負載均衡模型如公式(10)所示.

(10)

根據(jù)負載均衡模型，能求出在分布式系統(tǒng)下進行全比較計算的任務調(diào)度方案.將任務調(diào)度方案與任務列表進行聯(lián)合解析，可得到全比較計算的數(shù)據(jù)分發(fā)方案.負載均衡模型求得的數(shù)據(jù)分發(fā)方案只能滿足全比較計算的計算量負載均衡目標，在下一節(jié)中將在公式(10)的基礎上進行存儲優(yōu)化.

2.3 存儲優(yōu)化

通過公式(10)求得的任務調(diào)度方案可以計算出全部節(jié)點的計算量，將節(jié)點的最大計算量記為Nmax.在存儲優(yōu)化過程中，要保證每個節(jié)點所承擔的任務量都不超過Nmax.即：

(11)

(12)

綜上所述，可得在n個節(jié)點的分布式系統(tǒng)下進行m個文件的全比較計算，同時滿足負載均衡和最小化存儲的數(shù)據(jù)分發(fā)模型為：

(13)

通過對公式(13)進行解析，即可得到計算量負載均衡的全比較計算任務調(diào)度方案和實現(xiàn)分布式系統(tǒng)下的最小化存儲數(shù)據(jù)文件分發(fā)方案.

3 DDBTS模型相關算法設計與實現(xiàn)

DDBTS模型分為兩個階段進行計算，第1階段根據(jù)公式(10)求出負載均衡狀態(tài)的任務調(diào)度方案.第2階段根據(jù)公式(13)求得基于禁忌搜索優(yōu)化的全比較計算數(shù)據(jù)分發(fā)方案.任務調(diào)度方案和數(shù)據(jù)分發(fā)方案共同組成全比較數(shù)據(jù)分發(fā)策略，該策略滿足負載均衡、最小化存儲和數(shù)據(jù)完全本地化.

禁忌搜索算法是Glover教授于1986年提出來的，顯著的優(yōu)點之一是能基于禁忌表實現(xiàn)記憶式搜索[18].禁忌搜索算法的算子包括：適應度方程、編碼方案、鄰域結構、鄰域長度、候選解、禁忌表、禁忌長度和藐視準則.禁忌搜索算法因具有快速收斂的特性而被選作與全比較計算數(shù)據(jù)分發(fā)模型進行融合.在算法的設計與實現(xiàn)過程中，對禁忌搜索算法的算子進行了定制化實現(xiàn).

3.1 DDLBBTS算法設計

1)初始化參數(shù)

DDLBBTS算法涉及的一些參數(shù)的描述和初始化取值如表2所示.

表2 DDLBBTS算法參數(shù)設置

2)n進制編碼

DDLBBTS算法的編碼方案采用n進制編碼，n為節(jié)點數(shù)量，編碼長度表征任務個數(shù).在DDLBBTS算法中，n進制編碼的現(xiàn)實意義為某個任務應該被分派到某一個節(jié)點上.

3)負載偏離程度計算函數(shù)

DDLBBTS算法的適配值函數(shù)f1須滿足公式(10)中的目標函數(shù)，即求出編碼方案對應的負載均衡偏離程度loadtotal.在求解過程中，能夠得到每個節(jié)點的計算量負載情況，用loadi表示節(jié)點i的計算量負載情況.loadi的取值覆蓋整個實數(shù)域，大于0時表示節(jié)點負載超標，小于0表示節(jié)點負載過少，節(jié)點的計算量負載等于計算量負載的均值時loadi為0.使用offset存儲所有的loadi并將loadtotal和offset作為f1的返回值，稱該適配值函數(shù)為負載偏離程度計算函數(shù).

4)正向任務調(diào)度規(guī)則

鄰域結構是禁忌搜索算法中的一個關鍵算子，常用的鄰域結構設計方法包括互換、插值、逆序等[19].這些常用的鄰域設計方法通常需要隨機選取編碼的位置，隨機選取編碼的位置在DDLBBTS算法中是不適用的.故本文提出使用正向任務調(diào)度規(guī)則作為DDLBBTS算法的鄰域結構，其核心思想為找出待分配的任務和待指派的節(jié)點，并將任務隨機分派到待指派的節(jié)點上.從負載超標的節(jié)點上選取一個任務調(diào)度到負載過少的節(jié)點上進行計算.使用正向任務調(diào)度規(guī)則作為鄰域設計方案，能動態(tài)調(diào)整節(jié)點之間的負載，讓節(jié)點的計算量負載朝著均分的方向優(yōu)化.在定位負載超標節(jié)點時，如果出現(xiàn)了負載超標節(jié)點數(shù)量為0的情況，則說明該編碼方案是最優(yōu)狀態(tài)，應立即終止尋優(yōu)迭代并將當前最優(yōu)狀態(tài)對應的編碼bestsoforlb輸出.否則，構建一個待選擇任務的集合x并找出所有負載過少的節(jié)點集合Y.從X選出一個任務xi調(diào)度到Y中的節(jié)點yi上，組成DDLBBTS算法的鄰域結構A.

5)負載均衡鄰域解與候選解

6)負載均衡藐視準則

3.2 DDLBBTS算法實現(xiàn)

DDLBBTS算法采用n進制編碼、正向任務調(diào)度等定制化規(guī)則與公式(10)進行融合.最終設計出DDLBBTS算法如算法1所示.第5行-第11行對全比較數(shù)據(jù)分發(fā)的一種特殊情況進行了優(yōu)化.當文件大小完全相同且比較任務能夠被均勻分發(fā)到節(jié)點時，只需為每個節(jié)點指派等量的任務即可讓分布式系統(tǒng)達到完全負載均衡狀態(tài).第16行-第32行是正向任務調(diào)度規(guī)則的實現(xiàn).第33行通過對鄰域解的負載偏離程度進行升序排序得到Cabest.第34行-第42行是負載均衡藐視準則的實現(xiàn).

算法1.基于禁忌搜索優(yōu)化的負載均衡全比較數(shù)據(jù)分發(fā)算法

輸入：文件大小列表files、節(jié)點數(shù)量n、剩余存儲capacity

1. 根據(jù)公式(9)對files，capacity進行計算；

2. 計算文件個數(shù)m←size(files,2)；

3. 根據(jù)公式(3)構建任務矩陣tasks；

4. 計算任務個數(shù)tc←size(tasks,1)；

5.ifsize(unique(files),2)=1andmod(tc,n)=0then

6.fori1totcby1 do

7.bestsofarlb(i)←mod(i,n)+1；

8.endfor

10. return;

11.endif

16. 找出能夠提供任務的節(jié)點編號:

[～,nodes]←find(offset>0);

17. 計算能夠提供待指派任務的節(jié)點個數(shù)

num←size(nodes,2);

18.ifnum← 0then

19. break;

20.endif

21. 令鄰解個數(shù)LCa←0;令待調(diào)度任務集合X←[];

22.fori1tonumby1do

25.endfor

26. 找出待指派的節(jié)點編號Y←find(offset<0);

27. 初始化鄰域結構A←[],迭代變量i←1;

28.whilei≤LCado

29.if[xi,yi]?Athen

30.A=[A;[xi,yi]];

31.endif

32.endwhile

33. 計算鄰域解并求出候選解Cabest;

36.else

37.fori1tosize(tabu1,1)by1do

38.loadtotal←從Cabest找出第一個優(yōu)于tabu1(i)的候選解;

39. 更新相關參數(shù);

40.endfor

42.endif

43.p←p+1;

44.endwhile

3.3 DDMSBTS算法設計

1)初始化參數(shù)

表3 DDMSBTS算法參數(shù)設置

2)存儲優(yōu)化適配值函數(shù)

DDMSBTS算法的適配值函數(shù)f2旨在根據(jù)公式(12)求出分布式系統(tǒng)所需提供的存儲空間，同時得到公式(11)左邊表示的所有節(jié)點計算量負載nodeLoads并求出最大的節(jié)點計算量負載nodeLoadmax.為了保證在尋優(yōu)過程中負載均衡情況不變壞，全部節(jié)點計算量負載的極差不能超過任務列表中的最大任務量taskmax，否則要對當前編碼方案對應的nodeLoadmax進行懲罰.上述描述能夠形式化表示成公式(14).

(14)

3)異節(jié)點任務互換

由公式(1)可知全比較計算的任務需要兩個不同的文件，在一次全比較計算中，任務具有原子性和唯一性.因此，通過交換不同節(jié)點上的兩個任務能夠?qū)?jié)點上的文件分發(fā)方案進行擾動.不斷選擇存儲空間減小的編碼方案，從而達到尋優(yōu)目標.基于以上思想，能夠得到一個鄰域結構B.

4)負載約束鄰域解與最優(yōu)存儲候選解

5)最優(yōu)存儲藐視準則

6)自適應迭代次數(shù)

3.4 DDMSBTS算法實現(xiàn)

算法2.基于禁忌搜索優(yōu)化的最小化存儲全比較數(shù)據(jù)分發(fā)算法

輸入：files、n、bestsofarlb、最大節(jié)點計算量maxLoad

1. 計算文件個數(shù)m←size(files,2);

2. 根據(jù)公式(3)構建任務矩陣tasks;

3. 計算任務個數(shù)tc←size(tasks,1);

8. 初始化鄰域結構B←zeros(LCa,2),當前迭代次數(shù)i←1;

9.whilei≤LCado

10.task1← 隨機取出一個任務;

12.task2←從other中隨機取出第二個任務;

13.B(i,1)←max(task1,task2),B(i,2)←min(task1,task2);

14. 保證B(i,j)的唯一性;

15.endwhile

16. 設置鄰域長度LCabest←round(LCa/2);

17. 設置鄰域集合Cabest←Inf×ones(LCabest,4);

18. 設置適配值集合F←zeros(1,LCa);

19.fori1toLCaby1do

22. [nodeLoadmax,F(i)]←f2(SetCa(i,:),task,n,files);

23.ifnodeLoadmax>maxLoadthen

24.F(i)←Inf;

25.endif

26. 更新Cabest;

27.endfor

28.ifCabest(1,2)≤Rmsthen

30.else

31.fori1toLCabestby1do

32.iftabu2(Cabest(i,3),Cabest(i,4))=0then

34.endif

35.endfor

36.endif

41.endif

42.endif

43.p←p+1;

45.endwhile

4 實驗部分

4.1 實驗設置

實驗環(huán)境的配置不僅要能支撐本文提出的數(shù)據(jù)分發(fā)算法的運行，同時要支持運行現(xiàn)有的主流數(shù)據(jù)分發(fā)算法以便于實驗對比工作的開展.詳細配置情況如表4所示.實驗數(shù)據(jù)選用從NCBI下載的基因序列數(shù)據(jù)，數(shù)據(jù)擴充采用文件切分的方式進行.

表4 實驗環(huán)境

本文將基于MATLAB對全比較計算數(shù)據(jù)分發(fā)模型進行實現(xiàn)，并完成評價指標驗證和對比實驗.在VMWare上構建Hadoop平臺，使用Java編寫全比較計算模擬程序?qū)蛐蛄袛?shù)據(jù)文件進行分發(fā)，以及調(diào)度全比較任務.

為了驗證DDBTS模型的性能，進行了負載均衡、存儲節(jié)約率與數(shù)據(jù)本地化、求解效率、存儲優(yōu)化等實驗.前3個實驗將對比DDBTS模型求得數(shù)據(jù)分發(fā)策略與現(xiàn)有主流數(shù)據(jù)分發(fā)策略的性能差異.存儲優(yōu)化實驗將對DDMSBTS算法的存儲空間優(yōu)化效果進行驗證.

4.2 評價指標

對DDBTS模型進行求解，能夠得到一套分布式系統(tǒng)下的任務調(diào)度方案和數(shù)據(jù)分發(fā)方案.根據(jù)任務調(diào)度方案能分析出分布式系統(tǒng)下全比較計算的負載均衡程度，對數(shù)據(jù)分發(fā)方案按節(jié)點進行存儲空間統(tǒng)計并結合全量分發(fā)的存儲使用情況能得出分布式系統(tǒng)下全比較計算的存儲節(jié)約率.對各個節(jié)點完成指定計算任務所需的數(shù)據(jù)分發(fā)情況和對應節(jié)點上的數(shù)據(jù)分發(fā)方案進行計算，能算出數(shù)據(jù)分發(fā)策略在分布式系統(tǒng)下的數(shù)據(jù)本地化率.對DDBTS模型中兩個算法的執(zhí)行時間進行記錄，即可得到模型的計算時間.

負載均衡程度.對節(jié)點i的任務量進行統(tǒng)計可得li，所有的li組成集合L.由任務列表可得最大的任務量為tmax.若L中的元素完全相等，則當前全比較計算任務調(diào)度方案實現(xiàn)了完全負載均衡.若L中的元素不完全相等，但L中的最大值和最小值之差未超過tmax，稱這種狀態(tài)是近似負載均衡狀態(tài).其它情況均為非負載均衡狀態(tài).

存儲節(jié)約率.存儲節(jié)約率是DDBTS模型重要評價指標之一，也是DDMSBTS算法的優(yōu)化目標.將全量分發(fā)情況下分布式系統(tǒng)所需提供的存儲空間作為分母，分子為DDBTS模型計算所得的數(shù)據(jù)分發(fā)方案對應的存儲空間.這個分數(shù)能夠表征分布式系統(tǒng)的存儲空間利用率，故存儲節(jié)約率為1減去存儲空間利用率.

數(shù)據(jù)本地化率.若計算節(jié)點執(zhí)行全部比較任務所需的文件都在某個節(jié)點上，則該節(jié)點的數(shù)據(jù)本地化率為1，對應的狀態(tài)稱為完全數(shù)據(jù)本地化.否則，取在該節(jié)點上有效文件的總大小與所需文件的總大小的比值來描述計算節(jié)點的數(shù)據(jù)本地化率.

計算時間.計算時間表示全比較數(shù)據(jù)分發(fā)策略的求解時間，在DDBTS模型中，該評價指標主要包括DDLBBTS算法和DDMSBTS算法的執(zhí)行時間，由驅(qū)動模塊進行統(tǒng)計.

4.3 相關實驗

在這個實驗中，對DDBTS模型進行了若干次實驗.其中的一組實驗數(shù)據(jù)及相關描述如表5所示.

表5 實驗數(shù)據(jù)

根據(jù)表5對DDBTS模型進行多次實驗，求出各組實驗方案對應的全比較計算的任務調(diào)度方案與文件分發(fā)方案.隨機選取一次實驗的結果，如表6所示.

表6 任務調(diào)度與文件分發(fā)情況

4.3.1 負載均衡

將表5中的實驗數(shù)據(jù)放入基于禁忌搜索優(yōu)化實現(xiàn)的全比較數(shù)據(jù)分發(fā)模型，得到模型的負載均衡情況如圖1所示.各組實驗的負載均衡情況，與基于分支定界法求解的全比較數(shù)據(jù)分發(fā)模型和基于粒子群優(yōu)化的全比較數(shù)據(jù)分發(fā)模型的負載均衡情況表現(xiàn)基本一致.即當文件大小完全相同且比較任務數(shù)能被節(jié)點數(shù)整除時，分布式集群中各個節(jié)點的負載量能夠?qū)崿F(xiàn)完全均衡.其余情況下，均能讓分布式集群中的各個節(jié)點實現(xiàn)近似負載均衡狀態(tài).

圖1 負載均衡情況

4.3.2 存儲節(jié)約率與數(shù)據(jù)本地化率

為了與現(xiàn)有的數(shù)據(jù)分發(fā)算法對比存儲節(jié)約率和數(shù)據(jù)本地化率，我們得到了如圖2所示的存儲節(jié)約情況和圖3所示的數(shù)據(jù)本地化情況.

圖2 不同數(shù)據(jù)分發(fā)算法的存儲節(jié)約情況

圖3 不同數(shù)據(jù)分發(fā)算法的數(shù)據(jù)本地化情況

由圖2可知，基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)模型獲得的數(shù)據(jù)分發(fā)方案能夠有效地降低分布式集群中節(jié)點的存儲空間使用.在實驗2和實驗4中，基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)模型的存儲節(jié)約率均優(yōu)于基于Hadoop進行數(shù)據(jù)分發(fā)的方式和基于分支定界法求解的數(shù)據(jù)分發(fā)算法.在實驗1和實驗3中，基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)模型的存儲節(jié)約情況比基于Hadoop進行數(shù)據(jù)分發(fā)的方式要略差.根據(jù)圖3可知，盡管在存儲節(jié)約情況方面基于Hadoop的數(shù)據(jù)分發(fā)方式能夠?qū)崿F(xiàn)較優(yōu)于基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)模型，但是基于Hadoop數(shù)據(jù)分發(fā)方式的數(shù)據(jù)本地化情況較差.在進行全比較計算的過程中，需要從其它節(jié)點或數(shù)據(jù)中心獲取文件，極有可能造成網(wǎng)絡擁堵.

4.3.3 求解效率

通過記錄每組實驗的計算時間，我們得到了如表7所示的3種數(shù)據(jù)分發(fā)算法的執(zhí)行時間.顯然，DDBTS模型在各個實驗方案的計算速度上都是領先的.盡管在圖2中，基于禁忌搜索優(yōu)化的全比較數(shù)據(jù)分發(fā)模型的存儲節(jié)約率不如基于分支定界法的數(shù)據(jù)分發(fā)算法和基于粒子群優(yōu)化的數(shù)據(jù)分發(fā)算法，但其計算速度遠比這兩種算法快，更適合于實際的工程應用場景.

表7 不同數(shù)據(jù)分發(fā)算法的計算時間

4.3.4 存儲優(yōu)化實驗

分別針對不同任務規(guī)模量、計算節(jié)點數(shù)量的輸入數(shù)據(jù)進行了實驗.對DDBTS模型優(yōu)化前后的負載均衡情況與存儲節(jié)約率進行了分析.實驗設置和相關實驗結果及分析如下所示.

1)小規(guī)模數(shù)據(jù)量實驗

隨機選取10個大小近似相等的基因序列文件，分布式集群的規(guī)模分別選取5個計算節(jié)點或4個計算節(jié)點.設計了4組小規(guī)模數(shù)據(jù)量實驗，實驗的輸入數(shù)據(jù)如表8所示.

表8 小規(guī)模數(shù)據(jù)量實驗輸入數(shù)據(jù)

本文對實驗5-實驗8依次進行了10次實驗，實驗結果如圖4所示.在小規(guī)模數(shù)據(jù)量的情況下，DDBTS模型在存儲優(yōu)化之后的存儲節(jié)約率基本有改善.實驗5表現(xiàn)得尤為明顯，由DDLBBTS算法獲得的文件分發(fā)方案對應的存儲節(jié)約率僅為10%，而DDMSBTS算法輸出的文件分發(fā)方案對應的存儲節(jié)約率達到了34%～38%.實驗6-實驗8雖然節(jié)約了一些存儲空間，但是存儲節(jié)約率波動較大.其中，實驗8的波動最為嚴重，優(yōu)化后的存儲節(jié)約率的極差為14.7%.這種波動可能是數(shù)據(jù)量過小導致的，該猜想能夠通過大規(guī)模數(shù)據(jù)量實驗進行驗證.

圖4 小規(guī)模數(shù)據(jù)量的存儲優(yōu)化效果

2)大規(guī)模數(shù)據(jù)量實驗

在大規(guī)模數(shù)據(jù)量實驗中，增加了進行全比較計算的節(jié)點，同時增加了全比較計算涉及的文件數(shù)量.大規(guī)模數(shù)據(jù)量實驗的實驗數(shù)據(jù)如表9所示.

表9 大規(guī)模數(shù)據(jù)量實驗輸入數(shù)據(jù)

圖5所示的是實驗9-實驗12的存儲優(yōu)化情況.在存儲優(yōu)化后，實驗9-實驗12的存儲節(jié)約率達到了40%-50%.與圖4所示的實驗5-實驗8的存儲節(jié)約情況進行比較可知，大規(guī)模數(shù)據(jù)量實驗的存儲優(yōu)化效果更佳.存儲優(yōu)化后，實驗9-實驗12的存儲節(jié)約率極差分別為3.6%、2.23%、4.42%、4.7%，相比于小規(guī)模數(shù)據(jù)實驗的存儲節(jié)約效果要穩(wěn)定很多.根據(jù)DDBTS模型求得的數(shù)據(jù)分發(fā)策略在大規(guī)模數(shù)據(jù)量的情況下，存儲節(jié)約的效果穩(wěn)定.

圖5 大規(guī)模數(shù)據(jù)量的存儲優(yōu)化效果

5 總 結

本文研究了ATAC的數(shù)據(jù)分發(fā)問題，對主流的全比較數(shù)據(jù)算法進行了總結.構建了全比較數(shù)據(jù)分發(fā)模型，并提出了DDBTS模型.基于禁忌搜索算法設計了DDLBBTS算法與DDMSBTS算法，最后在MATLAB平臺上實現(xiàn)了相關算法.通過實驗證明了DDBTS模型求得的數(shù)據(jù)分發(fā)策略能夠讓分布式系統(tǒng)實現(xiàn)負載均衡，比較任務涉及的數(shù)據(jù)文件具有完全的數(shù)據(jù)本地性.盡管在存儲節(jié)約率方面稍遜于其它ATAC數(shù)據(jù)分發(fā)算法，但是其計算速度卻遠快于其它ATAC數(shù)據(jù)分發(fā)算法.在存儲優(yōu)化實驗中，驗證了DDBTS模型中存儲優(yōu)化過程的有效性以及DDBTS模型輸出的文件分發(fā)方案在大規(guī)模數(shù)據(jù)量下存儲效果穩(wěn)定，存儲節(jié)約率達到了40%-50%.DDBTS模型有效解決了大規(guī)模ATAC的數(shù)據(jù)分發(fā)問題，提高了計算速度，對生物信息學等學科ATAC任務的計算將產(chǎn)生較好的推動效果.

DDBTS模型是一個數(shù)據(jù)預分發(fā)模型，在開始ATAC之前即完成任務在分布式節(jié)點上的安排.如果出現(xiàn)節(jié)點故障，將需要重新進行數(shù)據(jù)分發(fā)方案和任務調(diào)度方案的計算.盡管DDBTS模型具備較快的計算速度，如果能夠提高任務調(diào)度方案的容錯能力，模型將更具實用性.因此，提高ATAC數(shù)據(jù)分發(fā)模型的容錯性是我們下一步模型優(yōu)化工作中的重點.本文僅對同構分布式系統(tǒng)下ATAC的數(shù)據(jù)分發(fā)工作進行了研究，在未來的工作中，我們將對異構分布式系統(tǒng)下的數(shù)據(jù)分發(fā)工作進行研究.