Graphlet Degree Vector方法的優(yōu)化與并行

宋祥帥，楊伏長，謝 江*，張 武，2

（1.上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院，上海200444；2.上海大學(xué)上海市應(yīng)用數(shù)學(xué)與力學(xué)研究所，上海200444）

0 引言

比較生物網(wǎng)絡(luò)的相似和差異是當(dāng)前計算生物學(xué)的一個主要問題［1］，生物網(wǎng)絡(luò)通常由圖來建立模型，圖中節(jié)點(diǎn)表示生物分子，如代謝物、蛋白質(zhì)、基因等，而邊則表示各生物分子之間的相互作用［2］，研究生物網(wǎng)絡(luò)可以為疾病的發(fā)生機(jī)制和治療手段提供深刻的見解［3］。其中，一項很重要的研究就是尋找生物網(wǎng)絡(luò)中的自同構(gòu)軌道。Graphlet Degree Vector（GDV）方法是Przulj在2003年提出的利用圖元及圖元向量來刻畫網(wǎng)絡(luò)中節(jié)點(diǎn)鄰域關(guān)系的方法，具體指在小連通非同構(gòu)子圖中計算每個節(jié)點(diǎn)的自同構(gòu)軌道，即每個節(jié)點(diǎn)所接觸的圖形數(shù)量［4］，這種方法基于網(wǎng)絡(luò)拓?fù)浜袜徲蚨x了一系列非同構(gòu)子圖和圖向量，用于識別網(wǎng)絡(luò)中結(jié)構(gòu)相似的模塊［5］。人們利用這種方法進(jìn)行了許多有意義的研究［6］，例如研究了生物網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)差異［7-8］，構(gòu)建生物網(wǎng)絡(luò)的進(jìn)化樹［9］，識別癌癥相關(guān)基因［4］，計算差異網(wǎng)絡(luò)的聚類系數(shù)［9］，生物網(wǎng)絡(luò)進(jìn)行最優(yōu)比對［10］和蛋白質(zhì)功能分析［11］等。然而隨著小連通非同構(gòu)子圖中節(jié)點(diǎn)數(shù)的增加，GDV 方法的計算時間復(fù)雜度會很高，它的擴(kuò)展會受到很大的約束［3］。盡管Przulj［8］提出可以利用提高CPU的性能來提高擴(kuò)展性，但是計算成本會變得越來越高，因此隨著生物網(wǎng)絡(luò)研究的規(guī)模以及小連通非同構(gòu)子圖規(guī)模的不斷增大，參與枚舉的自同構(gòu)軌道數(shù)量呈指數(shù)級別的增長，計算量越來越大，給圖元的擴(kuò)展帶來了挑戰(zhàn)。

當(dāng)前圖元方法仍以Przulj 于2003 年提出的GDV 方法為主流［12］，具體實(shí)現(xiàn)如Xie 等［5］于2017 年提出的基于2-4 nodes的枚舉方法，通過一個二維矩陣Net_Matrix 來存儲無向生物網(wǎng)絡(luò)，然后通過枚舉的方式找出2-4 nodes 連通非同構(gòu)子圖的15 個自同構(gòu)軌道，該算法通過枚舉的方式實(shí)現(xiàn)了軌道的查找，有效地完成了自同構(gòu)軌道查找的任務(wù)。Ho?evar 等［13］在2014 年提出了一種新的計算網(wǎng)絡(luò)節(jié)點(diǎn)圖形和軌道特征的組合方法，取得了比較顯著的效果。此外，由于復(fù)雜度的原因，Ahmed 等［14］只研究了節(jié)點(diǎn)為3 和4 的圖元，利用4 個節(jié)點(diǎn)和3個節(jié)點(diǎn)的圖元在結(jié)構(gòu)上相似性，減少判斷包含4 個節(jié)點(diǎn)的圖元向量的計算開銷。

目前，已有的GDV 方法在計算規(guī)模上都存在瓶頸［15］。隨著生物網(wǎng)絡(luò)數(shù)據(jù)獲取的渠道越來越多，生物網(wǎng)絡(luò)規(guī)模越來越大，對計算效率的要求也會越來越高［15］，因此，實(shí)現(xiàn)高效的并行化GDV 方法很有必要。本文從文獻(xiàn)［5］實(shí)現(xiàn)的串行的GDV方法著手，將該串行方法以消息傳遞接口（Message Passing Interface，MPI）為基礎(chǔ)實(shí)現(xiàn)并行化，并結(jié)合去除原來算法的重復(fù)運(yùn)算部分和負(fù)載均衡策略改進(jìn)并行算法，最后，通過仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)進(jìn)行了分析和討論。

1 GDV方法的主要思想

GDV 方法的主要思想是計算一個生物網(wǎng)絡(luò)中每個節(jié)點(diǎn)的自同構(gòu)軌道數(shù)量，即每個節(jié)點(diǎn)所接觸的圖形的數(shù)量［4］。這在研究生物網(wǎng)絡(luò)的過程中發(fā)揮著重要的作用。

圖1 展示了包含2、3、4 個節(jié)點(diǎn)的非同構(gòu)圖元。為了刻畫節(jié)點(diǎn)的拓?fù)涞葍r性，Przulj把圖元中具有相同拓?fù)湮恢玫墓?jié)點(diǎn)標(biāo)記為相同的記號，然后對其中具有不同拓?fù)湮恢玫墓?jié)點(diǎn)唯一標(biāo)號。圖1 中包含了2-節(jié)點(diǎn)、3-節(jié)點(diǎn)、4-節(jié)點(diǎn)這三種圖元的15 個不同的拓?fù)湮恢茫Q這些拓?fù)湮恢脼樽酝瑯?gòu)軌道，它們出現(xiàn)的頻率記錄為圖元向量［16］。

由于在大規(guī)模生物網(wǎng)絡(luò)中，非同構(gòu)圖元的網(wǎng)絡(luò)結(jié)構(gòu)差異各種各樣，下面將會以一個簡單無向網(wǎng)絡(luò)為例來對自同構(gòu)軌道的查找進(jìn)行說明。

圖1 圖元及圖元向量Fig.1 Graphlets and graphlet orbits

圖2 展示了網(wǎng)絡(luò)GA 所形成的無向網(wǎng)絡(luò)圖。在圖2 中，以節(jié)點(diǎn)1 為例，發(fā)現(xiàn)一共有4 個0 軌道向量，即（1，2）、（1，3）、（1，4）、（1，5），那么節(jié)點(diǎn)1 的0 軌道向量的數(shù)目就是4；同樣地，當(dāng)以節(jié)點(diǎn)2 為例時，0 軌道向量的數(shù)目是4，即（2，1）、（2，3）、（2，4）、（2，5）。其他軌道向量數(shù)目的計算過程依此類推。

表1展示了圖2實(shí)例中每個節(jié)點(diǎn)的軌道向量數(shù)目，其中行代表了軌道向量編號，3 個圖元中軌道向量的總數(shù)目為14。列則代表了每個節(jié)點(diǎn)的編號。

圖2 無向生物網(wǎng)絡(luò)實(shí)例Fig.2 Example of undirected biological network

表1 圖2中5個節(jié)點(diǎn)在GA網(wǎng)絡(luò)中圖元向量的數(shù)量Tab.1 Number of graphlet orbits of the five nodes in the GA network of Fig.2

2 GDV方法的實(shí)現(xiàn)

GDV 方法是一種在連通生物網(wǎng)絡(luò)中枚舉各節(jié)點(diǎn)自同構(gòu)軌道數(shù)量的方法，可以大致分為網(wǎng)絡(luò)初始化、自同構(gòu)軌道查找和統(tǒng)計自同構(gòu)軌道數(shù)量三個步驟。其中網(wǎng)絡(luò)的初始化是該方法的準(zhǔn)備工作，需要將邊集形式轉(zhuǎn)換為一個無向生物網(wǎng)絡(luò)，之后再將網(wǎng)絡(luò)轉(zhuǎn)換成一個n×n（n 指的是無向網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目）的鄰接矩陣用以存儲每個節(jié)點(diǎn)以及節(jié)點(diǎn)所對應(yīng)的邊；GDV 方法所提出的自同構(gòu)軌道查找保證了所枚舉圖元的唯一性和查找自同構(gòu)軌道數(shù)量的準(zhǔn)確性；最后是統(tǒng)計每個節(jié)點(diǎn)所對應(yīng)的自同構(gòu)軌道的數(shù)目，將其存儲在一個n×15 的矩陣中。查找每個節(jié)點(diǎn)的自同構(gòu)軌道是整個GDV 方法的核心部分，因此，下文在介紹GDV 方法的前提下，將著重介紹每個節(jié)點(diǎn)自同構(gòu)軌道的查找過程。

GDV方法的具體實(shí)現(xiàn)步驟（主要步驟如圖3）如下所示：

步驟1 網(wǎng)絡(luò)的初始化。GDV 方法在構(gòu)建網(wǎng)絡(luò)時輸入為邊集的形式，節(jié)點(diǎn)的編號以連續(xù)的數(shù)值表示，邊由節(jié)點(diǎn)對來確定是否進(jìn)行生成，若兩個點(diǎn)的節(jié)點(diǎn)值在同一個節(jié)點(diǎn)對中，那么就生成連接這兩個節(jié)點(diǎn)的邊。如圖2 就是由GA 的邊集所構(gòu)建的無向網(wǎng)絡(luò)。然后將生成的網(wǎng)絡(luò)轉(zhuǎn)換成一個n×n 的鄰接矩陣，其中n 表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。例如將圖2 的GA 無向圖轉(zhuǎn)化為鄰接矩陣A：

步驟2 查找每個節(jié)點(diǎn)的圖元向量的數(shù)量。對每個節(jié)點(diǎn)進(jìn)行遍歷，查找其與相鄰節(jié)點(diǎn)之間的關(guān)系，進(jìn)而來判定屬于哪一種自同構(gòu)軌道。通過分析可以得到，在圖1中，G0圖元可以通過一個二維循環(huán)來對0 軌道進(jìn)行查找，從而計算2-節(jié)點(diǎn)圖元中0 軌道的數(shù)量，但是當(dāng)計算3-節(jié)點(diǎn)或者4-節(jié)點(diǎn)的圖元向量時，二維循環(huán)難以解決復(fù)雜的計算過程。本文采用了Xie等［5］于2017 年實(shí)現(xiàn)的基于2-4 nodes 的方法，該方法對不同的圖元向量進(jìn)行了分類枚舉，巧妙地避開了在二維循環(huán)中計算過程復(fù)雜的問題，同時也確保了整個查找過程的嚴(yán)謹(jǐn)性，做到了精確查找。在該方法中對3-節(jié)點(diǎn)的圖元向量進(jìn)行了三維循環(huán)操作，針對4-節(jié)點(diǎn)的圖元進(jìn)行了四維循環(huán)操作，有效地解決了復(fù)雜的查找過程，但該方法的時間復(fù)雜度非常高。

步驟3 將步驟2 查找的結(jié)果存儲到一個n×15 的矩陣中，用以記錄每個節(jié)點(diǎn)的圖元向量的數(shù)量。

圖3 GDV方法的主要步驟Fig.3 Main steps of GDV method

3 GDV方法的優(yōu)化及其并行化的實(shí)現(xiàn)

枚舉每個節(jié)點(diǎn)的非同構(gòu)軌道數(shù)量的操作是整個GDV 方法的核心部分，同時也是整個方法中最耗時的部分，因此本文從查找每個節(jié)點(diǎn)的非同構(gòu)軌道數(shù)量這一步驟上進(jìn)行突破，完成了兩方面的工作：1）將串行GDV 方法實(shí)現(xiàn)并行化。2）分為兩步對GDV方法進(jìn)行了優(yōu)化：①改進(jìn)GDV串行方法解決鄰接矩陣中重復(fù)計算的問題，同時進(jìn)行并行化；②將改進(jìn)后的并行化GDV 方法進(jìn)行優(yōu)化以解決各進(jìn)程的負(fù)載不均衡問題，實(shí)現(xiàn)負(fù)載均衡。

3.1 GDV串行方法的并行實(shí)現(xiàn)

GDV 方法的主要任務(wù)就是尋找一個網(wǎng)絡(luò)中每個節(jié)點(diǎn)的自同構(gòu)軌道的數(shù)量，由GDV方法步驟2的分析可知，在尋找每個節(jié)點(diǎn)的自同構(gòu)軌道時，根據(jù)圖元向量的不同類別進(jìn)行不同層次的循環(huán)查找就可以計算出不同節(jié)點(diǎn)的自同構(gòu)軌道，所以可以將這類問題轉(zhuǎn)化為矩陣的運(yùn)算來進(jìn)行，針對矩陣的運(yùn)算，本文實(shí)現(xiàn)的是按照行數(shù)來進(jìn)行進(jìn)程間任務(wù)的分配，最后再將子任務(wù)的結(jié)果規(guī)約至0號進(jìn)程。

3.2 GDV串行方法的重復(fù)計算問題改善及其并行化實(shí)現(xiàn)

盡管進(jìn)行了GDV 方法的并行化實(shí)現(xiàn)，但是該并行方法仍然耗時甚多，為了盡可能地提高該方法的運(yùn)行效率，首先對GDV 串行方法進(jìn)行了解決重復(fù)計算問題的改進(jìn)，然后將改進(jìn)后的方法實(shí)現(xiàn)了并行化。

自同構(gòu)軌道數(shù)量的計算中，需要針對無向網(wǎng)絡(luò)中每個節(jié)點(diǎn)進(jìn)行遍歷，查找該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的關(guān)系，進(jìn)而確定以該節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)的自同構(gòu)軌道的數(shù)量，查找的過程是在無向網(wǎng)絡(luò)轉(zhuǎn)換為鄰接矩陣后進(jìn)行的。眾所周知，無向網(wǎng)絡(luò)轉(zhuǎn)換為鄰接矩陣后往往表現(xiàn)為是一個上（下）三角矩陣，以網(wǎng)絡(luò)GA 為例，很顯然它的鄰接矩陣A是一個上（下）三角矩陣，因此在計算的過程中只需要針對上（下）三角矩陣進(jìn)行查找即可，然后再根據(jù)對稱關(guān)系，在相應(yīng)的自同構(gòu)軌道上記錄，最后得到結(jié)果。該過程的偽代碼如下所示：

偽代碼中，在進(jìn)行第二次循環(huán)遍歷時，僅需要從第一個位置的下一個元素進(jìn)行遍歷即可，不需要再從頭進(jìn)行遍歷，這樣大大地縮短了對比所需要的時間；不過，在遍歷的同時，還需要對鄰接矩陣其對應(yīng)位置的自同構(gòu)軌道的數(shù)量進(jìn)行記錄，這樣才能在記錄時避免出現(xiàn)遺漏的現(xiàn)象。由前面的討論可知，GDV 方法最耗時的部分是對每個節(jié)點(diǎn)進(jìn)行枚舉自同構(gòu)軌道的數(shù)量，因此進(jìn)行并行化處理時需要針對這一問題展開分析，將矩陣按照進(jìn)程數(shù)來進(jìn)行行分，用以實(shí)現(xiàn)并行化。

3.3 改進(jìn)后GDV方法的并行優(yōu)化

傳統(tǒng)的矩陣行分較為規(guī)則化，但是在本文中由于改進(jìn)后的GDV 方法中提供的是一個上（下）三角矩陣，使用傳統(tǒng)的方法進(jìn)行行分時，就會出現(xiàn)每個進(jìn)程負(fù)載極其不均衡的情況，因此在對矩陣進(jìn)行行分時，需要改進(jìn)策略，以解決負(fù)載不均衡的情況。改進(jìn)策略屬于一個動態(tài)規(guī)劃的問題，程序需要根據(jù)進(jìn)程數(shù)來進(jìn)行合理行分。本文所采取的策略如下：

步驟1 根據(jù)矩陣的行數(shù)和進(jìn)程的規(guī)模數(shù)進(jìn)行劃分，具體劃分規(guī)則為：size*=n/(numprocs*2)。

步驟2 將得到的size*按照進(jìn)程編號的順序分發(fā)給各個進(jìn)程，此時所有進(jìn)程運(yùn)算的矩陣的行數(shù)為總體行數(shù)的一半。

步驟3 將得到的size*按照進(jìn)程編號的逆序再次分發(fā)給各個進(jìn)程，此時所有進(jìn)程運(yùn)算的矩陣的行數(shù)為總體行數(shù)的另外一半。

步驟4 根據(jù)主進(jìn)程分發(fā)的規(guī)模，各進(jìn)程開始進(jìn)行計算。

步驟5 各進(jìn)程將所得到的計算結(jié)果歸約求和發(fā)送給主進(jìn)程，并行結(jié)束。

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

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

本次研究使用的實(shí)驗(yàn)平臺是上海大學(xué)高性能計算集群“自強(qiáng)4000”。實(shí)驗(yàn)使用4 個內(nèi)存節(jié)點(diǎn)，每個內(nèi)存節(jié)點(diǎn)配置信息如下：2 顆Intel E5-2690 CPU（2.9 GHz/8-core），內(nèi)存大小為64 GB。集群節(jié)點(diǎn)間使用標(biāo)準(zhǔn)的CLOS 二層Infiniband 網(wǎng)絡(luò)架構(gòu)，MPI 庫版本為IntelMPI，實(shí)驗(yàn)運(yùn)行操作系統(tǒng)為CentOS 6.3，編程語言為C++。

4.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)同時使用了模擬數(shù)據(jù)和真實(shí)生物網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行性能分析，其中模擬數(shù)據(jù)使用NetworkX［17］的python 包模擬了三類不同的網(wǎng)絡(luò)模型，分別是無標(biāo)度網(wǎng)絡(luò)模型［18］、小世界網(wǎng)絡(luò)模型［19］和規(guī)則網(wǎng)絡(luò)模型［20］。

為了分析改進(jìn)后的GDV 方法在不同網(wǎng)絡(luò)模型中的可拓展性以及泛化能力，實(shí)驗(yàn)中使用了邊數(shù)相同（均為4 000）但節(jié)點(diǎn)數(shù)不同五種網(wǎng)絡(luò)模型進(jìn)行實(shí)驗(yàn)，具體情況如表2所示。

表2 五個模擬網(wǎng)絡(luò)數(shù)據(jù)集Tab.2 Five simulated network datasets

為了分析網(wǎng)絡(luò)的邊數(shù)對改進(jìn)后方法的影響，真實(shí)生物網(wǎng)絡(luò)選取了酵母菌代謝網(wǎng)絡(luò)（Yeast Protein Interaction Network，YPIN）和人類基因調(diào)控網(wǎng)絡(luò)（Human Genetic Regulatory Network，HGRN）兩個生物網(wǎng)絡(luò)數(shù)據(jù)集，其中HGRN 數(shù)據(jù)來源于STRING（Search Tool for Recurring Instances of Neighbouring Genes）在線數(shù)據(jù)庫［21］，YPIN數(shù)據(jù)集來源于Uri Alon實(shí)驗(yàn)室［22］。這兩個網(wǎng)絡(luò)的特點(diǎn)是節(jié)點(diǎn)數(shù)大致相同，但邊數(shù)不同：YPIN 的節(jié)點(diǎn)數(shù)為689，邊數(shù)為1 078；HGRN 的節(jié)點(diǎn)數(shù)為709，邊數(shù)為5 560。

圖4（a）為并行的GDV方法在5種網(wǎng)絡(luò)中所使用的時間比對。比較小世界模型、隨機(jī)模型和無標(biāo)度模型，三種模型的節(jié)點(diǎn)數(shù)均為1 000，邊數(shù)為4 000，在圖4（a）中可以看出這三種網(wǎng)絡(luò)在相同核數(shù)下所花費(fèi)的時間相差不大，因此可以認(rèn)為在并行的GDV 方法中自同構(gòu)軌道的查找與網(wǎng)絡(luò)的種類是不相關(guān)的。通過觀察圖4（a）可以看出，盡管兩種真實(shí)網(wǎng)絡(luò)的邊數(shù)相差很多，但它們的程序運(yùn)行時間卻相差不多，因此可以認(rèn)為并行的GDV方法與網(wǎng)絡(luò)的邊數(shù)并不相關(guān)。

圖4 GDV方法的并行性能Fig.4 Parallel performance of GDV method

圖4 （b）是并行的GDV 方法在5 種網(wǎng)絡(luò)中的加速比對比曲線。這5 種網(wǎng)絡(luò)雖然規(guī)模不相同，但它們的加速比曲線幾乎重合，加速比數(shù)值幾乎相同，說明了并行的GDV 方法應(yīng)用范圍廣，在不同的模型中均有好的作用。

在GDV 方法中，查找自同構(gòu)軌道的計算開銷比較大［12］，而且隨著網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模的增大，其運(yùn)行時間消耗得也越來越多，以表3 的兩種生物網(wǎng)絡(luò)和表2 中編號3、4、5 的1 000 個節(jié)點(diǎn)的網(wǎng)絡(luò)為例。從實(shí)驗(yàn)結(jié)果圖4（a）中可以看出，當(dāng)單核運(yùn)行程序查找自同構(gòu)軌道數(shù)量時，YPIN 和HGRN 網(wǎng)絡(luò)查找時間將近1 h，而表2的1 000節(jié)點(diǎn)的網(wǎng)絡(luò)的運(yùn)行時間長達(dá)近4 h，兩類網(wǎng)絡(luò)節(jié)點(diǎn)之差僅300 個節(jié)點(diǎn)左右。由分析可知，整個查找自同構(gòu)軌道的運(yùn)算過程時間復(fù)雜度達(dá)到了O（n4），因此其運(yùn)行時間也會隨著網(wǎng)絡(luò)規(guī)模的增大，呈現(xiàn)出冪函數(shù)4 次方級別的增大，因此對于GDV方法的并行化計算是十分有必要的。

4.2.1 解決重復(fù)計算問題后的結(jié)果

為了驗(yàn)證解決重復(fù)計算后GDV 方法的有效性，在表2 中編號3、4、5 的網(wǎng)絡(luò)和YPIN、HGRN 兩個真實(shí)網(wǎng)絡(luò)下進(jìn)行多次測試，各種條件下的測試結(jié)果都很相似，因此，選取了生成網(wǎng)絡(luò)中的一個測試結(jié)果進(jìn)行描述，生成網(wǎng)絡(luò)中選取的是編號為3 的無標(biāo)度網(wǎng)絡(luò)，結(jié)果如圖5 所示。從圖5 可以明顯地看到，在同一個網(wǎng)絡(luò)中，在不同的核數(shù)并行情況下，改進(jìn)后所消耗的時間遠(yuǎn)比改進(jìn)前所消耗的時間少，這在其他的網(wǎng)絡(luò)中也有所體現(xiàn)。

圖5 無標(biāo)度網(wǎng)絡(luò)在解決重復(fù)計算前后的時間消耗Fig.5 Time consumption before and after solving double counting in scale-free network

但是，解決了重復(fù)計算的問題后還面臨著各進(jìn)程資源分配極其不均勻的問題。為了驗(yàn)證資源分配不均勻這一問題，選取了表2 中編號3、4、5 的網(wǎng)絡(luò)以及YPIN、HGRN 兩個真實(shí)網(wǎng)絡(luò)模型作為數(shù)據(jù)集，它們在不同并行核數(shù)下程序時間消耗以及加速比如圖6所示。

圖6 解決重復(fù)計算后的并行性能Fig.6 Parallel performance after solving double counting

由圖6（a）可以看出，5 個網(wǎng)絡(luò)模型在使用一個核和兩個核進(jìn)行運(yùn)算時，所消耗的時間相差無幾，而且由圖6（b）可以看出，該并行性能的加速比比較低，原因就是進(jìn)程之間的資源分配不均勻。因?yàn)樵诙噙M(jìn)程的情況下，某一進(jìn)程所分得到的資源要遠(yuǎn)比其他兄弟進(jìn)程多，從而導(dǎo)致在計算時，該進(jìn)程所花費(fèi)的時間遠(yuǎn)遠(yuǎn)多于兄弟進(jìn)程，所以造成了這種加速比極低的情況。

從穩(wěn)定性方面進(jìn)行分析，通過觀察圖6（b），可以得出五個網(wǎng)絡(luò)模型加速比一致，其穩(wěn)定性良好。

4.2.2 采取負(fù)載均衡策略的實(shí)驗(yàn)結(jié)果

本節(jié)實(shí)驗(yàn)對4.2.1 節(jié)提到的各個進(jìn)程之間資源分配不均衡做出了改進(jìn)，通過對表2 中編號3、4、5 的網(wǎng)絡(luò)和YPIN、HGRN 兩個真實(shí)網(wǎng)絡(luò)進(jìn)行了多次測試，與采取負(fù)載均衡策略前的結(jié)果進(jìn)行了對比。實(shí)驗(yàn)在5個網(wǎng)絡(luò)中分別進(jìn)行了10次測試，選取了計算所需時間的平均值，并計算出改進(jìn)前后的加速比，對比結(jié)果如圖7所示。

圖7 采取負(fù)載均衡策略后的實(shí)驗(yàn)對比Fig.7 Experimental comparison after adopting load balancing strategy

圖7 展示了采取負(fù)載均衡策略后加速比的提升，上面的5條曲線展示的是前文提及的5 個網(wǎng)絡(luò)模型采取負(fù)載均衡策略后的加速比，而下面5條曲線則表示的是5個網(wǎng)絡(luò)模型未采取負(fù)載均衡策略的加速比，可以看出加速比提升較高，并且隨著并行核數(shù)的增大，加速比的提升空間也越來越大。

4.2.3 GDV方法改進(jìn)后的并行性能

本節(jié)主要研究對GDV 方法進(jìn)行了兩步優(yōu)化策略后的并行性能。為了說明改進(jìn)后的GDV 方法與網(wǎng)絡(luò)的節(jié)點(diǎn)和邊的關(guān)系以及該方法是否有良好的拓展性，本次實(shí)驗(yàn)選取了表2中編號1、2、3 的網(wǎng)絡(luò)進(jìn)行測試，該網(wǎng)絡(luò)選取的是隨機(jī)生成的無標(biāo)度網(wǎng)絡(luò)，結(jié)果如圖8所示。

圖8 無標(biāo)度網(wǎng)絡(luò)的并行性能Fig.8 Parallel performance of scale-free networks

在圖8 所顯示的實(shí)驗(yàn)結(jié)果中，選取的網(wǎng)絡(luò)為無標(biāo)度網(wǎng)絡(luò)，三個網(wǎng)絡(luò)的節(jié)點(diǎn)分別為500、800、1 000，其對應(yīng)的網(wǎng)絡(luò)的邊數(shù)都為4 000。從圖8（a）來看：隨著核數(shù)的增加，運(yùn)行時間變得越來越少，有較好的并行結(jié)果；在節(jié)點(diǎn)數(shù)與核數(shù)一定的情況下，從所耗時間角度來看，節(jié)點(diǎn)數(shù)越多，耗時越久。從圖8（b）來看：隨著核數(shù)的增加，加速比也在上升，但是加速比增加的效果并不是很理想，隨著核數(shù)的增加，加速比呈現(xiàn)出了非線性上升的狀態(tài)；縱向來看，盡管節(jié)點(diǎn)數(shù)不相同，但是它們的加速比曲線相互疊加，因此可以看出改進(jìn)后的GDV 方法擁有良好的擴(kuò)展性。

5 結(jié)語

本文實(shí)現(xiàn)了GDV 方法的并行計算，同時還提出了一種改進(jìn)策略應(yīng)用于GDV 方法：針對原有串行算法在計算自同構(gòu)軌道時耗時較長的問題，提出了解決重復(fù)計算策略和負(fù)載均衡策略，大大地節(jié)省了程序運(yùn)行時間并且實(shí)現(xiàn)了并行計算的負(fù)載均衡。本文使用了多種模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)生物網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測試，測試結(jié)果表明，GDV 的并行方法及改進(jìn)后的GDV并行方法在多個數(shù)據(jù)集上都能得到較好的加速比，有效解決了自同構(gòu)軌道查找效率低的問題。