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

doi:10.19665/j.issn1001-2400.2021.06.008

Abstract

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

CLC Number:

TP302.7

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.

Figures/Tables 15

References 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

Analysis of the relationship between the performance of the BC and the format of the graph data

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 33

Related Articles 10

Metrics

Comments

Recommended 10

[1]	SUN Yanjing;QU Qianqian;WANG Bowen;ZUO Haiwei;WANG Xiaolin. Medium access control mechanism and performance analysis for in band full duplex wireless networks [J]. Journal of Xidian University, 2018, 45(3): 123-129.
[2]	LIU Lifang;WU Dan;LANG Xiaoguang;QI Xiaogang. Research on data transmission and survivability technology of the GEO/LEO satellite network [J]. Journal of Xidian University, 2018, 45(1): 1-5+54.
[3]	YANG Jie;LIU Congfeng;TIAN Zhongcheng;ZHANG Bin. Iteration algorithm for joint TDOA＆FDOA location and its performance analysis [J]. J4, 2015, 42(4): 140-146.
[4]	YANG Jie;LIU Congfeng. Iteration FDOA location algorithm and its performance analysis [J]. J4, 2013, 40(5): 8-14.
[5]	LI Chuan;LIU Wei. Simple single-antenna amplify-and-forward relaying scheme for orthogonal space-time block codes [J]. J4, 2013, 40(2): 117-122.
[6]	TIE Man-xia1;2;LI Jian-dong1;2;WANG Yu-min1. Improvement and performance analysis of the WAPI certificate authentication protocol [J]. J4, 2007, 34(7): 1-4.
[7]	ZHANG Yi-wei1;Shen Xu-bang1;Zhu Xiang-dong1;2. An FM-QCSK chaotic communication system and its performance analysis [J]. J4, 2007, 34(2): 259-263.
[8]	LI Bo1;LI Jian-dong2;FANG Yong1. Performance analysis of the IEEE 802．11 DCF in the non-saturation state [J]. J4, 2007, 34(1): 76-81.
[9]	LI Jian-dong;LIU Jing;LUAN Ying-zi. The improvement and performance analysis of UPMA [J]. J4, 2005, 32(4): 497-500.
[10]	YANG Jun;LI Jian-dong;LI Wei-ying. A novel MAC protocol for the mobile Ad Hoc network with smart antennas [J]. J4, 2003, 30(3): 309-314.