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

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

面向高通量计算机的图算法优化技术

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构,具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上,BFS算法的优化已取得一系列进展,首先对现有的优化技术进行系统的介绍,并在此基础上提出2种面向高通量计算机的优化手段,通过减少冗余访存和提高缓存局部性,有效提高了算法的访存效率.通过这些优化手段,在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230,边数为234),优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比,单节点具有1.18倍的性能优势.在性能功耗比方面,高通量计算机的结果为181.04 MTEPS W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上,高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.

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

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

面向大规模图计算的连通分量算法分析与优化

近年来,图计算在诸多领域发挥着越来越重要的作用。连通分量算法是图计算的重要基础算法,可以应用于可达性查询、一致性检测等众多场景。面向大规模图遍历Graph500标准测试,对连通分量算法进行了算法和数据结构优化。主要有以下创新:(1)对并查集提出了捷径向量算法,并测试了算法和数据结构的配合程度;(2)利用多线程迭代轮转对算法实现并行加速;(3)从多个维度比较了不同实现方法的优缺点。基于优化方法,对性能进行了评估分析,当scale=25(包含2^(25)个节点)时,捷径向量算法对基于二维向量和链表的按秩合并算法的加速比分别是1.38倍和1.40倍,对BFS和DFS的加速比分别为4.76倍和4.70倍,且空间占用为该2个算法的4.1%~4.6%,此外,并行对串行的加速比为1.57倍。

面向超级计算机系统的大规模图遍历优化

现实中的数据问题通常被抽象为图。在大数据时代,图数据趋于复杂,这是因为数据量大幅提升,所需要的计算规模迅速增长。大规模的图数据问题对超算平台的存储运算能力具有广泛需求,并对此提出了更高的要求。为了高效地处理大规模图数据,发挥天河超级计算机实验平台的图处理能力,基于现实世界中图结构的小世界性和无尺度性特征,面向评测超级计算机图处理能力的重要基准Graph500,提出一种主要应用于大规模图的图遍历优化方法。这一方法结合了天河平台的体系结构特征,在图结构上应用了顶点排序和优先缓存策略,即将图中顶点按度数从高到低排序,令程序在图遍历阶段优先访问高度数邻居顶点,并将部分关键高度数顶点缓存至天河系统核组内的高速缓存中,以此来减少Graph500基准程序中的无效访存,降低进程间的通信开销,提高访存带宽利用率,从而有效地提升Graph500基准测试程序在天河平台上的性能。面向天河超级计算机系统实验平台提出的应用顶点排序与优先缓存优化方法的VS-Graph500程序,其加速的效果显著,可扩展性好。当图测试规模为2^(37)时,全系统稳定测试性能为2547.13 GTEPS,超过2020年11月Graph500国际排名榜上第7名的数据。

基于双向位图的CSR大规模图存储优化

大数据时代,Graph500是评测超级计算机处理数据密集型应用能力的重要工具,E级验证系统的图遍历处理能力主要受限于内存空间和访存带宽,尤其是内存空间利用率直接决定了图的测试规模和测试性能.针对天河E级验证系统小内存特征,提出了基于双向位图的大规模图数据压缩存储方法(bidirectional-bitmap based CSR,Bi-CSR),Bi-CSR在CSR矩阵压缩的基础上引入行方向位图和列方向位图协同完成稀疏矩阵压缩存储,行方向位图主要负责行方向位图的压缩存储与索引,列方向位图除了进一步压缩图存储空间,还负责为顶点遍历向量并行优化提供加速空间.Bi-CSR大幅度减少了稀疏矩阵存储空间.面向天河E级验证系统,当图输入规模为237时,Graph500的图存储空间节约效率接近70%,全系统稳定测试性能为2.131E+12TEPS,性能最大加速比超过100倍.

高通量计算机的图算法优化技术研究

高通量计算机具有高并发、强实时、低功耗等适于大数据计算特点,在单节点上,BFS算法的优化已取得一系列进展。文章对BFS算法的性能进行了系统的评估,优化后的BFS算法在高通量计算机上评价性能为24.26 GTEPS和两路X86构建服务器相比,单节点更具性能优势。

E级计算之远景

超级计算机在当今科技发展中占有举足轻重的地位。在向着E级计算时代迈进之时,精确衡量超算的性能是一个事关超算架构和应用的关键问题。评价一台超算采用不同的基准会产生不同的结果。本文介绍超算中主要的3种排名及其对应的评测基准,并分析了超算本身的发展及应用远景。