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

宋祥帥，楊伏長(zhǎng)，謝 江*，張 武，2

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

0 引言

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

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

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

1 GDV方法的主要思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本次研究使用的實(shí)驗(yàn)平臺(tái)是上海大學(xué)高性能計(jì)算集群“自強(qiáng)4000”。實(shí)驗(yàn)使用4 個(gè)內(nèi)存節(jié)點(diǎn)，每個(gè)內(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 庫(kù)版本為IntelMPI，實(shí)驗(yàn)運(yùn)行操作系統(tǒng)為CentOS 6.3，編程語(yǔ)言為C++。

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

實(shí)驗(yàn)同時(shí)使用了模擬數(shù)據(jù)和真實(shí)生物網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行性能分析，其中模擬數(shù)據(jù)使用NetworkX［17］的python 包模擬了三類不同的網(wǎng)絡(luò)模型，分別是無(wú)標(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 五個(gè)模擬網(wǎng)絡(luò)數(shù)據(jù)集Tab.2 Five simulated network datasets

為了分析網(wǎng)絡(luò)的邊數(shù)對(duì)改進(jìn)后方法的影響，真實(shí)生物網(wǎng)絡(luò)選取了酵母菌代謝網(wǎng)絡(luò)（Yeast Protein Interaction Network，YPIN）和人類基因調(diào)控網(wǎng)絡(luò)（Human Genetic Regulatory Network，HGRN）兩個(gè)生物網(wǎng)絡(luò)數(shù)據(jù)集，其中HGRN 數(shù)據(jù)來(lái)源于STRING（Search Tool for Recurring Instances of Neighbouring Genes）在線數(shù)據(jù)庫(kù)［21］，YPIN數(shù)據(jù)集來(lái)源于Uri Alon實(shí)驗(yàn)室［22］。這兩個(gè)網(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ò)中所使用的時(shí)間比對(duì)。比較小世界模型、隨機(jī)模型和無(wú)標(biāo)度模型，三種模型的節(jié)點(diǎn)數(shù)均為1 000，邊數(shù)為4 000，在圖4（a）中可以看出這三種網(wǎng)絡(luò)在相同核數(shù)下所花費(fèi)的時(shí)間相差不大，因此可以認(rèn)為在并行的GDV 方法中自同構(gòu)軌道的查找與網(wǎng)絡(luò)的種類是不相關(guān)的。通過(guò)觀察圖4（a）可以看出，盡管兩種真實(shí)網(wǎng)絡(luò)的邊數(shù)相差很多，但它們的程序運(yùn)行時(shí)間卻相差不多，因此可以認(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ò)中的加速比對(duì)比曲線。這5 種網(wǎng)絡(luò)雖然規(guī)模不相同，但它們的加速比曲線幾乎重合，加速比數(shù)值幾乎相同，說(shuō)明了并行的GDV 方法應(yīng)用范圍廣，在不同的模型中均有好的作用。

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

4.2.1 解決重復(fù)計(jì)算問(wèn)題后的結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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