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

doi:10.19678/j.issn.1000-3428.0057965

计算机工程 ›› 2021, Vol. 47 ›› Issue (6): 52-59. doi: 10.19678/j.issn.1000-3428.0057965

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

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

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

收稿日期:2020-04-03 修回日期:2020-05-20 发布日期:2020-06-15
作者简介:钱裳云(1996-),女,硕士研究生,主研方向为图计算;邵志远、郑然,副教授;陈继林,高级工程师。

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

摘要/Abstract

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

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

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

中图分类号:

TP311.132

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

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.

https://www.ecice06.com/CN/Y2021/V47/I6/52

图/表 15

20210618124008

20210618124011

20210618124015

20210618124018

20210618124022

20210618124026

20210618124029

20210618124033

20210618124037

20210618124041

20210618124045

20210618124048

20210618124051

20210618124055

20210618124102

参考文献

[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.

选择文件类型/文献管理软件名称

选择包含的内容

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

GPU-based Graph Analysis and Computation Method for Graph Database

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	袁佳伟, 宋庆增, 王雪纯, 姜文超, 金光浩. 边缘计算设备的性能功耗测量与分析[J]. 计算机工程, 2021, 47(2): 233-238,245.
[2]	周琦,柴小丽,马克杰,俞则人. 基于CUDA与CUBLAS的Tucker分解模块设计与实现[J]. 计算机工程, 2019, 45(3): 41-46.
[3]	饶志宏,刘杰,陈剑锋. 面向网络监测预警的海量知识存储研究[J]. 计算机工程, 2018, 44(3): 138-143.
[4]	裴鑫,聂俊,陈卯蒸,李健. 基于混合架构的双通道实时相关器实现[J]. 计算机工程, 2016, 42(5): 42-46,53.
[5]	杨仁忠,张洁,韦宏卫,石璐. 基于GPU的Landsat8实时解压缩处理技术[J]. 计算机工程, 2016, 42(3): 301-307.
[6]	杨先凤,李映洁,赖俊良,彭博. 基于GPU并行粒子群优化的超声弹性实时成像算法[J]. 计算机工程, 2015, 41(12): 220-225,230.
[7]	陆慧琳,黄博. 基于双索引的子图查询算法[J]. 计算机工程, 2015, 41(1): 44-48.
[8]	孟小华，黄丛珊，朱丽莎. 基于CUDA的热传导GPU并行算法研究[J]. 计算机工程, 2014, 40(5): 41-44,48.
[9]	王震，李仁发，李彦彪，田峥. 一种并行中英文混合多模式匹配算法[J]. 计算机工程, 2014, 40(4): 318-320.
[10]	闫钧华，杭谊青，孙思佳. 基于GPU的可见光与红外图像融合快速实现[J]. 计算机工程, 2013, 39(11): 249-253.
[11]	荆锐, 赵旦谱, 台宪青. 基于GPU的实时三维点云数据配准研究[J]. 计算机工程, 2012, 38(23): 198-202.
[12]	黄敏, 王金武, 顾力栩, 周喆, 陆文龙. 虚拟肩关节镜手术中软组织形变的模拟[J]. 计算机工程, 2012, 38(19): 281-284,289.
[13]	王华江, 周圣川, 马纯永, 陈戈. 并行化水体表面动态多分辨率物理仿真模型[J]. 计算机工程, 2012, 38(18): 286-290.
[14]	张德好, 刘青昆. 一种Cholesky分解重叠算法[J]. 计算机工程, 2012, 38(18): 262-264.
[15]	孟小华, 刘坚强, 区业祥, 张庆丰. 基于CUDA的拉普拉斯边缘检测算法[J]. 计算机工程, 2012, 38(18): 190-193.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

GPU-based Graph Analysis and Computation Method for Graph Database

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献

相关文章 15

编辑推荐

Metrics

本文评价