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

Implementation and performance analysis of BFS algorithm on a parallel prototype system

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

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 focu- ses 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 2^22 vertexs and 2^26 edges. Then we analyze the experiment performance and provide a reference for future wok.