GPU-based Graph Analysis and Computation Method for Graph Database

doi:10.19678/j.issn.1000-3428.0057965

Computer Engineering ›› 2021, Vol. 47 ›› Issue (6): 52-59. doi: 10.19678/j.issn.1000-3428.0057965

• Artificial Intelligence and Pattern Recognition • Previous Articles Next Articles

GPU-based Graph Analysis and Computation Method for Graph Database

QIAN Shangyun^1,2,3, SHAO Zhiyuan^1,2,3, ZHENG Ran^1,2,3, CHEN Jilin⁴

1. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;
2. Key Laboratory of Services Computing Technology and System of Minstry of Education, Huazhong University of Science and Technology, Wuhan 430074, China;
3. Key Laboratory of Cluster and Grid Computing in Hubei province, Huazhong University of Science and Technology, Wuhan 430074, China;
4. China Electric Power Research Institute, Beijing 100192, China

Received:2020-04-03 Revised:2020-05-20 Published:2020-06-15
Contact: 国家电网有限公司总部科技项目“适用于电力系统应用的高性能计算技术研究与开发”（XTB17201900305）。 E-mail:zyshao@hust.edu.cn

图数据库中基于GPU的图分析计算方法

钱裳云^1,2,3, 邵志远^1,2,3, 郑然^1,2,3, 陈继林⁴

1. 华中科技大学计算机科学与技术学院, 武汉 430074;
2. 华中科技大学服务计算技术与系统教育部重点实验室, 武汉 430074;
3. 华中科技大学集群与网格计算湖北省重点实验室, 武汉 430074;
4. 中国电力科学研究院有限公司, 北京 100192

作者简介:钱裳云(1996-),女,硕士研究生,主研方向为图计算;邵志远、郑然,副教授;陈继林,高级工程师。

Abstract

Abstract: Most of the existing graph databases use CPU-based distributed graph computing engines(such as GraphX) for online analysis operations, but the limited number of CPU cores will lead to low computing efficiency, and the synchronization between clusters will also generate additional communication overhead.This paper presents the design and implementation of a graph processing system, RockGraph, which uses Graphics Processing Units(GPU) to accelerate the graph computation.The system extracts the subgraph containing core information from the graph database according to the user needs.After the data format conversion, the dynamic link library is called by using the JNI tool, and the GPU graph computing framework is used for online analysis.Then the calculation results are written back to the graph database.Experimental results show that, compared with the CPU-based distributed graph computing system, the proposed RockGraph system increases the graph analysis efficiency by 3 times to 5 times.

Key words: graph database, graph analysis and computation, Graphics Processing Unit(GPU), subgraph extraction, out-of-memory computation

摘要： 现有的图数据库对于在线分析操作大多采用基于CPU的分布式图计算引擎（如GraphX），但CPU核心数量有限的不足会导致计算效率低下，同时集群间的同步也会产生额外的通信开销。通过使用图形处理单元（GPU）对图计算进行加速，设计并实现图处理系统RockGraph。该系统能够根据用户需求从图数据库中提取出包含核心信息的子图，经过数据格式转换后，利用JNI工具调用动态链接库，采用超显存GPU图计算框架进行在线分析，并将计算结果写回图数据库。实验结果表明，与基于CPU的分布式图计算系统相比，RockGraph的图分析效率可提高3倍~5倍。

关键词: 图数据库, 图分析计算, 图形处理单元, 子图提取, 超显存计算

CLC Number:

TP311.132

QIAN Shangyun, SHAO Zhiyuan, ZHENG Ran, CHEN Jilin. GPU-based Graph Analysis and Computation Method for Graph Database[J]. Computer Engineering, 2021, 47(6): 52-59.

钱裳云, 邵志远, 郑然, 陈继林. 图数据库中基于GPU的图分析计算方法[J]. 计算机工程, 2021, 47(6): 52-59.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0057965

http://www.ecice06.com/EN/Y2021/V47/I6/52

Figures/Tables 15

References

[1] JIM W,IAN R,EMIL E.Graph databases[M].[S.l.]:O'Reilly Media,Inc.,2015.
[2] XIN R S,GONZALEZ J E,FRANKLIN M J,et al.GraphX:a resilient distributed graph system on Spark[C]//Pro-ceedings of the 1st International Workshop on Graph Data Management Experience and Systems.New York,USA:ACM Press,2013:1-5.
[3] WANG Jing,ZHANG Yunquan,LIANG Jun.Vector algorithm library implementation and optimization based on ARM V8 platform[J].Computer Engineering,2019,45(6):82-88.(in Chinese)王晶,张云泉,梁军.基于ARM V8平台的向量算法库实现与优化[J].计算机工程,2019,45(6):82-88.
[4] LIU Jie,HAN Zuli,LI Zhangmei,et al.HugeGraph introduciton[EB/OL].(2020-03-23)[2020-04-01].https://hugegraph.github.io/hugegraph-doc/.
[5] WANG Y Z H,ANDREW D,PAN Y C,et al.Gunrock:a high-performance graph processing library on the GPU[C]//Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York,USA:ACM Press,2016:11-23.
[6] PARTNER J,VUKOTIC A,WATT N,et al.Neo4j in action[M].[S.l.]:Manning Publications,2014.
[7] FERNANDES D,BERNARDINO J.Graph databases comparison:AllegroGraph,ArangoDB,InfiniteGraph,Neo4J,and OrientDB[C]//Proceedings of the 7th International Conference on Data Science,Technology and Applications.Setubal,Portugal:SciTePress,2018:373-380.
[8] SESTAK M,KORNELIJE R,MATIJA N,et al.Integrity constraints in graph databases-implementation challenges[C]//Proceedings of 2016 Central European Conference on Information and Intelligent Systems.[S.l.]:Faculty of Organization and Informatics Varazdin,2016:20-28.
[9] SHVACHKO K,KUANG H,RADIA S,et al.Thehadoop distributed file system[C]//Proceedings of 2010 IEEE Symposium on Mass Storage Systems and Technologies.Washington D.C.,USA:IEEE Press,2010:1-10.
[10] HINGE A,AUBER D.Distributed graph layout with Spark[C]//Proceedings of the 19th International Conference on Information.Washington D.C.,USA:IEEE Press,2015:271-276.
[11] SHI Xuanhua,ZHENG Zhigao,ZHOU Yongluan,et al.Graph processing on GPUs:a survey[J].ACM Computing Surveys,2018,50(6):1-35.
[12] ABDULLAH G,TAHSIN R,ELIZEU S N,et al.Efficient large-scale graph processing on hybrid CPU and GPU systems[EB/OL].(2014-12-05)[2020-02-03].https://arxiv.org/ftp/arxiv/papers/1312/1312.3018.pdf.
[13] ZHONG Jianlong,HE Bingsheng.Medusa:simplified graph processing on GPUs[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(6):1543-1552.
[14] FU Z S,THOMPSONB B,MICHAEL P,et al.MapGraph:a high level API for fast development of high performance graph analytics on GPUs[C]//Proceedings of Workshop on Graph Data Management Experiences and Systems.New York,USA:ACM Press,2014:1-6.
[15] CHE Shuai.GasCL:a vertex-centric graph model for GPUs[C]//Proceedings of High Performance Extreme Computing Conference.Washington D.C.,USA:IEEE Press,2014:1-6.
[16] FARZAD K,KEVAL V,RAJIV G,et al.CuSha:vertex-centric graph processing on GPUs[C]//Proceedings of the 23rd International Symposium on High performance Parallel and Distributed Computing.New York,USA:ACM Press,2014:239-252.
[17] STATHIS M,BIANCA S.The evolution of the hadoop distributed file system[C]//Proceedings of the 32nd International Conference on Advanced Information Networking and Applications.Washington D.C.,USA:IEEE Press,2018:67-74.
[18] GIORGOS S,KOSTAS M.Rethinking HBase:design and implementation of an elastic key-value store over log-structured local volumes[C]//Proceedings of the 14th International Symposium on Parallel and Distributed Computing.Washington D.C.,USA:IEEE Press,2014:225-234.
[19] ANTONINO F,PAGLIA L,ROSA M,et al.Gremlin language for querying the BiographDB integrated biological database[C]//Proceedings of International Conference on Bioinformatics and Biomedical Engineering.Berlin,Germany:Springer,2017:303-313.
[20] MERRILL D,GARLAND M,GRIMSHAW A,et al.Scalable GPU graph traversal[C]//Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York,USA:ACM Press,2012:117-128.
[21] DAVIDSON A,BAXTER S,GARLAND M,et al.Work-efficent parallel GPU methods for single-source shortest paths[C]//Proceedings of the 28th International Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Press,2014:349-359.
[22] CABARET L,LACASSAGNE L,ETIEMBLE D,et al.Distanceless label propagation:an efficient direct connected component labeling algorithm for GPUs[C]//Proceedings of the 7th International Conference on Image Processing Theory,Tools and Applications.Washington D.C.,USA:IEEE Press,2018:1-6.

Please choose a citation manager

Content to export