BC算法性能与图数据格式的关系特性分析

doi:10.19665/j.issn1001-2400.2021.06.008

摘要/Abstract

摘要：

图计算中数据的压缩格式是图算法访存效率和性能的关键影响因素之一。基于此,针对中心性算法如何根据性能需求选择合适的压缩格式来提升图计算系统性能的问题,采用Skylake Xeon(R) Platinum 8164处理器上的硬件性能计数器对不同数据集的坐标表示、压缩稀疏列、压缩稀疏行、双压缩稀疏列和独立稀疏列压缩的5种压缩格式进行性能评测与分析。性能评价指标包括执行时间、计算量、数据移动量以及功耗等。评价结果表明,当硬件资源受限时,压缩稀疏行压缩格式在处理以遍历为中心的中心性算法时表现最优,可有效地减少程序执行时间、数据移动量以及降低功耗;使用CSC压缩格式,可有效地降低缓存缺失率,更好地利用数据局部性;在考虑内存占用情况下,双压缩稀疏列压缩格式可提高图数据存储效率;独立稀疏列压缩格式在硬件加速器的数据并行性方面有一定的优势,但在通用处理器上的图应用方面并不理想;坐标表示压缩格式在提升图计算应用性能方面相对较差。分析结果对于中心性算法如何根据不同性能需求选择预处理方式提供了依据。

关键词: 图计算, 压缩格式, 中心性, 性能分析

Abstract:

The data compression format in graph computing is one of the key influencing factors of graph algorithm memory access efficiency and performance.Based on this,this paper focuses on how the BC (Betweenness Centrality) algorithm selects the appropriate compression format according to performance requirements to improve the performance of the graph computing system.The hardware performance counter on the Skylake Xeon(R) Platinum 8164 processor is used to analyze different data,with acollection of five compression formats of COO,CSC,CSR,DCSC and CSCI adopted for performance evaluation and analysis.Performance evaluation indicators include execution time,calculation volume,data movement volume,and power consumption.The evaluation results show that when hardware resources are limited,the CSR compression format performs best when processing the traversal-centric BC algorithm,which can effectively reduce the program execution time,data movement,and power consumption.Using the CSC compression format can effectively reduce the Cache miss rate and lead to a better use of data locality.Using the DCSC compression format can improve the graph data storage efficiency when considering memory usage.Using the CSCI compression format has certain advantages in the data parallelism of hardware accelerators,but for general-purpose processors the graph application is not ideal.The COO compression format is relatively poor in improving the performance of graph computing applications.Analytical results provide a basis for how the BC algorithm selects preprocessing methods according to different performance requirements

Key words: graph processing, compression format, betweenness centrality, performance analysis

中图分类号:

TP302.7

蒋林,冯茹,邓军勇,李远成. BC算法性能与图数据格式的关系特性分析[J]. 西安电子科技大学学报, 2021, 48(6): 57-66.

JIANG Lin,FENG Ru,DENG Junyong,LI Yuancheng. Analysis of the relationship between the performance of the BC and the format of the graph data[J]. Journal of Xidian University, 2021, 48(6): 57-66.

图/表 15

图1

图2

图3

图4

图5

图6

表1

表2

图7

图8

图9

图10

图11

图12

图13

参考文献 33

[1]	ZHUO Y, WANG C, ZHANG M, et al. GraphQ:Scalable PIM-Based Graph Processing[C]// Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture.New York:ACM, 2019:712-725.
[2]	WU C, ZHANG G, ZHENG W. Reviewing Large Graph Computing from a System Perspective[J]. Big Data Research, 2015, 1(3):41-54.
[3]	KUMAR P, HUANG H H. GraphOne:A Data Store for Real-time Analytics on Evolving Graphs[J]. ACM Transactions on Storage, 2020, 15(4):1-40.
[4]	徐智诚, 李响, 毛剑, 等. 分布式架构中的Sybil攻击及防御综述[J]. 西安电子科技大学学报, 2021, 48(1):39-49.
	XU Zhicheng, LI Xiang, MAO Jian, et al. Overview of Sybil Attacks and Defenses in the Distributed Architecture[J]. Journal of Xidian University, 2021, 48(1):39-49.
[5]	GUI C, ZHENG L, HE B, et al. A Survey on Graph Processing Accelerators:Challenges and Opportunities[J]. Journal of Computer Science and Technology, 2019, 34(2):339-371. doi: 10.1007/s11390-019-1914-z
[6]	XU Z, CHEN X, SHEN J, et al. GARDENIA:A Graph Processing Benchmark Suite for Next-Generation Accelerators[J]. ACM Journal on Emerging Technologies in Computing Systems, 2019, 15(1):1-13.
[7]	GUI C, ZHENG L, HE B, et al. A Survey on Graph Processing Accelerators:Challenges and Opportunities[J]. Journal of Computer Science and Technology, 2019, 34(2):339-371. doi: 10.1007/s11390-019-1914-z
[8]	CHERNOSKUTOV M. Graph Processing System for Network Science[C]// 2020 International Conference Engineering and Telecommunication (En&T).Piscataway:IEEE, 2020:1-3.
[9]	BALAJI V, CRAGO N, JALEEL A, et al. P-OPT:Practical Optimal Cache Replacement for Graph Analytics[C]// 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA).Piscataway:IEEE, 2021:668-681.
[10]	ROY A, MIHAILOVIC I, ZWAENEPOEL W. X-stream:Edge-Centric Graph Processing Using Streaming Partitions[C]// Proceedings of the 24th ACM Symposium on Operating Systems Principles.New York:ACM, 2013:472-488.
[11]	SONG L, ZHUO Y, QIAN X, et al. GraphR:Accelerating Graph Processing Using ReRAM[C]// Proceedings of the 2018 IEEE International Symposium on High-Performance Computer Architecture.Piscataway:IEEE, 2018:531-543.
[12]	GONZALEZ J E, LOW Y, GU H, et al. PowerGraph:Distributed Graph-Parallel Computation on Natural Graphs[C]// Proceedings of the 10th Usenix Symposium on Operating Systems Design and Implementation.Berkeley:USENIX, 2012:17-30.
[13]	CHEN R, SHI J, CHEN Y, et al. PowerLyra:Dfferentiated Graph Computation and Partitioning on Skewed Graphs[C]// Proceedings of the 10th European Conference on Computer Systems.New York:ACM, 2015:1-15.
[14]	MAASS S, MIN C, KASHYAP S, et al. Mosaic:Processing a Trillion-Edge Graph on a Single Machine[C]// Proceedings of the 12th European Conference on Computer Systems.New York:ACM, 2017:527-543.
[15]	ZHANG J, KHORAM S, LI J. Boosting the Performance of FPGA-Based Graph Processor Using Hybrid Memory Cube:A Case for Breadth First Search[C]// Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays.New York:ACM, 2017:207-216.
[16]	ZHU X W, CHEN W G, ZHENG W M, et al. Gemini:A Computation-Centric Distributed Graph Processing System[C]// Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation.Berkeley:USENIX, 2016:301-316.
[17]	KEPNER J, GILBERT J. Graph Algorithms in the Language of Linear Algebra[M]. Philadelphia:SIAM, 2011.
[18]	BULUC A, GILBERT J R. On the Representation and Multiplication of Hypersparse Matrices[C]// 2008 IEEE International Symposium on Parallel and Distributed Processing.Piscatawy:IEEE, 2008:1-11.
[19]	OZDAL M M, YESIL S, KIM T, et al. Energy Efficient Architecture for Graph Analytics Accelerators[J]. ACM SIGARCH Computer Architecture News, 2016, 44(3):166-177. doi: 10.1145/3007787.3001155
[20]	BALAY S, BUSCHELMAN K, EIJKHOUT V, et al. PETSc Users Manual:Revision 3.8[R]. Argonne:Argonne National Laboratory,Office of Scientific and Technical Information (OSTI), 2017.
[21]	BULUC A, GILBERT J R. The Combinatorial BLAS:Design,Implementation,and Applications[J]. The International Journal of High Performance Computing Applications, 2011, 25(4):496-509. doi: 10.1177/1094342011403516
[22]	YUAN L, DING C, TEFANKOVIC D, et al. Modeling the Locality in Graph Traversals[C]// 2012 41st International Conference on Parallel Processing.Piscataway:IEEE, 2012:138-147.
[23]	ZHOU S, CHELMIS C, PRASANNA V K. High-Throughput and Energy-Efficient Graph Processing on FPGA[C]// 2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM).Piscataway:IEEE, 2016:103-110.
[24]	邓军勇, JOHN L K, SONG S, et al. 一种用于图计算加速器的图数据压缩方法及图计算加速器:中国,CN201910107925.2[P]. 2019-02-02.
[25]	BRANDES U. A Faster Algorithm for Betweenness Centrality[J]. Journal of Mathematical Sociology, 2001, 25(2):163-177. doi: 10.1080/0022250X.2001.9990249
[26]	CRESCENZI P, FRAIGNIAUD P, PAZ A. Simple and Fast Distributed Computation of Betweenness Centrality[C]// IEEE INFOCOM 2020-IEEE Conference on Computer Communications.Piscataway:IEEE, 2020:337-346.
[27]	KATSAROS D, DIMOKAS N, TASSIULAS L. Social Network Analysis Concepts in the Design of Wireless Ad Hoc Network Protocols[J]. IEEE Network, 2010, 24(6):23-29. doi: 10.1109/MNET.2010.5634439
[28]	PANTAZOPOULOS P, KARALIOPOULOS M, STAVRAKAKIS I. Distributed Placement of Autonomic Internet Services[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(7):1702-1712. doi: 10.1109/TPDS.2013.186
[29]	ZILBERMAN P, PUZIS R, ELOVICI Y. On Network Footprint of Traffic Inspection and Filtering at Global Scrubbing Centers[J]. IEEE Transactions on Dependable and Secure Computing, 2017, 14(5):521-534. doi: 10.1109/TDSC.2015.2494039
[30]	JIN S, HUANG Z, CHEN Y, et al. A Novel Application of Parallel Betweenness Centrality to Power Grid Contingency Analysis[C]// 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS).Piscataway:IEEE, 2010:1-7.
[31]	DE MELO A C. The New Linux ‘Perf’ Tools (2010)[R/OL]. [2010-09-01]http://www.linux-kongress.org/2010/slides/lk2010-perf-acme.pdf .
[32]	Stanford University.Stanford Large Network Dataset Collection (2021)[DS/OL]. [2021-01-01]https://snap.stanford.edu/data/ .
[33]	Network Repository.An Interactive Scientific Network Data Repository (2021)[DB/OL]. [2021-01-01]http://networkrepository.com/index.php .

标签	描述
Server	HPE580(208core,416line)
CPU	Iinter(R) Xeon (R) Platinum 8164
L1-icache	32 kB per core
L1-dcache	32 kB per core
L2 cache	1 024 kB per core
L3 cache	36 608 kB percore
RAM	1TB
Kernel	4.15.0-106-generic
Perf	4.15.18
gcc	5.4.0
Parameters	datamv,compute,energy,exec.Time,IPC,MPKI

数据集	描述	顶点数	边数	占用内存/kB
feather-deezer-social	Social network of Deezer users from Europe	28 281	92 752	1 012.40
Wiki-Vote	Wikipediaadminship vote network till January 2008	8 276	103 689	1 126.40
ca-AstroPh	Collaboration network ofArxiv Astro Physics category	18 772	198 110	5 160.96
Soc-brightkite	Social netwoks of location	56739	212 945	2 252.80
Soc_gemsec_HU	Friendship networks of users from 3 European countries	47 538	222 887	2 457.60
Soc_gemsec_HR	Friendship networks of users from 3 European countries	54 572	498 202	5 632.00