基于塊坐標(biāo)下降法的外存異步圖計(jì)算系統(tǒng)①

趙程 張志斌 郭嘉豐 劉丁瑋

(中國(guó)科學(xué)院計(jì)算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京100190)

(中國(guó)科學(xué)院大學(xué) 北京100049)

0 引言

圖數(shù)據(jù)普遍存在于各個(gè)領(lǐng)域,如社交網(wǎng)絡(luò)、網(wǎng)頁(yè)鏈接、金融網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等,其中大圖計(jì)算任務(wù)吸引了大量的關(guān)注,構(gòu)建高效易用的圖計(jì)算系統(tǒng)迫在眉睫。近些年的研究設(shè)計(jì)并實(shí)現(xiàn)了基于各類計(jì)算資源的高性能圖計(jì)算系統(tǒng)[1-9],其中,盡可能地利用外存擴(kuò)展處理數(shù)據(jù)的規(guī)模,并且探索更高效的外存計(jì)算模式成為圖計(jì)算系統(tǒng)擴(kuò)展能力研究的關(guān)鍵。

大部分基于外存的系統(tǒng)[2,7-8]在執(zhí)行圖計(jì)算的任務(wù)時(shí)采用整體同步并行計(jì)算(bulk synchronous parallel,BSP)模型,在圖計(jì)算的每輪迭代中都需要從外存加載全量圖數(shù)據(jù)進(jìn)行計(jì)算。外存圖計(jì)算系統(tǒng)使用相對(duì)簡(jiǎn)單的劃分算法劃分圖數(shù)據(jù),并據(jù)此安排流水線模式,通過(guò)計(jì)算時(shí)間掩蓋加載開(kāi)銷。然而,它們依據(jù)劃分信息順序執(zhí)行,每輪計(jì)算中的數(shù)據(jù)塊最多處理一次,從而造成數(shù)據(jù)的重復(fù)加載與計(jì)算,浪費(fèi)了外存帶寬。異步計(jì)算模式的外存圖計(jì)算系統(tǒng)通過(guò)有選擇的加載數(shù)據(jù)塊并對(duì)其進(jìn)行多次計(jì)算來(lái)減少外存加載的冗余,如Clip[5]、Lumos[3]等。然而,Lumos設(shè)置了每個(gè)數(shù)據(jù)塊計(jì)算的硬上限,而Clip 缺少對(duì)內(nèi)存異步執(zhí)行程度的控制,它們只是一定程度上緩解了冗余加載的問(wèn)題。

使用基于優(yōu)先選擇的異步圖計(jì)算仍然存在諸多挑戰(zhàn):第一,計(jì)算優(yōu)先級(jí)需要綜合全圖點(diǎn)信息,需要額外開(kāi)銷;第二,BSP 模型系統(tǒng)中的加載計(jì)算流水線設(shè)計(jì)得益于其順序執(zhí)行策略,而優(yōu)先選擇的策略會(huì)破壞這種順序執(zhí)行流程;第三,由于圖數(shù)據(jù)的偏斜性[10],基于點(diǎn)集的優(yōu)先級(jí)選擇策略要求每個(gè)數(shù)據(jù)塊包含相同的點(diǎn)數(shù),這會(huì)造成圖計(jì)算的負(fù)載不均衡。

本文提出了一個(gè)基于塊坐標(biāo)下降法(block coordinate descent,BCD) 的外存異步圖計(jì)算系統(tǒng)(BCD based asynchronous out-of-core graph computing system,BCDG)。首先將圖算法轉(zhuǎn)化為最優(yōu)化問(wèn)題,然后使用塊坐標(biāo)下降法作為塊優(yōu)先級(jí)算法,每次計(jì)算選擇對(duì)算法收斂貢獻(xiàn)最大的塊,以減少冗余計(jì)算。利用BCD 的優(yōu)先級(jí)序列能夠預(yù)測(cè)后續(xù)若干輪選擇的特性,設(shè)計(jì)了一次選擇多輪優(yōu)先的調(diào)度策略,從而降低了優(yōu)先級(jí)計(jì)算的平均開(kāi)銷?；诖颂匦?設(shè)計(jì)了后續(xù)計(jì)算的預(yù)取機(jī)制和對(duì)應(yīng)的計(jì)算加載流水線,填補(bǔ)了中央處理器(central processing unit,CPU)計(jì)算優(yōu)先級(jí)時(shí)加載線程的空閑。考慮到負(fù)載均衡問(wèn)題,設(shè)計(jì)了計(jì)算調(diào)度分離的劃分策略,根據(jù)邊將圖平均分為一個(gè)個(gè)分片,并將一個(gè)分片視為BCDG 中的最小計(jì)算調(diào)度單元。調(diào)度時(shí)將分片按點(diǎn)集合拼成BCD 選中的數(shù)據(jù)塊,計(jì)算時(shí)按邊對(duì)這些分片并發(fā)計(jì)算。使用BCDG 的系統(tǒng)框架實(shí)現(xiàn)了圖計(jì)算中的經(jīng)典問(wèn)題PageRank 和弱連通分量,并進(jìn)行了充分的實(shí)驗(yàn)驗(yàn)證。

1 相關(guān)工作

目前,外存圖計(jì)算系統(tǒng)設(shè)計(jì)外存友好的數(shù)據(jù)結(jié)構(gòu)以及對(duì)應(yīng)的劃分策略,并且據(jù)此設(shè)計(jì)對(duì)應(yīng)的執(zhí)行引擎。這些設(shè)計(jì)往往采用流式地加載、計(jì)算劃分后的數(shù)據(jù)庫(kù)的方式,以求最大化數(shù)據(jù)處理的局部性。下面簡(jiǎn)要討論近年來(lái)一些相關(guān)工作。

同步外存圖計(jì)算系統(tǒng)。Graphene[2]使用I/O 請(qǐng)求為中心的圖處理模型,通過(guò)將高層數(shù)據(jù)訪問(wèn)轉(zhuǎn)化為細(xì)粒度的I/O 請(qǐng)求來(lái)簡(jiǎn)化I/O 管理。Dynamic-Shards[11]通過(guò)動(dòng)態(tài)分區(qū),從分區(qū)中移除不必要的邊,以減少磁盤(pán)I/O。GraphOne[12]使用了鄰接表和壓縮系數(shù)矩陣兩套結(jié)構(gòu)存儲(chǔ)圖數(shù)據(jù)以實(shí)現(xiàn)部分的動(dòng)態(tài)圖數(shù)據(jù)處理的負(fù)載能力。

異步外存圖計(jì)算系統(tǒng)。Wonderland[13]抽取有效的圖摘要以捕捉特定的圖屬性,在圖摘要的引導(dǎo)下執(zhí)行處理,推斷出更好的優(yōu)先處理順序和更快的圖信息傳播。雖然這種基于圖摘要的技術(shù)很有效,但其應(yīng)用范圍僅限于基于路徑的單調(diào)圖算法,此外算法的適用性仍未確定。AsyncStripe[14]使用非對(duì)稱分區(qū)和基于條帶的自適應(yīng)訪問(wèn)策略來(lái)處理異步算法。由于這些工作沒(méi)有提供同步保證,它們僅適用于基于路徑的異步算法。文獻(xiàn)[15]針對(duì)libaio 引擎設(shè)計(jì)了自適應(yīng)的I/O 和計(jì)算調(diào)度機(jī)制并利用批(batch)機(jī)制平衡了異步計(jì)算的負(fù)載。

外存計(jì)算之外的工作。Gemini[1]和Symple-Graph[6]提供了分布式圖計(jì)算的同步處理模型。文獻(xiàn)[16]探討了分布式圖計(jì)算時(shí)的容錯(cuò)計(jì)算問(wèn)題。Teseo[17]關(guān)注動(dòng)態(tài)圖的存儲(chǔ)并提供同步處理模型。Kaleido[18]針對(duì)圖挖掘類任務(wù)以子圖為中心的模型計(jì)算提供了同步處理模型。

2 背景與動(dòng)機(jī)

本節(jié)首先討論最先進(jìn)的外存圖計(jì)算系統(tǒng),然后介紹整體同步并行、異步并行模式在圖計(jì)算中的應(yīng)用,隨后分析在外存圖計(jì)算系統(tǒng)中應(yīng)用異步并行的動(dòng)機(jī)與挑戰(zhàn)。

2.1 基于外存的圖計(jì)算系統(tǒng)

基于外存的單機(jī)圖計(jì)算系統(tǒng)對(duì)于圖劃分問(wèn)題采用不需要復(fù)雜計(jì)算的線性劃分策略,然后以流式的方式按照劃分后的數(shù)據(jù)塊計(jì)算圖數(shù)據(jù),以此最大化利用圖數(shù)據(jù)的順序局部性。

同步并行計(jì)算。GraphChi[7]在點(diǎn)集上進(jìn)行圖劃分,并保證每個(gè)分塊包含的邊數(shù)盡可能相同。GraphChi 為每個(gè)圖劃分在內(nèi)存中維護(hù)內(nèi)存緩沖區(qū),當(dāng)緩沖區(qū)耗盡時(shí)從外存中加載劃分?jǐn)?shù)據(jù),并且使用協(xié)程來(lái)實(shí)現(xiàn)重疊計(jì)算與加載的時(shí)間。GridGraph[8]將點(diǎn)集劃分為若干子集,將邊集劃分為基于點(diǎn)劃分子集的二維網(wǎng)絡(luò);然后構(gòu)建基于二維數(shù)據(jù)塊的流式執(zhí)行,根據(jù)不同的算法優(yōu)先選擇按行或按列執(zhí)行。加載任務(wù)被拆分成小塊,以隊(duì)列的形式維護(hù)到協(xié)程中,從而實(shí)現(xiàn)加載與計(jì)算的重疊。

缺陷:上述外存圖計(jì)算系統(tǒng)根據(jù)圖數(shù)據(jù)的劃分信息順序執(zhí)行,其數(shù)據(jù)劃分的計(jì)算順序是在計(jì)算前確定的,并且每輪計(jì)算中每個(gè)加載的塊最多處理一次。這類預(yù)先確定執(zhí)行順序和最多處理一次的限制浪費(fèi)了寶貴的外存帶寬,造成了重復(fù)的數(shù)據(jù)加載與計(jì)算。

異步并行計(jì)算。上述系統(tǒng)除了支持同步并行計(jì)算模型,還支持簡(jiǎn)單的異步執(zhí)行,在圖算法迭代過(guò)程中允許更新函數(shù)使用最新的中間結(jié)果,然而每個(gè)加載的塊在每輪迭代中最多仍然只能處理一次。Lumos[3]在GridGraph 的基礎(chǔ)上,使用無(wú)序的異步執(zhí)行在多輪計(jì)算中共用計(jì)算結(jié)果,以減少外存加載。Clip[5]針對(duì)此設(shè)計(jì)了同步與異步計(jì)算的折中,其在塊之間進(jìn)行同步處理以確保磁盤(pán)的順序I/O,在每個(gè)塊內(nèi)實(shí)現(xiàn)異步處理。

缺陷:Lumos 一定程度上緩解了每個(gè)加載塊在每輪計(jì)算中最多處理一次的問(wèn)題,但緩解程度受限于其設(shè)定的硬上限。Clip 缺少對(duì)于內(nèi)存異步執(zhí)行程度的控制,整體設(shè)計(jì)通過(guò)塊內(nèi)的異步計(jì)算的CPU 資源換取外存I/O,仍然存在冗余計(jì)算與加載。Clip僅提供了異步算法的支持,如廣度優(yōu)先搜索、最短路徑等,對(duì)于傳統(tǒng)的同步算法如PageRank 支持能力有限。

2.2 動(dòng)機(jī)與挑戰(zhàn)

近年來(lái),有些在分布式場(chǎng)景和異構(gòu)計(jì)算場(chǎng)景的圖計(jì)算系統(tǒng)使用塊選擇策略在圖算法迭代過(guò)程中優(yōu)先選擇“重要”的數(shù)據(jù)塊進(jìn)行計(jì)算,以此加速圖算法收斂。分布式圖計(jì)算系統(tǒng)PrIter[19]和Maiter[20]的優(yōu)先選擇策略是利用基于差值的計(jì)算方法選擇并更新每輪圖算法迭代中差值最大的數(shù)據(jù)塊?；贑PUFPGA 的異構(gòu)計(jì)算圖計(jì)算系統(tǒng)GraphABCD[21]將圖算法轉(zhuǎn)化為最優(yōu)化問(wèn)題,并使用塊坐標(biāo)下降方法,每輪選擇對(duì)目標(biāo)函數(shù)下降最大的塊進(jìn)行計(jì)算,以此最大程度地減少冗余計(jì)算。這些系統(tǒng)在多計(jì)算資源(分布式CPU、CPU-FPGA)環(huán)境中驗(yàn)證了對(duì)圖劃分進(jìn)行優(yōu)先選擇策略能夠減少冗余計(jì)算、提升收斂效率。在外存圖計(jì)算系統(tǒng)中,優(yōu)先選擇策略有助于計(jì)算過(guò)程中總是計(jì)算對(duì)于算法收斂幫助最大的數(shù)據(jù)塊,從而最大程度地提升算法收斂效率并減少冗余的數(shù)據(jù)加載。

在外存圖計(jì)算系統(tǒng)中應(yīng)用異步并行的挑戰(zhàn)有:第一,由于計(jì)算數(shù)據(jù)塊被選擇的優(yōu)先級(jí)帶來(lái)的每輪額外選擇時(shí)間開(kāi)銷不容忽略。數(shù)據(jù)塊的優(yōu)先級(jí)與塊內(nèi)容以及計(jì)算中間結(jié)果息息相關(guān)[19],需要綜合塊的數(shù)量、塊中包含的點(diǎn)信息以及點(diǎn)對(duì)應(yīng)的中間結(jié)果進(jìn)行計(jì)算;第二,基于優(yōu)先選擇設(shè)計(jì)外存圖計(jì)算框架還需要進(jìn)一步設(shè)計(jì)加載、計(jì)算的流水線。由于優(yōu)先選擇策略的計(jì)算模式為選擇-計(jì)算,每輪計(jì)算依賴于上一輪的計(jì)算結(jié)果,串行的執(zhí)行選擇、加載、計(jì)算操作將會(huì)浪費(fèi)大量CPU 時(shí)間。第三,基于點(diǎn)集的數(shù)據(jù)塊的優(yōu)先級(jí)選擇會(huì)造成圖計(jì)算的負(fù)載不均衡?？紤]到優(yōu)先選擇的計(jì)算量,不論P(yáng)rIter 還是基于BCD 的優(yōu)先選擇策略都是基于均分點(diǎn)集進(jìn)行計(jì)算、選擇的,圖數(shù)據(jù)的偏斜性平均分割的點(diǎn)集極易造成負(fù)載的不均衡。

3 系統(tǒng)架構(gòu)

為了解決上述問(wèn)題,本文提出了基于最優(yōu)化方法的外存圖計(jì)算系統(tǒng)BCDG。本節(jié)將介紹系統(tǒng)架構(gòu)以及BCDG 的工作流程。

如圖1 所示,本系統(tǒng)由圖存儲(chǔ)單元、選擇單元、計(jì)算單元和加載單元組成。對(duì)于輸入圖,圖存儲(chǔ)單元分別將按源點(diǎn)和目的點(diǎn)排序的圖數(shù)據(jù)分別存儲(chǔ)為壓縮稀疏行(compressedsparserow,CSR)和壓縮稀疏列(compressed sparse column,CSC)結(jié)構(gòu),其中頂點(diǎn)偏移量數(shù)組存儲(chǔ)在內(nèi)存中,邊集列表存儲(chǔ)在固態(tài)硬盤(pán)(solid state disk,SSD)中。該單元在邏輯上將邊集列表維護(hù)為數(shù)個(gè)分片(無(wú)數(shù)據(jù)拷貝),其中每個(gè)分片指示等量的邊數(shù)據(jù)。選擇單元使用優(yōu)先選擇策略中定義的優(yōu)先級(jí)為塊維護(hù)一個(gè)優(yōu)先級(jí)隊(duì)列。該單元計(jì)算出前τ個(gè)運(yùn)算必要的塊和需要預(yù)取的塊。加載單元作為守護(hù)進(jìn)程維護(hù)一個(gè)加載隊(duì)列和一個(gè)預(yù)取隊(duì)列,根據(jù)選擇單元從SSD 上的圖存儲(chǔ)單元加載運(yùn)算必要的邊數(shù)據(jù)和預(yù)取的邊數(shù)據(jù)。計(jì)算單元維護(hù)圖算法的計(jì)算邊緣(frontier),其中包含選中的前τ個(gè)塊和相應(yīng)的頂點(diǎn)。該單元為在使用push/pull 模式[4]的定制圖算法提供接口。

圖1 系統(tǒng)架構(gòu)

在BCDG 中運(yùn)行迭代圖算法時(shí),首先將頂點(diǎn)集分為β個(gè)塊,每個(gè)塊在內(nèi)存中以若干分片的形式維護(hù),每個(gè)分片中包含相等數(shù)量的邊。每次迭代中,選擇單元選擇優(yōu)先級(jí)最高的2τ個(gè)塊。其步驟如下:(1)選擇單元告知加載單元要加載的τ個(gè)塊和預(yù)取的τ個(gè)塊,加載單元從內(nèi)存中的圖存儲(chǔ)單元獲取這些塊的元數(shù)據(jù);(2)加載單元作為協(xié)程從SSD 中加載相應(yīng)的邊數(shù)據(jù);(3)計(jì)算單元從加載單元讀取邊數(shù)據(jù),并從圖存儲(chǔ)單元獲取相應(yīng)的數(shù)據(jù)分片信息,然后在塊上并行運(yùn)行用戶定義的push/pull 操作;(4)一輪迭代結(jié)束時(shí)計(jì)算單元重新計(jì)算每個(gè)塊的優(yōu)先級(jí),并通知選擇單元更新塊的優(yōu)先級(jí)隊(duì)列。其中,只有步驟(2)包含外存的讀操作,而其他的都是原地計(jì)算。

4 優(yōu)先選擇策略

將圖計(jì)算問(wèn)題轉(zhuǎn)化為最優(yōu)化問(wèn)題并使用最優(yōu)化問(wèn)題的解決方法是目前最直觀且有效的方案。沿用GraphABCD[21]中的思路,使用塊坐標(biāo)下降方法解決圖計(jì)算的最優(yōu)化問(wèn)題。本節(jié)首先介紹將圖計(jì)算任務(wù)轉(zhuǎn)化為最優(yōu)化問(wèn)題的方法,再探討基于最優(yōu)化選擇的塊的重用距離,最后介紹根據(jù)此設(shè)計(jì)BCDG 的優(yōu)先選擇策略。

4.1 最優(yōu)化圖計(jì)算任務(wù)

最優(yōu)化問(wèn)題可以被描述為找到能夠使得目標(biāo)函數(shù)F(x) 最小化的向量x∈Rn。用于解決最優(yōu)化問(wèn)題的BCD 算法已經(jīng)被充分研究[21]。在BCD 中,x被分解為β個(gè)等長(zhǎng)塊x1,x2,…,xβ;記第k輪計(jì)算中的向量x為xk=。在第k輪迭代中,除了被選定的塊xki外,其余所有塊的值都是固定的。更新過(guò)程為其中為步長(zhǎng),為下降方向。

本文中,使用G={V,E} 表示輸入圖;V、E分別為點(diǎn)集和邊集;vi表示第i個(gè)點(diǎn);eij表示從點(diǎn)vi到點(diǎn)vj的邊;分別表示點(diǎn)vi的出度和入度;A表示鄰接矩陣;分別表示點(diǎn)vi的出鄰居集和入鄰居集。

下面將圖計(jì)算任務(wù)中的一個(gè)經(jīng)典任務(wù)PageRank 轉(zhuǎn)化為最優(yōu)化問(wèn)題,并介紹如何應(yīng)用BCD 求解。PageRank 的更新公式為xk+1=Pxk +b,其中P=α(D-1A)T,b=(1-α)/ | V|,D為由每個(gè)點(diǎn)的出度構(gòu)成的對(duì)角陣,α為PageRank 的阻尼系數(shù)。當(dāng)PageRank 收斂時(shí),記最終結(jié)果為x*,那么有x*=Px*+b。由此構(gòu)建PageRank 收斂的最優(yōu)化問(wèn)題的目標(biāo)函數(shù),其L-2 正則形式為+b-x*)2選擇的下降方向d為目標(biāo)函數(shù)的梯度。

至此,將PageRank 轉(zhuǎn)化為了使用BCD 解決的最優(yōu)化問(wèn)題。關(guān)于圖算法的轉(zhuǎn)化以及塊選擇方法的選擇在現(xiàn)有的工作中有詳盡的討論[19-21],包括弱連通分量、最短路徑和協(xié)同過(guò)濾等。

BCD 算法給定3 個(gè)可配置參數(shù),塊大小σ、塊選擇方法和塊更新方法。塊大小表示被分配到一個(gè)塊中的點(diǎn)數(shù),取值范圍為1 ≤σ≤| V|。塊選擇方法可以是預(yù)定義的固定順序或者是目標(biāo)函數(shù)的梯度方向。塊更新方法指定圖算法使用的迭代更新函數(shù)。若以梯度下降方法為塊選擇方法,BCD 中的坐標(biāo)下降方向沿著目標(biāo)函數(shù)的梯度方向。以上述PageRank為例,式(1)計(jì)算每個(gè)點(diǎn)的梯度下降方向,式(2)表示每次迭代的更新函數(shù)。坐標(biāo)下降方向表示給定圖的哪些部分對(duì)算法的收斂最“有價(jià)值”,也即能夠讓目標(biāo)函數(shù)最速下降的方向。

4.2 調(diào)度策略

基于4.1 節(jié)描述的方法,實(shí)現(xiàn)了基于BCD 的PageRank 算法,并在LiveJournal(LJ)和Twitter-2010(TW)數(shù)據(jù)集上進(jìn)行了測(cè)試。對(duì)于任意BCD 迭代輪次k,塊選擇方法產(chǎn)生的優(yōu)先塊順序?yàn)槠渲笑聻榭倝K數(shù),塊的優(yōu)先級(jí)大于塊的優(yōu)先級(jí),那么在第k輪中塊被選中。

定義事件A:塊在第(k+i-1) 輪中被選中,即。考察事件A的頻率,結(jié)果如圖2 所示,左右圖分別為L(zhǎng)J 和TW 數(shù)據(jù)集,每條曲線表示不同的測(cè)試塊大小,水平和垂直的虛線表示每次塊選擇方法產(chǎn)生的優(yōu)先序列中的前τ個(gè)塊與接下來(lái)τ輪中被選中的塊一致的頻率超過(guò)90%。由此可以得到,每輪的塊選擇方法可以預(yù)測(cè)接下來(lái)若干輪的選擇結(jié)果。

圖2 事件A 發(fā)生頻率(歸一化)

據(jù)此,設(shè)計(jì)BCDG 的調(diào)度策略為一次選擇多輪優(yōu)先。在BCDG 中,為了區(qū)分與BSP 模型中圖計(jì)算算法迭代輪次的概念,稱從一次選擇開(kāi)始到下一次選擇開(kāi)始前為一個(gè)超步(superstep)。記每個(gè)超步的塊選擇個(gè)數(shù)為τ。在每個(gè)超步開(kāi)始時(shí),執(zhí)行塊選擇方法計(jì)算數(shù)據(jù)塊的優(yōu)先級(jí),選擇優(yōu)先級(jí)最大的前τ個(gè)塊加載、計(jì)算,如圖3 中的①所示。那么相較于原始的BCD 算法,BCDG 節(jié)省了τ-1 次計(jì)算塊選擇方法的時(shí)間,并且能夠?qū)⒓虞d與計(jì)算重疊起來(lái)。而考慮到不能精確地預(yù)測(cè),τ越大會(huì)出現(xiàn)越多的冗余計(jì)算,并且影響收斂效率。根據(jù)圖2 的結(jié)果,推薦選取能夠保障預(yù)測(cè)準(zhǔn)確率90%的τ=5～10。

預(yù)取策略。圖3 為調(diào)度和預(yù)取流水線示意圖,t2 時(shí)刻前后分別表示超步1 和超步2。由于加載隊(duì)列的任務(wù)是根據(jù)選擇的結(jié)果派發(fā),當(dāng)計(jì)算超步中最后一個(gè)塊以及計(jì)算塊選擇方法時(shí),加載線程必定為空閑,如圖3①中的時(shí)刻t1～t3。為了更好地重疊加載與計(jì)算,并且進(jìn)一步利用SSD 的讀帶寬,引入預(yù)取機(jī)制,即在計(jì)算過(guò)程中,當(dāng)加載任務(wù)隊(duì)列中本輪的τ個(gè)塊加載任務(wù)完成時(shí),繼續(xù)從中加載。圖3②中時(shí)刻t1～t3繼續(xù)加載塊優(yōu)先列表中的內(nèi)容,以期在下一個(gè)超步中可以命中選擇的塊。算法1 展示在t3時(shí)刻(第4 行)主線程收到第k +1 的優(yōu)先選擇結(jié)果,如果加載隊(duì)列中的任務(wù)尚未完成,則需要分情況處理:如果正在加載的塊不在超步2 的選擇列表中(第7 行),則立即停止加載,并將選擇列表中的尚未被加載的塊加入加載隊(duì)列(第9 行);否則,如果選擇列表中存在尚未被加載、且優(yōu)先級(jí)高于當(dāng)前塊的塊(第13 行),就停止當(dāng)前加載,并將這些塊加入加載隊(duì)列(第15 行),如果不存在,則繼續(xù)當(dāng)前加載。另外,如果加載過(guò)程中(包括預(yù)取階段)內(nèi)存不足,則將已經(jīng)計(jì)算完畢且不在加載隊(duì)列中的塊汰換出內(nèi)存。

圖3 調(diào)度和預(yù)取流水線(①未使用預(yù)?、谑褂妙A(yù)取)

5 圖數(shù)據(jù)的劃分與計(jì)算

本節(jié)介紹BCDG 的計(jì)算調(diào)度分離的劃分策略與其相應(yīng)的計(jì)算模式。根據(jù)第2.2 節(jié)的分析,在BCD算法中,數(shù)據(jù)塊的大小對(duì)于性能的影響很大。更大的塊有利于計(jì)算局部性和點(diǎn)間的計(jì)算并行性,但是犧牲了收斂速度;更小的塊整體收斂輪次減少,但是計(jì)算性能會(huì)降低。在第4 節(jié)中介紹了BCDG 的調(diào)度策略,基于BCD 算法對(duì)圖數(shù)據(jù)根據(jù)點(diǎn)集進(jìn)行了劃分,每個(gè)數(shù)據(jù)塊包含的點(diǎn)數(shù)一致。在圖計(jì)算任務(wù)中,由于圖數(shù)據(jù)的偏斜性,為了負(fù)載均衡,往往需要均衡每個(gè)數(shù)據(jù)塊的邊數(shù)量而非點(diǎn)數(shù)。因此,BCDG 首先針對(duì)圖的邊數(shù)據(jù)構(gòu)建等寬的分片(chunk),然后以分片為最小運(yùn)算單元進(jìn)行計(jì)算和調(diào)度。

5.1 圖數(shù)據(jù)的分片

對(duì)于給定圖G(V,E),G的原始?jí)嚎s稀疏列結(jié)構(gòu)如圖4(a)所示;圖4(b)展示了在原始的CSC 數(shù)組上的劃分策略,左側(cè)每行表示一個(gè)分片,不同的灰度表示不同點(diǎn)的鄰居,右側(cè)為分片的數(shù)據(jù)結(jié)構(gòu)。BCDG 中,假設(shè)圖計(jì)算中每條邊上需要的計(jì)算資源是等價(jià)的。為了平衡計(jì)算負(fù)載,BCDG 將邊集列表切分為包含同等數(shù)量邊的若干部分,每個(gè)部分為一個(gè)分片。每個(gè)分片則為整體圖計(jì)算的最小運(yùn)算單元,針對(duì)每個(gè)分片的計(jì)算是通過(guò)單線程串行執(zhí)行的。

圖4 圖劃分策略與數(shù)據(jù)塊調(diào)度

然而,如此切分會(huì)在面對(duì)相同目標(biāo)點(diǎn)的時(shí)候引入寫(xiě)沖突,如圖4(b)所示,分片分界線將處在分片邊界的目標(biāo)點(diǎn)的鄰居劃分到了不同分片。為了解決寫(xiě)沖突的問(wèn)題,引入實(shí)虛點(diǎn)機(jī)制。在每個(gè)分片中,若一點(diǎn)的鄰居列表中的最后一個(gè)點(diǎn)屬于本分片,那么稱此點(diǎn)為實(shí)點(diǎn),反之稱之為虛點(diǎn)。分別稱實(shí)點(diǎn)、虛點(diǎn)對(duì)應(yīng)的邊集為實(shí)部、虛部。那么一個(gè)分片Ci的邏輯構(gòu)成如下:

其中se表示起始邊,rs、re分別表示實(shí)部中的起始和終止點(diǎn),vv、ve分別表示虛部中的虛點(diǎn)和其在虛部中的終止邊。注意,一個(gè)分片中的虛部只包含一個(gè)虛點(diǎn)。BCDG 維護(hù)分片的集合C。BCDG 維護(hù)了每個(gè)虛點(diǎn)和其對(duì)應(yīng)的實(shí)點(diǎn)的映射:

那么,在一輪迭代計(jì)算中,BCDG 首先將每個(gè)虛點(diǎn)添加至計(jì)算邊緣中,并對(duì)虛點(diǎn)進(jìn)行等價(jià)實(shí)點(diǎn)的計(jì)算、更新操作;在此輪計(jì)算結(jié)束前,將每個(gè)虛點(diǎn)的更新至合并到對(duì)應(yīng)的實(shí)點(diǎn)結(jié)果中。

算法2 描述了基于分片的最小運(yùn)算單元計(jì)算流程CalChunk。其中第1～2 行從輸入圖中讀入CSC結(jié)構(gòu)圖數(shù)據(jù),包含偏移量數(shù)組和數(shù)據(jù)數(shù)組(圖4(a))。它串行計(jì)算了單個(gè)分片的實(shí)部和虛部,并分別更新了對(duì)應(yīng)的計(jì)算邊緣(frontier)值。函數(shù)Comp的輸入值為每條邊的源點(diǎn)和目標(biāo)點(diǎn),用于執(zhí)行在每條邊上的計(jì)算。函數(shù)Filter 作為計(jì)算中的可選項(xiàng),其作用為自定義過(guò)濾計(jì)算時(shí)的不必要計(jì)算的點(diǎn)或邊。并行計(jì)算時(shí),首先將虛點(diǎn)擴(kuò)展至計(jì)算邊緣,然后每輪迭代中利用CalChunk 并行計(jì)算每個(gè)分塊的內(nèi)容,利用用戶定義的Reduce 函數(shù)在上RV計(jì)算,將虛點(diǎn)的結(jié)果合并至其對(duì)應(yīng)的實(shí)點(diǎn)結(jié)果中,并更新計(jì)算邊緣,重復(fù)此過(guò)程直至收斂。

5.2 基于分片的塊計(jì)算

為了應(yīng)用BCD 算法于圖計(jì)算,BCDG 以分片作為粒度將給定的圖劃分為若干個(gè)塊,然后按照分片運(yùn)行基于BCD 的圖算法。圖4(c)展示了圖劃分的設(shè)計(jì)。對(duì)于BCD 視角,點(diǎn)集被分割為β個(gè)片段,其中β由BCD 算法的塊大小確定。據(jù)此,給定圖被劃分為β個(gè)子圖。一個(gè)點(diǎn)集片段和其對(duì)應(yīng)的邊集構(gòu)成子圖,其中1 ≤i≤β。以分片作為計(jì)算粒度,因此子圖Bi由分片集合CBi構(gòu)成,其包含所有中的邊。滿足下述條件:其中Vc表示分片c中的點(diǎn)集,包括真實(shí)點(diǎn)和其對(duì)應(yīng)的虛擬點(diǎn);Ec表示分片c中的邊集。在BCD 計(jì)算中,BCDG 依據(jù)塊選擇方法在初始迭代輪次選擇τ個(gè)塊,其中1 ≤τ≤s。圖計(jì)算的計(jì)算邊緣由這些被選中的塊中的點(diǎn)集構(gòu)成。然后,BCDG 以分片作為粒度依次遍歷被選中的子圖中的所有邊。

算法3 描述了基于分片的塊計(jì)算流程。其中第1～2 行為BCD 算法中的特殊過(guò)濾器BlockFilter 函數(shù),其消除了不屬于被選中塊的真實(shí)點(diǎn)以及其對(duì)應(yīng)的虛擬點(diǎn)。第3 行初始化計(jì)算邊緣,并將虛擬點(diǎn)擴(kuò)展至計(jì)算邊緣。第4～12 行為迭代計(jì)算過(guò)程,重復(fù)計(jì)算直到收斂。第5 行使用SelectBlock 函數(shù)選擇一個(gè)或多個(gè)塊。第7～8 行并行計(jì)算分片。第9～10行將所有虛擬點(diǎn)的結(jié)果合并至其對(duì)應(yīng)的真實(shí)點(diǎn)結(jié)果中。當(dāng)所有優(yōu)先塊計(jì)算完畢后,第11 行擴(kuò)展計(jì)算邊緣。

6 實(shí)驗(yàn)

6.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境:單臺(tái)計(jì)算節(jié)點(diǎn),CPU 為Intel(R) Xeon(R) E5-2640 v4 CPU(雙節(jié)點(diǎn);40 個(gè)超線程),128 GB內(nèi)存,1 塊477 GB 的SSD(讀寫(xiě)帶寬分別為3.0 GB/s 和2.7 GB/s)。

基線:GridGraph[8]是外存圖處理系統(tǒng)的一個(gè)強(qiáng)有力的基線。Lumos[3]是基于GridGraph 實(shí)現(xiàn)的框架,其提供了對(duì)十億級(jí)圖處理的同步執(zhí)行框架。由于實(shí)驗(yàn)環(huán)境中的計(jì)算單元是CPU,所以本文復(fù)現(xiàn)了GraphABCD 的CPU 版本作為基線。在第6.2 節(jié)中對(duì)比了GraphABCD 文中的基線GraphMat[22],結(jié)果見(jiàn)表1,可以看出復(fù)現(xiàn)的結(jié)果與文中報(bào)告的性能提升一致,因此可以以此來(lái)作為基線。

表1 BCDG 與基線的運(yùn)行時(shí)間(s)對(duì)比

數(shù)據(jù)集:使用4 個(gè)真實(shí)世界的圖數(shù)據(jù)和1 個(gè)合成圖數(shù)據(jù),如表2 所示,其中Pokec[23](PO)、Live-Journal[24](LJ)和Twitter-2010[25](TW)為社交網(wǎng)絡(luò)圖,Yahoo[26](YH)為網(wǎng)頁(yè)鏈接圖,RMat27[27](RM)為使用冪律分布合成的圖數(shù)據(jù)。文件大小為二進(jìn)制邊集文件大小,圖計(jì)算系統(tǒng)一般存儲(chǔ)CSC、CSR結(jié)構(gòu)各一份,與二進(jìn)制邊集文件大小相近。

表2 實(shí)驗(yàn)中使用的數(shù)據(jù)集

6.2 與現(xiàn)有工作比較

將BCDG 與GridGraph(GG)、Lumos(LU)和復(fù)現(xiàn)的GraphABCD(GA*)以及其基線GraphMat(GM)進(jìn)行對(duì)比,在表2 中的數(shù)據(jù)集上測(cè)試了PageRank 應(yīng)用直到收斂于相同的條件。每次測(cè)試均使用全部40 個(gè)超線程,運(yùn)行10 次取平均結(jié)果。表1 報(bào)告了測(cè)試的結(jié)果,“-”表示超內(nèi)存,“/”表示無(wú)法運(yùn)行。其中復(fù)現(xiàn)的GraphABCD 和GraphMat 在純內(nèi)存中運(yùn)行,BCDG 與GridGraph、Lumos 運(yùn)行中均使用了SSD。對(duì)于外存測(cè)試,使用了cgroup 限制程序運(yùn)行內(nèi)存。在所有數(shù)據(jù)集上,BCDG 的性能均優(yōu)于其他系統(tǒng)。

對(duì)比GraphABCD。首先,復(fù)現(xiàn)的GraphABCD 相較于GraphMat 性能平均提升2.46 倍,與其報(bào)告的2.1～2.5 倍一致。除了在Yahoo 數(shù)據(jù)集上,由于內(nèi)存不足復(fù)現(xiàn)的GraphABCD 無(wú)法完成,在其余數(shù)據(jù)集上,相較于復(fù)現(xiàn)的GraphABCD,BCDG 性能平均提升了3.86 倍(PageRank)和2.61 倍(CC)。由于BCDG 的調(diào)度策略為選擇更多的數(shù)據(jù)塊而非一個(gè),所以相比于GraphABCD,每輪計(jì)算重新選擇塊提升了計(jì)算性能。

對(duì)比GridGraph 和Lumos。在不限制內(nèi)存的情況下,BCDG 相比GridGraph 性能平均提升了10.30 倍(PageRank)和3.61 倍(CC),相比Lumos 提升了平均8.72 倍(PageRank)。由于GridGraph 在每輪迭代中需要加載全量數(shù)據(jù),并且每個(gè)數(shù)據(jù)塊在每輪計(jì)算中只計(jì)算一次,外存I/O 時(shí)間為主要開(kāi)銷。雖然Lumos 中使用了異步的計(jì)算邏輯,但是其載入的每個(gè)數(shù)據(jù)塊只計(jì)算2 次,在一定程度上緩解了加載開(kāi)銷,但這仍然是瓶頸。BCDG 相比于GridGraph 的提升主要體現(xiàn)在兩方面,一方面優(yōu)先加載策略節(jié)省了計(jì)算中的外存加載總量,從而節(jié)省了外存開(kāi)銷;另一方面基于分片的劃分方式更加均衡了計(jì)算負(fù)載。

表3 報(bào)告了限制內(nèi)存時(shí),BCDG 與GridGraph、Lumos 在數(shù)據(jù)集LJ 和TW 上運(yùn)行PageRank 的時(shí)間對(duì)比,第1 列和第4 列表示在LJ 和TW 上限制內(nèi)存的大小,單位為字節(jié),“-”表示不限制內(nèi)存,“/”表示無(wú)法運(yùn)行。當(dāng)限制內(nèi)存時(shí),GridGraph 和Lumos 的性能沒(méi)有明顯變化。BCDG 性能損失較大,因?yàn)閮?nèi)存較小時(shí),BCDG 會(huì)選擇更小的BCD 塊放入內(nèi)存中計(jì)算;另外,內(nèi)存較小時(shí)預(yù)取策略幾乎失效。但當(dāng)限制更小的內(nèi)存上限時(shí),只有BCDG 能夠正常運(yùn)行,這是因?yàn)锽CDG 的分片策略使得調(diào)度計(jì)算能夠以分片作為最小粒度,其相對(duì)于GridGraph 的二維劃分而言粒度更細(xì)。當(dāng)內(nèi)存充足時(shí),BCDG 的預(yù)取策略可以有更大的空間存儲(chǔ)對(duì)下一個(gè)超步計(jì)算的數(shù)據(jù)塊的預(yù)測(cè)。

表3 限制內(nèi)存時(shí)運(yùn)行時(shí)間(s)對(duì)比

6.3 調(diào)度策略

圖5 描述了BCD 算法中選擇不同的BCD 塊數(shù)時(shí),塊選擇個(gè)數(shù)τ對(duì)于收斂時(shí)間的影響,左右圖分別為數(shù)據(jù)集LJ 和TW 上的結(jié)果,圖中橫軸為選擇塊的個(gè)數(shù)τ,每條曲線表示總BCD 塊數(shù)。注意,塊大小σ與BCD 塊數(shù)的積約等于圖的點(diǎn)數(shù)。從圖中可得,在2 個(gè)數(shù)據(jù)集上,每種塊大小的選擇下,相比于原始BCD 算法中只選擇一個(gè)塊,增加選擇塊數(shù)都可使收斂時(shí)間顯著減少。其原因?yàn)檫x擇多個(gè)塊使得加載和計(jì)算能夠重疊起來(lái),而其預(yù)測(cè)塊的性能損失遠(yuǎn)小于重疊帶來(lái)的性能提升。當(dāng)選擇塊數(shù)τ ＞5 時(shí),收斂時(shí)間的降低速度有所放緩。其原因?yàn)楫?dāng)選擇塊數(shù)增加到一定程度時(shí),流水線重疊趨于穩(wěn)定,選擇更多的塊不會(huì)更顯著地降低CPU 等待時(shí)間。當(dāng)選擇塊數(shù)τ＞10 時(shí),收斂時(shí)間普遍出現(xiàn)波動(dòng)。其原因?yàn)檫x擇更多的塊意味著預(yù)測(cè)正確率下降,所以出現(xiàn)了較多的冗余計(jì)算。根據(jù)實(shí)驗(yàn)結(jié)果,推薦選取能夠保障預(yù)測(cè)準(zhǔn)確率90%的塊選擇數(shù)τ為5～10。

圖5 不同BCD 數(shù)據(jù)塊大小下PageRank 收斂時(shí)間統(tǒng)計(jì)

6.4 預(yù)取策略

圖6描述了當(dāng)選擇塊數(shù)為5時(shí),預(yù)取的塊數(shù)對(duì)運(yùn)行時(shí)間與消耗內(nèi)存的影響,左右圖分別為數(shù)據(jù)集LJ 和TW 上的結(jié)果,橫軸表示預(yù)取的塊數(shù),左縱軸表示內(nèi)存消耗,右縱軸表示歸一化的運(yùn)行時(shí)間。其中測(cè)試應(yīng)用為PageRank,運(yùn)行時(shí)間按照關(guān)閉預(yù)取策略的對(duì)照組(預(yù)取塊數(shù)為0)進(jìn)行歸一化。從圖中得出結(jié)論:預(yù)取更多的塊幾乎不會(huì)造成更多的內(nèi)存消耗,但是卻可以顯著降低整體的運(yùn)行時(shí)間,當(dāng)預(yù)取塊數(shù)與選擇塊數(shù)一致時(shí),運(yùn)行時(shí)間總體降低10%。這得益于預(yù)取策略能夠更好地利用加載線程,消除其在圖3中t1～t3時(shí)間內(nèi)的空閑。

圖6 預(yù)取塊數(shù)對(duì)運(yùn)行時(shí)間和消耗內(nèi)存的影響

6.5 運(yùn)行時(shí)間分析

圖7 描述了BCDG 的運(yùn)行時(shí)間分析。其中測(cè)試應(yīng)用為PageRank,圖7 給出了不同數(shù)據(jù)集在不限制內(nèi)存和限制內(nèi)存情況下的運(yùn)行時(shí)間分析,在數(shù)據(jù)集PO、LJ、TW 和RM 上的內(nèi)存限制分別為256 MB、512 MB、4 GB 和6 GB,運(yùn)行時(shí)間按照每個(gè)例子的總運(yùn)行時(shí)間進(jìn)行歸一化。從圖中可以得出,相比于GridGraph 中外存I/O 占總計(jì)算時(shí)間的70%～80%、占Lumos 的50%～60%[3],BCDG 從外存讀入的時(shí)間在總計(jì)算時(shí)間的占比僅為10%～30%。限制內(nèi)存時(shí),BCDG 的性能一方面受到BCD 選塊大小的影響,另一方面也需要消耗更多的時(shí)間在加載數(shù)據(jù)上。這是因?yàn)轭A(yù)取策略受到內(nèi)存限制,優(yōu)化性能有限。另外也說(shuō)明了相比于其他外存圖計(jì)算系統(tǒng),BCDG 能夠更加高效地利用內(nèi)存減少外存I/O。

圖7 不同數(shù)據(jù)集上運(yùn)行PageRank 的運(yùn)行時(shí)間分析

7 結(jié)論

本文針對(duì)外存圖計(jì)算系統(tǒng)存在的計(jì)算冗余問(wèn)題以及外存I/O 瓶頸,在基于優(yōu)先選擇的外存異步圖計(jì)算系統(tǒng)上作了深入研究。計(jì)算數(shù)據(jù)塊優(yōu)先級(jí)本身引入的性能開(kāi)銷不可忽略,并且優(yōu)先選擇策略會(huì)破壞加載計(jì)算的流水線以及會(huì)引入計(jì)算的負(fù)載不均衡。為此本文提出了基于塊坐標(biāo)下降法的外存異步圖計(jì)算系統(tǒng)。首先,觀察并驗(yàn)證可得,BCD 算法在每輪中賦予每個(gè)數(shù)據(jù)塊的優(yōu)先級(jí)能夠預(yù)測(cè)后續(xù)輪次的選擇,由此設(shè)計(jì)了一次選擇多輪優(yōu)先調(diào)度策略;其次,繼續(xù)利用此性質(zhì)設(shè)計(jì)了預(yù)取策略,并構(gòu)建加載計(jì)算流水線;最后,發(fā)現(xiàn)面向計(jì)算的按邊劃分策略不影響按點(diǎn)調(diào)度,因此設(shè)計(jì)了計(jì)算調(diào)度分離的劃分策略,同時(shí)實(shí)現(xiàn)了計(jì)算的負(fù)載均衡和優(yōu)先調(diào)度。實(shí)驗(yàn)結(jié)果表明,相比于目前最先進(jìn)的外存圖計(jì)算系統(tǒng)Grid-Graph 和Lumos,BCOG 平均性能分別提升10.30 倍與8.72倍。整體計(jì)算過(guò)程中,CPU 等待外存I/O 的時(shí)間僅占10%～30%。本文更多關(guān)注基于推拉計(jì)算模型中的拉操作,后續(xù)工作將對(duì)推操作進(jìn)一步探索。