基于处理器SW26010的宽度优先搜索方法

近年来，人们越来越关注计算机对数据密集型课题的处理能力。宽度优先搜索（ Breadth first Search，BFS）是一种典型的数据密集型课题，被广泛应用于多种图算法。 Graph500 Benchmark以BFS搜索为核心算法，已经成为评价计算机处理大数据能力的基准。神威太湖之光超级计算机从2016年6月至2017年11月连续4次荣登Tσp500榜单榜首，其处理器sw26010是首款由我国自主研制的异构众核处理器。文中研究了如何利用SW26010的体系结构特点加速BFS算法的问题，在SW26010上实现了基于单个核组的方向优化的融合BFS算法，使用字节图（ bytemap）释放内层循环依赖性，利用异步DMA隐藏计算与便签存储器的访问开销，利用异构架构协冋运算并对图做预处理。最终，以 Graph500作为基准测试程序处理 scale为22的图，SsW26010处理器单核组BFS的性能达到457.54 MTEPS。