摘要：圖計算平臺的性能優(yōu)化與并行計算策略仍面臨諸多挑戰(zhàn)。對圖計算平臺的性能優(yōu)化與并行計算策略進行了綜述與分析。首先，分析了圖計算平臺的特點及其面臨的性能瓶頸；其次，總結(jié)了常見的數(shù)據(jù)分割策略、任務(wù)調(diào)度策略以及并行計算框架，對比分析了它們的優(yōu)缺點；再次，探討了圖數(shù)據(jù)存儲壓縮、緩存機制、數(shù)據(jù)預(yù)取與延遲加載等優(yōu)化技術(shù)；最后，指出了圖計算領(lǐng)域的研究趨勢和有待進一步探索的方向。

關(guān)鍵詞：圖計算性能優(yōu)化并行計算數(shù)據(jù)分割任務(wù)調(diào)度

中圖分類號：TP391

ResearchonPerformanceOptimizationandParallelComputingStrategiesofGraphComputingPlatform

WANGYannan

AntGroup，BeijingCity，100020China

Abstract：Theperformanceoptimizationandparallelcomputing strategiesofGraphComputingplatformstillfacemanychallenges.ThisarticleprovidesanoverviewandanalysisofperformanceoptimizationandparallelcomputingstrategiesforGraphComputingplatform.Firstly，thecharacteristicsofGraphComputingplatformandtheperformancebottleneckstheyfaceareanalyzed;Secondly，commondatasegmentationstrategies，taskschedulingstrategies，andparallelcomputingframeworksaresummarized，andtheiradvantagesanddisadvantagesarecomparedandanalyzed;Then，optimizationtechniquessuchasgraphdatastoragecompression，cachingmechanism，dataprefetchinganddelayedloadingareexplored;Finally，theresearchtrendsanddirectionsforfurtherexplorationinthefieldofgraphcomputingarepointedout.

KeyWords：GraphComputing;Performanceoptimization;Parallelcomputing;Datasegmentation;Taskscheduling

圖計算是一種針對圖結(jié)構(gòu)數(shù)據(jù)進行分析和處理的計算范式，廣泛應(yīng)用于社交網(wǎng)絡(luò)分析、推薦系統(tǒng)、金融風(fēng)控等領(lǐng)域。隨著圖數(shù)據(jù)規(guī)模的不斷增長，圖計算平臺的性能優(yōu)化與并行計算策略面臨著諸多挑戰(zhàn)。本文將從多個角度對圖計算平臺的性能優(yōu)化與并行計算策略進行綜述，以期為相關(guān)研究提供參考。

1圖計算平臺的特點及性能瓶頸分析

1.1圖計算平臺的特點

圖計算平臺是專門針對圖結(jié)構(gòu)數(shù)據(jù)進行存儲、處理和分析的計算系統(tǒng)。與傳統(tǒng)數(shù)據(jù)庫和大數(shù)據(jù)平臺不同，圖計算平臺充分考慮了圖數(shù)據(jù)的特點，如節(jié)點關(guān)聯(lián)性、數(shù)據(jù)稀疏性和分布不均等，采用屬性圖模型表示數(shù)據(jù)，支持靈活的圖查詢和遍歷操作。同時提供了豐富的圖算法庫，如PageRank、社區(qū)發(fā)現(xiàn)、最短路徑等，方便用戶進行復(fù)雜圖分析。圖計算平臺具有良好的可擴展性和容錯性，能處理大規(guī)模圖數(shù)據(jù)，并在分布式環(huán)境下高效計算。一些著名圖計算平臺如ApacheGiraph、GraphX和Neo4j等，已在社交網(wǎng)絡(luò)、金融風(fēng)控、推薦系統(tǒng)等領(lǐng)域得到成功應(yīng)用[1]。

1.2圖計算平臺面臨的性能瓶頸

圖計算平臺在處理圖數(shù)據(jù)方面具有獨特優(yōu)勢，但實際應(yīng)用仍面臨諸多性能瓶頸。圖數(shù)據(jù)高度稀疏和分布不均給負(fù)載均衡和任務(wù)調(diào)度帶來挑戰(zhàn)。圖數(shù)據(jù)通常呈冪律分布，少數(shù)節(jié)點有大量邊，多數(shù)節(jié)點邊很少，導(dǎo)致計算任務(wù)分配不均，出現(xiàn)“數(shù)據(jù)傾斜”，影響整體性能。圖計算涉及大量隨機訪問和數(shù)據(jù)傳輸，對內(nèi)存和I/O帶寬要求高[2]。傳統(tǒng)數(shù)據(jù)存儲和訪問方式難以適應(yīng)圖計算特點，易產(chǎn)生大量內(nèi)存開銷和數(shù)據(jù)傳輸延遲。同時，圖算法的迭代特性帶來了挑戰(zhàn)。許多圖算法需多輪迭代收斂，每輪迭代需大量數(shù)據(jù)交換和同步，導(dǎo)致計算效率降低。

2基于數(shù)據(jù)分割和任務(wù)調(diào)度的并行計算策略

2.1數(shù)據(jù)分割策略

數(shù)據(jù)分割是克服圖計算性能瓶頸的關(guān)鍵優(yōu)化策略。合理的數(shù)據(jù)分割可減少數(shù)據(jù)傳輸開銷，提高并行度，實現(xiàn)負(fù)載均衡。常見數(shù)據(jù)分割策略有邊切分、點切分和混合切分。邊切分將圖的邊均勻分配到不同計算節(jié)點，每個節(jié)點只存儲相關(guān)邊和頂點信息，減少節(jié)點間數(shù)據(jù)依賴，提高并行度。點切分將圖的頂點分配到不同節(jié)點，每個節(jié)點存儲分配的頂點及相關(guān)邊信息，減少邊的重復(fù)存儲，降低內(nèi)存開銷?；旌锨蟹纸Y(jié)合邊切分和點切分的優(yōu)點，根據(jù)圖特點動態(tài)調(diào)整分割策略。此外，考慮圖拓?fù)浣Y(jié)構(gòu)、節(jié)點度分布等因素的高級數(shù)據(jù)分割策略，可進一步優(yōu)化數(shù)據(jù)分布和負(fù)載均衡。表1比較了不同數(shù)據(jù)分割策略在LiveJournal數(shù)據(jù)集上的性能表現(xiàn)。

2.2任務(wù)調(diào)度策略

任務(wù)調(diào)度是并行計算的另一個重要組成部分。圖計算任務(wù)包含大量子任務(wù)，合理分配這些子任務(wù)至關(guān)重要。常見任務(wù)調(diào)度策略有靜態(tài)調(diào)度和動態(tài)調(diào)度。靜態(tài)調(diào)度在計算開始前根據(jù)預(yù)定義規(guī)則分配任務(wù)，如輪詢調(diào)度、哈希調(diào)度等，實現(xiàn)簡單，開銷小，但難以適應(yīng)動態(tài)負(fù)載變化[3]。動態(tài)調(diào)度在計算過程中根據(jù)節(jié)點實時負(fù)載動態(tài)分配任務(wù)，如工作竊取調(diào)度、優(yōu)先級調(diào)度等，實現(xiàn)更好的負(fù)載均衡，提高資源利用率，但調(diào)度開銷大。有針對圖計算特點設(shè)計的調(diào)度策略，如基于圖拓?fù)浣Y(jié)構(gòu)的調(diào)度、數(shù)據(jù)局部性感知調(diào)度等，通過考慮數(shù)據(jù)依賴關(guān)系和局部性原理優(yōu)化任務(wù)分配。表2展示不同任務(wù)調(diào)度策略在Twitter數(shù)據(jù)集上的性能表現(xiàn)。

2.3并行計算策略的實現(xiàn)

并行計算策略的實現(xiàn)涉及多個方面，包括編程模型、通信機制、同步策略等。圖計算平臺通常采用基于消息傳遞的并行編程模型，如Pregel的“ThinkLikeaVertex”模型和GraphLab的“Gather-Apply-Scatter”模型。這些模型通過定義頂點和邊的計算邏輯，實現(xiàn)圖算法的并行化。在通信機制方面，圖計算平臺利用消息傳遞接口（如MPI）實現(xiàn)節(jié)點間的數(shù)據(jù)交換和同步。常見的通信模式包括點對點通信、集合通信和全局同步等[4]。合理的通信模式減少了數(shù)據(jù)傳輸量，提高通信效率。同步策略決定了并行任務(wù)的協(xié)調(diào)和一致性維護方式。同步策略分為同步和異步兩種。同步策略在每個迭代步結(jié)束時進行全局同步，保證數(shù)據(jù)一致性，但同步開銷較大。異步策略允許部分任務(wù)的數(shù)據(jù)不一致，通過局部同步和容錯機制保證最終結(jié)果的正確性，獲得更高的并行效率。3并行計算框架對比分析

3.1編程模型

Pregel采用基于BSP的“思考像頂點”（ThinkLikeAVertex）編程模型。用戶只需定義頂點計算函數(shù)，并通過消息傳遞實現(xiàn)頂點間通信。這種模型簡單易用，但在處理非常稀疏的圖時，會產(chǎn)生大量中間消息，影響性能。GraphLab使用GAS（Gather-Apply-Scatter）模型。頂點可讀取鄰居狀態(tài)（Gather），更新自己狀態(tài)（Apply），并影響鄰居的狀態(tài)（Scatter）。GAS適合機器學(xué)習(xí)等需要異步計算的場景，但不適合同步算法。PowerGraph提出了GAS模型的增強版本——Vertex-Cut，可將高度頂點進行切分，減少通信開銷。PowerGraph還支持異步計算和增量計算，適應(yīng)性更強。

3.2通信機制

Pregel采用基于消息傳遞的同步通信。頂點給鄰居頂點發(fā)送消息，框架在每個超步結(jié)束時同步消息。這種方式實現(xiàn)簡單，但在處理數(shù)據(jù)傾斜時，性能會急劇下降。

GraphLab初始采用共享內(nèi)存通信，不同計算節(jié)點可以直接讀寫鄰居頂點狀態(tài)。但當(dāng)圖規(guī)模增大時，共享內(nèi)存通信會受到內(nèi)存帶寬的限制。后期GraphLab也支持混合的消息傳遞通信。PowerGraph在共享內(nèi)存通信的基礎(chǔ)上，提出了主動消息聚合（ActiveMessageCombining）技術(shù)。多個消息可以在發(fā)送前進行聚合，大幅減少了通信量，提高了計算效率。

4圖數(shù)據(jù)存儲和訪問優(yōu)化

4.1圖數(shù)據(jù)的壓縮存儲

圖數(shù)據(jù)高度稀疏，大部分節(jié)點度小，少數(shù)節(jié)點度大。圖數(shù)據(jù)壓縮存儲技術(shù)可減少存儲開銷，提高存儲效率。常見壓縮技術(shù)包括鄰接表壓縮、位圖壓縮和編碼壓縮。鄰接表壓縮對鄰接表重新編碼排序，位圖壓縮將鄰接表表示為二進制位圖，編碼壓縮利用圖的結(jié)構(gòu)特性重新編碼。壓縮技術(shù)顯著減小存儲空間，提高存儲密度，加速查詢和分析，減少I/O開銷。表3展示不同壓縮技術(shù)在WikiVote數(shù)據(jù)集上的壓縮效果。

從表3中可以看出，運用壓縮技術(shù)可以將圖數(shù)據(jù)的存儲空間減小50%以上。其中，編碼壓縮的壓縮比最高，達(dá)到了3.16。合理選擇壓縮技術(shù)可以在減小存儲空間的同時，保證圖數(shù)據(jù)的查詢和分析效率。

4.2圖數(shù)據(jù)的緩存機制

圖計算具有較強的數(shù)據(jù)訪問局部性，即計算任務(wù)在一段時間內(nèi)頻繁訪問一小部分圖數(shù)據(jù)。為了加速數(shù)據(jù)訪問，減少磁盤I/O，圖數(shù)據(jù)緩存機制被廣泛應(yīng)用。常見的緩存機制包括靜態(tài)緩存和動態(tài)緩存。靜態(tài)緩存在計算開始前將預(yù)選的圖數(shù)據(jù)子集加載到內(nèi)存，如度高的節(jié)點及其鄰居關(guān)系。動態(tài)緩存則根據(jù)實時的數(shù)據(jù)訪問模式動態(tài)調(diào)整緩存內(nèi)容，常用策略有LRU、LFU等。針對圖計算特點設(shè)計的緩存機制，如圖感知緩存和分布式緩存，通過考慮圖的拓?fù)浣Y(jié)構(gòu)和分布式環(huán)境特性，進一步優(yōu)化緩存性能。合理設(shè)計和使用緩存機制是提高圖數(shù)據(jù)訪問效率的關(guān)鍵。

4.3圖數(shù)據(jù)的預(yù)取和延遲加載

圖計算任務(wù)通常需要遍歷大部分節(jié)點和邊，存在大量隨機訪問操作。為減少訪問延遲，提高數(shù)據(jù)局部性，圖數(shù)據(jù)預(yù)取和延遲加載技術(shù)受到關(guān)注。預(yù)取技術(shù)根據(jù)圖的拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)訪問模式，提前將可能訪問的數(shù)據(jù)加載到內(nèi)存或緩存中。常見的預(yù)取策略包括鄰居預(yù)取、路徑預(yù)取和社區(qū)預(yù)取[5]。鄰居預(yù)取根據(jù)當(dāng)前訪問節(jié)點預(yù)取其鄰居數(shù)據(jù)，路徑預(yù)取沿遍歷路徑預(yù)取后續(xù)數(shù)據(jù)，社區(qū)預(yù)取在訪問社區(qū)內(nèi)節(jié)點時預(yù)取該社區(qū)其他數(shù)據(jù)。延遲加載則在實際需要時才加載數(shù)據(jù)，減少不必要的加載開銷和內(nèi)存占用。延遲加載與預(yù)取技術(shù)可結(jié)合使用，在保證數(shù)據(jù)及時性的同時減少內(nèi)存浪費，是優(yōu)化圖數(shù)據(jù)訪問的有效方法。

5結(jié)語

本文對圖計算平臺的性能優(yōu)化與并行計算策略進行了綜述。通過分析圖計算平臺的特點和性能瓶頸，對比總結(jié)了數(shù)據(jù)分割、任務(wù)調(diào)度、并行計算等關(guān)鍵技術(shù)，探討了圖數(shù)據(jù)存儲和訪問的優(yōu)化方法。展望未來，圖計算平臺的優(yōu)化還需要在自適應(yīng)并行化、異構(gòu)計算、領(lǐng)域特定優(yōu)化等方面進行持續(xù)探索，以支撐日益廣泛的大規(guī)模圖分析應(yīng)用。

參考文獻(xiàn)

[1]甘雨.面向云計算平臺的任務(wù)調(diào)度算法研究[D].武漢：武漢科技大學(xué)，2022.

• 潘靈.一種高性能嵌入式云計算平臺架構(gòu)[J].通信技術(shù)，2021，54（5）：1184-1188.

[3]朱光輝.分布式與自動化大數(shù)據(jù)智能分析算法與編程計算平臺[D].南京：南京大學(xué)，2020.

[4]張魯飛，孫茹君，秦芳.面向圖計算的運行時系統(tǒng)的消息聚合技術(shù)[J].計算機應(yīng)用，2021，41（4）：984-989.

[5]劉廣一，戴仁昶，路軼，等.電力圖計算平臺及其在能源互聯(lián)網(wǎng)中的應(yīng)用[J].電網(wǎng)技術(shù)，2021，45（6）：2051-2063.