并行原型系统上BFS算法设计实现与测试分析

计算机工程与科学

并行原型系统上BFS算法设计实现与测试分析

衡冬冬,唐玉华,易晓东,刘向阳,周侗

（国防科学技术大学计算机学院,湖南长沙 410073）

收稿日期:2016-08-20 修回日期:2016-10-20 出版日期:2017-01-25 发布日期:2017-01-25
基金资助:
高性能计算国家重点实验室开放课题(20130201,20151301)

Implementation and performance analysis of BFS

algorithm on a parallel prototype system

HENG Dongdong,TANG Yuhua,YI Xiaodong,LIU Xiangyang,ZHOU Tong

（College of Computer,National University of Defense Technology,Changsha 410073,China）

Received:2016-08-20 Revised:2016-10-20 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

相对于传统应用，大数据应用表现出并行性高、访存数据量大、访存模式不规则、程序访存时空局部性差等特性，对传统的计算机体系结构提出了新的挑战。Graph500是评测计算机系统大数据处理能力的基准测试排名，BFS算法是Graph500的核心程序，是典型的数据密集型应用。从1D数据划分、优化的混合算法设计和远程通信方式设计三个方面开展研究，在课题组设计的大数据处理并行结构原型系统上设计实现了多节点的并行BFS算法，在222顶点、226边的数据规模下取得了803.8 MTEPS的性能，并在此基础上进行多节点并行BFS算法的性能测试分析，为进一步的研究工作奠定了基础。

关键词: 大数据处理, Graph500, 并行BFS, 并行结构原型系统, 性能测试分析

Abstract:

Compared with traditional applications, big data applications present have diffident characteristics, such as high parallelism, large volumes of data, irregular memory access mode, and poor temporal locality, which bring new challenges to traditional computer architectures. Graph500 which focuses on data intensive loads, is a rating of supercomputer systems. And the Bread First Search (BFS) algorithm is the core of the benchmark. Based on the parallel prototype system designed for big data applications, we implement the BFS algorithm from the perspectives of 1D partitioning, optimized hybrid algorithm and convenient remote communication design. The performance achieves 803.8 MTEPS under the scale of an input graph of 222 vertexs and 226 edges. Then we analyze the experiment performance and provide a reference for future wok.

Key words: big data processing, Graph500, parallel BFS, parallel prototype system, performance analysis

衡冬冬,唐玉华,易晓东,刘向阳,周侗. 并行原型系统上BFS算法设计实现与测试分析[J]. 计算机工程与科学.

HENG Dongdong,TANG Yuhua,YI Xiaodong,LIU Xiangyang,ZHOU Tong.

Implementation and performance analysis of BFS

algorithm on a parallel prototype system

[J]. Computer Engineering & Science.

参考文献［13］

［1］	www.graph500.org.
［2］	Beamer S,Asanovic K,Patterson D A.Searching for a parent instead of fighting over children: A fast breadthfirst search implementation for graph500:
	Tech Rep UCB/EECS2011117［R］.
	Berkeley:EECS Department,University of California,2011.
［3］	Beamer S, Asanovic K, Patterson D. Directionoptimizing breadthfirst search［J］.Scientific Programming,2013,21(34): 137148.
［4］	Bader D,Madduri K. Designing multithreaded algorithms for breadthfirst search and stconnectivity on the Cray MTA2［C］∥Proc of the 35th International Conference on Parallel Processing (ICPP),2006:523530.
［5］	Harish P,Narayanan P J.Accelerating large graph algorithms on the GPU using CUDA ［C］∥Proc of High Performance Computing(HiPC 2007),2007:197208.
［6］	Agarwal V,Petrin F,Pasetto D,et al.Scalable graph exploration on multicore processors［C］∥Proc of ACM/IEEE International Conference on High Performance Computing,Networking,Storage and Analysis (SC 2010),2010:111.
［7］	Xia Y,Prasanna V.Topologically adaptive parallel breadth
	first search on multicore processors［C］∥Proc of International Conference on Paralleland Distributed Computing Systems (PDCS),2009:1.
［8］	Leserson C E, Schardl T B. A workefficient parallel breadthfirst search algorithm［C］∥Proc of SPAA 10,2010:303314.
［9］	Edmonds N,Willcock J,Hoefler T,et al.Design of a largescale hybridparallel graph library［C］∥Proc of International Conference on High Performance Computing,Student Research Symposium,2010:1.
［10］	Cong G,Almasi G,Saraswat V.Fast PGAS implementation of distributed graph algorithms［C］∥Proc of International Conference for High Performance Computing,Networking,Storage and Analysis (SC 2010),2010:111.
［11］	Checconi F,Petrini F,Willcock J,et al.Breaking the speed and scalability barriers for graph exploration on distributedmemory machines［C］∥Proc of 2012 International Conference on High Performance Computing,Networking,Storage and Analysis (SC 2012),2012: 112.
［12］	Ueno K, Suzumura T. Highly scalable graph search for the graph500 benchmark［C］∥Proc of the 21st ACM International Symposium on HighPerformance Parallel and Distributed Computing,2012: 149160.
［13］	Yasui Y, Fujisawa K, Sato Y. Fast and energyefficient breadthfirst search on a single NUMA system［C］∥Proc of International on Conference on Supercomputing,2014: 365381.

[1]	葛旭冉, 刘洋, 陈志广, 肖侬. 基于MPI的并行大数据集生成器[J]. 计算机工程与科学, 2022, 44(07): 1152-1161.
[2]	白皓, 甘新标, 杨文祥, 贾孟涵, 涂旭平, 张一鸣, 郭敏, 来乐, 张意, 朱春平. 面向大规模图计算的连通分量算法分析与优化[J]. 计算机工程与科学, 2022, 44(02): 191-198.
[3]	聂含伊，杨希，张文喆. 面向多领域的高性能计算机应用综述[J]. 计算机工程与科学, 2018, 40(增刊S1): 145-153.
[4]	王永坤1,罗萱1,金耀辉1,2. 基于私有云和物理机的混合型大数据平台设计及实现[J]. 计算机工程与科学, 2018, 40(02): 191-199.