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

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