基于协程的高效图算法框架研究

由于图（Graph）强大的表达能力，图结构和算法被广泛用在各个领域的数据上，例如社交网络，电子商务和生物分子建模。近些年来，随着社交网络的不断发展，许多图算法被提出用于分析图数据，同时很多图系统和框架被提出以实现图算法的并行加速。基于以顶点为中心（Vertex centric）和子图为中心（Partition centric）的图算法并行执行成为主流的应用模式和研究方向。

  尽管许多图计算系统提出了许多方法使图算法能够在高性能硬件上并行执行，但现有工作仍存在一些待解决的问题。一方面，以顶点为中心的执行模式虽然可以利用基于优先级的调度方式剪枝冗余计算，但是由于调度的动态性和邻居顶点数据的随机访问导致了大量缓存未命中（Cache misses），所以CPU利用率较低；另一方面，以子图为中心的的执行模式虽然减少了大量缓存未命中，但是由于较大的计算和存储粒度无法实现基于优先级的调度，进而导致了大量冗余计算。总体来说，现有工作无法同时兼顾图算法的剪枝高效率和硬件的缓存高效率。

  本文主要研究了一种新型图算法框架，旨在解决现有内存图处理系统中固有的缓存效率和工作效率之间的权衡问题。我们提出了一种创新的混合执行模型，该模型以顶点为粒度生成更新消息，以实现高效率的执行；同时以子图为粒度汇总更新以共享数据访问以提高缓存效率。为了将图算法的随机内存访问与计算重叠，系统广泛使用了协程。协程（Coroutines）是一种轻量级函数，可以低开销地挂起和恢复执行，方便系统预读取所需的数据。本研究还进行了一系列系统优化设计，以充分利用协程的特性，包括预读友好的图存储格式、预读取流水线和无阻塞的同步算法。实验结果表明，与五种最先进的图算法系统相比，在18个不同的测试实例中，该系统的算法执行时间优于其他所有基线系统，且相比目前性能最佳的系统的加速比可以超过2.5倍。系统同时实现了高缓存命中和高剪枝效果，这表明该系统在图计算上是一种高效的内存系统，兼顾了算法和硬件优化特性。

[1] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[M]. MITPress, 2022.
[2] SHIN K, ELIASSI-RAD T, FALOUTSOS C. Corescope: Graph mining using k-core analysis—patterns, anomalies and algorithms[C]//2016 IEEE 16th International Conference on DataMining. IEEE, 2016: 469-478.
[3] EASLEY D, KLEINBERG J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge University Press, 2010.
[4] KOREN Y, BELL R, VOLINSKY C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.
[5] VORA K, GUPTA R, XU G. Kickstarter: Fast and accurate computations on streaming graphsvia trimmed approximations[C]//Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems. 2017: 237-251.
[6] EKSOMBATCHAI C, JINDAL P, LIU J Z, et al. Pixie: A system for recommending 3+ billionitems to 200+ million users in real-time[C]//Proceedings of World Wide Web Conference. 2018:1775-1784.
[7] MIAO Y, HAN W, LI K, et al. Immortalgraph: A system for storage and analysis of temporalgraphs[J]. ACM Transactions on Storage, 2015, 11(3): 1-34.
[8] JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic networks[J]. Nature, 2000, 407(6804): 651-654.
[9] IDEKER T, OZIER O, SCHWIKOWSKI B, et al. Discovering regulatory and signalling circuitsin molecular interaction networks[J]. Bioinformatics, 2002, 18(suppl_1): S233-S240.
[10] CEN Y, ZHANG J, WANG G, et al. Trust relationship prediction in alibaba E-commerce platform[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 32(5): 1024-1035.
[11] MARIAPPAN M, VORA K. Graphbolt: Dependency-driven synchronous processing of streaming graphs[C]//Proceedings of the 14th EuroSys Conference 2019. 2019: 1-16.
[12] 李贺, 刘延娜, 杨舒琪, 等. 基于顶点组重分配的动态增量图划分算法[J]. 软件学报, 2024,35(04): 1819-1840.
[13] BEUTEL A, AKOGLU L, FALOUTSOS C. Fraud detection through graph-based user behaviormodeling[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 2015: 1696-1697.
[14] MAO R, LI Z, FU J. Fraud transaction recognition: A money flow network approach[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. 2015: 1871-1874.
[15] AKOGLU L, TONG H, KOUTRA D. Graph based anomaly detection and description: a survey[J]. Data Mining and Knowledge Discovery, 2015, 29(3): 626-688.
[16] FENG G, MA Z, LI D, et al. RisGraph: A Real-Time Streaming System for Evolving Graphsto Support Sub-millisecond Per-update Analysis at Millions Ops/s[C]//Proceedings of the 2021ACM SIGMOD International Conference on Management of Data. 2021: 513-527.
[17] ZHU X, FENG G, SERAFINI M, et al. LiveGraph: A transactional graph storage system withpurely sequential adjacency list scans[J]. Proceedings of the VLDB Endowment, 2020, 13(7):1020-1034.
[18] DIJKSTRA E W. A note on two problems in connexion with graphs[M]//Edsger Wybe Dijkstra:His Life, Work, and Legacy. 2022: 287-290.
[19] SEIDMAN S B. Network structure and minimum degree[J]. Social Networks, 1983, 5(3):269-287.
[20] LU Y, CHENG J, YAN D, et al. Large-scale distributed graph computing systems: An experimental evaluation[J]. Proceedings of the VLDB Endowment, 2014, 8(3): 281-292.
[21] AMMAR K, OZSU T. Experimental analysis of distributed graph systems[J]. Proceedings ofthe VLDB Endowment, 2018, 11(10): 1151-1164.
[22] EULER L. Leonhard Euler and the Königsberg bridges[J]. Scientific American, 1953, 189(1):66-72.
[23] 李忠飞, 杨雅君, 王鑫. 基于规则的最短路径查询算法[J]. 软件学报, 2019, 30(03): 515-536.
[24] 孙天元, 王永才, 李德英. 图实现算法综述与评测分析[J]. 自动化学报, 2020, 46(04): 613-630.
[25] SHARMA A, JIANG J, BOMMANNAVAR P, et al. GraphJet: Real-time content recommendations at Twitter[J]. Proceedings of the VLDB Endowment, 2016, 9(13): 1281-1292.
[26] 陈子俊, 马德龙, 王一舒, 等. GPPR: 跨域分布式个性化 PageRank 算法[J]. 软件学报, 2024,35(03): 1090-1106.
[27] MARTINEZ-BAZAN N, GOMEZ-VILLAMOR S, ESCALE-CLAVERAS F. DEX: A highperformance graph database management system[C]//2011 IEEE 27th International Conferenceon Data Engineering Workshops. IEEE, 2011: 124-127.
[28] GONG P, LIU R, MAO Z, et al. gSampler: General and efficient GPU-based graph samplingfor graph learning[C]//Proceedings of the 29th Symposium on Operating Systems Principles.2023: 562-578.
[29] 吴博, 梁循, 张树森, 等. 图神经网络前沿进展与应用[J]. 计算机学报, 2022, 45(01): 35-68.
[30] MCGREGOR A. Graph stream algorithms: a survey[J]. ACM SIGMOD Record, 2014, 43(1):9-20.
[31] ROBINSON I, WEBBER J, EIFREM E. Graph databases: new opportunities for connecteddata[M]. O’Reilly Media, Inc., 2015.
[32] neo4j[EB/OL]. 2022. https://neo4j.com/.
[33] SHUN J, BLELLOCH G E. Ligra: a lightweight graph processing framework for shared memory[C]//Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice ofParallel Programming. 2013: 135-146. al. GPOP: A cache and memory-efficient frameworkfor graph processing over partitions[C]//Proceedings of the 24th Symposium on Principles andPractice of Parallel Programming. 2019: 393-394.
[38] ZHANG Y, YANG M, BAGHDADI R, et al. Graphit: A high-performance graph dsl[J]. Proceedings of the ACM on Programming Languages, 2018, 2(OOPSLA): 1-30.
[39] LU S, SUN S, PAUL J, et al. Cache-efficient fork-processing patterns on large graphs[C]//Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data.2021: 1208-1221.
[40] DHULIPALA L, BLELLOCH G E, SHUN J. Low-latency graph streaming using compressedpurely-functional trees[C]//Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. 2019: 918-934.
[41] MACKO P, MARATHE V J, MARGO D W, et al. Llama: Efficient graph analytics usinglarge multiversioned arrays[C]//2015 IEEE 31st International Conference on Data Engineering.IEEE, 2015: 363-374.
[42] EDIGER D, MCCOLL R, RIEDY J, et al. Stinger: High performance data structure for streaming graphs[C]//2012 IEEE Conference on High Performance Extreme Computing. IEEE, 2012:1-5.
[43] 祝贺, 华强胜, 金海, 等. LMSA:NVM 环境下高性能动态图处理数据结构[J]. 计算机学报,2022, 45(07): 1446-1461.
[44] 李贺, 刘延娜, 袁航, 等. 动态图划分算法研究综述[J]. 软件学报, 2023, 34(02): 539-564.
[45] LEE J, KIM H, YOO S, et al. Extrav: boosting graph processing near storage with a coherentaccelerator[J]. Proceedings of the VLDB Endowment, 2017, 10(12): 1706-1717.
[46] 李琪, 钟将, 李雪. 图划分在混合内存系统的实现与性能优化[J]. 计算机学报, 2019, 42(11): 2481-2498.
[47] 蒋筱斌, 熊轶翔, 张珩, 等. ChattyGraph: 面向异构多协处理器的高可扩展图计算系统[J].软件学报, 2023, 34(04): 1977-1996.
[48] ZHU X, HAN W, CHEN W. GridGraph:Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning[C]//2015 USENIX Annual Technical Conference. 2015:375-386.
[49] KIM J, SWANSON S. Blaze: fast graph processing on fast SSDs[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis.IEEE, 2022: 1-15.
[50] KYROLA A, BLELLOCH G, GUESTRIN C. GraphChi:Large-Scale Graph Computation onJust a PC[C]//10th USENIX Symposium on Operating Systems Design and Implementation.2012: 31-46.
[51] ROY A, MIHAILOVIC I, ZWAENEPOEL W. X-stream: Edge-centric graph processing using streaming partitions[C]//Proceedings of the 24th ACM Symposium on Operating SystemsPrinciples. 2013: 472-488.
[52] KUMAR P, HUANG H H. G-store: high-performance graph store for trillion-edge processing[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2016: 830-841.
[53] SENGUPTA D, SONG S L. Evograph: On-the-fly efficient mining of evolving graphs on gpu[C]//International Supercomputing Conference. Springer, 2017: 97-119.
[54] 苗旭鹏, 王驭捷, 沈佳, 等. 面向多 GPU 的图神经网络训练加速[J]. 软件学报, 2023, 34(09):4407-4420.
[55] SHA M, LI Y, HE B, et al. Accelerating Dynamic Graph Analytics on GPUs[J]. Proceedingsof the VLDB Endowment, 2017, 11(1): 107-120.
[56] WANG Y, PAN Y, DAVIDSON A, et al. Gunrock: GPU graph analytics[J]. ACM Transactionson Parallel Computing, 2017, 4(1): 1-49.
[57] MONDAL J, DESHPANDE A. Managing large dynamic graphs efficiently[C]//Proceedings ofthe 2012 ACM SIGMOD International Conference on Management of Data. 2012: 145-156.
[58] 李玲, 印莹, 赵宇海, 等. 基于解耦概要图的大规模图数据高效分布式挖掘算法[J]. 计算机学报, 2020, 43(07): 1183-1198.
[59] 崔鹏杰, 袁野, 李岑浩, 等. RGraph: 基于 RDMA 的高效分布式图数据处理系统[J]. 软件学报, 2022, 33(03): 1018-1042.
[60] 沈斯杰, 陈榕, 陈海波, 等. 基于图结构索引的分布式 OLAP 加速方法[J]. 软件学报, 2023,34(10): 4661-4680.
[61] 王鑫, 徐强, 柴乐乐, 等. 大规模 RDF 图数据上高效率分布式查询处理[J]. 软件学报, 2019,30(03): 498-514.
[62] 王童童, 荣垂田, 卢卫, 等. 分布式图处理系统技术综述[J]. 软件学报, 2018, 29(03): 569-586.
[63] ZHU X, CHEN W, ZHENG W, et al. Gemini: A Computation-Centric Distributed Graph Processing System[C]//12th USENIX Symposium on Operating Systems Design and Implementation. 2016: 301-316.
[64] MALEWICZ G, AUSTERN M H, BIK A J, et al. Pregel: a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Managementof data. 2010: 135-146.
[65] BRONSON N, AMSDEN Z, CABRERA G, et al. TAO:Facebook’s Distributed Data Storefor the Social Graph[C]//2013 USENIX Annual Technical Conference. 2013: 49-60.
[66] SHAO B, WANG H, LI Y. Trinity: A distributed graph engine on a memory cloud[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.2013: 505-516.
[67] GONZALEZ J E, LOW Y, GU H, et al. PowerGraph: Distributed Graph-Parallel computationon natural graphs[C]//10th USENIX Symposium on Operating Systems Design and Implementation. 2012: 17-30.
[68] BURAGOHAIN C, RISVIK K M, BRETT P, et al. A1: A distributed in-memory graph database[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management ofData. 2020: 329-344.
[69] GONZALEZ J E, XIN R S, DAVE A, et al. GraphX: Graph processing in a distributed dataflowframework[C]//11th USENIX Symposium on Operating Systems Design and Implementation.2014: 599-613.
[70] WANG K, XU G, SU Z, et al. GraphQ: Graph Query Processing with Abstraction Refinement—Scalable and Programmable Analytics over Very Large Graphs on a Single PC[C]//2015USENIX Annual Technical Conference. 2015: 387-401.
[71] JU W, LI J, YU W, et al. iGraph: an incremental data processing system for dynamic graph[J].Frontiers of Computer Science, 2016, 10(3): 462-476.
[72] PRABHAKARAN V, WU M, WENG X, et al. Managing Large Graphs on Multi-Cores withGraph Awareness[C]//2012 USENIX Annual Technical Conference. 2012: 41-52.
[73] SENGUPTA D, SUNDARAM N, ZHU X, et al. Graphin: An online high performance incremental graph processing framework[C]//European Conference on Parallel Processing. Springer,2016: 319-333.
[74] ZHAO J, ZHANG Y, LIAO X, et al. GraphM: an efficient storage system for high throughput of concurrent graph processing[C]//Proceedings of the International Conference for HighPerformance Computing, Networking, Storage and Analysis. 2019: 1-14.
[75] PSAROPOULOS G, LEGLER T, MAY N, et al. Interleaving with coroutines: a practical approach for robust index joins[J]. Proceedings of the VLDB Endowment, 2017, 11(7): 230-242.
[76] JONATHAN C, MINHAS U F, HUNTER J, et al. Exploiting coroutines to attack the” killernanoseconds”[J]. Proceedings of the VLDB Endowment, 2018, 11(11): 1702-1714.
[77] MENON P, MOWRY T C, PAVLO A. Relaxed operator fusion for in-memory databases: Making compilation, vectorization, and prefetching work together at last[J]. Proceedings of theVLDB Endowment, 2017, 11(1): 1-13.
[78] MÜHLIG J, TEUBNER J. MxTasks: How to Make Efficient Synchronization and PrefetchingEasy[C]//Proceedings of the 2021 ACM SIGMOD International Conference on Managementof Data. 2021: 1331-1344.
[79] LEE J, KIM H, VUDUC R. When prefetching works, when it doesn’t, and why[J]. ACMTransactions on Architecture and Code Optimization, 2012, 9(1): 1-29.
[80] AYERS G, LITZ H, KOZYRAKIS C, et al. Classifying memory access patterns for prefetching[C]//Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems. 2020: 513-526.
[81] CHEN S, AILAMAKI A, GIBBONS P B, et al. Improving hash join performance throughprefetching[J]. ACM Transactions on Database Systems, 2007, 32(3): 17-29.
[82] NARAYANAN V, DETWEILER D, HUANG T, et al. DRAMHiT: A Hash Table Architected forthe Speed of DRAM[C]//Proceedings of the 18th European Conference on Computer Systems.2023: 817-834.
[83] KOCBERBER O, FALSAFI B, GROT B. Asynchronous memory access chaining[J]. Proceedings of the VLDB Endowment, 2015, 9(4): 252-263.
[84] ISO/IEC. Technical Specifcation —C++ Extensions for Coroutines[EB/OL]. 2017. https://www.iso.org/standard/73008.html.
[85] MOURA A L D, IERUSALIMSCHY R. Revisiting coroutines[J]. ACM Transactions on Programming Languages and Systems, 2009, 31(2): 1-31.
[86] CARTER A, RODRIGUEZ A, YANG Y, et al. Nanosecond indexing of graph data with hashmaps and VLists[C]//Proceedings of the 2019 ACM SIGMOD International Conference onManagement of Data. 2019: 623-635.
[87] HE Y, LU J, WANG T. Coroutine-Oriented Main-Memory Database Engine[J]. Proceedings ofthe VLDB Endowment, 2021, 14(3): 431-444.
[88] SUN S, CHEN Y, LU S, et al. ThunderRW: an in-memory graph random walk engine[Z]. 2021.
[89] ZHANG K, CHEN R, CHEN H. NUMA-aware graph-structured analytics[C]//Proceedingsof the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.2015: 183-193.
[90] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the internettopology[J]. ACM SIGCOMM Computer Communication Review, 1999, 29(4): 251-262.
[91] HUBERMAN B A, ADAMIC L A. Growth dynamics of the world-wide web[J]. Nature, 1999,401(6749): 131-131.
[92] ANGLES R, ARENAS M, BARCELÓ P, et al. Foundations of modern query languages forgraph databases[J]. ACM Computing Surveys, 2017, 50(5): 1-40.
[93] CHING A, EDUNOV S, KABILJO M, et al. One trillion edges: Graph processing at facebookscale[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1804-1815.
[94] ROY A, BINDSCHAEDLER L, MALICEVIC J, et al. Chaos: Scale-out graph processing fromsecondary storage[C]//Proceedings of the 25th Symposium on Operating Systems Principles.2015: 410-424.
[95] FIRMLI S, TRIGONAKIS V, LOZI J P, et al. CSR++: A Fast, Scalable, Update-Friendly GraphData Structure[C]//24th International Conference on Principles of Distributed Systems. 2020.
[96] LEIS V, KEMPER A, NEUMANN T. The adaptive radix tree: ARTful indexing for mainmemory databases[C]//2013 IEEE 29th International Conference on Data Engineering. IEEE,2013: 38-49.
[97] BENDER M A, DEMAINE E D, FARACH-COLTON M. Cache-oblivious B-trees[C]//Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000: 399-409.
[98] XING W, GHORBANI A. Weighted pagerank algorithm[C]//Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004. IEEE, 2004: 305-314.
[101] SHUN J, DHULIPALA L, BLELLOCH G E. Smaller and faster: Parallel processing of compressed graphs with Ligra+[C]//2015 Data Compression Conference. IEEE, 2015: 403-412.
[102] BLELLOCH G E, FERIZOVIC D, SUN Y. Just join for parallel ordered sets[C]//Proceedingsof the 28th ACM Symposium on Parallelism in Algorithms and Architectures. 2016: 253-264.
[103] COORPORATION I. Intel 64 and IA-32 architectures optimization reference manual[EB/OL].2016.
[104] MITZENMACHER M, UPFAL E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis[M]. Cambridge University Press, 2017.
[105] CHAKRABARTI D, ZHAN Y, FALOUTSOS C. R-MAT: A recursive model for graph mining[C]//Proceedings of the 2004 SIAM International Conference on Data Mining. SIAM, 2004:442-446.
[106] ERLING O, AVERBUCH A, LARRIBA-PEY J, et al. The LDBC social network benchmark:Interactive workload[C]//Proceedings of the 2015 ACM SIGMOD International Conference onManagement of Data. 2015: 619-630.
[107] IOSUP A, HEGEMAN T, NGAI W L, et al. LDBC Graphalytics: A benchmark for large-scalegraph analysis on parallel and distributed platforms[J]. Proceedings of the VLDB Endowment,2016, 9(13): 1317-1328.
[108] LISSANDRINI M, BRUGNARA M, VELEGRAKIS Y. Beyond macrobenchmarks:microbenchmark-based graph database evaluation[J]. Proceedings of the VLDB Endowment,2018, 12(4): 390-403.
[109] BOLDI P, VIGNA S. The webgraph framework I: compression techniques[C]//Proceedings ofthe 13th International Conference on World Wide Web. 2004: 595-602.
[110] KUNEGIS J. Konect: the koblenz network collection[C]//Proceedings of the 22nd InternationalConference on World Wide Web. 2013: 1343-1350.
[111] KWAK H, LEE C, PARK H, et al. What is Twitter, a social network or a news media?[C]//Proceedings of the 19th International Conference on World Wide Web. 2010: 591-600.
[112] MEYER U, SANDERS P. 𝛥-stepping: a parallelizable shortest path algorithm[J]. Journal ofAlgorithms, 2003, 49(1): 114-152.