面向国产异构众核处理器SW26010的BFS优化方法  

Optimization of BFS on Domestic Heterogeneous Many-core Processor SW26010

作　　者：袁欣辉 林蓉芬[1] 魏迪[1] 尹万旺[1] 徐金秀[1] YUAN Xin-hui;LIN Rong-fen;WEI Di;YIN Wan-wang;XU Jin-xiu(Jiangnan Institute of Computing Technology,Wuxi,Jiangsu 214083,China)

机构地区：[1]江南计算技术研究所,江苏无锡214083

出　　处：《计算机科学》2020年第8期98-104,共7页Computer Science

基　　金：国家重点研发计划资助项目(2016YFB0201100,2017YFB0202702);国家“973”计划资助项目(2014CB744100);国家“863”计划资助项目(2012AA01A306)。

摘　　要：近年来,人们越来越关注计算机对数据密集型课题的处理能力。宽度优先搜索(Breadth First Search,BFS)是一种典型的数据密集型课题,被广泛应用于多种图算法。Graph 500 Benchmark以BFS搜索为核心算法,已经成为评价计算机处理大数据能力的基准。神威太湖之光超级计算机从2016年6月至2017年11月连续4次荣登Top 500榜单榜首,其处理器SW26010是首款由我国自主研制的异构众核处理器。文中研究了如何利用SW26010的体系结构特点加速BFS算法的问题,在SW26010上实现了基于单个核组的方向优化的融合BFS算法,使用字节图(bytemap)释放内层循环依赖性,利用异步DMA隐藏计算与便签存储器的访问开销,利用异构架构协同运算并对图做预处理。最终,以Graph 500作为基准测试程序处理scale为22的图,SW26010处理器单核组BFS的性能达到457.54MTEPS。In recent years,there is growing concern for the processing capabilities of data-intensive task.Breadth-first search(BFS)is a typical data-intensive problem,which is widely used in a variety of graph algorithms.Graph 500 Benchmark,taking BFS algorithm as the core,has become the benchmark for the evaluation of processing capabilities of data-intensive tasks.Sunway TaihuLight supercomputer topped the Top 500 list for four consecutive times from June 2016 to November 2017,the processor of which,named SW26010,is the first Chinese homegrown heterogeneous many-core processor.This paper studies how to use the architecture characteristics of SW26010 to accelerate BFS algorithm.A direction-optimizing hybrid BFS algorithm based on a single core group(CG)is implemented on SW26010,using bytemap to release the data dependencies in inner loops,hiding overhead of calculation and SPM access by using asynchronous DMA,taking advantage of heterogeneous architecture to compute collaboratively and carrying out graph preprocessing.Eventually,with Graph 500 as the benchmark processing a scale 22 graph,a single CG of SW26010 processor achieves a performance of 457.54MTEPS.

关 键 词：SW26010 神威太湖之光 Graph 500 数据密集 异构众核 宽度优先搜索 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]