張魯飛，孫茹君，秦 芳

（1.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫 214125）

0 引言

在社交網(wǎng)絡(luò)關(guān)系挖掘、網(wǎng)頁(yè)排序、推薦系統(tǒng)及自然語(yǔ)言處理等大規(guī)模數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)應(yīng)用中，大量數(shù)據(jù)以圖的形式進(jìn)行描述和存儲(chǔ)，數(shù)據(jù)存儲(chǔ)在圖中的頂點(diǎn)以及連接頂點(diǎn)的邊上，需要通過(guò)迭代計(jì)算的方式分析數(shù)據(jù)間的關(guān)聯(lián)性，典型的算法包括PageRank 算法、Clustering 算法、Collaborative Filtering算法等。為了應(yīng)對(duì)大規(guī)模圖計(jì)算應(yīng)用的問(wèn)題，使用高性能計(jì)算機(jī)進(jìn)行分布式并行處理成為重要的解決方案［1］。但是傳統(tǒng)的數(shù)據(jù)并行計(jì)算模型并不適用于圖計(jì)算應(yīng)用，其特殊的通信模式是重要制約因素之一，目前已有多方面的通信優(yōu)化工作［2］。在應(yīng)用驅(qū)動(dòng)下，各種面向數(shù)據(jù)中心或者高性能計(jì)算機(jī)的圖計(jì)算平臺(tái)應(yīng)運(yùn)而生［3］。這些圖計(jì)算平臺(tái)采用各種手段解決通信量、負(fù)載均衡性和通信局部性等方面的問(wèn)題。

圖計(jì)算應(yīng)用的通信特性包括：

1）訪存/通信密集。通常圖計(jì)算算法中頂點(diǎn)上的計(jì)算量很小，在單機(jī)情況下訪存時(shí)間占總時(shí)間的98%以上，在分布式處理的情況下網(wǎng)絡(luò)通信和訪存占了大部分［4］。

2）隨機(jī)訪存/通信。圖計(jì)算算法有很強(qiáng)的數(shù)據(jù)依賴(lài)性，如圖1 所示，頂點(diǎn)上的計(jì)算需要收集鄰居頂點(diǎn)的數(shù)據(jù)，圖中的兩種陰影表示兩個(gè)頂點(diǎn)的鄰居，一般需要沿著邊訪問(wèn)鄰居頂點(diǎn)。但是由于圖結(jié)構(gòu)所限，沒(méi)有辦法將任意一個(gè)頂點(diǎn)的鄰居頂點(diǎn)連續(xù)存儲(chǔ)。在分布式處理的情況下，很難將整個(gè)大圖分割成若干完全獨(dú)立的子圖并行處理，面臨嚴(yán)重的隨機(jī)訪存/通信問(wèn)題。

圖1 數(shù)據(jù)依賴(lài)示意圖Fig.1 Schematic diagram of data dependency

3）數(shù)據(jù)訪問(wèn)粒度小。圖計(jì)算算法的數(shù)據(jù)訪問(wèn)粒度一般是一個(gè)頂點(diǎn)或者一條邊。在分布式處理的情況下，每一次遠(yuǎn)程訪存就需要發(fā)送一個(gè)消息，消息內(nèi)容就是頂點(diǎn)或者邊上的數(shù)據(jù)再加上目的地信息，形成了大量細(xì)粒度消息。

4）非規(guī)則性。實(shí)際生活中的圖一般是出于某種現(xiàn)實(shí)的目而建立的，網(wǎng)絡(luò)的度分布服從冪律（Power-Law）分布［5］，即絕大多數(shù)頂點(diǎn)只有少量的鏈接，但極少數(shù)“樞紐”頂點(diǎn)卻擁有大量的鏈接。在分布式處理的情況下，可能會(huì)造成極大的負(fù)載不均衡問(wèn)題。

5）動(dòng)態(tài)性。很多圖計(jì)算算法采用迭代計(jì)算的方式，而且每一輪迭代中參與計(jì)算的頂點(diǎn)數(shù)量都可能變化。因此，事先針對(duì)負(fù)載不均衡問(wèn)題采取的措施可能在實(shí)際運(yùn)行過(guò)程中不能取得預(yù)期效果。

本文聚焦圖計(jì)算應(yīng)用的“大量隨機(jī)細(xì)粒度消息”特征，分析消息的固定開(kāi)銷(xiāo)對(duì)可擴(kuò)展性造成的影響，并分析傳統(tǒng)的直接消息聚合方法中聚合開(kāi)銷(xiāo)的影響，研究面向圖計(jì)算的消息聚合方法及相關(guān)運(yùn)行時(shí)系統(tǒng)。本文暫不考慮圖計(jì)算應(yīng)用通信的非規(guī)則性和動(dòng)態(tài)性，因此也只和不做負(fù)載均衡優(yōu)化的圖計(jì)算平臺(tái)作橫向比較。

具體地，本文工作總結(jié)如下：

1）提出結(jié)構(gòu)動(dòng)態(tài)的消息聚合和路由技術(shù)（Structuredynamic Message Aggregation and Routing Technique，SMART），使用參數(shù)化的虛擬拓?fù)鋵⑾⒕酆戏椒☉?yīng)用在從源到目的地的多個(gè)中間點(diǎn)上，這樣一方面可以減少聚合緩沖區(qū)的數(shù)量；另一方面可以有效增強(qiáng)通信的局部性，提升傳遞大量隨機(jī)細(xì)粒度消息時(shí)的性能。不同虛擬拓?fù)浣Y(jié)構(gòu)和配置可以使得消息聚合適應(yīng)特定圖計(jì)算應(yīng)用。

2）提出運(yùn)行時(shí)系統(tǒng)中虛擬拓?fù)涞南⒕酆夏KVAggregator。V-Aggregator 模塊將消息聚合功能和消息路由功能分離，并加入了若干策略控制點(diǎn)，方便探索最優(yōu)的通信優(yōu)化策略。利用自動(dòng)調(diào)優(yōu)工具可以方便地用于從多個(gè)候選策略中針對(duì)性地選擇最佳策略，有效降低應(yīng)用開(kāi)發(fā)人員的調(diào)優(yōu)難度。

3）提出基于消息聚合庫(kù)的圖計(jì)算平臺(tái)AGGraph。使用VAggregator 可以使得應(yīng)用開(kāi)發(fā)人員不需要再針對(duì)隨機(jī)細(xì)粒度消息做應(yīng)用層的通信優(yōu)化，使用AGGraph 的編程接口可以方便快捷地開(kāi)發(fā)一系列圖計(jì)算算法。實(shí)驗(yàn)結(jié)果表明，基于AGGraph 的典型應(yīng)用性能比目前常用的圖計(jì)算平臺(tái)提升100%以上。

1 相關(guān)工作

1.1 基于消息傳遞模型的圖計(jì)算平臺(tái)

很多分布式內(nèi)存系統(tǒng)上的圖計(jì)算平臺(tái)使用基于消息傳遞的通信模型，例如Pregel［6］、GPS（Graph Processing System）［7］、PBGL（Parallel Boost Graph Library）2.0［8］和Giraph［9］。在基于消息傳遞的圖計(jì)算平臺(tái)中，頂點(diǎn)的狀態(tài)保存在本地，通過(guò)消息傳遞方式更新其他機(jī)器上的頂點(diǎn)的狀態(tài)。其中，PBGL 2.0 基于Active Pebbles 編程系統(tǒng)［10］開(kāi)發(fā)。Active Pebbles 使用主動(dòng)消息機(jī)制，其執(zhí)行模型包含了消息聚合機(jī)制，能夠?qū)⒓?xì)粒度表達(dá)映射到高效實(shí)現(xiàn)，適合圖計(jì)算應(yīng)用，但是消息聚合方法固定，靈活性不足。

1.2 具備消息聚合功能的運(yùn)行時(shí)系統(tǒng)

Grappa［11］和Active Pebbles 編程系統(tǒng)分別在網(wǎng)絡(luò)傳輸層和運(yùn)行時(shí)系統(tǒng)支持請(qǐng)求的聚合，基于它們實(shí)現(xiàn)的圖計(jì)算應(yīng)用性能良好。此外，STAPL（Standard Template Adaptive Parallel C++Library）編程框架［12］也支持直接的消息聚合，該圖計(jì)算平臺(tái)用于位于美國(guó)勞倫斯伯克利國(guó)家實(shí)驗(yàn)室（Lawrence Berkeley National Laboratory）的采用Cray XE6 架構(gòu)的“Hopper”高性能計(jì)算機(jī)。以上系統(tǒng)采用的是直接消息聚合方法，緩沖區(qū)內(nèi)存開(kāi)銷(xiāo)存在限制，聚合隨機(jī)請(qǐng)求的時(shí)間開(kāi)銷(xiāo)也較大，因此可擴(kuò)展性不足。

1.3 面向消息聚合的虛擬拓?fù)浣Y(jié)構(gòu)

在應(yīng)用層、運(yùn)行時(shí)系統(tǒng)層、網(wǎng)絡(luò)層利用虛擬拓?fù)浣Y(jié)構(gòu)進(jìn)行消息聚合，可以增加大量細(xì)粒度消息的聚合機(jī)會(huì)并且減少緩沖區(qū)的內(nèi)存開(kāi)銷(xiāo)，使得應(yīng)用層的細(xì)粒度通信的表達(dá)不必要翻譯成網(wǎng)絡(luò)層上的細(xì)粒度消息。虛擬拓?fù)浣Y(jié)構(gòu)上的路由的基本思想是在所有節(jié)點(diǎn)上都提供尋址方案，并且任何消息可以?xún)H根據(jù)當(dāng)前節(jié)點(diǎn)的地址以及目的地節(jié)點(diǎn)的地址進(jìn)行路由，路由的跳數(shù)與源和目的地的坐標(biāo)差有關(guān)。Kumar 在Charm++運(yùn)行時(shí)系統(tǒng)的通信抽象層上通過(guò)使用2D 正方形和3D 正方形虛擬拓?fù)渖系南⒕酆戏椒▉?lái)優(yōu)化all-to-all 通信，并分析了消息數(shù)量減少的情況［13］。但是這種方法只是針對(duì)單次通信進(jìn)行優(yōu)化，沒(méi)有采用流式發(fā)送策略，也沒(méi)有使用可配置的虛擬拓?fù)?。神威·太湖之光上的圖計(jì)算平臺(tái)ShenTu［14］提出了基于分組的消息聚合技術(shù)，來(lái)解決超大規(guī)模網(wǎng)絡(luò)下無(wú)規(guī)則消息的傳輸問(wèn)題：一方面解決了連接數(shù)過(guò)多的問(wèn)題，另一方面在系統(tǒng)規(guī)模很大的情況下提升了應(yīng)用性能。但是這種方法只是針對(duì)神威·太湖之光的有裁剪的多層胖樹(shù)網(wǎng)絡(luò)結(jié)構(gòu)，沒(méi)有使用可配置的虛擬拓?fù)?。Charm++運(yùn)行時(shí)系統(tǒng)上的消息聚合庫(kù)TRAM（Topological Routing and Aggregation Module）［15］使用了可以配置的虛擬拓?fù)?，但是并沒(méi)有針對(duì)圖計(jì)算應(yīng)用作深入分析。

2 結(jié)構(gòu)動(dòng)態(tài)的消息聚合和路由技術(shù)

結(jié)構(gòu)動(dòng)態(tài)的消息聚合和路由技術(shù)（SMART）和傳統(tǒng)的直接消息聚合方法相比強(qiáng)調(diào)了“結(jié)構(gòu)動(dòng)態(tài)性”，體現(xiàn)在兩個(gè)方面：一是消息聚合的動(dòng)態(tài)性，使用虛擬拓?fù)浜笙⒖梢栽谀骋恢虚g點(diǎn)上動(dòng)態(tài)地聚合；二是虛擬拓?fù)涞膭?dòng)態(tài)性，可以靈活地改變虛擬拓?fù)涞呐渲靡赃m應(yīng)不同的軟硬件條件。

SMART使用發(fā)送端發(fā)起的消息聚合策略，如圖2所示，即發(fā)送端決定如何聚合消息以及何時(shí)發(fā)送聚合后的大消息。

圖2 發(fā)送端發(fā)起的消息聚合策略示意圖Fig.2 Schematic diagram of message aggregation strategy initiated by sender

發(fā)送端發(fā)送聚合后的大消息的時(shí)機(jī)為到達(dá)最大緩沖區(qū)大小，緩沖區(qū)大小即消息聚合后發(fā)送的大消息的粒度。固定緩沖區(qū)大小，將緩沖區(qū)設(shè)置為與應(yīng)用無(wú)關(guān)的大小，以能有效利用帶寬為宜。另外，約定每個(gè)緩沖區(qū)大小是固定的，可以增強(qiáng)虛擬拓?fù)涞膶?duì)稱(chēng)性。

在圖計(jì)算應(yīng)用中，消息的時(shí)空隨機(jī)性很強(qiáng)，消息隨時(shí)可能發(fā)往任意地方?？赡苡邢?lái)源于不同的處理器，但前往同一目的地；也有可能來(lái)源于同一個(gè)處理器，但前往不同目的地。但是傳統(tǒng)的直接消息聚合方法只能對(duì)通信路徑完全一樣的消息進(jìn)行聚合，聚合機(jī)會(huì)有限。很多編程系統(tǒng)的消息框架支持機(jī)制和策略分離，可以利用網(wǎng)絡(luò)虛擬化技術(shù)，可以將任意物理拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為虛擬網(wǎng)格拓?fù)浣Y(jié)構(gòu)。SMART 方法首先構(gòu)建一個(gè)廣義超立方體虛擬拓?fù)浣Y(jié)構(gòu)，如圖3 所示，然后將消息的通信過(guò)程劃分為若干步驟，形成若干中間目的地，在每一個(gè)中間目的地均可以重新聚合數(shù)據(jù)項(xiàng)。在虛擬拓?fù)渲?，即使消息的源和目的地都不相同，也可能通過(guò)一部分相同的子路徑到達(dá)目的地。

圖3 通信路徑列舉示意圖Fig.3 Schematic diagram of communication path enumeration

路由采用最高維度優(yōu)先轉(zhuǎn)發(fā)算法，即每次沿著虛擬網(wǎng)格拓?fù)涞囊粋€(gè)單一維度進(jìn)行消息路由。這種路由算法可以保持最小路由的性質(zhì)，且具有負(fù)載均衡性。

傳統(tǒng)的直接消息聚合方法在系統(tǒng)規(guī)模較大的情況下內(nèi)存開(kāi)銷(xiāo)過(guò)大，更為重要的是，在緩沖區(qū)上重組消息通常會(huì)導(dǎo)致聚合開(kāi)銷(xiāo)過(guò)大，可能會(huì)影響性能。如圖4所示，SMART使用中間頂點(diǎn)轉(zhuǎn)發(fā)消息可以增加聚合機(jī)會(huì)從而使得緩沖區(qū)填充速度加快，同時(shí)降低緩沖區(qū)內(nèi)存開(kāi)銷(xiāo)。

圖4 某一對(duì)頂點(diǎn)之間通信示意圖Fig.4 Schematic diagram of communication between a pair of vertices

SMART對(duì)于圖計(jì)算應(yīng)用具有適應(yīng)性，具體分析如下：

1）系統(tǒng)規(guī)模非常大時(shí)，SMART 在減少消息聚合方法使用的緩沖區(qū)的內(nèi)存開(kāi)銷(xiāo)方面意義重大。

2）對(duì)于圖計(jì)算應(yīng)用“大量細(xì)粒度消息流式發(fā)送”的通信特征，消息聚合方法可以減少發(fā)送消息次數(shù)從而減少固定開(kāi)銷(xiāo)。

3）對(duì)于圖計(jì)算應(yīng)用的“時(shí)空隨機(jī)通信”的通信特征，消息聚合方法帶來(lái)的聚合開(kāi)銷(xiāo)對(duì)性能影響較大，SMART 相較于傳統(tǒng)的直接消息聚合方法因?yàn)榫酆祥_(kāi)銷(xiāo)減少而獲得一定的加速效果。

4）系統(tǒng)規(guī)模越大，SMART 使用虛擬拓?fù)湓黾酉⒕酆系臋C(jī)會(huì)從而減少，聚合開(kāi)銷(xiāo)的優(yōu)勢(shì)越大。

5）隨著虛擬拓?fù)涞木S度數(shù)量的增加，消息聚合方法獲得的收益和付出的代價(jià)都在增加。當(dāng)維度大到一定程度時(shí)，由于重復(fù)發(fā)送數(shù)據(jù)造成的可變開(kāi)銷(xiāo)增加會(huì)使得SMART 不能取得預(yù)期效果。

6）SMART 并不能解決圖計(jì)算應(yīng)用的“非規(guī)則通信”的問(wèn)題，但是SMART本身不會(huì)引入負(fù)載不平衡問(wèn)題。

3 面向圖計(jì)算的消息聚合運(yùn)行時(shí)實(shí)現(xiàn)

在通信軟件棧的不同層次都可以使用消息聚合方法，越接近應(yīng)用層，越有利于減少發(fā)送和聚合后的數(shù)據(jù)項(xiàng)相關(guān)的消息頭，越有利于減少通信軟件棧底層的通信開(kāi)銷(xiāo)。但是通信軟件棧中的層次越高，和應(yīng)用本身的相關(guān)性越強(qiáng)。因此，在運(yùn)行時(shí)系統(tǒng)層使用消息聚合方法有兩點(diǎn)優(yōu)勢(shì)：一是效果好，可以減少在網(wǎng)絡(luò)和運(yùn)行時(shí)系統(tǒng)層的頭部數(shù)據(jù)，降低細(xì)粒度通信的可變開(kāi)銷(xiāo)和固定開(kāi)銷(xiāo)；二是通用性好，將消息聚合行為抽象為一些簡(jiǎn)單接口提供給應(yīng)用程序，可以方便為應(yīng)用開(kāi)發(fā)人員所使用。如圖5 所示，通過(guò)縱向增加軟件層次，橫向拓展軟件功能，形成網(wǎng)絡(luò)虛擬化的通信軟件棧V-Aggregator。

V-Aggregator 為應(yīng)用開(kāi)發(fā)人員提供了簡(jiǎn)單、優(yōu)化的細(xì)粒度通信接口，并支持應(yīng)用開(kāi)發(fā)人員根據(jù)各種軟硬件條件靈活配置參數(shù)以得到最優(yōu)性能，這些參數(shù)包括拓?fù)浣Y(jié)構(gòu)、緩沖區(qū)大小。由于圖計(jì)算應(yīng)用一般有迭代的過(guò)程，V-Aggregator 可在應(yīng)用程序確定一組配置集合后，在每一輪迭代中自動(dòng)地嘗試各種配置，直到收斂到最佳的解決方案。

圖5 網(wǎng)絡(luò)虛擬化的通信軟件棧V-Aggregator示意圖Fig.5 Schematic diagram of communication software stack for network virtualization named V-Aggregator

基于V-Aggregator 實(shí)現(xiàn)的圖計(jì)算平臺(tái)AGGraph 是以頂點(diǎn)為中心的：將一個(gè)頂點(diǎn)作為一個(gè)基本對(duì)象，用戶(hù)只需要按照模板實(shí)現(xiàn)不同的頂點(diǎn)類(lèi)就可以實(shí)現(xiàn)不同的圖計(jì)算算法。

在AGGraph 中，主對(duì)象Mainchare 負(fù)責(zé)創(chuàng)建頂點(diǎn)對(duì)象集合，并協(xié)調(diào)它們之間的計(jì)算和通信；而頂點(diǎn)對(duì)象Vertex 主要負(fù)責(zé)處理頂點(diǎn)之間的消息。

AGGraph的一般處理流程是：

1）主對(duì)象使用適當(dāng)?shù)腉raphIO 對(duì)象讀取圖數(shù)據(jù)，并將頂點(diǎn)和邊數(shù)據(jù)發(fā)送到每個(gè)頂點(diǎn)對(duì)象。

2）使用運(yùn)行時(shí)系統(tǒng)的靜默檢測(cè)功能來(lái)確定所有數(shù)據(jù)都已發(fā)送到對(duì)應(yīng)的頂點(diǎn)對(duì)象，然后發(fā)起start（）回調(diào)，此回調(diào)函數(shù)在不同計(jì)算模型下，以不同的方式調(diào)用頂點(diǎn)對(duì)象的run（）方法。

3）每個(gè)超步結(jié)束時(shí)調(diào)用check（），決定整個(gè)計(jì)算是否結(jié)束。

4 實(shí)驗(yàn)分析

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

實(shí)驗(yàn)使用CPU通用計(jì)算系統(tǒng)，詳細(xì)配置如表1所示。

表1 系統(tǒng)軟硬件配置Tab.1 System hardware and software configuration

測(cè)試程序?yàn)榛贏GGraph 實(shí)現(xiàn)的PageRank 算法、寬度優(yōu)先搜索（Breadth-first Search，BFS）算法、連通分支（Contected Component，CC）算法［16］。

測(cè)試數(shù)據(jù)為生成的不同運(yùn)行規(guī)模（scale）的R-MAT（Recursive MATrix）圖［17］，總的頂點(diǎn)數(shù)量為2scale。具體方法為，利用Graph500 測(cè)試規(guī)范中的克羅內(nèi)科（Kronecker）生成器［18］產(chǎn)生服從冪律分布的邊因子（edgefactor）為16 的無(wú)向圖，每個(gè)頂點(diǎn)使用8個(gè)字節(jié)存儲(chǔ)。

4.2 實(shí)驗(yàn)結(jié)果

分別測(cè)試同步計(jì)算模式下的PageRank 算法、異步計(jì)算模式下的BFS算法、異步計(jì)算模式下的CC算法使用原有通信框架（naive）和V-Aggregator 的性能，并和PBGL（Parallel Boost Graph Library）［19］中的算法作比較。選用PBGL 作為對(duì)比平臺(tái)主要是由于它只是做了簡(jiǎn)單通信優(yōu)化，沒(méi)有采用過(guò)多的負(fù)載均衡優(yōu)化，和本文研究出發(fā)點(diǎn)類(lèi)似。采用強(qiáng)可擴(kuò)展性測(cè)試，物理資源規(guī)模分別為1、2、4、8、16、32個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)上運(yùn)行8個(gè)程序?qū)嵗＿\(yùn)行規(guī)模分別為20、22。

1）PageRank算法。

指定迭代次數(shù)為3。通過(guò)使用自動(dòng)調(diào)優(yōu)工具確定：節(jié)點(diǎn)數(shù)量在1 至4 時(shí)，最優(yōu)策略為1 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為2 KB；節(jié)點(diǎn)數(shù)量在8 至16 時(shí)，最優(yōu)策略為2 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為2 KB；節(jié)點(diǎn)數(shù)量為32 時(shí)，最優(yōu)策略為3 維虛擬拓?fù)浣Y(jié)構(gòu)，維度大小分別為4、8 和8，緩沖區(qū)大小為4 KB。強(qiáng)可擴(kuò)展性測(cè)試結(jié)果如圖6所示。

圖6 不同運(yùn)行規(guī)模時(shí)PageRank算法的測(cè)試結(jié)果Fig.6 Test results of PageRank algorithm under different running scales

2）BFS算法。

通過(guò)使用自動(dòng)調(diào)優(yōu)工具確定：節(jié)點(diǎn)數(shù)量在1 至2 時(shí)，最優(yōu)策略為1 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為4 KB；節(jié)點(diǎn)數(shù)量在4至32 時(shí)，最優(yōu)策略為2 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為8 KB。強(qiáng)可擴(kuò)展性測(cè)試結(jié)果如圖7所示。

圖7 不同運(yùn)行規(guī)模時(shí)BFS算法的測(cè)試結(jié)果Fig.7 Test results of BFS algorithm under different running scales

3）CC算法。

通過(guò)使用自動(dòng)調(diào)優(yōu)工具確定：節(jié)點(diǎn)數(shù)量在1 至2 時(shí)，最優(yōu)策略為1 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為2 KB；節(jié)點(diǎn)數(shù)量在4至16 時(shí)，最優(yōu)策略為2 維虛擬拓?fù)浣Y(jié)構(gòu)，緩沖區(qū)大小為2 KB；節(jié)點(diǎn)數(shù)量為32時(shí)，最優(yōu)策略為3維虛擬拓?fù)浣Y(jié)構(gòu)，維度大小分別為4、8 和8，緩沖區(qū)大小為4 KB。強(qiáng)可擴(kuò)展性測(cè)試結(jié)果如圖8所示。

圖8 不同運(yùn)行規(guī)模時(shí)CC算法的測(cè)試結(jié)果Fig.8 Test results of CC algorithm under different running scales

4.3 結(jié)果分析

V-Aggregator相對(duì)PBGL加速比如表2所示。

表2 運(yùn)行規(guī)模為20和22時(shí)V-Aggregator相對(duì)PBGL加速比Tab.2 Acceleration ratio of V-Aggregator to PBGL at running scale of 20 and 22

可以得到以下結(jié)論：

1）AGGraph 圖計(jì)算平臺(tái)可以有效支持應(yīng)用開(kāi)發(fā)人員方便、快捷、正確地實(shí)現(xiàn)圖計(jì)算算法，在節(jié)點(diǎn)數(shù)量32 以?xún)?nèi)可擴(kuò)展性良好。

2）基于V-Aggregator 模塊實(shí)現(xiàn)的典型圖計(jì)算算法比使用原有通信框架時(shí)性能大幅提升，比目前常用的圖計(jì)算平臺(tái)PBGL 提升100%以上。PBGL 圖計(jì)算平臺(tái)使用了傳統(tǒng)的消息聚合方法，因此AGGraph 相對(duì)于它的加速比可以體現(xiàn)本文所提出的基于虛擬拓?fù)涞南⒕酆戏椒ǖ膬?yōu)勢(shì)。

3）基于V-Aggregator 模塊實(shí)現(xiàn)的典型圖計(jì)算算法中，PageRank 算法加速效果最好，BFS算法加速效果最差，區(qū)別在于PageRank 算法比BFS 算法更加規(guī)整，主要是由于本平臺(tái)沒(méi)有考慮非規(guī)則性方面的優(yōu)化。

5 結(jié)語(yǔ)

本文根據(jù)圖計(jì)算應(yīng)用“大規(guī)模流式非規(guī)則隨機(jī)細(xì)粒度消息”的通信特征提出了基于虛擬拓?fù)涞慕Y(jié)構(gòu)動(dòng)態(tài)的消息聚合和路由技術(shù)，并給出了該方法的適用范圍。本文提出了運(yùn)行時(shí)系統(tǒng)面向消息聚合的網(wǎng)絡(luò)虛擬化技術(shù)，對(duì)原有通信接口做微小改動(dòng)后即可支持消息聚合方法，便于應(yīng)用開(kāi)發(fā)人員使用。該運(yùn)行時(shí)支持自動(dòng)調(diào)優(yōu)，可以方便地用于從多個(gè)候選策略中選擇最佳策略，真正意義上實(shí)現(xiàn)“結(jié)構(gòu)動(dòng)態(tài)”?；谏鲜黾夹g(shù)，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于消息聚合技術(shù)的圖計(jì)算平臺(tái)，可以實(shí)現(xiàn)根據(jù)軟硬件條件自動(dòng)地選擇最優(yōu)通信策略，支持以頂點(diǎn)為中心的編程模型，并開(kāi)發(fā)了若干圖計(jì)算算法。最后，通過(guò)大量實(shí)驗(yàn)驗(yàn)證了本文所提算法的有效性和實(shí)用性。

本文選取的對(duì)比平臺(tái)時(shí)間并不能代表圖計(jì)算平臺(tái)的最前沿技術(shù)，下一步會(huì)基于消息聚合運(yùn)行時(shí)設(shè)計(jì)更加先進(jìn)的圖計(jì)算平臺(tái)，重點(diǎn)解決圖計(jì)算應(yīng)用通信的非規(guī)則性和動(dòng)態(tài)性問(wèn)題，然后再和業(yè)界領(lǐng)先的圖計(jì)算平臺(tái)作橫向比較。