论文部分内容阅读
大规模图计算已在网页搜索、计算生物学及机器学习等领域发挥着越来越重要的作用。但是,随着大数据时代的到来,图数据海量增长,面对广泛的大规模图计算需求,单机算法运行效率低下。由于图结构本身的不规则性,在现在的高性能计算系统上进行图计算难以获得高性能。与相对成熟的数值科学计算相比,以图计算为代表的高性能组合计算是一个新兴领域,如何使大规模图计算获得高性能是一个待解决的问题。但由于能将图算法转换为一系列基本线性代数的操作,使得用传统的矩阵计算技术解决图问题成为一个有效的、有活力的发展方向。其中,高性能数值计算的许多方法,特别是针对稀疏矩阵计算的并行算法及数据结构可以为并行图计算提供支撑。GraphBLAS(istc-bigdata.org/GraphBLAS)定义了一组基于稀疏矩阵的图操作的集合,可以在不同的编程环境下实现一系列的图算法,以Combinatorial BLAS库为代表,其本质是对稀疏线性代数库的继承和扩展。图聚类是指把图中相对连接紧密的顶点及其相关的边分组形成一个子图的过程,在模式识别、生物信息、图像分析等领域有着广泛应用,同辈压力(Peer Pressure)聚类算法是一种基于随机游走的图聚类算法,其最大特点是简单、高效。本文的工作主要分为两部分。第一部分,首先介绍了 Combinatorial BLAS库的架构,然后对其提供的相关图原语的性能进行了剖析,最后对其提供的宽度优先搜索算法的性能在曙光超级计算机上进行了测试。第二部分,在Combinatorial BLAS上实现了经线性代数转换后的同辈压力(PeerPressure)聚类算法,第一步,将图算法转化为一系列基于稀疏矩阵的线性代数操作,第二步,针对每一个基本的线性代数操作分别确定相关算法和数据结构,第三步,基于MPI编程模型对经线性代数转化后的聚类算法进行并行实现,其中,针对该算法目前最费时的部分(打结问题),我们提出了相应的并行算法,并基于MPI和MPI-OpenMP分别在Combinatorial BLAS库中予以实现。实验结果显示,在处理规模达到43000亿的由稀疏矩阵表示的超大规模图(扩展度为21的R-Mat图)时,基于线性代数表示的同辈压力图聚类算法在曙光超级计算机上取得了较高的性能表现,良好的可扩展性。其MPI实现在1024个核上获得了 76.8%的并行效率;其MPI-OpenMP实现在2048个核上取得了 46.4%的并行效率。可见,高性能计算中的稀疏矩阵计算技术可以对大规模图计算提供支撑。通过将图聚类问题归约为数值计算的矩阵运算问题,可以将图的不规则数据结构及接入模式进行结构化表示,最后再利用传统的稀疏矩阵计算技术对经转换后的算法进行优化,最终使得大规模图计算在超级计算机的环境下获得高性能。