圖計(jì)算平臺性能優(yōu)化與并行計(jì)算策略研究

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

關(guān)鍵詞：圖計(jì)算性能優(yōu)化并行計(jì)算數(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

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

1圖計(jì)算平臺的特點(diǎn)及性能瓶頸分析

1.1圖計(jì)算平臺的特點(diǎn)

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

1.2圖計(jì)算平臺面臨的性能瓶頸

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

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

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

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

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

任務(wù)調(diào)度是并行計(jì)算的另一個(gè)重要組成部分。圖計(jì)算任務(wù)包含大量子任務(wù)，合理分配這些子任務(wù)至關(guān)重要。常見任務(wù)調(diào)度策略有靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。靜態(tài)調(diào)度在計(jì)算開始前根據(jù)預(yù)定義規(guī)則分配任務(wù)，如輪詢調(diào)度、哈希調(diào)度等，實(shí)現(xiàn)簡單，開銷小，但難以適應(yīng)動(dòng)態(tài)負(fù)載變化[3]。動(dòng)態(tài)調(diào)度在計(jì)算過程中根據(jù)節(jié)點(diǎn)實(shí)時(shí)負(fù)載動(dòng)態(tài)分配任務(wù)，如工作竊取調(diào)度、優(yōu)先級調(diào)度等，實(shí)現(xiàn)更好的負(fù)載均衡，提高資源利用率，但調(diào)度開銷大。有針對圖計(jì)算特點(diǎn)設(shè)計(jì)的調(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并行計(jì)算策略的實(shí)現(xiàn)

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

3.1編程模型

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

3.2通信機(jī)制

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

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

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

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

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

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

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

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

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

圖計(jì)算任務(wù)通常需要遍歷大部分節(jié)點(diǎn)和邊，存在大量隨機(jī)訪問操作。為減少訪問延遲，提高數(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é)點(diǎn)預(yù)取其鄰居數(shù)據(jù)，路徑預(yù)取沿遍歷路徑預(yù)取后續(xù)數(shù)據(jù)，社區(qū)預(yù)取在訪問社區(qū)內(nèi)節(jié)點(diǎn)時(shí)預(yù)取該社區(qū)其他數(shù)據(jù)。延遲加載則在實(shí)際需要時(shí)才加載數(shù)據(jù)，減少不必要的加載開銷和內(nèi)存占用。延遲加載與預(yù)取技術(shù)可結(jié)合使用，在保證數(shù)據(jù)及時(shí)性的同時(shí)減少內(nèi)存浪費(fèi)，是優(yōu)化圖數(shù)據(jù)訪問的有效方法。

5結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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