基于高通量计算机的图算法优化技术分析*

江西工程学院智能制造与能源工程学院 曾宏志

随着现代化信息技术的发展及广泛应用,使得图数据得到了迅速的增长,因此如何准确、快速的对各种图数据进行处理成为了主要研究的问题。宽度优先搜索算法(BFS)是一种解决图遍历问题的主要算法,其优化算法取得了重要的进展。高通量计算机是一种利用ARM架构的体系,具有低功耗、实时性强等特点,能够应用在大规模的图计算当中。本文介绍了BFS算法过程,在BFS算法的基础上,提出了两种基于高通量计算机的图算法优化技术,极大的提升了算法的访问速度。

0 引言

图数据能够快速、灵活的处理大量的、稀疏的数据,并且完成大数据的实时分析,被广泛的应用在知识图谱、交通网络等方面。由于图数据的迅速增加,如何对图数据进行快速的处理成为了目前研究的重要内容。宽度优先搜索(Breadth First Search,BFS)算法主要利用Graph500基准的核心测试程序,是一种典型的图遍历方法,但是具有访存比低、扩展性差等一系列缺陷,不能较好的处理大规模的图数据[1]。高通量计算机应用了高通量众核体系结构,具有低功耗、实时性强等特点,因此可以应用在大规模、密集性的数据处理当中。因此,对基于高通量计算机的图算法优化技术进行研究具有重要的意义。

1 相关工作

为了进一步提高性能,降低功耗,BFS并行算法得到了许多学者的广泛关注,目前,主要研究内容包括分布式系统、共享内存系统以及GPU等,相关的BFS优化算法也得到了创新和发展[2]。针对现阶段BFS算法当中存在的负载不均衡以及局限性等缺陷,本文在以上优化算法的基础上,提出了基于块查找的位图访问优化算法,极大的提升了访存效率。同时,对Bottom-up算法的遍历过程进行创新,从而解决传统算法当中数据处理的局限性问题。

2 算法介绍

2.1 历程优化

BFS算法可以看做一种自顶而下的历程优化算法,在遍历的时候会存在很多的冗余遍历。自下而上的算法,能够在一定程度上减少冗余。Bottom-up算法能够在各层优先对没有访问的顶点(行(8))进行处理,当顶点已经被访问时则跳出循环过程,对其余的顶点进行查找,极大的减短了冗余的访问时间。另外,在后续的研究过程中,进一步强化了BFS算法的性能。

2.2 去零点优化

Kronecker生成图当中具有较多的孤立顶点,即顶点位置的出度等于0,根据研究结果,孤立顶点的数量在生成图当中大约占据50%,且顶点规模越大数量越多。在遍历的时候,先找到没有访问的顶点,再在这些顶点当中搜索节点。在对每层遍历的时候,孤立顶点的产生会存在无效遍历以及无效访问等问题,所以必须进行去零点优化操作,从而提升遍历的速度。

2.3 顶点排序优化

利用顶点度数将顶点完成降序排列,把低索引和高度数的顶点相结合,从而解决局部性等问题,提升访存速度。然而由于图数据分布呈现幂律分布,所以在对块粒度大的数据进行处理时,使得不同度数块的处理时间存在较大的差异,存在明显的负载不均等问题。而对于块粒度较小的数据,虽然可以解决负载不均衡的问题,然而线程调度会提升操作时的成本以及时间,降低整体的性能。

2.4 静态Shuffle优化

对于高通量计算机高并发的结构特征,提出静态Shuffle优化算法,主要是以顶点优先排序的原则基础上,进行度数轮询分配的优化算法,不仅解决了负载均衡的问题,而且提升了高通量计算机中BFS算法的效果[3]。静态Shuffle优化算法的具体过程为:对于图数据中的存储结构,根据度数降序的原则对行列表当中的顶点进行排列,通过轮询的形式把顶点放置在各个数组当中,确保不同度数顶点在各个线程当中分布的均衡性,同时将顶点按照降序的原则在线程数据中进行排列,并且实现新顶点向旧顶点的映射,以便在完成图遍历之后恢复相关的图数据。通过静态Shuffle循环,不仅能够保存顶点的数据信息,防止出现由于线程调度产生的开销问题,及时的调整与优化动态分配过程中的块粒度值,而且还解决了顶点数据排序中的局限性问题,极大的提升了利用效率。

2.5 度数感知优化

在遍历的过程中,Bottom-up算法能够获取没有进行访问的顶点的邻居顶点,当寻找到一个邻居节点的时候则停止遍历过程,结束越早,遍历时间越短。Bottom-up算法能够检测到没有访问的顶点的第一个邻居节点,可以直接跳过其余的顶点,但是在实际操作过程中,不能明确邻居顶点的排序位置,其最佳顺序存在较大的差异性[4]。基于此,为了提升访存效率,即:访问次数随着顶点度数的增大而增加,提出了度数感知优化算法,能够在一定程度上降低冗余遍历次数,同时提升数据的访问频率。

3 BFS算法的优化处理

针对BFS算法不能较好的处理大规模的图数据这一问题,根据高通量计算机的结构特征以及相关的优化算法,本文提出了基于块查找的位图访问以及Bottom-up历程优化算法,极大的提升了BFS算法在高通量计算机当中的应用性能。

3.1 基于块查找的位图访问

在进行遍历的时候,BFS算法通过位图的方式记录顶点的情况。位图属于数据结构类型,能够放置最后一级缓存当中,减少了访存的时间及成本。对于Bottom-up算法,遍历时对Visit位图进行扫描以便搜索没有访问的顶点。在Kronecker生成图当中,算法经过迭代会减少没有访问的顶点的数量,具有稀疏的特性。因此,对于大规模的图数据,通过扫描Visit位图有着明显的性能改善。

针对上述问题,本文提出基于块(Block)查找的Visit位图访问算法,利用Bottom-up算法遍历的过程中,可以较快的得出没有访问的顶点在块当中的具体位置。未访问顶点的快速遍历过程如图1所示。

图1 未访问顶点的快速遍历过程Fig.1 Fast traversal of unvisited vertices

在进行遍历时,以Block为单位,对Visit位图的顶点情况进行判断。一般而言,在处理器当中,通用寄存器的位宽是64位,因此能够显示出64个顶点的访问情况,所以可以将一个“块”的面积设置成64。进行遍历的时候,把Visit位图里面第i个Block的访问情况加入到通用寄存器Block_Visit当中,再把其中的整型变量进行取反操作,从而获得寄存器变量Block_no_visit,当寄存器变量显示0时,说明Block当中没有未访问的顶点,可以选择跳过对顶点情况的访问;而当寄存器变量存在除0之外的数据,则可以基于块查找对顶点实现快速定位。

在寄存器变量当中寻找未访问顶点,循环的次数和比特位等于1的数量存在关联,但是和Block没有关系。但是对于传统的算法,在进行顺序遍历的过程中,遍历Block大小的次数也会影响到访问的性能。针对BFS算法局部性差、访存效率低等问题,提出基于块查找的位图访问优化算法,把Block的位移入到寄存器当中,能够降低对Cache的访问次数,减少错误的发生。

从算法优化前后顶点遍历数量的对比结果能够得出:当遍历第五次时,存在99.8%的顶点是已经访问的情况,Visit位图出现很多无效的访存。当对Visit位图进行优化后,根据Block为单位进行粗粒度的判别,基于块查找的位图访问优化算法能够快速、准确的找到未访问的顶点,且和传统的方式相比较,可以减少98.4%的顶点判断,从而提高了遍历的速度。

3.2 Bottom-up历程优化

Bottom-up历程优化算法是在Bottom-up算法的基础上进行改进,利用current-frontier等结构来存储遍历时的数据信息。其中,current-frontier用来提升顶点的活跃程度,Visit保存遍历好的顶点,而next-frontier保存下次遍历的活跃顶点。利用Visit图能够节约数据结构的应用,在遍历时不需要对该层活跃的顶点进行访问,从而把Bottom-up算法当中应用的三个数据结构减少为两个,极大的提升了访存的速度。此外,根据度数感知优化算法,针对Bottom-up算法的性能缺陷,把邻接列表A分别AB+(度数高的邻接顶点)和AB-(度数降序排列的其余顶点),对两个相邻的列表进行遍历,从而提升邻居顶点的搜索速度,提高数据的访存效率。

对算法在邻接列表的AB+和AB-遍历效率进行分析,顶点规模为226(其中,26表示规模,即顶点数为226)时该算法遍历后的顶点数量,可以得出:Bottom-up算法在遍历的过程中,邻接列表AB+更新的顶点数量达到96.14%,且随着遍历层数的增加,活跃顶点数量也在上升。在第三次遍历时,全部的活跃顶点均利用邻接列表的AB+完成更新。所以,对于Bottom-up历程优化算法,可以把邻接列表AB+和AB-进行合并,仅进行一次遍历过程,不但能够保证AB+的局部性,而且避免出现AB-中数据的无效访存等问题。

4 结论

针对BFS算法不能较好的处理大规模的图数据这一问题,根据高通量计算机的结构特征以及相关的优化算法,本文提出了基于块查找的位图访问以及Bottom-up历程优化算法,极大的提升了BFS算法在高通量计算机当中的应用性能。通过对优化算法在高通量计算机当中的性能评估,可以得到:对于性能而言,与x86服务器相比较,高通量计算机不用进行NUMA优化,且其平均性能达到了24.26GTEPS,并且具有2.5倍作用的功耗比优势,在大规模、密集型的图数据过程当中有着明显的优势。

引用

[1] 丁旭阳,谢盈,张小松.基于边缘计算的进化多目标优化图像隐写算法[J].计算机研究与发展,2020(11):2260-2270.

[2] 叶楠,郝子宇,郑方,等.BFS算法与众核处理器的适应性研究[J].计算机研究与发展,2015(5):1187-1197.

[3] 刘建友,蒋春霞.一种基于高通量计算机的图算法优化技术[J].信息与电脑,2020(22):69-71.

[4] 张嘉文,董晓斌,苗桂君,等.基于计算机视觉的液滴图像拼接与识别算法研究[J].中国生物医学工程学报,2021(3):375-379.