Article(id=1329420622796534726, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329420435915125316, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202550501, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1750867200000, receivedDateStr=2025-06-26, revisedDate=1775750400000, revisedDateStr=2026-04-10, acceptedDate=1777478400000, acceptedDateStr=2026-04-30, onlineDate=1794888175915, onlineDateStr=2026-11-17, pubDate=1788192000000, pubDateStr=2026-09-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794888175915, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794888175915, creator=13701087609, updateTime=1794888175915, updator=13701087609, issue=Issue{id=1329420435915125316, tenantId=1146029695717560320, journalId=1324759914146529478, year='2026', volume='63', issue='9', pageStart='2183', pageEnd='2477', issueExtLink='null', onlineDate='null', pubDate='1788192000000', pubDateStr='2026-09-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794888131359, creator='13701087609', updateTime=1794888131359, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=2442, endPage=2462, ext={EN=ArticleExt(id=1329420622985278407, articleId=1329420622796534726, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Saturn: High Performance Graph Pattern Mining System on Multi-GPU Platform, columnId=1325493593498059289, journalTitle=Journal of Computer Research and Development, columnName=High Performance Computing, runingTitle=null, highlight=null, articleAbstract=

Graph pattern mining, as a core task for analyzing entity relationships, finds extensive applications in fields such as community detection and drug discovery. However, due to its non-polynomial time complexity, large-scale graph processing encounters challenges related to search space explosion and low computational efficiency. Existing GPU-accelerated solutions utilize parallel computing to enhance performance but often suffer from thread idleness caused by the power-law distribution of graph data and excessive CPU intervention in multi-GPU communication, which impede the full utilization of hardware capabilities. We present Saturn, a GPU-based graph pattern mining system, which overcomes the above bottlenecks through computation-communication co-optimization. At computation level, Saturn decouples the loading and querying phases of set operations, employs fine-grained parallel batch processing to dynamically adapt Hash and binary search algorithms, and optimizes memory access efficiency via shared memory caching, significantly improving thread utilization. At communication level, it establishes a CPU-free GPU communication model, leveraging high-bandwidth NVLink interconnect and unified memory mechanism for direct cross-device data access, while reducing redundant transmission and link contention through vertex caching and message aggregation scheduling. Experimental results demonstrate that Saturn outperforms state-of-the-art GPU-based graph mining systems on real-world datasets, achieving superior computational parallel efficiency and cross-device communication effectiveness for large-scale graph pattern mining tasks.

, authors=Zhiheng Lin, Ke Meng, Guangming Tan*, authorsList=Zhiheng Lin, Ke Meng, Guangming Tan, authorCompany=null, correspAuthors=Guangming Tan, authorNote=

born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

, correspAuthorsNote=null, copyrightStatement=Copyright © 2026 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329420627397686272, articleId=1329420622796534726, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=Saturn: 面向Multi-GPU平台的高性能图模式挖掘系统, columnId=1325493595259666971, journalTitle=计算机研究与发展, columnName=高性能计算, runingTitle=null, highlight=null, articleAbstract=

图模式挖掘作为分析实体关系的核心任务,在社区检测、药物发现等领域具有广泛应用。但由于其非多项式时间复杂度,大规模图数据处理面临搜索空间爆炸与计算效率低下的挑战。现有基于GPU的加速方案虽利用并行计算提升性能,但受限于图数据幂律分布导致的线程空闲问题,以及多GPU场景下频繁的CPU介入通信开销,难以充分释放硬件算力。提出GPU图模式挖掘系统Saturn,通过计算与通信协同优化突破上述瓶颈:在计算层面,将集合操作的装载与查询阶段解耦,采用细粒度并行批处理策略动态适配哈希与二分查找算法,并结合共享内存缓存优化访存效率,显著提升线程利用率;在通信层面,构建CPU无感的全GPU通信模式,利用NVLink高带宽链路与统一内存机制实现跨设备数据直接访问,通过顶点缓存与消息聚合调度降低冗余传输与链路竞争。实验结果表明,Saturn在真实数据集上相比主流GPU图挖掘系统,实现了更高的计算并行效率与跨设备通信能效,为大规模图模式挖掘任务提供了高效解决方案。

, authors=林志恒, 孟轲, 谭光明*, authorsList=林志恒, 孟轲, 谭光明, authorCompany=null, correspAuthors=谭光明, authorNote=

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

, correspAuthorsNote=
谭光明()
, copyrightStatement=版权所有 © 2026 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=e1w++pdanPzbCOdgqwDCuw==, magXml=rlCj1B7oXxoX27cXJ5CkXw==, pdfUrl=null, pdf=tVLUsDBB/4bFKdIWjsabmA==, pdfFileSize=2137464, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=GXXhUYZ+Gz2qCsJgctX7Iw==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=wwlzrSDSSl+qc7xA2K2KsQ==, mapNumber=null, fund=null)}, authors=[Author(id=1329420627762589703, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=linzhiheng@ncic.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329420627825504264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627762589703, language=EN, stringName=Zhiheng Lin, firstName=Zhiheng, middleName=null, lastName=Lin, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

"}, bioImg=null, bioContent=

born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420627884224521, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627762589703, language=CN, stringName=林志恒, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"8ECZoWGS6FiQnRNMP2T35A==","content":"

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

"}, bioImg=8ECZoWGS6FiQnRNMP2T35A==, bioContent=

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329420627955527691, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329420628014247948, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627955527691, language=EN, stringName=Ke Meng, firstName=Ke, middleName=null, lastName=Meng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

"}, bioImg=null, bioContent=

born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420628081356813, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627955527691, language=CN, stringName=孟轲, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"GvP7CMUevhaySZOx1pQmJA==","content":"

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

"}, bioImg=GvP7CMUevhaySZOx1pQmJA==, bioContent=

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329420628219768847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=tgm@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329420628291072016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420628219768847, language=EN, stringName=Guangming Tan, firstName=Guangming, middleName=null, lastName=Tan, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

"}, bioImg=null, bioContent=

born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420628412706834, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420628219768847, language=CN, stringName=谭光明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"7THW1PQcsfBduQiccY2qjA==","content":"

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

"}, bioImg=7THW1PQcsfBduQiccY2qjA==, bioContent=

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

, aboutCorrespAuthor=null)}, companyList=null)], keywords=[Keyword(id=1329420628509175827, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, orderNo=1, keyword=graph pattern mining), Keyword(id=1329420628605644820, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, orderNo=2, keyword=distributed graph processing), Keyword(id=1329420628681142293, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, orderNo=3, keyword=GPU), Keyword(id=1329420628756639766, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, orderNo=4, keyword=parallel computing), Keyword(id=1329420628827942935, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, orderNo=5, keyword=communication optimization), Keyword(id=1329420628882468888, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, orderNo=1, keyword=图模式挖掘), Keyword(id=1329420628957966361, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, orderNo=2, keyword=分布式图处理), Keyword(id=1329420629033463834, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, orderNo=3, keyword=GPU), Keyword(id=1329420629092184091, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, orderNo=4, keyword=并行计算), Keyword(id=1329420629180264476, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, orderNo=5, keyword=通信优化)], refs=[Reference(id=1329420633177436248, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Spirin N, Han Jiawei. Survey on Web spam detection: Principles and algorithms[J]. ACM SIGKDD Explorations Newsletter, 2012, 13(2): 50−64., articleTitle=null, refAbstract=null), Reference(id=1329420633244545113, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Guo Zhichun, Guo Kehan, Nan Bozhao, et al. Graph-based molecular representation learning[C]//Proc of the 32nd Int Joint Conf on Artificial Intelligence (IJCAI’23). New York: ACM, 2023: 6638−6646, articleTitle=null, refAbstract=null), Reference(id=1329420633303265370, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Ranu S, Singh A K. Indexing and mining topological patterns for drug discovery[C]//Proc of the 15th Int Conf on Extending Database Technology (EDBT’12). New York: ACM, 2012: 562−565, articleTitle=null, refAbstract=null), Reference(id=1329420633378762843, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=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, articleTitle=null, refAbstract=null), Reference(id=1329420633441677404, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Mawhirter D, Wu B. AutoMine: Harmonizing high-level abstraction and high performance for graph mining[C]//Proc of the 27th ACM Symp on Operating Systems Principles (SOSP ’19). New York: ACM, 2019: 509−523, articleTitle=null, refAbstract=null), Reference(id=1329420633521369181, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Jamshidi K, Mahadasa R, Vora K. Peregrine: A pattern-aware graph mining system[C]//Proc of the 15th European Conf on Computer Systems (EuroSys ’20). New York: ACM, 2020: 13: 1–13: 16, articleTitle=null, refAbstract=null), Reference(id=1329420633575895134, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Mawhirter D, Reinehr S, Holmes C, et al. GraphZero: A high-performance subgraph matching system[J]. SIGOPS Operating Systems Review, 2021, 55(1): 21−37., articleTitle=null, refAbstract=null), Reference(id=1329420633634615391, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Tianhui, Zhai Mingshu, Xu Yi, et al. GraphPi: High performance graph pattern matching through effective redundancy elimination[C]//Proc of the 32nd Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’20). Piscataway, NJ: IEEE, 2020: 1−14, articleTitle=null, refAbstract=null), Reference(id=1329420633693335648, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=JEDEC. High bandwidth memory (HBM) DRAM[EB/OL]. (2021-03-01)[2025-06-13]. https://www.jedec.org/standards-documents/docs/jesd235a, articleTitle=null, refAbstract=null), Reference(id=1329420633768833121, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Xuhao, Arvind. Efficient and scalable graph pattern mining on GPUs[C]//Proc of the 16th USENIX Symp on Operating Systems Design and Implementation (OSDI’22). Berkely, CA: USENIX Association, 2022: 857−877, articleTitle=null, refAbstract=null), Reference(id=1329420633835941986, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Tianhui, Zhai Jidong, Wang Haojie, et al. GraphSet: High performance graph mining through equivalent set transformations[C]//Proc of the 35th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’23). New York: ACM, 2023: 32: 1−32: 14, articleTitle=null, refAbstract=null), Reference(id=1329420633894662243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Pandey S, Li Xiaoye, Buluc A, et al. H-index: Hash-indexing for parallel triangle counting on GPUs[C]//Proc of the 23rd IEEE High Performance Extreme Computing Conf (HPEC). Piscataway, NJ: IEEE, 2019: 1−7, articleTitle=null, refAbstract=null), Reference(id=1329420633949188196, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Hu Yang, Liu Hang, Huang H. Tricore: Parallel triangle counting on GPUs[C]//Proc of the 30th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’18). Piscataway, NJ: IEEE, 2018: 171−182, articleTitle=null, refAbstract=null), Reference(id=1329420634007908453, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Guo Wentian, Li Yuchen, Sha Mo, et al. GPU-accelerated subgraph enumeration on partitioned graphs[C]//Proc of the 40th ACM SIGMOD Int Conf on Management of Data (SIGMOD’20). New York: ACM, 2020: 1067–1082, articleTitle=null, refAbstract=null), Reference(id=1329420634075017318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Guanxian, Zhou Qihui, Jin Tatiana, et al. VSGM: View-based GPU-accelerated subgraph matching on large graphs[C]//Proc of the 34th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’22). Piscataway, NJ: IEEE, 2022: 1−15, articleTitle=null, refAbstract=null), Reference(id=1329420634137931879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Yuan Lyuheng, Ahmad A, Yan Da, et al. G2-AIMD: A memory-efficient subgraph-centric framework for efficient subgraph search on GPUs[C]//Proc of the 40th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2024: 3164−3177, articleTitle=null, refAbstract=null), Reference(id=1329420634209235048, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Pandey S, Wang Zhibin, Zhong Sheng, et al. Trust: Triangle counting reloaded on GPUs[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(11): 2646−2660, articleTitle=null, refAbstract=null), Reference(id=1329420634272149609, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Zhibin, Meng Ziheng, Li Xue, et al. Smog: Accelerating subgraph matching on GPUs[C]//Proc of the 27th IEEE High Performance Extreme Computing Conf (HPEC). Piscataway, NJ: IEEE, 2023: 1–7, articleTitle=null, refAbstract=null), Reference(id=1329420634326675562, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Iosup A, Hegeman T, Ngai W L, et al. LDBC graph-analytics: A benchmark for large-scale graph analysis on parallel and distributed platforms[J]. Proceedings of the VLDB Endowment, 2016, 9(13): 1317−1328, articleTitle=null, refAbstract=null), Reference(id=1329420634385395819, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Jingji, Qian Xuehai. Khuzdul: Efficient and scalable distributed graph pattern mining engine[C]//Proc of the 28th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS’23). New York: ACM, 2023: 413−426, articleTitle=null, refAbstract=null), Reference(id=1329420634460893292, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Leskovec J, Krevl A. SNAP datasets: Stanford large network dataset collection[EB/OL]. 2014[2025-06-13]. http://snap.stanford.edu/data, articleTitle=null, refAbstract=null), Reference(id=1329420634532196461, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Lin Hu, Lin Yinnian, Zou Lei, et al. A graph pattern mining framework for large graphs on GPU[J]. The VLDB Journal, 2025, 34(1): 117−143., articleTitle=null, refAbstract=null), Reference(id=1329420634590916718, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Teixeira C H C, Fonseca A J, Serafini M, et al. Arabesque: A system for distributed graph mining[C]//Proc of the 25th Symp on Operating Systems Principles (SOSP’15). New York: ACM, 2015: 425–440, articleTitle=null, refAbstract=null), Reference(id=1329420634658025583, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Xuhao, Dathathri R, Gill G, et al. Pangolin: An efficient and flexible graph mining system on CPU and GPU[J]. Proceedings of the VLDB Endowment, 2020, 13(8): 1190−1205, articleTitle=null, refAbstract=null), Reference(id=1329420634729328752, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Wei Yihua, Jiang Peng. STMatch: Accelerating graph pattern matching on GPU with stack-based loop optimizations[C]//Proc of the 34th Int Conf for High Performance Computing, Networking, Storage and Analysis(SC’22). Piscataway, NJ: IEEE, 2022: 53: 1–53: 13, articleTitle=null, refAbstract=null), Reference(id=1329420634800631921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Sun Xibo, Luo Qiong. Efficient GPU-accelerated subgraph matching[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 181: 1−181: 26, articleTitle=null, refAbstract=null), Reference(id=1329420634901295218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Lin Zhiheng, Meng Ke, Shui Chaoyang, et al. Exploiting fine-grained redundancy in set-centric graph pattern mining[C]//Proc of the 29th ACM SIGPLAN Annual Symp on Principles and Practice of Parallel Programming (PPoPP’24). New York: ACM, 2024: 175–187, articleTitle=null, refAbstract=null), Reference(id=1329420634960015475, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273−288, articleTitle=null, refAbstract=null), Reference(id=1329420635111010420, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Heng, Zhang Libo, Wu Yanjun. Large-scale graph processing on Multi-GPU platforms[J]. Journal of Computer Research and Development, 2018, 55(2): 273−288 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329420635165536373, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=蒋筱斌, 熊轶翔, 张珩, 等. ChattyGraph: 面向异构多协处理器的高可扩展图计算系统[J]. 软件学报, 2023, 34(4): 1977−1996, articleTitle=null, refAbstract=null), Reference(id=1329420635224256630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Xiaobin, Xiong Yixiang, Zhang Heng, et al. ChattyGraph: Highly scalable graph computing system for heterogeneous multi accelerators[J]. Journal of Software, 2023, 34(4): 1977−1996 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329420635287171191, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Gonzalez Joseph E, Low Y, Guerin R, et al. PowerGraph: Distributed graph-parallel computation on natural graphs[C]//Proc of the 10th USENIX Symp on Operating Systems Design and Implementation (OSDI 12). Berkeley, CA: USENIX Association, 2012: 17−30, articleTitle=null, refAbstract=null), Reference(id=1329420635350085752, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]//Proc of the 30th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135−146, articleTitle=null, refAbstract=null), Reference(id=1329420635404611705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Gonzalez J E, Xin R S, Dave A, et al. GraphX: Graph processing in a distributed dataflow framework[C]//Proc of the 11th USENIX Symp on Operating Systems Design and Implementation (OSDI 2014). Berkeley, CA: USENIX Association, 2014: 599−613, articleTitle=null, refAbstract=null), Reference(id=1329420635459137658, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Minjie, Yu Ling, Zheng Da, et al. Deep graph library: Towards efficient and scalable deep learning on graphs[J]. arXiv preprint, arXiv: 1909.01315, 2019, articleTitle=null, refAbstract=null), Reference(id=1329420635522052219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Fey M, Lenssen J. Fast graph representation learning with PyTorch Geometric[J]. arXiv preprint, arXiv: 1903.02428, 2019, articleTitle=null, refAbstract=null), Reference(id=1329420635584966780, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Si, Tong Hanghang, Xu Jiejun, et al. Graph convolutional networks: A comprehensive review[J]. Computational Social Networks, 2019, 6(1): 1−23, articleTitle=null, refAbstract=null), Reference(id=1329420635643687037, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Xu Keyulu, Hu Weihua, Leskovec J, et al. How powerful are graph neural networks?[J]. arXiv preprint, arXiv: 1810.00826, 2018, articleTitle=null, refAbstract=null), Reference(id=1329420635698212990, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint, arXiv: 1710.10903, 2017, articleTitle=null, refAbstract=null), Reference(id=1329420635761127551, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Yu Wenyuan, Zhang Liang, Yang Chao, et al. Vineyard: Optimizing data sharing in data-intensive analytics[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1−27, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329420627599011840, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, xref=null, ext=[AuthorCompanyExt(id=1329420627607400449, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, companyId=1329420627599011840, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190), AuthorCompanyExt(id=1329420627615789058, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, companyId=1329420627599011840, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=中国科学院计算技术研究所 北京 100190)]), AuthorCompany(id=1329420627674509315, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, xref=null, ext=[AuthorCompanyExt(id=1329420627678703620, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, companyId=1329420627674509315, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=University of Chinese Academy of Sciences, Beijing 100049), AuthorCompanyExt(id=1329420627691286533, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, companyId=1329420627674509315, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=中国科学院大学 北京 100049)])], figs=[ArticleFig(id=1329420629310287901, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 1, caption=Multi-GPU hardware architecture, figureFileSmall=8b6FCzNUU/N2V0y4w2ybSA==, figureFileBig=GXXhUYZ+Gz2qCsJgctX7Iw==, tableContent=null), ArticleFig(id=1329420629381591070, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图1, caption=Multi-GPU硬件架构, figureFileSmall=8b6FCzNUU/N2V0y4w2ybSA==, figureFileBig=GXXhUYZ+Gz2qCsJgctX7Iw==, tableContent=null), ArticleFig(id=1329420629549363231, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 2, caption=Characteristics of graph pattern mining problems, figureFileSmall=cVSp1LuJK+1wjcA0eOWRAA==, figureFileBig=dsDWHQnPuR9CxM3SumBTqA==, tableContent=null), ArticleFig(id=1329420629608083488, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图2, caption=图模式挖掘问题的特征, figureFileSmall=cVSp1LuJK+1wjcA0eOWRAA==, figureFileBig=dsDWHQnPuR9CxM3SumBTqA==, tableContent=null), ArticleFig(id=1329420629666803745, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 3, caption=Host memory based multi-GPU graph pattern mining, figureFileSmall=dfKiwlbsm0KR4nYh9igKFg==, figureFileBig=Ry1Pn6k7t4DRk9BJaXoTuQ==, tableContent=null), ArticleFig(id=1329420629742301218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图3, caption=基于主存的multi-GPU图模式挖掘, figureFileSmall=dfKiwlbsm0KR4nYh9igKFg==, figureFileBig=Ry1Pn6k7t4DRk9BJaXoTuQ==, tableContent=null), ArticleFig(id=1329420629801021475, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 4, caption=Architecture of Saturn system, figureFileSmall=+u+LnqoujPmpTdB8THZHyg==, figureFileBig=krkfNZVJZq258zeV1AJPZw==, tableContent=null), ArticleFig(id=1329420629868130340, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图4, caption=Saturn系统架构, figureFileSmall=+u+LnqoujPmpTdB8THZHyg==, figureFileBig=krkfNZVJZq258zeV1AJPZw==, tableContent=null), ArticleFig(id=1329420629931044901, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 5, caption=Cumulative degree distribution of varying graph datasets, figureFileSmall=Sp4ObGB0jdDJ55kCtSop3Q==, figureFileBig=olFmwb0GI6T63qoElMHpZg==, tableContent=null), ArticleFig(id=1329420629989765158, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图5, caption=不同图数据集的累积度数分布, figureFileSmall=Sp4ObGB0jdDJ55kCtSop3Q==, figureFileBig=olFmwb0GI6T63qoElMHpZg==, tableContent=null), ArticleFig(id=1329420630044291111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 6, caption=Thread idle issue caused by coarse-grained parallelism, figureFileSmall=sYLKXMroKZLfDLdg6iwz5g==, figureFileBig=z+8b23CgKWhkTTAGNDI0ww==, tableContent=null), ArticleFig(id=1329420630098817064, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图6, caption=粗粒度并行引发的线程空闲问题, figureFileSmall=sYLKXMroKZLfDLdg6iwz5g==, figureFileBig=z+8b23CgKWhkTTAGNDI0ww==, tableContent=null), ArticleFig(id=1329420630161731625, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 7, caption=Two-stage decoupling of set operations, figureFileSmall=nc8yHSqqeilu/zIMGuWVFQ==, figureFileBig=jROGjmqoDUvlsZSvcUK/FQ==, tableContent=null), ArticleFig(id=1329420630212063274, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图7, caption=集合操作的2阶段解耦, figureFileSmall=nc8yHSqqeilu/zIMGuWVFQ==, figureFileBig=jROGjmqoDUvlsZSvcUK/FQ==, tableContent=null), ArticleFig(id=1329420630287560747, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 8, caption=Fine-grained parallelism computing process, figureFileSmall=m4rETExjhq2WTCDgvgS3Ow==, figureFileBig=u6wOI6FPKU2G0WeNSc3/Qg==, tableContent=null), ArticleFig(id=1329420630354669612, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图8, caption=细粒度并行计算流程, figureFileSmall=m4rETExjhq2WTCDgvgS3Ow==, figureFileBig=u6wOI6FPKU2G0WeNSc3/Qg==, tableContent=null), ArticleFig(id=1329420630417584173, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 9, caption=Comparison of binary search intersection and Hash index intersection, figureFileSmall=gCPLSRi/s5XwAsihSG8ZXg==, figureFileBig=zff0oySKVBhB1RpnxsG0og==, tableContent=null), ArticleFig(id=1329420630472110126, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图9, caption=二分查找求交和哈希查找求交的对比, figureFileSmall=gCPLSRi/s5XwAsihSG8ZXg==, figureFileBig=zff0oySKVBhB1RpnxsG0og==, tableContent=null), ArticleFig(id=1329420630530830383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 10, caption=Distributed-memory based GPM communication mode, figureFileSmall=UVxb8EPxZCV1SSwiaBS75A==, figureFileBig=sTvd2YSfu2ypnh6ZRrAaFQ==, tableContent=null), ArticleFig(id=1329420630606327856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图10, caption=基于分布式内存的图模式挖掘通信模式, figureFileSmall=UVxb8EPxZCV1SSwiaBS75A==, figureFileBig=sTvd2YSfu2ypnh6ZRrAaFQ==, tableContent=null), ArticleFig(id=1329420630656659505, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 11, caption=NVSHMEM APIs listing, figureFileSmall=s5MrKDsrgNEMF/mbU67QIw==, figureFileBig=0GYvpxtoOfmlXmMMkknGtw==, tableContent=null), ArticleFig(id=1329420630711185458, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图11, caption=NVSHMEM接口列表, figureFileSmall=s5MrKDsrgNEMF/mbU67QIw==, figureFileBig=0GYvpxtoOfmlXmMMkknGtw==, tableContent=null), ArticleFig(id=1329420630774100019, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 12, caption=UMA-based GPM communication mode, figureFileSmall=XmJM2KM5+fcLNIsMxiJYyg==, figureFileBig=7faZqgqjKgWOPCQWL+dYvw==, tableContent=null), ArticleFig(id=1329420630837014580, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图12, caption=基于统一内存架构的图模式挖掘通信模式, figureFileSmall=XmJM2KM5+fcLNIsMxiJYyg==, figureFileBig=7faZqgqjKgWOPCQWL+dYvw==, tableContent=null), ArticleFig(id=1329420630904123445, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 13, caption=UMA based graph data storage, figureFileSmall=9pqFQ7l32q3gYNEz/0GuoQ==, figureFileBig=dGVnUcD8oTRs2uObT9krHw==, tableContent=null), ArticleFig(id=1329420630979620918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图13, caption=基于统一内存架构的图数据存储, figureFileSmall=9pqFQ7l32q3gYNEz/0GuoQ==, figureFileBig=dGVnUcD8oTRs2uObT9krHw==, tableContent=null), ArticleFig(id=1329420631034146871, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 14, caption=“Binning-Merge” based communication optimization, figureFileSmall=96/wNnu4W+QiFNtSVfvY5w==, figureFileBig=7sOinZ1CHZy4il421TfNUQ==, tableContent=null), ArticleFig(id=1329420631088672824, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图14, caption=基于“分桶-聚合”的通信优化, figureFileSmall=96/wNnu4W+QiFNtSVfvY5w==, figureFileBig=7sOinZ1CHZy4il421TfNUQ==, tableContent=null), ArticleFig(id=1329420631159975993, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 15, caption=Pattern diagram used in experiment, figureFileSmall=wQvkwyInQP6S4Yhg2dAfMA==, figureFileBig=PfIaMAJKJs2edBEAHW2H8g==, tableContent=null), ArticleFig(id=1329420631218696250, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图15, caption=实验中所用的模式图, figureFileSmall=wQvkwyInQP6S4Yhg2dAfMA==, figureFileBig=PfIaMAJKJs2edBEAHW2H8g==, tableContent=null), ArticleFig(id=1329420631273222203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 16, caption=Execution time comparison of Single-GPU GPM systems on small/medium-scale data graph, figureFileSmall=dV5CwittBvY46SO9pygrDQ==, figureFileBig=fELBV8KtYZtHLG8no3798A==, tableContent=null), ArticleFig(id=1329420631323553852, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图16, caption=单GPU图模式挖掘系统在中小规模数据图的运行时间对比, figureFileSmall=dV5CwittBvY46SO9pygrDQ==, figureFileBig=fELBV8KtYZtHLG8no3798A==, tableContent=null), ArticleFig(id=1329420631382274109, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 17, caption=Execution time comparison of multi-GPU GPM systems on large-scale data graph, figureFileSmall=H+jvS7aI8KUcQVKZdzDryQ==, figureFileBig=u31Lbv8SWVGoVlXNOJRVrA==, tableContent=null), ArticleFig(id=1329420631445188670, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图17, caption=多GPU图模式挖掘系统在大规模数据图的运行时间对比, figureFileSmall=H+jvS7aI8KUcQVKZdzDryQ==, figureFileBig=u31Lbv8SWVGoVlXNOJRVrA==, tableContent=null), ArticleFig(id=1329420631508103231, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 18, caption=Computational optimization effect evaluation, figureFileSmall=LK/vGqyrE2qcGVpzO9/xkA==, figureFileBig=ECxqBofuy3epqEKWL4bUTQ==, tableContent=null), ArticleFig(id=1329420631571017792, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图18, caption=计算优化效果评估, figureFileSmall=LK/vGqyrE2qcGVpzO9/xkA==, figureFileBig=ECxqBofuy3epqEKWL4bUTQ==, tableContent=null), ArticleFig(id=1329420631629738049, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 19, caption=Communication optimization effect evaluation, figureFileSmall=xVxOpAFV9bCtZz79P05GlQ==, figureFileBig=5ePfOIXa7NMqI+a/+ocWYQ==, tableContent=null), ArticleFig(id=1329420631692652610, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图19, caption=通信优化效果评估, figureFileSmall=xVxOpAFV9bCtZz79P05GlQ==, figureFileBig=5ePfOIXa7NMqI+a/+ocWYQ==, tableContent=null), ArticleFig(id=1329420631763955779, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 20, caption=Comparison of overall utilization for GPU and CPU in eight collaborative computing scenarios, figureFileSmall=q5Ag1xYPzIwTkdY/41MHwA==, figureFileBig=GMM+69rAy7kmCrbdEE+K7Q==, tableContent=null), ArticleFig(id=1329420631826870340, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图20, caption=在8卡协同计算场景下GPU和CPU整体利用率对比, figureFileSmall=q5Ag1xYPzIwTkdY/41MHwA==, figureFileBig=GMM+69rAy7kmCrbdEE+K7Q==, tableContent=null), ArticleFig(id=1329420631889784901, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 21, caption=Scalability of Saturn system on Multi-GPU platform, figureFileSmall=O5Ct7DQ7mHz9wgheZy+viA==, figureFileBig=9c95yigy/MBAGUSB1Y40ww==, tableContent=null), ArticleFig(id=1329420631956893766, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图21, caption=Saturn系统在Multi-GPU平台上的可扩展性, figureFileSmall=O5Ct7DQ7mHz9wgheZy+viA==, figureFileBig=9c95yigy/MBAGUSB1Y40ww==, tableContent=null), ArticleFig(id=1329420632015614023, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 22, caption=Evaluation of thread group utilization on single GPU, figureFileSmall=+qdQsDH8MaYYcGSiFryr7w==, figureFileBig=nYuv4h7r5CCAc6crtBOLvA==, tableContent=null), ArticleFig(id=1329420632112083016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图22, caption=单GPU上线程组利用率评估, figureFileSmall=+qdQsDH8MaYYcGSiFryr7w==, figureFileBig=nYuv4h7r5CCAc6crtBOLvA==, tableContent=null), ArticleFig(id=1329420632179191881, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 23, caption=Impact of various thresholds on hybrid operator selection, figureFileSmall=xFBHZ4x8B/ib+oDDwu5fnw==, figureFileBig=5NGcIhw093XJcoh88Yh/AQ==, tableContent=null), ArticleFig(id=1329420632242106442, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图23, caption=不同阈值对混合算子选择的影响, figureFileSmall=xFBHZ4x8B/ib+oDDwu5fnw==, figureFileBig=5NGcIhw093XJcoh88Yh/AQ==, tableContent=null), ArticleFig(id=1329420632309215307, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 24, caption=Details of runtime and memory cost, figureFileSmall=S074q7AnMotP9JJS2sTzyg==, figureFileBig=Yr0UZTXN9Smqp8fbX4qlog==, tableContent=null), ArticleFig(id=1329420632384712780, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图24, caption=运行时间和内存开销明细, figureFileSmall=S074q7AnMotP9JJS2sTzyg==, figureFileBig=Yr0UZTXN9Smqp8fbX4qlog==, tableContent=null), ArticleFig(id=1329420632443433037, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Figure 25, caption=System communication behavior analysis, figureFileSmall=B8+//axl6PQOubV44z8Qkg==, figureFileBig=xG4TtAFF1+g0cUUngKChQA==, tableContent=null), ArticleFig(id=1329420632518930510, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=图25, caption=系统通信行为分析, figureFileSmall=B8+//axl6PQOubV44z8Qkg==, figureFileBig=xG4TtAFF1+g0cUUngKChQA==, tableContent=null), ArticleFig(id=1329420632598622287, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Table 1, caption=

Comparison of State-of-the-Art Graph Pattern Mining Systems

, figureFileSmall=null, figureFileBig=null, tableContent=
图挖掘系统运行平台并行粒度图划分策略通信方式处理
规模
计算
性能
通信
性能
G2Miner单GPU粗粒度全图备份无通信低低无
GraphSet单GPU粗粒度全图备份无通信低低无
GraphPi多GPU粗粒度全图备份无通信低低无
VSGMCPU+GPU粗粒度K跳分区CPU+PCIe高低低
G2-AIMDCPU+GPU粗粒度K跳分区CPU+PCIe高低低
GAMMACPU+GPU粗粒度K跳分区CPU+PCIe高低低
Saturn
(本文)
多GPU细粒度完全图划分GPU+
NVLink
高高高
), ArticleFig(id=1329420632669925456, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=表1, caption=

主流图模式挖掘系统对比

, figureFileSmall=null, figureFileBig=null, tableContent=
图挖掘系统运行平台并行粒度图划分策略通信方式处理
规模
计算
性能
通信
性能
G2Miner单GPU粗粒度全图备份无通信低低无
GraphSet单GPU粗粒度全图备份无通信低低无
GraphPi多GPU粗粒度全图备份无通信低低无
VSGMCPU+GPU粗粒度K跳分区CPU+PCIe高低低
G2-AIMDCPU+GPU粗粒度K跳分区CPU+PCIe高低低
GAMMACPU+GPU粗粒度K跳分区CPU+PCIe高低低
Saturn
(本文)
多GPU细粒度完全图划分GPU+
NVLink
高高高
), ArticleFig(id=1329420632737034321, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Table 2, caption=

Graph Datasets in Real World

, figureFileSmall=null, figureFileBig=null, tableContent=
数据名称
缩写
图数据名称顶点数量
V
边数量
E
最大
度数
社交MIMico0.10×1062.00×1061359
邮件ENEnron0.69×1060.27×1061391
电商AMAmazon06010.40×1062.40×1062747
道路CAroadNet-CA1.90×1062.80×10612
专利CPCit-Patents3.70×10633.00×106793
社交YTYouTube7.00×106114.00×1064017
社交LJLiveJournal4.85×10685.70×10620333
社交FRFriendster66.00×1063600.00×1065214
人工合成DGDatagen-sf10k98.70×10618800.00×1064485
), ArticleFig(id=1329420632799948882, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=表2, caption=

真实世界图数据集

, figureFileSmall=null, figureFileBig=null, tableContent=
数据名称
缩写
图数据名称顶点数量
V
边数量
E
最大
度数
社交MIMico0.10×1062.00×1061359
邮件ENEnron0.69×1060.27×1061391
电商AMAmazon06010.40×1062.40×1062747
道路CAroadNet-CA1.90×1062.80×10612
专利CPCit-Patents3.70×10633.00×106793
社交YTYouTube7.00×106114.00×1064017
社交LJLiveJournal4.85×10685.70×10620333
社交FRFriendster66.00×1063600.00×1065214
人工合成DGDatagen-sf10k98.70×10618800.00×1064485
), ArticleFig(id=1329420632871252051, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Table 3, caption=

Execution Time Comparison on Motif-Counting Applications s

, figureFileSmall=null, figureFileBig=null, tableContent=
数据集3-motif4-motif
G2MinerGraphSetSaturn
(本文)
G2MinerGraphSetSaturn
(本文)
CP1.230.910.331.872.380.44
MI0.460.340.061.340.710.42
LJ1.891.530.4445.389.855.87
YT2.652.280.827.897.333.21
), ArticleFig(id=1329420632946749525, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=表3, caption=

在主题计数应用上的运行时间对比

, figureFileSmall=null, figureFileBig=null, tableContent=
数据集3-motif4-motif
G2MinerGraphSetSaturn
(本文)
G2MinerGraphSetSaturn
(本文)
CP1.230.910.331.872.380.44
MI0.460.340.061.340.710.42
LJ1.891.530.4445.389.855.87
YT2.652.280.827.897.333.21
), ArticleFig(id=1329420633022246998, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=EN, label=Table 4, caption=

Execution Time Comparison on Frequent Subgraph Mining Applications

, figureFileSmall=null, figureFileBig=null, tableContent=
带标签数据集2-fsm3-fsm
支持度G2Miner/sGraphSet/sSaturn(本文)/s支持度G2Miner/sGraphSet/sSaturn(本文)/s
MI-290.3×1030.840.250.1410×103运行失败21.3713.55
0.5×1030.780.230.0915×103运行失败20.8613.21
YT-291×1033.652.141.271×103运行失败280.39137.94
5×1033.381.970.825×103运行失败57843258
), ArticleFig(id=1329420633080967255, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, language=CN, label=表4, caption=

在频繁子图挖掘应用上的运行时间对比

, figureFileSmall=null, figureFileBig=null, tableContent=
带标签数据集2-fsm3-fsm
支持度G2Miner/sGraphSet/sSaturn(本文)/s支持度G2Miner/sGraphSet/sSaturn(本文)/s
MI-290.3×1030.840.250.1410×103运行失败21.3713.55
0.5×1030.780.230.0915×103运行失败20.8613.21
YT-291×1033.652.141.271×103运行失败280.39137.94
5×1033.381.970.825×103运行失败57843258
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550501, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550501, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202550501, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202550501, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1788192000000, fullTextJson=null, articleText=null, reference=null)
收藏切换
Saturn: 面向Multi-GPU平台的高性能图模式挖掘系统
林志恒 , 孟轲 , 谭光明 *
计算机研究与发展 | 高性能计算 2026,63(9): 2442-2462
收起
收藏切换
计算机研究与发展 |高性能计算 2026 , 63 (9) : 2442 -2462
Saturn: 面向Multi-GPU平台的高性能图模式挖掘系统
全屏
[Author(id=1329420627762589703, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=linzhiheng@ncic.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329420627825504264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627762589703, language=EN, stringName=Zhiheng Lin, firstName=Zhiheng, middleName=null, lastName=Lin, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

"}, bioImg=null, bioContent=

born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420627884224521, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627762589703, language=CN, stringName=林志恒, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"8ECZoWGS6FiQnRNMP2T35A==","content":"

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

"}, bioImg=8ECZoWGS6FiQnRNMP2T35A==, bioContent=

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329420627955527691, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329420628014247948, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627955527691, language=EN, stringName=Ke Meng, firstName=Ke, middleName=null, lastName=Meng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

"}, bioImg=null, bioContent=

born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420628081356813, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420627955527691, language=CN, stringName=孟轲, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"GvP7CMUevhaySZOx1pQmJA==","content":"

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

"}, bioImg=GvP7CMUevhaySZOx1pQmJA==, bioContent=

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329420628219768847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=tgm@ict.ac.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329420628291072016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420628219768847, language=EN, stringName=Guangming Tan, firstName=Guangming, middleName=null, lastName=Tan, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

"}, bioImg=null, bioContent=

born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329420628412706834, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329420622796534726, authorId=1329420628219768847, language=CN, stringName=谭光明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"7THW1PQcsfBduQiccY2qjA==","content":"

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

"}, bioImg=7THW1PQcsfBduQiccY2qjA==, bioContent=

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

, aboutCorrespAuthor=null)}, companyList=null)]
林志恒 , 孟轲, 谭光明*
作者信息
  • 中国科学院计算技术研究所 北京 100190
  • 中国科学院大学 北京 100049
通讯作者:
谭光明()
作者简介:

1997年生。博士。CCF学生会员。主要研究方向为高性能计算、异构计算、大规模图数据处理

1993年生。博士,副研究员。CCF会员。主要研究方向为高性能计算、并行算法设计与优化、图计算

1980年生。博士,研究员。CCF高级会员。主要研究方向为并行程序与算法设计、领域专用体系结构、生物信息学、大数据

Saturn: High Performance Graph Pattern Mining System on Multi-GPU Platform
Zhiheng Lin , Ke Meng, Guangming Tan*
Affiliations
  • Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190
  • University of Chinese Academy of Sciences, Beijing 100049
  • born in 1997. PhD. Student member of CCF. His main research interests include high-performance computing, heterogeneous computing, and large-scale graph data processing

    born in 1993. PhD, associate professor. Member of CCF. His main research interests include high-performance computing, parallel algorithm design and optimization, and graph computing

    born in 1980. PhD, professor. Senior member of CCF. His main research interests include parallel programming and algorithms design, domain-specific architecture, bioinformatics, and big data

出版时间: 2026-09-01 doi: 10.7544/issn1000-1239.202550501
文章导航
收藏切换

图模式挖掘作为分析实体关系的核心任务,在社区检测、药物发现等领域具有广泛应用。但由于其非多项式时间复杂度,大规模图数据处理面临搜索空间爆炸与计算效率低下的挑战。现有基于GPU的加速方案虽利用并行计算提升性能,但受限于图数据幂律分布导致的线程空闲问题,以及多GPU场景下频繁的CPU介入通信开销,难以充分释放硬件算力。提出GPU图模式挖掘系统Saturn,通过计算与通信协同优化突破上述瓶颈:在计算层面,将集合操作的装载与查询阶段解耦,采用细粒度并行批处理策略动态适配哈希与二分查找算法,并结合共享内存缓存优化访存效率,显著提升线程利用率;在通信层面,构建CPU无感的全GPU通信模式,利用NVLink高带宽链路与统一内存机制实现跨设备数据直接访问,通过顶点缓存与消息聚合调度降低冗余传输与链路竞争。实验结果表明,Saturn在真实数据集上相比主流GPU图挖掘系统,实现了更高的计算并行效率与跨设备通信能效,为大规模图模式挖掘任务提供了高效解决方案。

图模式挖掘  /  分布式图处理  /  GPU  /  并行计算  /  通信优化

Graph pattern mining, as a core task for analyzing entity relationships, finds extensive applications in fields such as community detection and drug discovery. However, due to its non-polynomial time complexity, large-scale graph processing encounters challenges related to search space explosion and low computational efficiency. Existing GPU-accelerated solutions utilize parallel computing to enhance performance but often suffer from thread idleness caused by the power-law distribution of graph data and excessive CPU intervention in multi-GPU communication, which impede the full utilization of hardware capabilities. We present Saturn, a GPU-based graph pattern mining system, which overcomes the above bottlenecks through computation-communication co-optimization. At computation level, Saturn decouples the loading and querying phases of set operations, employs fine-grained parallel batch processing to dynamically adapt Hash and binary search algorithms, and optimizes memory access efficiency via shared memory caching, significantly improving thread utilization. At communication level, it establishes a CPU-free GPU communication model, leveraging high-bandwidth NVLink interconnect and unified memory mechanism for direct cross-device data access, while reducing redundant transmission and link contention through vertex caching and message aggregation scheduling. Experimental results demonstrate that Saturn outperforms state-of-the-art GPU-based graph mining systems on real-world datasets, achieving superior computational parallel efficiency and cross-device communication effectiveness for large-scale graph pattern mining tasks.

graph pattern mining  /  distributed graph processing  /  GPU  /  parallel computing  /  communication optimization
林志恒, 孟轲, 谭光明. Saturn: 面向Multi-GPU平台的高性能图模式挖掘系统. 计算机研究与发展, 2026 , 63 (9) : 2442 -2462 . DOI: 10.7544/issn1000-1239.202550501
Zhiheng Lin, Ke Meng, Guangming Tan. Saturn: High Performance Graph Pattern Mining System on Multi-GPU Platform[J]. Journal of Computer Research and Development, 2026 , 63 (9) : 2442 -2462 . DOI: 10.7544/issn1000-1239.202550501
图作为一种灵活的数据结构,能够高效表示实体间的关系,已被广泛用于建模现实世界数据。图模式挖掘(graph pattern mining,GPM)任务旨在从给定的数据图G中找出所有与模式图P同构的子图,而数据图G的规模通常远大于模式图P。这类图任务可挖掘隐藏的数据特征或实现特定模式匹配,在社区检测[1]、分子动力学[2]、药物发现[3]及异常检测[4]等数据分析领域具有广泛应用。然而,图模式挖掘问题目前尚无多项式时间解法,实际处理中需从数据图中每个顶点出发,迭代添加邻边并检查候选子图是否与目标图模式同构,这不仅需要遍历庞大的搜索空间,还需实例化大量的中间结果。
近年来,先进的图模式挖掘系统为提高搜索效率,开始采用以集合为中心的范式[5-7]。该范式的核心思路是充分挖掘模式图的拓扑信息,以此过滤掉无法形成有效最终匹配的中间结果。这类系统常将搜索过程表示为嵌套循环,每层迭代都通过由集合求交($ \cap $)等集合运算构成的表达式进行形式化描述。例如,表达式$ S\left({v}_{2}\right)=N\left({v}_{0}\right)\cap N\left({v}_{1}\right) $表示$ {v}_{2} $的合法候选集($ S\left({v}_{2}\right) $)必须是顶点$ {v}_{0} $和$ {v}_{1} $的公共邻居。以集合为中心的范式借助关系代数等价变换实现大量优化,例如AutoMine[5]通过估算集合计算的代价生成最优匹配顺序(matching order)以缩小搜索空间。GraphPi[8]结合对称性破坏(symmetry breaking)规则减少冗余搜索。这些系统大多遵循模式感知范式(pattern-aware paradigm),将模式图的拓扑信息转化为集合表达式,通过以集合为中心的抽象分析,最大限度地寻找并复用公共元素。
随着图数据规模不断增长,对高效图模式挖掘的需求愈发迫切。GPU凭借其大规模并行计算核心,以及高带宽内存(high bandwidth memory,HBM)提供的TB级访存带宽[9],成为加速图模式挖掘应用的理想硬件选择。近年来,基于GPU的图模式挖掘加速工作不断涌现,其核心围绕任务并行与算子优化2个方面展开。其中,一些系统[10-11]采用2阶段任务并行策略将GPU线程组分配至不同顶点或边的搜索任务,线程组内并行执行集合操作以实现任务的高效映射。在算子优化方面,则通过HashIndex[12],BinarySearch[13]等算法加速搜索过程中频繁调用的集合算子。但由于现实图数据的幂律分布特性导致集合求交计算量差异显著。现有系统多采用单一或粗粒度并行方案,导致GPU线程组在处理小度数顶点时线程的高空闲率问题,制约了GPU图挖掘系统的性能。
尽管借助GPU的高并行性可加速图模式挖掘算法,但单GPU有限的内存容量(如V100仅32 GB)制约了其对大规模图数据的处理能力。为突破这一瓶颈,研究者转而采用图划分策略,将庞大的图数据分散至Multi-GPU平台进行处理,期望通过并行计算与内存资源整合提升处理能力。跨GPU的顶点邻接表分布导致边连接判断需频繁传输数据,通信开销极大。现有多GPU图挖掘系统[14-16]利用CPU主存扩展GPU处理数据的规模。这些系统需要CPU来管理GPU显存上的图分区数据驻留和驱逐[15],或者依赖CPU执行显式的同步操作,让多个GPU并行处理分区内和分区间(inter/intra partition)的图挖掘任务[14]。然而,频繁的PCIe数据交换与CPU的深度介入,使得GPU计算频繁中断,造成系统GPU利用率低下且可扩展性不足。
为了应对上述挑战,本文提出GPU图模式挖掘系统Saturn。Saturn系统旨在通过计算和通信2个层面协同优化来提升图挖掘系统处理大规模图数据时的整体性能。在计算层面,我们将集合操作的加载与查询阶段解耦,通过细粒度并行将同层循环内的多个集合操作批处理,使线程组能利用空闲线程并行处理多个任务,同时根据顶点度数动态适配哈希与二分查找策略,并结合共享内存分层缓存优化访存效率;在通信层面,构建CPU无感的全GPU通信的图挖掘模式,利用GPU间NVLink高带宽链路和统一内存机制实现GPU直接访问远端图数据。通过高度数顶点缓存减少远程通信,并采用消息聚合分桶调度机制降低链路竞争与冗余传输。
本文的主要贡献包括3个方面:
1)详尽分析了GPU上现有图模式挖掘系统的并行优化方法的缺陷和性能影响。针对图挖掘任务高度不规则的计算特性,设计了细粒度并行任务调度机制,并结合混合算子策略有效解决了由于数据倾斜导致的线程利用率低下问题。
2)提出 CPU 无感的Multi-GPU图挖掘通信方案。该方案利用 GPU 内核直接管理跨设备数据传输,消除了传统模式中频繁的 CPU 干预与主从同步开销。通过引入数据缓存机制和消息聚合策略,进一步降低了冗余通信带来的链路竞争。
3)实现计算-通信协同优化的GPU图挖掘系统Saturn,并在多种真实世界数据集上进行系统性的测试与验证。实验结果表明,Saturn系统性能显著优于主流基于单GPU和多GPU平台的图挖掘系统,实现了更高的并行效率与跨设备通信效率。相比于基线系统,Saturn展现出更优的强扩展性。
在GPU架构中,计算模块和存储模块紧密耦合,共同支撑起高效的并行计算任务。如图1所示,GPU采用单指令多线程(single instruction multiple thread,SIMT)的执行模型,以Warp(通常包含32个线程)线程组为粒度,线程以锁步的方式执行同一指令流。多个Warp组成线程块(Block),而流式多处理器(streaming multiprocessor,SM)作为核心计算单元,可同时调度多个线程块执行计算任务,实现高效并行处理。另一方面,GPU存储层次采用分层设计,全局内存(global memory)用于存放计算所需的各类数据,共享内存(shared memory)作为片上高速缓存,用于同一线程块内的数据共享。在各级存储层次中,L2缓存不可编程,L1缓存则和共享内存共享同一存储空间,可根据计算任务特性动态调整分配比例。
在多GPU协同计算场景下,NVLink高速互连技术突破传统PCIe带宽瓶颈,实现了GPU 间高效直接通信。如图1所示,这类Multi-GPU的服务器通常由若干个CPU和多个GPU组成。各设备通过PCIe总线或NVLink传输线互连。在软件层面,NCCL(NVIDIA collective communications library)和NVSHMEM等通信库为多GPU并行计算提供了高效的编程接口。其中,NCCL 提供了包括NCCL_Send/Recv点对点通信以及 AllGather,AllReduce,Broadcast等集合通信原语。NVSHMEM则提供了核函数内的通信原语(如shmem_put/shmem_get),支持多设备间的单边通信。在存储层次设计上,NCCL 采用分布式内存架构,NVSHMEM 则采用统一内存架构。
图模式挖掘算法旨在从数据图中识别或统计与模式图同构的匹配实例。给定一个包含 m 条边(m > 2)的模式图$ {G}_{\mathrm{P}}=\left({V}_{\mathrm{P}},{E}_{\mathrm{P}}\right) $和数据图 $ G=\left(V,E\right) $,图挖掘算法需要找到所有的边映射关系,即$ (e\mapsto \hat{e}) $,其中$ e\in {E}_{\mathrm{P}} $且$ \hat{e}\in E $,使得匹配实例子图 $ \{{\hat{e}}_{0},{\hat{e}}_{1},… ,{\hat{e}}_{m-1}\} $ 与模式图$ {G}_{\mathrm{P}} $同构。近期研究[5-7]表明,图挖掘算法可通过以集合为中心的抽象进行描述,并借助集合求交等集合运算实现计算逻辑。因此,图挖掘算法的搜索过程呈嵌套循环结构:在第i层嵌套循环中,生成第$ {e}_{i} $的候选集供下一层循环枚举。当数据图的所有边均与模式图中的边匹配时,程序终止。为避免搜索过程中产生自同构(automorphism)的子图,图挖掘系统[5,7-8]通常采用对称性破坏规则对匹配顶点进行约束,即$ {vid(v}_{i})< {vid(v}_{j}) $,$ vid $为数据图顶点序号。另外,系统[5, 7-8]会根据模式图特征选择最优的匹配顺序构成程序的嵌套循环。
算法1展示了4-团(4-clique)模式挖掘的执行流程伪代码。考虑到对称性破坏规则,要求$ v{id(v}_{0})< {vid(v}_{1})< {vid(v}_{2})< {vid(v}_{3}) $。最外层循环遍历数据图中的所有顶点,并将其作为搜索的起始根节点。每个根节点维护各自的搜索状态并保存到候选集合S中。迭代轮次和模式图尺寸有关(图中迭代轮次为4轮),每轮迭代负责匹配在数据图中匹配模式图的1个顶点。在每次迭代开始时,首先读取此前的部分匹配结果,然后枚举当前候选集合S中的每个顶点$ {v}_{i} $,根据模式图的连通性,对匹配结果和$ N({v}_{i}) $执行集合运算,生成下一轮遍历的新候选集合,同时更新搜索状态。在搜索完成后,程序输出匹配数量或者所有匹配结果。
算法1. 基于集合求交的4-团模式挖掘算法。
输入:数据图$ G(V,E) $,模式图${G}_{\mathrm{P}}\left({V}_{\mathrm{P}},{E}_{\mathrm{P}}\right) $;
输出:所有4-团的匹配结果$ e。 $
① for $ {v}_{0}\in V $ do /* 任务并行 */
②  S1 =$ {N(v}_{0}) $;
③ for $ {v}_{1}\in {S}_{1} $ do /* 串行执行 */
④   S2 = $ {S}_{1}\cap {N(v}_{1}) $;
⑤  for $ {v}_{2}\in {S}_{2} $ do /* 串行执行 */
⑥    S3 = $ {S}_{2}\cap {N(v}_{2}) $;/* 算子并行 */
⑦   for $ {v}_{3}\in {S}_{3} $ do
⑧    return e {v0, v1, v2, v3};
⑨   end for
⑩  end for
⑪ end for
⑫ end for
1)图数据特征。真实世界的图数据通常展现出幂律分布的特性,即有少量高度数顶点和大量低度数顶点。图2(a)展示了不同图数据的顶点度数分布情况,在OR和LJ图数据集上,最大度数超过1万而顶点的邻居数量平均值则在100以内。而对于YT和MI而言,其顶点的平均度数则低于32。在图挖掘场景中,由于嵌套循环结构特性,程序需要反复遍历图中的顶点和边,这种幂律分布带来的数据倾斜被进一步放大,导致任务的负载不均问题更加严重。我们对4-团匹配任务进行了分组统计。在图2(b)中不同数据块上4-团匹配数量呈现出显著差异,最高和最低的4-团匹配数量差距近30倍。这种负载不均现象并非4-团模式挖掘任务所独有,在频繁子图挖掘(frequent subgraph mining)、主题模式挖掘(motif finding)等其他图模式挖掘场景中同样普遍存在。这意味着在执行搜索任务时,处理包含高度数顶点的数据块所需要的计算资源和时间远超其他数据块,使得数据图中不同顶点的搜索任务负载不均,制约了图挖掘系统性能。
2)GPU图挖掘中的任务并行和算子并行。现有工作[10-11]通常采用2阶段并行来提升GPU图挖掘系统性能,即线程组内和线程组间并行。在线程组间,系统以固定线程组(比如GPU的Warp)为粒度进行任务划分,并行处理数据图中的单个顶点或者边上的搜索任务(算法1中行①的任务并行)。另一方面,集合计算需要频繁的内存访问,检查顶点之间的连接关系。线程组内的所有线程并行处理搜索过程的集合操作以实现算子并行(算法1中行⑥的算子并行)。而中间的迭代中,线程组以串行的方式遍历搜索树(算法1中行③和行⑤)。因此,GPU的图挖掘系统呈现出任务和算子2个层级的并行特性。
由于图挖掘任务的负载不均问题,一些工作[17]采用混合线程组映射技术进行任务分配。该技术根据顶点的度数对任务进行分桶。采用GPU的线程块、Warp, Thread 这3个并行粒度处理不同度数的搜索任务。对于高度数顶点,使用线程块协作处理任务可避免过多的任务成为程序拖后腿的部分。相反,对于低度数顶点,使用更多的线程并不会带来性能提升,通常用Warp和Thread处理。尽管任务并行和算子并行通过分层设计提升了GPU利用率,但现有方案[10-13]普遍忽略了搜索树遍历过程中内层循环的串行执行特性,导致GPU资源利用率不足。
算法2. 集合求交的2种底层实现。
输入:有序数组List1和List2;
输出:公共元素数组List。
① function BinarySearchIntersect(List1, List2)
② for $ key\in {List}_{1} $do
③  if BinarySearch(List2, $ key $) = true then
④    List.append($ key $);
⑤  end if
⑥ end for
⑦ return List;
⑧ end function
⑨ function HashIndexIntersect(List1, List2)
⑩  for value $ \in {List}_{2} $ do
⑪   Hashtable.insert(value);
⑫  end for
⑬  for $ key\in {List}_{1} $ do
⑭   if Hashtable.lookup($ key $) = true then
⑮     List.append($ key $);
⑯   end if
⑰  end for
⑱  return List;
⑲ end function
3)集合操作实现。集合求交计算是图挖掘中的核心操作。该操作的输入为2个整数有序数组A和B,在图挖掘场景中表示为顶点的邻居$ N({v}_{i}) $或是候选集$ S({v}_{i}) $。算法输出为这2个数组的共同元素。在GPU的SIMT架构上,通常采用2种实现方法:二分查找求交(binary search intersection)和哈希查找求交(Hash index intersection)。如算法2所示,基于二分查找的求交算法将2个数组中较长的数组组织为二叉树结构(search list),以较短列表中的元素作为搜索键值(key list)。对于每个搜索键值,算法通过遍历二叉搜索树来查找匹配项。该方法的时间复杂度是O(nlog(n))。一些研究工作[5,8,10,13]在图挖掘中系统采用二分查找法实现集合操作。另一方面,基于哈希查找法的求交算法则为其中一个数组构建哈希表,再以另一个列表的元素为搜索键,在哈希表中查找公共元素。当发生哈希冲突时,通常采用线性探测机制解决冲突。该方法的时间复杂度为O(n),但需要占据额外的内存空间存储哈希表。另一些研究工作[12,17-18]在图挖掘系统中采用哈希查找法实现集合操作。综合来看,二分查找法的搜索效率低,但其不需要占用额外的存储空间。而哈希查找法则采取以空间换时间的思路提升查找效率。
由于异构设备的显存容量有限,难以处理大规模图数据。以英伟达的32 GPU显存的V100显卡为例,单个V100的显存无法处理如Datagen-sf10k(70 GB)这样的大图数据[19]。一些工作[14-16]利用CPU主存扩展图数据处理规模。这些工作通过将原始图数据划分成多个分区并流式传输到不同GPU进行处理。由于带匹配的模式图通常尺寸较小,因此搜索范围不会超过K跳邻居(K为模式图的直径)。利用这一局部性特征,VSGM[15]在CPU主存上构建多个具有重叠部分的图数据分区,在分区内包含其内部顶点搜索所需的全部图拓扑数据。图3展示了利用CPU主存扩展的多GPU协同计算方案。其中CPU管理图数据以及分区数据传输,不同的GPU并行处理各自的分区数据,在本地进行无通信的图挖掘任务。然而,这种重叠策略在每个分区中冗余存储K跳邻居,导致额外的预处理开销和内存资源浪费。更严重的是,该方案需要频繁地进行低速PCIe数据传输,忽略了GPU互连拓扑和直接通信的特性,拖慢了多GPU的计算效率。
本文提出面向Multi-GPU的高性能图模式挖掘系统Saturn以充分发挥多个异构设备的计算和通信能力。如图4所示,Saturn系统包含2个模块:计算引擎和通信引擎。其中,计算引擎负责并行本地的图挖掘任务。为提升计算效率,我们在计算引擎中设计了细粒度并行的集合求交优化方法(将在第2节中详细介绍)。另一方面,通信引擎负责GPU设备间的数据传输。与先前方法不同,通信引擎充分利用NVLink高带宽特性,在内核函数内直接发起通信请求获取远端邻居数据(通信技术将在第3节中详细介绍)。在图挖掘执行过程中,图数据和迭代产生的中间结果保存在各个GPU的显存上。总的来说,Saturn系统通过计算引擎和通信引擎以实现计算和通信的协同优化。
表1 呈现了当前主流图挖掘系统的核心特性对比。其中,G2Miner,GraphSet,VSGM,G2-AIMD,GAMMA均属于基于GPU架构的图挖掘系统,GraphPi则为CPU图挖掘系统。在计算优化层面,现有系统普遍采用粗粒度并行方案,但该模式难以适配图数据的不规则分布特性,易引发线程负载不均衡问题,制约计算效率。在通信优化层面,G2Miner,GraphSet,GraphPi通过全图备份策略完全规避设备间通信以换取性能,但这些系统受限于显存容量,无法支撑超设备存储上限的图挖掘任务;VSGM,G2-AIMD,GAMMA所采用的K跳分区策略,因依赖CPU参与数据传输,在处理大规模图数据时性能表现受限。相比之下,本文提出的Saturn系统实现计算与通信优化的协同设计,通过细粒度并行策略结合CPU无感通信技术,在保障高计算性能与通信性能的同时,能够支持大规模图数据挖掘任务的高效执行。具体而言,Saturn利用完全图划分与GPU+NVLink互连技术,有效规避了 CPU 通信开销,实现了更优的多卡扩展性。
图数据的度数分布特性与GPU线程组执行模型之间的不匹配,是制约图挖掘系统性能的关键瓶颈。在图5中,我们对真实图数据集LJ和YT的累积度数进行统计。从图5中可以看到YT度数小于32的顶点占比达91.17%,度数低于256的顶点占比更是超过99%。在LJ中二者比例分别为86.04%和99.48%。这种长尾分布特征导致传统的粗粒度线程分配策略(大度数任务用线程块处理,小度数任务用Warp处理)产生大量的线程空闲,造成显著的计算资源浪费。以4-团模式挖掘算法的内层循环为例(如算法1的行⑤⑥所示),我们需要串行遍历候选集S中的每个顶点v2,对候选集S和顶点v2的邻居列表执行集合求交计算。当采用32线程的Warp作为基本执行单元时,即使操作数规模仅为4~16,仍需完整地占用1个Warp周期,导致平均每个周期存在12.5%~50%的线程处于空闲状态。
图6展示了4-团模式挖掘的内层循环计算的例子。为简化描述,假设Warp包含4个线程。图6中当前匹配的候选集$ {S}_{2}=\left\{1,~2,~3,~4\right\} $,计算循环需要遍历集合S2内的顶点执行集合求交产生下一层候选集S3。由于S2的大小为4,本层迭代总共执行4次集合操作,即$ {S}_{2}\cap N\left(1\right),{S}_{2}\cap N\left(2\right),{S}_{2}\cap N\left(3\right),{S}_{2}\cap N\left(4\right) $,占用4个Warp执行周期。在执行$ {S}_{2}\cap N\left(4\right) $时,由于顶点4仅有一个邻居顶点5(根据破坏对称性规则,仅考虑顶点vid比当前顶点大的情况),导致Warp内仅有1个活跃线程。在图6中展示的4个Warp执行周期中共产生9次线程空闲,有效的线程执行率仅56.25%,造成严重的计算效率损耗。类似地,对于大度数顶点处理采用的线程块级并行策略同样存在算力浪费问题。这种以固定线程组粒度处理单一集合操作的策略,本质上延续了串行算法的执行模式,无法适应图数据的幂律分布特性。当处理小规模操作数时,线程组内大量线程难以避免地处于计算空闲状态。
现有方法仅考虑算子内并行是导致线程空闲的原因。在图挖掘应用中,传统集合操作的处理模式呈现“算子内并行、算子间串行”的局限性。当前流程通常为“数据准备”与“集合求交”的交替循环执行,即每次仅能处理单一集合操作的2个操作数,由线程组完成当前任务后再进入下一轮计算。这种粗粒度的算子并行的核心问题在于任务粒度与线程组粒度的静态绑定:当处理小规模操作数,如小度数顶点邻居$ N({v}_{i}) $时,固定线程组(包含32个线程的Warp)因负载不足导致大量线程空闲,而串行执行的多个集合操作被割裂为独立任务单元,进一步加剧资源浪费。图挖掘算法的迭代循环特性(如第i层循环需对候选集S与多个顶点邻居$ N({v}_{i}) $依次求交)隐含重要优化机会:同层循环内的多个集合操作共享公共操作数S,且各操作的计算逻辑高度一致。若能打破“单次操作独占线程组”的静态约束,将线程组从单一操作的固定绑定中释放,使其能够利用空闲线程并行处理循环内的多个集合操作(如同时计算不同顶点的$ N({v}_{i}) $与S的交集),则可显著提升资源利用率。
集合操作的细粒度展开是获取算子间并行性的关键。集合操作通常包含装载与查询这2个阶段:前者需将邻居列表或哈希表加载为待查列表,后者则需在待查列表中检索另一列表的键值。针对图挖掘迭代循环中多个集合操作共享公共操作数S的特性,装载阶段可优化为仅需一次性并行加载共享操作数S,避免重复数据搬运;而线程空闲主要发生于于查询阶段:循环内依次将$ N({v}_{i}) $中的数据作为键值在共享操作数S中查询时产生了大量线程闲置。现有方法是粗粒度地对集合操作按线程组计算,忽略了装载阶段的操作数重复和查询阶段列表的长度差异。如图7所示,若能对查询阶段的键值进行细粒度并行,让线程组内每个线程负责单个键值的查询任务,则可使得线程空闲次数减少到1次。由此可见,细粒度展开集合操作的2阶段流程,针对查询阶段的多操作并行性进行调度优化,是解决线程空闲的潜在机会。
为了利用上述优化机会,我们提出了细粒度并行的计算优化方案来处理线程空闲的问题,将单次循环内的多个集合操作进行批处理。考虑到集合操作的这2个阶段,我们利用线程组并行加载待查列表,而在查询阶段让线程组内的每一个线程并行查询循环内操作数的每个键值。
1)查询阶段的细粒度并行。区别于传统的以集合操作为中心的粗粒度并行,细粒度并行将集合操作的装载和查询阶段解耦。首先,我们通过前缀和(prefix sum)计算邻居列表的长度和偏移地址。线程组内每个线程根据偏移索引到对应的顶点邻边和对应的邻居顶点vid。每个线程根据vid获取单个顶点作为键值,在待查列表中查找是否命中,执行顶点连接关系判断。每个线程独立计算索引并进行查询,查询过程可以并行执行且无数据依赖。当前周期内线程查找完毕,所有线程读取线程组内最后一个线程处理的顶点vid,更新各自要处理的下一个任务索引。重复上述过程直到循环内所有集合操作的查找任务结束。在索引更新阶段,以Warp为粒度的线程组采用__shfl_sync和__syncwarp原语进行Warp内线程索引通信。以线程块为粒度的任务并行则采用共享内存的索引数组shared_idx[]和__syncthreads原语进行通信。
图8展示了细粒度并行的计算流程。该流程描述了用Warp处理图7 中$ {S}_{2}\cap N\left(1\right),{S}_{2}\cap N\left(2\right) $这2个集合操作。首先每个线程判断tid是否超过邻居边界,由于$ N\left(1\right)=\left\{2,~3,~4\right\} $,线程3重新计算待处理的顶点和边。在读取邻居阶段,每个线程根据vid和eid读取各自的邻居数据作为键值,并在查询阶段并行执行查询任务。在索引更新阶段,线程3则在线程组内广播vid和eid,为下一个Warp执行周期做数据准备。
2)装载阶段的混合算子策略。现有的工作采用2种不同的集合操作实现,即哈希查找法和二分查找法。对于哈希查找法,其装载阶段需要对查列表构建哈希表。而对于二分查找法则是构建二叉搜索树。而我们发现真实世界图数据中的度数的大小会影响这2种方法的效果。在图9中,我们展示了2种集合计算方法在LJ和FR这2个数据集上不同度数区间的性能差异。我们可以看到在大度数任务中,哈希查找法的效果优于二分查找法。而在处理小度数任务时,由于装载阶段引入了建表的开销,哈希查找法的加载效率低于二分查找法。因此,我们通过设置度数阈值的方式来混合使用2种集合计算方法。对于度数大于阈值的顶点,我们采用哈希查找方法;而对于度数小于该阈值的顶点,则使用二分查找法。度数阈值是一个经验参数,在实验设置中,我们采用阈值256来区分这2种方法。
此外,装载阶段可以进一步对访存进行优化,对于低度数顶点,可将构建的二叉搜索树缓存至共享内存中。由于小度数顶点的邻居规模较小,共享内存的高速访问特性能够显著减少不规则的二分查找对访存的影响。对于大度数的哈希表结构,我们将哈希表的前k层数据缓存至共享内存,若未命中则退化成全局内存的哈希表查找。分层缓存策略能够提升高频访问的哈希表关键层读取性能,降低查询阶段的访存延迟。
在分布式内存的系统中,GPU间通过NCCL通信库进行消息传递。在这种通信模式下,GPU负责将通信数据在核函数内准备好,再通过CPU发起通信请求将数据通过NVLink发送到目的GPU。在分布式图模式挖掘场景中,由于图数据分布在不同的GPU设备上,其通信主要是在传递邻居列表。由于NCCL库依赖于CPU控制通信,每个GPU无法直接访问其他GPU的设备内存来获取顶点及其邻居数据。在这种情况下只能通过CPU调用ncclSend/ ncclRecv等显式通信方式完成。另外,为了最小化通信启动开销并充分利用带宽,需将发往相同GPU的数据进行聚合并批量发送。图10介绍了在分布式内存场景下多GPU间如何进行通信来协作完成图模式挖掘。图10中展示的2个GPU分别存放奇数顶点和偶数顶点及其邻居数据。在搜索过程中,GPU0需要顶点0,1,2,3的邻居数据,GPU1则需要顶点4,5,6,7的邻居数据。由于数据分布在本地和远端,此时GPU需要对所需数据按目标设备进行重排和分桶(如图10中的步骤①所示)。在目标GPU接收顶点之前,需先传输顶点数量,再传输实际顶点vid(如图10中步骤②所示)。每个GPU在获取所有顶点vid后,在步骤③对其他GPU所需邻居数据执行本地批量写入操作。随后在步骤④中,所有聚合后的顶点邻居数据将被回传,在多个GPU间执行邻居交换操作。由此可见,若采用CPU协同的多GPU图挖掘方案,不仅需要大量通信操作,还需多次同步操作以避免读写冲突,这导致了更高的通信量和内存带宽占用。
考虑英伟达原生的GPU通信技术和编程框架。其中最值得关注的是NVSHMEM库,它为细粒度(几字节到几十字节)的GPU间通信提供了内核级接口,如图11所示。本地GPU的数据可直接访问,而远端数据的读取则通过NVSHMEM API函数nvshmemx_TYPENAME_get_warp实现,该函数将所需数据传输至本地共享内存(TYPENAME可为int/float/double等常见数据类型)。类似地,远端访问支持按Thread/Warp/线程块为粒度进行通信。另外,NVSHMEM提供统一内存注册函数nvshmem_malloc将数据放置共享内存区域。
传统的GPU通信框架通常将数据传输分为2条路径:数据实际移动的路径,以及包含消息准备、触发数据移动和向远程进程发送信号的通信控制路径。大多数框架虽支持GPU到 GPU的数据移动路径,但仍将控制路径实现在CPU 上,这导致了额外的控制延迟和同步开销。在本工作中,我们采用CPU无感的GPU通信模式,将这2条路径均实现在GPU上,从而显著降低了控制路径延迟,并减少了跨设备同步开销。这些改进共同使得核函数内通信变得可行且具有潜在优势。具体而言,在具有NVLink互连的多GPU系统上,我们能对同一节点上远程GPU内存进行直接读写操作,从而将整个集群构建成一个统一内存架构(unified memory architecture,UMA),后文简称“统一内存”。在底层实现上,我们采用NVIDIA的NVSHMEM库及其提供的GET/PUT/ATOMIC原语。这一机制将所有控制逻辑保留在GPU上,无需CPU干预。通过这种设计,我们不仅充分利用了GPU的并行计算能力处理通信控制逻辑,还避免CPU与 GPU间的数据传输开销,实现更高效的核函数内通信。
在统一内存架构的多GPU系统中,每个GPU可以直接访问其他GPU的设备内存,因此只需要在每个GPU上在内核函数内读写远端地址即可完成通信操作。如图12所示,GPU在执行本地图挖掘的搜索任务时,如果所需的邻居数据不在本地,则根据远端数据所在的地址直接读取远端内存并将邻居列表写入本地,继续执行后续的搜索任务。这种方法消除了分布式内存下多GPU通信时的数据重排和跨GPU同步开销。在这个过程中GPU上不同的SM将同时发起单边通信请求。这样的单边通信模式仅需1个步骤,减少了冗余的通信量和占用更低的网络带宽。
考虑分布式环境,我们需要进行图划分来处理更大规模的图数据,本文采用1维图划分方法[20]。将输入图的顶点集V划分为N个部分( $ {V}_{0},{V}_{1},… ,{V}_{N-1} $),其中 N 为GPU设备数量。GPU设备 i($ 0\leq $i$ \lt N $)会在其全局内存中保存与 Vi相关的所有图数据,即与Vi相关的所有边和邻居数据。为确保数据分布均衡,我们采用与Khuzdul[20]一致的图划分哈希函数。顶点所属的GPU设备号由哈希函数$ H\left(v\right) $决定,该函数将顶点 v 映射到对应的设备ID上($ 0\leq $ID$ \lt N $)。每个GPU设备上包含映射到它的顶点子集以及与这些顶点相连的所有边。
我们采用压缩稀疏行(compress sparse row,CSR)格式存储图结构,并将其划分为多个数据分区。每个分区包含一组顶点及其对应的邻居顶点数据,索引和实际数据均位于统一内存空间中。为支持内存共享下的快速邻居访问,我们为每个GPU维护一个邻居地址指针,该指针记录了每个顶点在统一内存中的起始和结束地址。我们通过邻居地址指针确定目标顶点所在的GPU并获取其地址。本地GPU上的数据可直接访问,而远程数据则按Warp为通信粒度传输到本地。例如,若顶点vi存储在GPUi上,指针m的第i个条目记录顶点vi在GPUi上的内存地址,第i + 1个条目则记录顶点vi+1的内存地址。
传统1维图划分方法与GPU内存共享设计结合时,会因未充分考虑高度数顶点对通信的影响而产生显著通信开销。为此,我们提出基于高度数缓存(high degree caching,HDC)的优化策略,即将高度数顶点的邻居数据备份存储至每个GPU设备内存中,通过将高度数顶点的远程访问转换为本地读取,显著降低通信量。尽管备份高度数顶点会引入数据冗余并增加存储需求,但这一代价可被通信开销的显著降低所抵消,该特性在处理具有偏斜度分布的真实世界图数据时尤为关键。
图13展示了基于统一内存架构的图数据存储:统一内存区域存储了图的CSR索引结构和图拓扑数据。在私有内存区域,每个GPU保存图挖掘过程中的搜索状态和高度数顶点的邻居数据备份。在搜索过程中,系统根据哈希函数决定是从本地还是远端获取邻居列表(包含顶点索引和加载邻居2个步骤),在得到邻居列表后,即可执行后续的集合操作。
1)CPU无感的图模式挖掘算法。算法3展示了CPU无感的图模式挖掘流程,该算法主要通过单边通信实现跨GPU数据访问。在CPU端,CPU主机端先通过1维图划分生成子图分区(算法3的行⑩),再将顶点列表和边列表注册到统一内存空间并加载至各GPU(算法3的行⑪⑫),为内核函数的跨设备直接访问提供数据基础,后续的图模式挖掘过程中的计算和通信则完全交由GPU核函数负责。在GPU端,gpu_graph_mining核函数遍历本地顶点集合并对每个顶点v0通过get_neighbours以单边通信方式获取其邻居列表v0_adj,再递归遍历v0的邻居v1并获取v1_adj,通过计算2组邻居的交集统计子图模式数量(算法3的行②~⑧,以4-团匹配为例)。
算法3. CPU无感的图模式挖掘算法。
① function GPU_graph_mining(g)
②  for each v0 in g.V
③    v0_adj = g.get_neighbours(v0);
   /* 本地访存 */
④   for each v1 in v0_adj
⑤     v1_adj = g.get_neighbours(v1);
    /* 单边通信 */
⑥     count += intersect(v0_adj, v1_adj);
⑦   end for
⑧  end for
⑨ end function
⑩ function graph_mining_program( )
⑪   g = graph_1D_partition( );
⑫   register_memory(v_list, e_list);
  /*注册统一内存*/
⑬   load_graph(g, v_list, e_list);
⑭   GPU_graph_mining (g);
⑮ end function
2)基于消息聚合的通信优化。在多GPU的分布式图挖掘场景中,远端数据访问面临显著挑战。一方面,不同SM可能同时发起对同一远端GPU数据的请求,受限于NVLink端口资源,易引发链路冲突与带宽竞争,从而降低数据传输效率;另一方面,多次重复邻居数据请求会产生大量冗余通信,且图挖掘的动态性与不确定性导致远端数据访问时机难以预测,进一步加剧通信低效问题。
为解决上述问题,我们提出基于消息聚合的通信优化策略。具体而言,在本地设备内存上系统为各GPU配置多消息队列,依据目的GPU对SM发起的数据请求进行分桶调度(如图14所示,通过 GPU_ID与vid映射关系,将请求定向分配至对应 GPU队列),从而规避同一远端GPU链路的竞争冲突;针对同一目的GPU的请求队列,在获取邻居数据之前,我们对重复邻居数据通信采取聚合处理,合并冗余请求。该策略适配图挖掘任务特性,有效缓解链路竞争与冗余传输问题,提升GPU带宽利用率。
1)硬件和软件环境。实验在2个硬件平台进行:在单节点平台上,测试采用1台配有8块A100 GPU的Linux服务器,单卡的显存容量是40 GB,GPU之间通过300 GBps带宽的NVLink实现高速互连, CPU使用2颗AMD EPYC 7763,总共128核。在多节点平台上,测试采用1个8节点集群(每个计算节点包含4块V100 GPU),单卡的显存容量是32 GB,GPU间采用150 GBps带宽的NVLink互联,节点间采用100 Gbps带宽的InfiniBand互联。软件环境方面,操作系统版本为Ubuntu 22.04。采用的CUDA版本是12.2,NVSHMEM版本是3.0.6。GPU程序编译使用nvcc 编译器,启用-O3优化选项以提升执行效率。构建工具CMake的版本为3.28,gcc 编译器版本为11.4.0。
2)数据集和模式图。实验中我们采用了来自SNAP[21]和LDBC[19]的真实世界和人工生成图数据。如表2所示,这些数据集包含7个中小规模数据集(图边数分别达百万级和千万级),用于评估单GPU图挖掘系统性能,以及2个大规模图数据FR和DG(图边数达10亿级)用于测评多GPU协同计算的图挖掘系统。具体而言,CP是专利之间的引用图;EN是电子邮件通信图;AM是亚马逊电商产品购买数据图;CA则是道路网络图;在社交网络类别中,MI刻画作者合作网络,YT属于网页图类别,FR和LJ则是具有倾斜顶点的社交网络图。DG是用LDBC工具生成的大规模社交网络数据。此外,如图15所示,实验选取9个典型模式图(顶点数量为3~6个)作为测试基准,这些模式图在图挖掘系统评测领域已被广泛应用[6-7,14-15],能够有效验证系统在不同计算场景下的性能表现。
3)对比系统。为全面评估本文方法的性能,我们选取多个主流GPU上的图挖掘系统作为对照,具体包含G2Miner[10],GraphSet[11],VSGM[15],G2-AIMD[16],GAMMA[22]。在单GPU系统方面,G2Miner和GraphSet将整个数据图存储在GPU的显存上,并采用高效并行策略与高性能集合算子优化计算效率。Multi-GPU系统GAMMA在处理小图时支持该种图存储模式。因此我们选择这些系统来评估本文方法在处理小规模数据上的计算优化效果。
在多GPU协同计算场景中,VSGM,G2-AIMD,GAMMA采用CPU-GPU混合内存架构存储数据图,以支持更大规模图挖掘任务。因此我们选择这些系统来评估Saturn在处理大规模数据上的效果。考虑到图挖掘问题的NP难特性,所有对比系统均采用相同的匹配顺序(matching order)和对称性破坏(symmetry breaking)规则,以确保实验结果的公平性。
实验评测方法分为以下3个维度:
1)端到端性能对比。4.2节通过单GPU与多GPU场景下的端到端性能测试,验证Saturn在不同规模数据处理中的效率优势。首先通过单GPU环境下的对比测试,验证Saturn在不依赖通信优化时的计算效率优势;其次展示了在多GPU协同计算场景中,对比Saturn与现有系统的整体性能表现;最后展示了单GPU上不同系统在处理主题计数应用的性能差异。
2)性能优化效果评估。4.3节聚焦Saturn核心优化策略的量化效果,通过消融实验揭示各模块对系统性能的贡献度,评估系统在GPU内和GPU间整体的算力利用率以及可扩展性。首先深入分析计算效率提升的主要来源;然后重点评估数据缓存与消息聚合策略对通信性能的优化效果;接着讨论CPU无感调度机制对多GPU协同的影响;最后通过多卡集群测试验证Saturn的强扩展性表现。
3)系统微基准测试分析。4.4节通过微基准测试评估系统运行时的计算、存储及通信开销行为,以体现优化方法的低开销特性。首先探究细粒度并行技术对GPU线程组利用率的提升;然后讨论不同阈值选择对GPU混合算子策略性能的影响;接着展示系统运行时的时间分布和内存占用情况;最后则讨论了多卡协同计算时采用统一内存架构和NCCL传统分布式内存架构在NVLink带宽利用率和延迟的差异。
4.4节评估系统在GPU内和GPU间整体的算力利用率以及可扩展性。首先探索细粒度并行技术对GPU线程组利用率的提升;其次讨论CPU无感调度机制对多GPU协同的加速作用;最后实验通过8卡集群测试验证Saturn的强扩展性表现。
1)单GPU图挖掘系统对比。为了评估Saturn系统的计算效率,我们将其与G2Miner,GraphSet和单GPU版本的GAMMA这3个主流的单GPU图模式挖掘系统进行对比。我们选择7个中小规模的数据图(CP,MI,YT,LJ,EN,AM,CA)和全部的9个模式图(P0,P1,P2,P3,P4,P5,P6,P7,P8)展开性能评估,所有数据图均存储于GPU显存中。端到端性能对比结果如图16所示。实验结果显示,Saturn在所有测试场景中性能均优于G2Miner,GraphSet,GAMMA,相对三者的平均加速比(几何平均值)分别达2.51、3.73和8.76,最高加速比分别达7.28、12.32和42.81。整体来看,Saturn 的运行速度在各类场景下都有明显优势。
在数据图方面,小图普遍存在平均度数较低的特征,这使得传统图挖掘系统在执行过程中产生大量线程空闲,制约了计算效率。而Saturn的细粒度并行方法可以充分利用线程组的并行性,在小数据集(如MI等大部分顶点度数偏低的数据集)上对比G2Miner平均取得2.8的加速比。在模式图方面,我们发现随着模式图结构复杂度提升,Saturn 的性能优势越发显著。以处理YT数据图为例,在挖掘简单模式(如模式图P0)时,Saturn系统相比于GraphSet取得1.7的加速比,而当面对复杂的模式图(如P3和P4)时,最高可取得2.6的加速比。在处理P8这种包含6个顶点模式图时取得了5.95的加速比。这是由于复杂模式图涉及更多嵌套循环,线程负载不均问题更为突出,进一步加剧了线程空闲。而我们的计算优化方法能够有效缓解负载不均衡问题,更好地适配复杂模式图的挖掘过程。总的来说,本文的计算优化方法能够应对数据图和模式图的不同组合场景。
另外,GraphSet作为GPU自动代码生成系统,为支持任意模式图引入额外运行时开销,这使其在处理非规则模式图(P1和P2)时,性能显著低于G2Miner和Saturn系统。
2)多GPU图挖掘系统对比。如图17所示,我们在8个A100 GPU的服务器上将Saturn与VSGM,G2-AIMD和GAMMA这3个多GPU协同计算的图挖掘系统进行性能对比。为屏蔽计算优化对通信性能的影响,在实验中我们采用基础版本Saturn(w/o opt)(和基线保持相同计算能力)和开启第2节介绍的计算优化版本Saturn进行测试。我们使用2个大规模数据图FR和DG,在全部9个模式图(P0,P1,P2,P3,P4,P5,P6,P7,P8)。由于数据图和中间结果内存开销超过单GPU显存,多GPU协同计算系统需要对数据图进行图划分。实验结果表明:优化后的Saturn能处理更大的图数据,而GAMMA在P0~P7时,DG图数据上会用尽内存(图中OOM),在最复杂的P8上,GAMMA、VSGM、未开启优化的Saturn运行时间远超4 h,而优化后的Saturn能在数百秒内完成计算;Saturn较 VSGM,G2-AIMD,GAMMA在不同数据及模式图下,平均加速比分别达12.3(最高20.4)、6.2(最高13.8)和59.7(最高85.5);另外,Saturn较Saturn(w/o opt)平均性能提升1.44倍。性能优势主要来源于2个方面:VSGM和G2-AIMD依赖于CPU传输数据图,性能受PCIe低带宽的限制。Saturn采用CPU无感的调度策略,充分利用GPU间NVLink的高带宽特点。而GAMMA并没有将CPU的PCIe数据传输和GPU计算进行掩盖,导致处理大图时性能劣于其他3个系统。另一方面,在处理复杂模式图时,VSGM和G2-AIMD采用的K跳分区方法会增大分区直径,导致数据通信量激增。Saturn通过消息聚合和数据缓存优化,降低了GPU间通信开销,由此实现相较于对比系统的性能优势。
3)图挖掘应用性能对比。我们选取主题计数(motif counting)和频繁子图挖掘(frequent subgraph mining,FSM)作为典型图挖掘应用展开性能分析。主题计数旨在识别固定顶点数量的高频模式,其搜索需同时查找多个模式。频繁子图挖掘的核心目标是在带标签的属性图中,挖掘出现频率高于预设阈值(即支持度)的子图结构。
在主题计数应用上,我们测试了单GPU配置下不同系统在处理3-motif和4-motif这2类应用在4个数据集上的性能表现,结果如表3所示。所有场景下,Saturn的性能均优于G2Miner 和 GraphSet,平均加速比分别达4.59和3.21,最高则为7.66和5.67。这表明在处理多模式查询时,Saturn 的细粒度并行机制能发挥更大优势,显著减少冗余计算与线程闲置。
在频繁子图挖掘应用上,我们选取带标签版本的属性图MI-29和YT-29(这2个图上顶点均有29类标签)上验证Saturn系统处理异构图的能力,其中2-fsm和3-fsm这2类应用的性能对比如表4所示。实验结果显示,Saturn系统相较于G2Miner 和 GraphSet分别取得平均5.84和1.87的加速比,在标签数量多、结构复杂度高的异构图挖掘任务中依旧保持稳定高效,充分验证了Saturn在异构图上执行频繁子图挖掘任务的高效处理能力。
1)计算优化的性能分析。为了评估Saturn系统在单GPU上计算优化对性能的影响,我们使用YT和LJ这2个数据图和4个模式图(P1,P2,P3,P4)进行测试。如图18所示,实验以未做任何优化的基础版本作为性能基线。其中,细粒度并行聚焦于集合算子的查询阶段,通过并行处理同一层循环内的多个集合操作,大幅降低GPU线程组内的空闲线程比例,有效缓解传统串行执行模式导致的计算资源浪费问题,在不同数据图和模式图场景下,该策略平均实现了2.12倍的性能提升。而访存优化则是在细粒度并行的基础上进一步升级,采用混合算子策略,针对数据图中大度数顶点与小度数顶点的特性,分别设计差异化的集合算子实现方案,同时将待查询数据提前预加载至共享内存,避免多次重复读取数据带来的性能损耗,该优化策略带来了22%的平均性能增益。实验结果表明,面对数据图与模式图的多种组合,Saturn系统的计算优化方法均展现出了显著的性能提升效果。
2)通信优化的性能分析。为了评估多GPU协同计算的场景下通信优化技术带来的性能提升,我们在FR和DG大图上对4个模式图(P5,P6,P7,P8)执行图挖掘任务。我们主要评测2种优化方法:第1种是数据缓存优化。该优化是在多GPU的设备内存上备份了高度数顶点的邻居数据,避免了GPU间频繁的高度数顶点通信。第2种是消息合并优化,该优化聚焦于多GPU间通信的链路竞争问题,将发往相同GPU的数据分桶,并在桶内将重复的邻居数据请求合并,在提升带宽利用率的同时降低了冗余数据通信。如图19所示,经过数据缓存优化,Saturn系统的整体性能提升了51.4%。在此基础上,叠加消息合并优化,可以带来平均1.46的加速比。
3)GPU整体利用率的分析。为探究不同Multi-GPU系统在图挖掘任务中的CPU和GPU资源利用效率,我们在配备8个A100 GPU的服务器上执行P6模式挖掘任务,并对比VSGM与Saturn系统的CPU和GPU整体利用率,见图20。
实验数据显示,VSGM系统受限于CPU与GPU间的数据传输瓶颈,在FR和DG这2个数据集上的平均GPU利用率仅为42.9%和58.8%,峰值利用率亦仅达68%。这主要归因于其执行图挖掘任务时,需频繁在CPU主存与GPU显存间进行数据搬移,导致GPU计算资源出现大量闲置。这种频繁的数据搬运不仅拉长了整体执行时间,也严重制约了GPU算力的实际发挥。在这一过程中,CPU需频繁执行图分区的构建、索引与传输操作,导致VSGM在运行时CPU平均利用率高达68.7%。
相较之下,Saturn展现出更优的资源利用效率:一方面系统将GPU利用率稳定维持在96%以上,另一方面通过将计算与通信整合到单一完整内核中,无需 CPU 参与干预,使得系统运行时CPU 利用率维持在5%以下。该优势得益于2个方面:其一,通过CPU无感的通信机制,将数据传输的控制路径与数据路径完全卸载至GPU,规避CPU与GPU间的协同延迟;其二,系统对GPU计算单元进行细致调度,确保所有计算单元在图挖掘过程中保持计算或是通信状态,从而实现计算资源的高效复用。
4)系统的强扩展性。为验证Saturn系统在大规模计算环境下的强扩展性,我们在1台配备NVLink 互连的8个A100 GPU服务器和8个节点构成的32卡V100 GPU集群上,针对P2,P5,P6,P7这4个模式图及FR,DG这2个数据图开展性能测试(其他数据集与模式图呈现相似趋势)。图21所示的实验结果显示,Saturn系统在单机8卡A100和32卡V100的不同配置下均展现出优异的并行处理能力。其中,在8 卡A100的单节点内Saturn的并行效率在不同查询场景中稳定处于73.8%~82.5%,平均并行效率达77.8%。而在32卡V100的分布式场景中,Saturn的并行效率稳定于57.5%~72.6%,平均并行效率达64.2%。这一方面主要归功于我们的CPU无感的通信策略,避免了在GPU执行图挖掘任务过程中CPU的频繁干预。另一方面,我们通过数据缓存和消息合并优化,有效减少冗余数据传输与链路资源竞争,实现多GPU间的高效协同计算。
1)GPU线程组利用率。在单GPU环境下执行图挖掘任务时,线程组内线程利用率是衡量计算效率的关键指标。为验证Saturn系统的细粒度并行技术相对于传统算子内并行方法的优势,我们在图22中对比展示了不同数据图(MI和LJ)与模式图(P2,P3,P4)组合下的线程利用率表现。传统的“算子内并行-算子间串行”计算模式在处理小度数顶点的查询任务时存在显著缺陷,即线程组内大量线程因等待数据或任务分配而处于空闲状态,导致整体利用率低下。实验数据显示,该模式下线程利用率平均值仅为22.4%,在处理复杂模式图(如P4)或低平均度数数据图(如MI,利用率为19.5%)时,利用率最低可降至13.8%。Saturn系统的细粒度并行优化通过重构查询阶段的执行逻辑,显著提升了线程利用率。该技术将同一层循环内的多个集合操作进行并行化处理,确保每个线程在执行周期内均有明确的查询任务。优化后的数据表明,线程组内利用率平均达到89.98%,峰值利用率可达92.5%,且在不同数据图与模式图组合下均保持稳定的高利用率表现。这一改进不仅解决了传统模式中的线程空闲问题,还通过任务的动态分配机制有效平衡了计算负载,实现了GPU资源的高效利用。
2)混合算子策略的阈值选择。图23呈现了不同度数阈值对混合算子策略性能的影响。实验以单 GPU配置下选取P2和P3这2个模式图,在LJ,YT,MI,CP这4个数据集上开展评估,度数阈值范围设定为0~1024。其中,阈值0对应二分查找法,其性能作为实验基准。结果表明,当模式图P2和P3的度数阈值设为256时,平均加速比分别达到1.58与1.42;而当阈值处于64~384时,可至少实现1.4的加速效果。基于上述结果,系统性能对比实验中,混合算子策略的静态度数阈值统一设置为256已足够展示Saturn的优势。尽管采用更精准的自适应阈值能进一步挖掘潜力,但其涉及的算法复杂度和运行时开销与本研究的算子优化相互正交。因此,本文将阈值256作为实验评估的标准配置,而更复杂的自动化参数寻优机制可作为未来的研究方向进一步探索。
3)运行时开销评估。为阐明细粒度并行优化与多卡通信优化不会产生过多开销,我们在2个数据图与2个模式图上开展图挖掘任务,以此评估运行时间和内存占用状况。图24呈现了多GPU场景下的运行时间开销与内存开销。执行时间分别对计算时间、通信时间以及额外开销时间进行统计,这3部分的平均占比依次为4%,37%,59%;额外开销源于2方面:一是计算索引更新过程中所依赖的Warp内线程广播通信,二是通信内存管理与消息聚合操作,这2类操作仅涉及本地显存的索引更新,不会产生跨设备的数据传输开销,故而额外开销占比处于较低水平。运行时内存消耗主要分为3个部分:用于临时通信数据存放的通信内存、跨节点高度邻居数据的缓存内存和用于本地执行图挖掘任务的计算内存,它们的平均占比分别为31%,16%,53%。借助Saturn的共享内存机制,在维持内存分布稳定的同时,还能确保较低的运行时通信开销,实现了性能与内存开销的良好平衡。
4)系统通信行为分析。为测试 Saturn 的通信效率,我们在FR数据图上使用P4,P7这2个模式图执行4 个GPU协同计算的图挖掘任务,重点评估3方面性能:统一内存架构下的NVLink带宽利用率与平均延迟,以及不同迭代层次的平均消息尺寸和通信频率。实验对比了传统通信库NCCL与NVSHMEM在多GPU图挖掘任务中的通信效率,结果如图25所示,NCCL的平均带宽利用率为77%,而NVSHMEM可达88%;由于NCCL需要CPU进行多次显式同步与数据重排,其平均延迟达NVSHMEM 的2.4倍。另一方面,由于图挖掘这类算法的任务特性,消息大小通常较小(例如,本实验中小于600×109),但消息频率较高,随迭代层数增加,消息尺寸与频率均呈增长趋势,我们的消息聚合机制能够将小消息合并且消除重复邻居数据访问,从而能有效提升通信效率。这也进一步验证了基于 NVSHMEM 与消息聚合的设计更适配图挖掘高频率、小消息的通信特征。
Arabesque[23]是提出“按实例思考”(think like embedding, TLE)编程抽象的分布式图模式匹配系统。该系统采用广度优先搜索算法逐步生成部分匹配实例,该方法虽然能增量得到匹配结果,但会导致较高的内存开销。Peregrine[6]提出了基于模式感知(pattern aware)的图挖掘系统。该系统通过直接计算最终结果的方式在单节点上处理大规模图数据,避免对无关子图的无效遍历。AutoMine[5]将图模式挖掘问题形式化为集合问题,通过集合代数(如集合求交、集合求差等)实现图挖掘算法。该系统基于关系代数生成最优查询计划,并通过调整匹配顺序,在匹配初始阶段对伪候选集(false candidates)进行剪枝,同时复用中间计算结果以提升搜索效率。GraphPi[8]旨在解决模式图的对称性导致的大量冗余计算和不同匹配顺序对性能的影响。该系统构建了精确的性能预测模型,动态确定最优匹配顺序与非对称约束组合,实现高效图模式挖掘。Khuzdul[20]是一个基于CPU多节点的分布式图挖掘系统。该系统提出了可扩展实例(extendable embedding)的编程抽象来表达模式枚举算法,支持细粒度的任务调度和计算通信掩盖,同时采用了静态的缓存策略降低多节点间的通信负担。现有的CPU系统存在显著性能瓶颈,其设计侧重抽象机制与编程灵活性,未能有效利用异构设备的高并发特性。
Pangolin[24]是一个GPU上的图挖掘系统,其针对GPU架构提出了基于“扩展—规约—过滤”(extend-reduce-filter)的执行模型,并设计了结构化数组(structure of arrays,SoA)的子图存储结构适配GPU的高并发特点。但由于其编程接口不够灵活,系统仅能支持有限种类的图挖掘应用。G2Miner[10]根据数据图、模式图和GPU架构这3个维度的特征为用户自动生成高性能的GPU代码,其在GPU内核函数中采用边上任务划分结合GPU的Warp任务并行,同时实现了基于Warp原语的集合求交算子。STMatch[25]和EGSM[26]考虑了GPU上图挖掘的负载均衡问题。其中,每个线程组通过维护独立的栈结构,并通过任务窃取机制拆分搜索任务。STMatch采用单纯的深度优先搜索方案而TDFS和EGSM则采用了广度搜索和深度搜索的混合方案。GraphFold[27]聚焦于GPU在处理图挖掘任务的冗余搜索问题,采用合并匹配(fused matching)算法避免了重复的集合操作。然而,这些GPU上的图挖掘系统仅考虑整个数据图存放在设备内存的场景,无法处理超出单个显存容量的图数据。
在传统的图计算领域,张珩等人[28]设计了基于Multi-GPU平台的图计算系统,提出了Grid图数据切分策略,动态地从SSD加载图数据至多个GPU上并行处理。蒋筱斌等人[29]提出了混合感知的细粒度通信模型,优化多GPU间的通信效率以支持大规模图处理(最短路径、PageRank等图计算应用)。然而,图挖掘问题与图计算任务特征的不同导致优化技术难以迁移。在图挖掘领域,PBE[14]将图数据保存在CPU主存上,由CPU负责对大图数据进行切分,将分区数据分别加载给多个GPU设备进行并行处理。VSGM[15]提出了基于视图(view-based)的技术来掩盖分数数据的计算和通信从而提升GPU的利用率。G2-AIMD[16]使用拥塞控制算法改进了VSGM的调度流程,降低了GPU产生中间结果的显存开销。但现有的基于多GPU的图挖掘方案均面临显著的CPU-GPU 数据传输开销问题,且普遍忽略GPU间的高效通信链路。
当前图处理领域已涌现出众多功能分化的图系统,涵盖图计算、图挖掘及图学习等核心方向。在传统图计算领域,PowerGraph[30],Pregel[31],GraphX[32]等经典系统,主要聚焦于BFS,Pagerank等基础图遍历算法的高效执行;而图学习领域中,DGL[33],PyTorch Geometric[34]等主流框架,则提供了GCN[35],GIN[36],GAT[37]等丰富的图神经网络模型,支撑深度学习任务开展。为实现复杂图任务的端到端处理,这类系统常需协同工作,例如Yu等人[38]设计的Vineyard系统,致力于提供通用的图处理支撑能力。以欺诈检测场景为例,通常先通过图计算系统的遍历功能从海量用户数据中构建图结构,再将生成的数据图输入图挖掘系统,借助K-团识别、环形模式匹配等图挖掘算法产出分析结果并为图中顶点赋值属性,最后将带属性的数据图输入图学习系统以完成诈骗团伙预测。本文设计的Saturn系统接收数据图和模式图为输入,提供结构查询功能,输出顶点属性特征,为下游图学习任务的高效执行提供支撑。
本文针对图模式挖掘在GPU加速中面临的线程利用率低、多GPU通信开销大等挑战,提出了高效的GPU图模式挖掘系统Saturn。通过深入分析现有并行优化方法的缺陷,我们设计了细粒度并行策略与混合算子优化,将集合操作的加载与查询解耦,动态适配哈希与二分查找策略,显著提升了GPU线程利用率,有效解决了幂律图数据下小度数顶点处理时的线程空闲问题。在多GPU协同方面,提出CPU无感的全GPU通信模式,利用NVLink高带宽链路和统一内存机制,结合高度数顶点缓存与消息聚合分桶调度,大幅降低了跨设备通信开销,避免了CPU介入导致的计算中断与PCIe数据传输瓶颈。实验结果表明,Saturn系统在多个真实数据集上实现了对主流GPU图挖掘系统的性能超越,不仅提升了单GPU环境下的计算并行效率,还在多GPU场景中展现出优异的通信能效与可扩展性。
林志恒提出了方案、完成实验并撰写论文;孟轲指导论文思路与写作;谭光明提供研究思路并给予指导意见。

参考文献 引证文献
排序方式:
1
Spirin N, Han Jiawei. Survey on Web spam detection: Principles and algorithms[J]. ACM SIGKDD Explorations Newsletter, 2012, 13(2): 50−64.
2
Guo Zhichun, Guo Kehan, Nan Bozhao, et al. Graph-based molecular representation learning[C]//Proc of the 32nd Int Joint Conf on Artificial Intelligence (IJCAI’23). New York: ACM, 2023: 6638−6646
3
Ranu S, Singh A K. Indexing and mining topological patterns for drug discovery[C]//Proc of the 15th Int Conf on Extending Database Technology (EDBT’12). New York: ACM, 2012: 562−565
4
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
5
Mawhirter D, Wu B. AutoMine: Harmonizing high-level abstraction and high performance for graph mining[C]//Proc of the 27th ACM Symp on Operating Systems Principles (SOSP ’19). New York: ACM, 2019: 509−523
6
Jamshidi K, Mahadasa R, Vora K. Peregrine: A pattern-aware graph mining system[C]//Proc of the 15th European Conf on Computer Systems (EuroSys ’20). New York: ACM, 2020: 13: 1–13: 16
7
Mawhirter D, Reinehr S, Holmes C, et al. GraphZero: A high-performance subgraph matching system[J]. SIGOPS Operating Systems Review, 2021, 55(1): 21−37.
8
Shi Tianhui, Zhai Mingshu, Xu Yi, et al. GraphPi: High performance graph pattern matching through effective redundancy elimination[C]//Proc of the 32nd Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’20). Piscataway, NJ: IEEE, 2020: 1−14
9
JEDEC. High bandwidth memory (HBM) DRAM[EB/OL]. (2021-03-01)[2025-06-13]. https://www.jedec.org/standards-documents/docs/jesd235a
10
Chen Xuhao, Arvind. Efficient and scalable graph pattern mining on GPUs[C]//Proc of the 16th USENIX Symp on Operating Systems Design and Implementation (OSDI’22). Berkely, CA: USENIX Association, 2022: 857−877
11
Shi Tianhui, Zhai Jidong, Wang Haojie, et al. GraphSet: High performance graph mining through equivalent set transformations[C]//Proc of the 35th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’23). New York: ACM, 2023: 32: 1−32: 14
12
Pandey S, Li Xiaoye, Buluc A, et al. H-index: Hash-indexing for parallel triangle counting on GPUs[C]//Proc of the 23rd IEEE High Performance Extreme Computing Conf (HPEC). Piscataway, NJ: IEEE, 2019: 1−7
13
Hu Yang, Liu Hang, Huang H. Tricore: Parallel triangle counting on GPUs[C]//Proc of the 30th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’18). Piscataway, NJ: IEEE, 2018: 171−182
14
Guo Wentian, Li Yuchen, Sha Mo, et al. GPU-accelerated subgraph enumeration on partitioned graphs[C]//Proc of the 40th ACM SIGMOD Int Conf on Management of Data (SIGMOD’20). New York: ACM, 2020: 1067–1082
15
Jiang Guanxian, Zhou Qihui, Jin Tatiana, et al. VSGM: View-based GPU-accelerated subgraph matching on large graphs[C]//Proc of the 34th Int Conf for High Performance Computing, Networking, Storage and Analysis (SC’22). Piscataway, NJ: IEEE, 2022: 1−15
16
Yuan Lyuheng, Ahmad A, Yan Da, et al. G2-AIMD: A memory-efficient subgraph-centric framework for efficient subgraph search on GPUs[C]//Proc of the 40th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2024: 3164−3177
17
Pandey S, Wang Zhibin, Zhong Sheng, et al. Trust: Triangle counting reloaded on GPUs[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(11): 2646−2660
18
Wang Zhibin, Meng Ziheng, Li Xue, et al. Smog: Accelerating subgraph matching on GPUs[C]//Proc of the 27th IEEE High Performance Extreme Computing Conf (HPEC). Piscataway, NJ: IEEE, 2023: 1–7
19
Iosup A, Hegeman T, Ngai W L, et al. LDBC graph-analytics: A benchmark for large-scale graph analysis on parallel and distributed platforms[J]. Proceedings of the VLDB Endowment, 2016, 9(13): 1317−1328
20
Chen Jingji, Qian Xuehai. Khuzdul: Efficient and scalable distributed graph pattern mining engine[C]//Proc of the 28th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS’23). New York: ACM, 2023: 413−426
21
Leskovec J, Krevl A. SNAP datasets: Stanford large network dataset collection[EB/OL]. 2014[2025-06-13]. http://snap.stanford.edu/data
22
Lin Hu, Lin Yinnian, Zou Lei, et al. A graph pattern mining framework for large graphs on GPU[J]. The VLDB Journal, 2025, 34(1): 117−143.
23
Teixeira C H C, Fonseca A J, Serafini M, et al. Arabesque: A system for distributed graph mining[C]//Proc of the 25th Symp on Operating Systems Principles (SOSP’15). New York: ACM, 2015: 425–440
24
Chen Xuhao, Dathathri R, Gill G, et al. Pangolin: An efficient and flexible graph mining system on CPU and GPU[J]. Proceedings of the VLDB Endowment, 2020, 13(8): 1190−1205
25
Wei Yihua, Jiang Peng. STMatch: Accelerating graph pattern matching on GPU with stack-based loop optimizations[C]//Proc of the 34th Int Conf for High Performance Computing, Networking, Storage and Analysis(SC’22). Piscataway, NJ: IEEE, 2022: 53: 1–53: 13
26
Sun Xibo, Luo Qiong. Efficient GPU-accelerated subgraph matching[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 181: 1−181: 26
27
Lin Zhiheng, Meng Ke, Shui Chaoyang, et al. Exploiting fine-grained redundancy in set-centric graph pattern mining[C]//Proc of the 29th ACM SIGPLAN Annual Symp on Principles and Practice of Parallel Programming (PPoPP’24). New York: ACM, 2024: 175–187
28
张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273−288
Zhang Heng, Zhang Libo, Wu Yanjun. Large-scale graph processing on Multi-GPU platforms[J]. Journal of Computer Research and Development, 2018, 55(2): 273−288 (in Chinese)
29
蒋筱斌, 熊轶翔, 张珩, 等. ChattyGraph: 面向异构多协处理器的高可扩展图计算系统[J]. 软件学报, 2023, 34(4): 1977−1996
Jiang Xiaobin, Xiong Yixiang, Zhang Heng, et al. ChattyGraph: Highly scalable graph computing system for heterogeneous multi accelerators[J]. Journal of Software, 2023, 34(4): 1977−1996 (in Chinese)
30
Gonzalez Joseph E, Low Y, Guerin R, et al. PowerGraph: Distributed graph-parallel computation on natural graphs[C]//Proc of the 10th USENIX Symp on Operating Systems Design and Implementation (OSDI 12). Berkeley, CA: USENIX Association, 2012: 17−30
31
Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]//Proc of the 30th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135−146
32
Gonzalez J E, Xin R S, Dave A, et al. GraphX: Graph processing in a distributed dataflow framework[C]//Proc of the 11th USENIX Symp on Operating Systems Design and Implementation (OSDI 2014). Berkeley, CA: USENIX Association, 2014: 599−613
33
Wang Minjie, Yu Ling, Zheng Da, et al. Deep graph library: Towards efficient and scalable deep learning on graphs[J]. arXiv preprint, arXiv: 1909.01315, 2019
34
Fey M, Lenssen J. Fast graph representation learning with PyTorch Geometric[J]. arXiv preprint, arXiv: 1903.02428, 2019
35
Zhang Si, Tong Hanghang, Xu Jiejun, et al. Graph convolutional networks: A comprehensive review[J]. Computational Social Networks, 2019, 6(1): 1−23
36
Xu Keyulu, Hu Weihua, Leskovec J, et al. How powerful are graph neural networks?[J]. arXiv preprint, arXiv: 1810.00826, 2018
37
Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint, arXiv: 1710.10903, 2017
38
Yu Wenyuan, Zhang Liang, Yang Chao, et al. Vineyard: Optimizing data sharing in data-intensive analytics[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1−27
2026年第63卷第9期
83
40
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202550501
  • 接收时间:2025-06-26
  • 首发时间:2026-11-17
  • 出版时间:2026-09-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2025-06-26
  • 修回日期:2026-04-10
  • 录用日期:2026-04-30
基金
作者信息
    中国科学院计算技术研究所 北京 100190
    中国科学院大学 北京 100049

通讯作者:

谭光明()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550501
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏