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

发布时间：2021-01-25 06:34

　　近年来,人们越来越关注计算机对数据密集型课题的处理能力。宽度优先搜索（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。 

【文章来源】：计算机科学. 2020,47(08)北大核心

【文章页数】：7 页

【部分图文】：

SW26010 运算的核心簇结构

使用bitmap可以压缩BFS算法中In,Out和Vis数组的存储空间,进而增加这些数据的局部性;还能并行判断64个顶点是否都在Frontier中或都没有被访问过,从而降低循环开销。但对于SW26010这种众核架构,CSR格式下,使用bitmap会在TD算法中产生竞争问题:1)如果将bitmap放在从核阵列中,须写其他从核的SPM,目前硬件不支持RDMA,而寄存器通信必须收发双方显式配对,不适合TD算法的需求。2) 如果将bitmap放在主存中,从核阵列内多个核心有可能同时试图改写Out数组,进而产生“读-修改-写”竞争。若两个从核恰好同时试图将Out中属于同一字节的两个不同比特位置1,则后完成的写操作会覆盖稍前完成的操作,造成某些比特位置1失败。如图3所示,Bytek的正确值应当是0x84,但当竞争出现时,Bytek的值变为0x04或0x80。因此,为保证结果的正确性,TD算法对Out数组执行置1操作时必须使用锁,这将导致TD算法内层循环“串行化”,效率较低。为避免使用锁,在SW26010上设计实现了两种topdown算法:利用bitmap结合父亲树中特殊标记的tag-TD算法(算法3)和利用bytemap表示主存中Out数组的bytemap-TD算法(算法4)。

SW26010的基本结构[13]

【参考文献】：
期刊论文
[1]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG.  Science China（Information Sciences）. 2016(07)



本文编号：2998760