基于粒子群優(yōu)化的全比較計(jì)算數(shù)據(jù)分發(fā)策略

李雷孝，鄧 丹，李 杰，王永生

1.內(nèi)蒙古工業(yè)大學(xué) 數(shù)據(jù)科學(xué)與應(yīng)用學(xué)院，呼和浩特 010080

2.內(nèi)蒙古自治區(qū)基于大數(shù)據(jù)的軟件服務(wù)工程技術(shù)研究中心，呼和浩特 010080

全比較計(jì)算[1]是一種典型的計(jì)算模式，用于解決兩兩數(shù)據(jù)文件相關(guān)聯(lián)的一類(lèi)計(jì)算。全比較計(jì)算作為一類(lèi)特殊的計(jì)算模式在眾多學(xué)科領(lǐng)域中頻繁出現(xiàn)，如：生物信息學(xué)[2-5]、生物測(cè)定學(xué)[6-8]、傳統(tǒng)機(jī)器學(xué)習(xí)領(lǐng)域[9]、自然語(yǔ)言處理領(lǐng)域[10]、交通大數(shù)據(jù)領(lǐng)域[11]。

國(guó)內(nèi)外學(xué)者針對(duì)全比較計(jì)算一直在開(kāi)展研究，全比較計(jì)算是研究的熱點(diǎn)之一。在國(guó)外，有學(xué)者曾將全比較任務(wù)所需的全部數(shù)據(jù)在分布式集群中的各個(gè)計(jì)算節(jié)點(diǎn)均復(fù)制一份[12]。這種分發(fā)方式適用于小數(shù)據(jù)量的情況，在面對(duì)海量數(shù)據(jù)時(shí)將造成嚴(yán)重的網(wǎng)絡(luò)擁堵與存儲(chǔ)空間的浪費(fèi)。有人曾使用Hadoop的分布式存儲(chǔ)文件系統(tǒng)（Hadoop Distributed File System，HDFS）來(lái)存儲(chǔ)執(zhí)行全比較任務(wù)所需的數(shù)據(jù)[13]。HDFS采用分布式的副本存儲(chǔ)方案，該組件默認(rèn)采用副本數(shù)為3的存儲(chǔ)方案。這種數(shù)據(jù)存儲(chǔ)方式，雖然能夠節(jié)約存儲(chǔ)空間，但無(wú)法保證在執(zhí)行比較任務(wù)時(shí)數(shù)據(jù)的完全本地化。Chaudhary等人在分析生物序列時(shí)搭建了一個(gè)異構(gòu)計(jì)算平臺(tái)。為了實(shí)現(xiàn)整個(gè)系統(tǒng)的負(fù)載均衡，他們根據(jù)節(jié)點(diǎn)的硬件配置來(lái)分配任務(wù)。在數(shù)據(jù)分配方面，他們將數(shù)據(jù)庫(kù)進(jìn)行分割，然后將其分發(fā)到各個(gè)節(jié)點(diǎn)上。盡管使用異構(gòu)計(jì)算平臺(tái)進(jìn)行計(jì)算，但仍然無(wú)法避免從集群中的其他節(jié)點(diǎn)上請(qǐng)求數(shù)據(jù)[14]。對(duì)于通用的全比較數(shù)據(jù)分發(fā)方案，有學(xué)者提出了使用啟發(fā)式的方案來(lái)進(jìn)行全比較計(jì)算的數(shù)據(jù)分發(fā)與任務(wù)調(diào)度[1]。該方法使用枚舉的方式來(lái)獲取最優(yōu)的數(shù)據(jù)分發(fā)方案，當(dāng)遇到大數(shù)據(jù)集時(shí)，該方法將成為一個(gè)NP難問(wèn)題。在這個(gè)研究的基礎(chǔ)上，該學(xué)者又提出了使用模擬退火算法的思想構(gòu)造元啟發(fā)式的數(shù)據(jù)分發(fā)算法，該算法能夠有效地降低分布式系統(tǒng)中存儲(chǔ)空間的使用[15]。

在國(guó)內(nèi)，有學(xué)者提出了使用圖覆蓋的方式來(lái)進(jìn)行全比較任務(wù)的數(shù)據(jù)分配，并基于圖覆蓋理論提出了DAABGC算法[16]。DAABGC算法在文件個(gè)數(shù)與節(jié)點(diǎn)個(gè)數(shù)相同的條件下能夠得到較好的數(shù)據(jù)分發(fā)方案，但不適用于數(shù)據(jù)文件個(gè)數(shù)與節(jié)點(diǎn)個(gè)數(shù)不同的場(chǎng)景。在之前的全比較計(jì)算研究中，采用了分支定界法求解的方法來(lái)完成全比較計(jì)算的數(shù)據(jù)分發(fā)[17]，這種方法雖然能夠獲得最優(yōu)化的數(shù)據(jù)分發(fā)方案，但需要犧牲一定的求解時(shí)間。

綜上所述，目前全比較計(jì)算的數(shù)據(jù)分發(fā)研究成果還存在一些問(wèn)題。本文對(duì)全比較計(jì)算的數(shù)據(jù)分發(fā)問(wèn)題進(jìn)一步展開(kāi)理論分析，并將該問(wèn)題與粒子群算法的思想相結(jié)合，構(gòu)建了一個(gè)基于粒子群優(yōu)化（Particle Swarm Optimization，PSO）的數(shù)據(jù)分發(fā)模型，提出了基于粒子群優(yōu)化實(shí)現(xiàn)負(fù)載均衡的數(shù)據(jù)分發(fā)算法（Data Distribution Based on Particle Swarm Optimization for Load Balance，DDBPSOLB）和基于粒子群優(yōu)化實(shí)現(xiàn)最優(yōu)化存儲(chǔ)的數(shù)據(jù)分發(fā)算法（Data Distribution Based on Particle Swarm Optimization for Best Storage，DDBPSOBS）。最后基于Matlab 驗(yàn)證了模型的可行性，并通過(guò)相關(guān)實(shí)驗(yàn)與Hadoop 框架數(shù)據(jù)分發(fā)策略作比較，驗(yàn)證了算法在分布式系統(tǒng)中各節(jié)點(diǎn)計(jì)算負(fù)載均衡、存儲(chǔ)空間占用、數(shù)據(jù)本地化、算法運(yùn)算速度方面的優(yōu)勢(shì)。

1 全比較計(jì)算相關(guān)研究

1.1 全比較計(jì)算

在全比較計(jì)算的數(shù)據(jù)集中，兩兩數(shù)據(jù)間必然且僅僅會(huì)發(fā)生一次比較計(jì)算。在一個(gè)具有m個(gè)數(shù)據(jù)文件的數(shù)據(jù)集和n個(gè)節(jié)點(diǎn)的分布式集群中，設(shè)具體的比較算法為C(i,j)，其中i和j是數(shù)據(jù)集中的兩個(gè)數(shù)據(jù)文件。全比較計(jì)算能夠被形式化地描述為公式（1）。其中Mi,j是比較運(yùn)算C(i,j)的計(jì)算結(jié)果。

1.2 全比較計(jì)算的數(shù)據(jù)分發(fā)模型構(gòu)建

本文研究的是同構(gòu)分布式系統(tǒng)下的數(shù)據(jù)分發(fā)工作，假定分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)的軟硬件配置一致。在核酸序列比對(duì)中[18]，數(shù)據(jù)文件的大小是相同或近似相同的。假設(shè)數(shù)據(jù)集中有m個(gè)數(shù)據(jù)文件，每個(gè)數(shù)據(jù)文件的大小為si，i=1,2,…,m。那么數(shù)據(jù)文件的大小相同或近似相同的形式化描述如下：

全比較計(jì)算的數(shù)據(jù)分發(fā)工作要使得節(jié)點(diǎn)間的負(fù)載達(dá)到均衡，降低分布式系統(tǒng)總體的存儲(chǔ)空間使用。同時(shí)要保證每個(gè)比較任務(wù)都能夠使用具有本地化屬性的數(shù)據(jù)，盡可能地減少每一臺(tái)計(jì)算節(jié)點(diǎn)上的存儲(chǔ)空間。

在進(jìn)行兩兩數(shù)據(jù)文件的比較運(yùn)算時(shí)，兩個(gè)數(shù)據(jù)文件的大小之和與比較運(yùn)算的計(jì)算量將成正比。令cij表示比較任務(wù)C(i,j)的計(jì)算量。則cij與數(shù)據(jù)文件i和數(shù)據(jù)文件j有如下關(guān)系：

根據(jù)公式（2）可知所有的cij的數(shù)值將相同或近似相同。假設(shè)為節(jié)點(diǎn)p上分配K個(gè)比較任務(wù)，每個(gè)任務(wù)的計(jì)算量為，i和j為分發(fā)到節(jié)點(diǎn)p上數(shù)據(jù)文件的編號(hào)，節(jié)點(diǎn)p上的任務(wù)量大小pc為：

令tcount為全比較計(jì)算中的總?cè)蝿?wù)個(gè)數(shù)，一個(gè)比較任務(wù)與兩個(gè)不同的數(shù)據(jù)文件有關(guān)，當(dāng)數(shù)據(jù)集中有m個(gè)數(shù)據(jù)文件時(shí)，tcount為：

使用xkp來(lái)表示是否將比較任務(wù)k分配到節(jié)點(diǎn)p上，由公式（1）可知xkp具有唯一性，在進(jìn)行任務(wù)分配時(shí)，每個(gè)比較任務(wù)能且必須分配到一個(gè)計(jì)算節(jié)點(diǎn)上。xkp的取值使用0 和1 來(lái)表示，1 表示將比較任務(wù)k分配到計(jì)算節(jié)點(diǎn)p上，0表示不進(jìn)行分配。

用ck表示第k個(gè)任務(wù)的大小，那么公式（4）中節(jié)點(diǎn)p上的任務(wù)量大小pc能夠被重新定義為：

在具有n個(gè)計(jì)算節(jié)點(diǎn)的分布式系統(tǒng)中，用ck表示任務(wù)k的大小，全比較計(jì)算的節(jié)點(diǎn)平均計(jì)算量cavg為：

由公式（7）、公式（8）可以得出節(jié)點(diǎn)p的計(jì)算量相對(duì)于cavg的偏離程度f(wàn)p。

那么分布式系統(tǒng)的負(fù)載均衡能夠被描述為：

令wq表示分發(fā)到節(jié)點(diǎn)p上的文件的總大小。假設(shè)分發(fā)到節(jié)點(diǎn)p上的文件數(shù)為m′(m′≤m)，wp中文件i的大小為ri。則有：

令up(p=1,2,…,n)為節(jié)點(diǎn)p的存儲(chǔ)空間上限，分發(fā)到節(jié)點(diǎn)p上的文件大小總和不能超過(guò)up。

以公式（10）作為求解目標(biāo)，得到全比較計(jì)算在分布式系統(tǒng)中的負(fù)載均衡求解模型如下：

根據(jù)公式（13）進(jìn)行全比較任務(wù)在分布式系統(tǒng)中的調(diào)度將使得各個(gè)計(jì)算節(jié)點(diǎn)之間實(shí)現(xiàn)負(fù)載均衡，并且能夠保證每個(gè)比較任務(wù)所需的數(shù)據(jù)文件具有數(shù)據(jù)本地性。在這個(gè)基礎(chǔ)上，對(duì)模型進(jìn)行優(yōu)化，期待找到一個(gè)最小化分布式系統(tǒng)中所需存儲(chǔ)空間的數(shù)據(jù)分發(fā)方案。

數(shù)據(jù)文件與比較任務(wù)之間存在一個(gè)多對(duì)多的關(guān)系，即同一個(gè)數(shù)據(jù)文件與多個(gè)比較任務(wù)相關(guān)，一個(gè)比較任務(wù)需要兩個(gè)數(shù)據(jù)文件?；谶@種多對(duì)多關(guān)系進(jìn)行任務(wù)分配的重組，調(diào)整執(zhí)行比較任務(wù)k的計(jì)算節(jié)點(diǎn)，修改數(shù)據(jù)文件分發(fā)方案，得到一個(gè)數(shù)據(jù)分發(fā)方案與任務(wù)調(diào)度方案。

通過(guò)公式（13）能夠得到負(fù)載均衡狀態(tài)下每個(gè)節(jié)點(diǎn)的計(jì)算量，記為gi(i=1,2,…,n)。gi之間可能存在數(shù)值上的差異。在優(yōu)化算法中，讓每個(gè)計(jì)算節(jié)點(diǎn)上計(jì)算量都不超過(guò)gi的最大值。通過(guò)公式（7）對(duì)節(jié)點(diǎn)計(jì)算量的描述得到，某一時(shí)刻節(jié)點(diǎn)p上的任務(wù)分配情況與計(jì)算量的關(guān)系如下：

在具有n個(gè)計(jì)算節(jié)點(diǎn)的分布式系統(tǒng)中，將m個(gè)數(shù)據(jù)文件進(jìn)行分發(fā)。每個(gè)文件在一臺(tái)計(jì)算節(jié)點(diǎn)上最多只有一個(gè)備份，用yjp表示是否將第j個(gè)數(shù)據(jù)文件分發(fā)到第p個(gè)節(jié)點(diǎn)上，yjp取值為1 時(shí)表示將第j個(gè)數(shù)據(jù)文件分發(fā)到第p個(gè)節(jié)點(diǎn)上，yjp為0 時(shí)表示不分發(fā)。因此分布系統(tǒng)下全比較計(jì)算的數(shù)據(jù)分發(fā)策略對(duì)應(yīng)的最優(yōu)化存儲(chǔ)的數(shù)據(jù)分發(fā)方案能夠被描述成以下方程：

由公式（13）、公式（14）、公式（15），得出優(yōu)化后的分布式系統(tǒng)下全比較計(jì)算數(shù)據(jù)分發(fā)模型如公式（16）所示：

根據(jù)公式（16）進(jìn)行全比較計(jì)算的數(shù)據(jù)分發(fā)，得出的數(shù)據(jù)分發(fā)結(jié)果將降低分布式系統(tǒng)的存儲(chǔ)空間，實(shí)現(xiàn)完全的數(shù)據(jù)本地化與負(fù)載均衡。

2 DDBPSO模型相關(guān)算法設(shè)計(jì)

粒子群算法是一種群?jiǎn)l(fā)式算法，該算法于1995年被美國(guó)社會(huì)心理學(xué)家Kenedy 和電氣工程師Eberthart共同提出[19]。根據(jù)上文對(duì)全比較計(jì)算數(shù)據(jù)分發(fā)問(wèn)題的理論分析可知，DDBPSO模型由兩部分構(gòu)成。第一部分為求出使得分布式系統(tǒng)達(dá)到負(fù)載均衡的數(shù)據(jù)分發(fā)方案與任務(wù)調(diào)度方案?；诘谝徊糠值呢?fù)載均衡結(jié)果進(jìn)行優(yōu)化求解，在保證負(fù)載均衡的前提下降低分布式系統(tǒng)中存儲(chǔ)空間的使用。為了便于描述，將DDBPSO 模型的第一部分稱(chēng)為基于粒子群優(yōu)化實(shí)現(xiàn)負(fù)載均衡的數(shù)據(jù)分發(fā)算法（DDBPSOLB），將DDBPSO 模型的第二部分稱(chēng)為基于粒子群優(yōu)化實(shí)現(xiàn)最優(yōu)化存儲(chǔ)的數(shù)據(jù)分發(fā)算法（DDBPSOBS）。

2.1 DDBPSOLB算法設(shè)計(jì)

DDBPSOLB 算法將參照公式（13）進(jìn)行設(shè)計(jì)，得出分布式系統(tǒng)下負(fù)載均衡狀態(tài)的數(shù)據(jù)分發(fā)方案。其參數(shù)設(shè)置如表1所示。

表1 DDBPSOLB參數(shù)設(shè)置Table 1 Parameter setting of DDBPSOLB algorithm

考慮到數(shù)據(jù)文件數(shù)量增加后全比較問(wèn)題的比較任務(wù)規(guī)模將增加，全比較計(jì)算與分布式系統(tǒng)中的節(jié)點(diǎn)數(shù)目有關(guān)，故動(dòng)態(tài)調(diào)整粒子維度D。將單個(gè)粒子的維度指定為分布式系統(tǒng)中的節(jié)點(diǎn)數(shù)量與比較任務(wù)的數(shù)量tc的乘積。

慣性權(quán)重是粒子群算法中一個(gè)非常重要的控制參數(shù)，能夠用來(lái)控制求解算法的開(kāi)發(fā)與探索能力。DDBPSOLB算法在優(yōu)化的過(guò)程當(dāng)中，會(huì)逐代地獲取到較好適應(yīng)度值的可行解。因此希望在開(kāi)始尋優(yōu)時(shí)粒子較為活躍，即速度較快，隨著優(yōu)化的進(jìn)行，粒子的運(yùn)動(dòng)狀態(tài)逐漸趨于穩(wěn)定，于是在DDBPSOLB 算法中采用線(xiàn)性遞減權(quán)值策略[20]。

DDBPSOLB 算法中涉及到幾個(gè)更新規(guī)則，包括慣性權(quán)重更新規(guī)則、粒子飛行速度更新規(guī)則以及粒子位置更新規(guī)則。

令w表示當(dāng)前粒子的慣性權(quán)重，wmin與wmax分別表示慣性權(quán)重最小值和最大值，Tmax為最大迭代次數(shù)，t是DDBPSOLB算法當(dāng)前迭代次數(shù)。則w能被形式化地表示為：

第t次迭代中粒子i第j維的飛行速度為vij(t)，c1、c2為加速系數(shù)，RAND為0～1之間的隨機(jī)數(shù)，xij(t)為中粒子i第j維的編碼，pij(t)為粒子i的個(gè)體最佳位置，g(t)是第t次迭代得出的全局最佳位置。則第t+1次迭代中粒子i第j維的飛行速度vij(t+1) 為：

是否更新位置由概率q決定，令變量xij表示是否更新概率，xij取值為1時(shí)表示進(jìn)行更新，xij取值為0時(shí)表示不進(jìn)行更新。其形式化描述如公式（19）、公式（20）所示：

其中，vij為粒子i第j維的當(dāng)前速度，r表示0～1之間的隨機(jī)數(shù)。當(dāng)xij=1 時(shí)，進(jìn)行位置的更新。DDBPSOLB算法的適應(yīng)度函數(shù)用于評(píng)價(jià)粒子編碼對(duì)應(yīng)的分布式系統(tǒng)的負(fù)載均衡程度，其數(shù)學(xué)原理遵循公式（9）。

DDBPSOLB算法的偽代碼如算法1所示：

算法1DDBPSOLB算法

算法要求輸入分布式系統(tǒng)的節(jié)數(shù)量n，節(jié)點(diǎn)存儲(chǔ)上限ut和全比較計(jì)算所需的文件的大小列表s。輸出參數(shù)為全比較計(jì)算的任務(wù)列表task，分布式系統(tǒng)中各節(jié)點(diǎn)的總計(jì)算量nodeLoads，全局最優(yōu)位置gbest。這三個(gè)參數(shù)都被用作DDBPSOBS 算法的輸入?yún)?shù)。第6 行對(duì)輸入?yún)?shù)進(jìn)行檢驗(yàn)，比如判斷計(jì)算節(jié)點(diǎn)是否有能力存儲(chǔ)全比較計(jì)算所需的一份完整數(shù)據(jù)。第11行到第30行進(jìn)行粒子群迭代尋優(yōu)。第31 行將從全局最優(yōu)解gbest中解析出各個(gè)節(jié)點(diǎn)的負(fù)載情況，并存儲(chǔ)到nodeLoads中。

時(shí)間復(fù)雜度。DDBPSOLB算法的主要耗時(shí)操作在于迭代求解部分，該部分包含三個(gè)嵌套的for 循環(huán)。優(yōu)化迭代次數(shù)為T(mén)，粒子群規(guī)模為N，粒子編碼長(zhǎng)度為D，則DDBPSOLB算法的時(shí)間復(fù)雜度為T(mén)1=O(TND)，與離散粒子群算法的時(shí)間復(fù)雜度處于同一數(shù)量級(jí)。

收斂性。如算法1第18～25行所示，粒子在進(jìn)化時(shí)，會(huì)隨機(jī)選擇兩個(gè)節(jié)點(diǎn)上，并將其中一個(gè)節(jié)點(diǎn)上的某一個(gè)任務(wù)安排到另一個(gè)節(jié)點(diǎn)上，對(duì)可行解進(jìn)行擾動(dòng)。在擾動(dòng)的過(guò)程中，如果新解優(yōu)于當(dāng)前粒子的最佳解則對(duì)該粒子的編碼進(jìn)行更新。這樣的更新方式使得算法能夠接受次優(yōu)解，有效避免算法陷入局部最優(yōu)解。在下一次迭代時(shí)第13、14 行會(huì)根據(jù)負(fù)載偏離程度對(duì)個(gè)體最優(yōu)位置與全局最優(yōu)位置進(jìn)行更新，從而讓負(fù)載偏離程度朝著縮小的方向收斂。

2.2 DDBPSOBS算法設(shè)計(jì)

DDBPSOBS算法用于在保證分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)實(shí)現(xiàn)負(fù)載平衡的條件下，對(duì)分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)需要提供的存儲(chǔ)空間大小進(jìn)行優(yōu)化。在DDBPSOLB算法計(jì)算完畢之后，能夠得出使得分布式系統(tǒng)實(shí)現(xiàn)負(fù)載均衡狀態(tài)下的全比較計(jì)算任務(wù)調(diào)度方案，以及分布式系統(tǒng)中每個(gè)節(jié)點(diǎn)所需承擔(dān)的計(jì)算量。從各個(gè)節(jié)點(diǎn)的計(jì)算量中選出節(jié)點(diǎn)計(jì)算量的最大值Cmax作為DDBPSOBS 算法中的一個(gè)約束條件。

DDBPSOBS 算法思想與DDBPSOLB 算法類(lèi)似，相關(guān)的參數(shù)除粒子種群規(guī)模N外其余均與表1 保持一致。粒子種群規(guī)模N在DDBPSOBS算法中取值為10，這樣做的目的是希望通過(guò)降低種群規(guī)模，提高算法的運(yùn)算效率。

由于DDBPSOLB算法中獲取到了使得系統(tǒng)實(shí)現(xiàn)負(fù)載均衡的粒子最佳位置，因此在DDBPSOBS 算法中的種群初始化工作中，只需要將編碼復(fù)制N份，通過(guò)滿(mǎn)足公式（14）來(lái)調(diào)整粒子的編碼，實(shí)現(xiàn)初始種群的多樣性。DDBPSOBS算法對(duì)應(yīng)的適應(yīng)度值為粒子當(dāng)前的編碼對(duì)應(yīng)的分布式系統(tǒng)的存儲(chǔ)空間大小。使用公式（16）來(lái)進(jìn)行算法的開(kāi)發(fā)，與粒子群優(yōu)化的相關(guān)更新規(guī)則與DDBPSOLB算法基本保持一致，具體的位置更新規(guī)則有所改變。

算法2所示的是DDBPSOBS算法步驟描述：

算法2DDBPSOBS算法

算法要求輸入的參數(shù)包括n、s、task、nodeLoads、以及DDBPSOLB算法的全局最優(yōu)位置gbest1。輸出結(jié)果為分布式系統(tǒng)下全比較計(jì)算的任務(wù)調(diào)度方案taskAssign和文件分發(fā)方案fileAssign。第6 行到第22 行將進(jìn)行粒子群迭代尋優(yōu)之前的初始化工作，這部分主要是給粒子群優(yōu)化所需的參數(shù)信息做初始化。第24行到第50行進(jìn)行迭代尋優(yōu)，當(dāng)滿(mǎn)足位置更新規(guī)則時(shí)，使用第34行到第45行所定義的內(nèi)容進(jìn)行粒子位置的更新。第49行將每一次迭代所得到的最優(yōu)位置所對(duì)應(yīng)的適應(yīng)度值記錄下來(lái)，方便后期查看算法的適應(yīng)度進(jìn)化情況。在完成迭代尋優(yōu)后，第51 行將從DDBPSOBS 算法的全局最優(yōu)位置編碼gbest中解析出taskAssign和fileAssign。

時(shí)間復(fù)雜度。DDBPSOBS算法的耗時(shí)操作同樣發(fā)生在迭代求解部分，該算法同樣是根據(jù)迭代次數(shù)T，粒子群規(guī)模N，粒子編碼長(zhǎng)度D構(gòu)建了for循環(huán)。其時(shí)間復(fù)雜度為T(mén)2=O(TND)，與DDBPSOLB 算法和離散粒子群算法的時(shí)間復(fù)雜度保持在同一個(gè)數(shù)量級(jí)。

收斂性。算法2第31～47行表示的是粒子的進(jìn)化過(guò)程，通過(guò)概率q確定要修改粒子i的編碼之后，將粒子i的位置編碼x備份為y。隨機(jī)挑選兩個(gè)計(jì)算節(jié)點(diǎn)上的任務(wù)集合set1與set2。從set1中隨機(jī)挑選一個(gè)任務(wù)task1，計(jì)算任務(wù)1 的大小ts1。計(jì)算set2中每個(gè)任務(wù)與task1的大小差異，挑選出差異最小的任務(wù)作為交換任務(wù)task2。在y上交換task1和task2的執(zhí)行節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)上的任務(wù)量均在Cmax的范圍內(nèi)，則計(jì)算編碼y對(duì)應(yīng)的適應(yīng)度值fit″。如果fit″的適應(yīng)度值優(yōu)于粒子i的個(gè)體最優(yōu)值，則使用y更新x。與個(gè)體最優(yōu)值做比較的這種方式，是為了避免算法陷入局部最優(yōu)解。算法2第27、28 行會(huì)將每次迭代過(guò)程中的個(gè)體最優(yōu)的位置與全局最優(yōu)位置進(jìn)行更新，從而讓全局最優(yōu)解朝著所需存儲(chǔ)空間變小的方向收斂。

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

3.1 評(píng)價(jià)指標(biāo)

本文將采用負(fù)載均衡、存儲(chǔ)節(jié)約率、數(shù)據(jù)本地化率、模型計(jì)算時(shí)間4 個(gè)評(píng)價(jià)指標(biāo)來(lái)對(duì)DDBPSO 模型進(jìn)行分析與評(píng)價(jià)。

負(fù)載均衡。根據(jù)公式（9）能得到節(jié)點(diǎn)i的負(fù)載均衡偏離程度f(wàn)i，全部fi組成的集合為F。負(fù)載均衡有三種狀態(tài)：完全負(fù)載均衡STATE1、近似負(fù)載均衡STATE2、非負(fù)載均衡STATE3。負(fù)載均衡LB對(duì)應(yīng)的數(shù)學(xué)描述如公式（21）所示，其中c是所有任務(wù)計(jì)算量的集合。

存儲(chǔ)節(jié)約率。存儲(chǔ)節(jié)約率的計(jì)算將把全比較計(jì)算所需的整份數(shù)據(jù)向分布式系統(tǒng)中每個(gè)節(jié)點(diǎn)分發(fā)一份時(shí)分布式系統(tǒng)所需的存儲(chǔ)空間作為分母，分子為每個(gè)節(jié)點(diǎn)所需提供存儲(chǔ)空間的總和。m個(gè)數(shù)據(jù)文件，n個(gè)節(jié)點(diǎn)，令hr為存儲(chǔ)節(jié)約率，hr的計(jì)算公式如下：

在公式（22）中，sk表示文件k的大小，sij是分發(fā)到i上的文件j的大小，m′表示分發(fā)到節(jié)點(diǎn)i上的文件數(shù)目。

3.2 實(shí)驗(yàn)方案設(shè)計(jì)

考慮文件大小是否完全相同和全比較計(jì)算的比較任務(wù)數(shù)量是否能夠被分布式系統(tǒng)中的節(jié)點(diǎn)數(shù)所整除。對(duì)這兩個(gè)條件的組合進(jìn)行分析，可以得出如下四組實(shí)驗(yàn)方案。

（1）文件大小完全相同，比較任務(wù)數(shù)能夠被節(jié)點(diǎn)數(shù)整除。

（2）文件大小完全相同，比較任務(wù)數(shù)不能被節(jié)點(diǎn)數(shù)整除。

（3）文件大小不完全相同，比較任務(wù)數(shù)能夠被節(jié)點(diǎn)數(shù)整除。

（4）文件大小不完全相同，比較任務(wù)數(shù)不能被節(jié)點(diǎn)數(shù)整除。

實(shí)驗(yàn)數(shù)據(jù)。將從國(guó)家生物技術(shù)中心下載的一個(gè)基因序列文件進(jìn)行切分處理。將基因序列文件切分成12個(gè)大小不完全相同的小文件，每次從中挑選出10 個(gè)數(shù)據(jù)文件進(jìn)行實(shí)驗(yàn)。切分后的數(shù)據(jù)文件的大小分別為[9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，9.7 MB，8.1 MB，12.1 MB]，以這些數(shù)據(jù)文件為例，進(jìn)行實(shí)驗(yàn)方案設(shè)計(jì)。

使用Hadoop 進(jìn)行數(shù)據(jù)分發(fā)工作時(shí)，具備較好的存儲(chǔ)節(jié)約性能[15]。使用HDFS 組件和MapReduce 組件進(jìn)行配合，能較好地完成全比較計(jì)算的數(shù)據(jù)分發(fā)工作。在進(jìn)行DDBPSO 模型驗(yàn)證實(shí)驗(yàn)之前，首先使用Hadoop 執(zhí)行四組數(shù)據(jù)分發(fā)實(shí)驗(yàn)，并編寫(xiě)MapReduce程序讀取數(shù)據(jù)文件模擬序列比對(duì)中的文件加載操作。記錄每一組實(shí)驗(yàn)中全比較計(jì)算的數(shù)據(jù)分發(fā)方案與任務(wù)調(diào)度情況，用于與DDBPSO 模型的實(shí)驗(yàn)結(jié)果做比較。四組實(shí)驗(yàn)的文件與節(jié)點(diǎn)信息如表2所示。表2所示的實(shí)驗(yàn)方案旨在覆蓋可能出現(xiàn)的文件大小完全相同與否條件和比較任務(wù)數(shù)能否被節(jié)點(diǎn)均分的情況，對(duì)其他節(jié)點(diǎn)數(shù)量和文件大小列表具備普適性。

表2 實(shí)驗(yàn)方案設(shè)計(jì)Table 2 Design of experimental scheme

3.3 Hadoop數(shù)據(jù)分發(fā)實(shí)驗(yàn)

本文將使用Hadoop的數(shù)據(jù)分發(fā)結(jié)果與DDBPSO模型所得數(shù)據(jù)分發(fā)結(jié)果在負(fù)載均衡程度、存儲(chǔ)節(jié)約情況和數(shù)據(jù)本地化情況這三個(gè)評(píng)價(jià)指標(biāo)上做對(duì)比。Hadoop集群配置方案如下：

宿主機(jī)配置：Intel i7-8750CPU，16 GB RAM，1 TB SATA+256 GB SSD，Window10操作系統(tǒng)。虛擬化軟件及版本：VMWareWorkStation10。

虛擬機(jī)配置：CPU 核心數(shù)為2，2 GB 內(nèi)存，20 GB 磁盤(pán)空間，在5臺(tái)虛擬機(jī)上安裝Centos6.8并配置Hadoop2.7.2。

Hadoop 數(shù)據(jù)分發(fā)實(shí)驗(yàn)將在宿主機(jī)上進(jìn)行一次全比較計(jì)算所需的數(shù)據(jù)從宿主機(jī)分發(fā)到HDFS 上，并通過(guò)Hadoop 提供的可視化界面對(duì)上傳的每個(gè)數(shù)據(jù)進(jìn)行所在位置統(tǒng)計(jì)。HDFS中的文件副本數(shù)不做修改，使用默認(rèn)值3。

基于Hadoop 依次完成四組實(shí)驗(yàn)得到的Hadoop 的全比較計(jì)算數(shù)據(jù)分發(fā)方案與全比較計(jì)算任務(wù)執(zhí)行情況如表3所示。數(shù)據(jù)分發(fā)方案的統(tǒng)計(jì)是基于Hadoop提供的Web界面獲取到的，任務(wù)執(zhí)行情況是根據(jù)模擬的全比較計(jì)算程序得出的。

表3 Hadoop實(shí)驗(yàn)結(jié)果Table 3 Results of Hadoop experiment

與將全比較計(jì)算所需的全部數(shù)據(jù)向所有節(jié)點(diǎn)都分發(fā)一次的數(shù)據(jù)分發(fā)方案相比較，能夠得出Hadoop 集群的存儲(chǔ)節(jié)約情況。四組實(shí)驗(yàn)的存儲(chǔ)節(jié)約率如圖1 所示。本次實(shí)驗(yàn)全程使用Hadoop默認(rèn)的副本數(shù)3，實(shí)驗(yàn)2與實(shí)驗(yàn)4 的計(jì)算節(jié)點(diǎn)數(shù)量為4，分布式系統(tǒng)的存儲(chǔ)節(jié)約率為25%；當(dāng)計(jì)算節(jié)點(diǎn)數(shù)量為5時(shí)，實(shí)驗(yàn)1與實(shí)驗(yàn)3的分布式系統(tǒng)存儲(chǔ)節(jié)約率為40%。

圖1 Hadoop實(shí)驗(yàn)存儲(chǔ)節(jié)約率Fig.1 Storage savings rate of Hadoop experiment

對(duì)表3的數(shù)據(jù)分發(fā)方案與任務(wù)執(zhí)行情況進(jìn)行分析，結(jié)合Hadoop 在向HDFS 請(qǐng)求數(shù)據(jù)時(shí)的數(shù)據(jù)發(fā)送特點(diǎn)：當(dāng)客戶(hù)端向HDFS 請(qǐng)求數(shù)據(jù)時(shí)，NameNode 會(huì)將滿(mǎn)足條件的且離客戶(hù)端最近的DataNode 上的數(shù)據(jù)發(fā)送給客戶(hù)端。能夠分析出在進(jìn)行全比較計(jì)算時(shí)，各個(gè)比較任務(wù)請(qǐng)求到的數(shù)據(jù)是本地的還是其他節(jié)點(diǎn)的。四次實(shí)驗(yàn)中節(jié)點(diǎn)的數(shù)據(jù)本地率如圖2 所示。從圖中可以看出使用Hadoop 進(jìn)行全比較計(jì)算，數(shù)據(jù)文件的副本數(shù)為3 時(shí)，分布式系統(tǒng)無(wú)法實(shí)現(xiàn)完全的數(shù)據(jù)本地化。

圖2 Hadoop實(shí)驗(yàn)數(shù)據(jù)本地化情況Fig.2 Data localization for Hadoop experiment

3.4 DDBPSO模型實(shí)驗(yàn)

對(duì)3.2 節(jié)中設(shè)計(jì)的實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn)，分布式系統(tǒng)的存儲(chǔ)節(jié)約率如圖3所示，負(fù)載均衡情況如圖4所示。

圖3 DDBPSO模型存儲(chǔ)節(jié)約率Fig.3 Storage savings for DDBPSO model

圖4 DDBPSO模型負(fù)載均衡情況Fig.4 Load balancing of DDBPSO model

由圖3可知，DDBPSO模型的存儲(chǔ)節(jié)約率在大多數(shù)情況下都高于Hadoop的數(shù)據(jù)分發(fā)策略。盡管實(shí)驗(yàn)3的存儲(chǔ)節(jié)約率不如Hadoop，但是DDBPSO 模型的數(shù)據(jù)本地化率在任何情況下都能實(shí)現(xiàn)全部節(jié)點(diǎn)的完全數(shù)據(jù)本地化，而Hadoop 的數(shù)據(jù)分發(fā)策略無(wú)法達(dá)到這種效果。對(duì)圖4進(jìn)行分析可知，DDBPSO模型能夠使得分布式系統(tǒng)下的全比較計(jì)算實(shí)現(xiàn)完全負(fù)載均衡或近似負(fù)載均衡。使用分支定界法對(duì)同規(guī)模的數(shù)據(jù)進(jìn)行求解時(shí)，往往需要20 h 的求解時(shí)間[17]，而DDBPSO 模型在20～40 s 內(nèi)便可完成計(jì)算。從效率角度來(lái)看，DDBPSO模型具備顯著的優(yōu)勢(shì)。

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

本文研究了全比較計(jì)算的數(shù)據(jù)分發(fā)問(wèn)題，提出了基于粒子群優(yōu)化算法的數(shù)據(jù)分發(fā)模型DDBPSO 及相關(guān)算法，對(duì)DDBPSO 模型和相關(guān)算法進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，DDBPSO模型給出的數(shù)據(jù)分發(fā)方案可以實(shí)現(xiàn)任務(wù)所需數(shù)據(jù)文件的完全本地化，能夠降低分布式系統(tǒng)中存儲(chǔ)空間的使用。在負(fù)載均衡方面，DDBPSO模型給出的任務(wù)調(diào)度方案基本能夠?qū)崿F(xiàn)分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)間的負(fù)載均衡。在計(jì)算時(shí)間方面，DDBPSO 模型能夠以較快速度求出數(shù)據(jù)分發(fā)方案與任務(wù)調(diào)度方案，可以較好地完成分布式系統(tǒng)下全比較計(jì)算數(shù)據(jù)分發(fā)工作。DDBPSO 模型有效地解決了大規(guī)模全比較計(jì)算的數(shù)據(jù)分發(fā)問(wèn)題，對(duì)生物信息學(xué)、自然語(yǔ)言處理等領(lǐng)域研究進(jìn)展將產(chǎn)生較好的推動(dòng)作用。