一种基于GPU的图分析算法通用优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN114117150A(43)申请公布日2022.03.01(21)申请号202111459716.4(22)申请日2021.12.01(71)申请人湖南大学地址410082湖南省长沙市岳麓区麓山南路1号湖南大学(72)发明人赵瑾陈浩(51)Int.Cl.G06F16/903(2019.01)G06F16/901(2019.01)权利要求书1页说明书7页附图3页(54)发明名称一种基于GPU的图分析算法通用优化方法(57)摘要本发明涉及图计算技术领域，是一种基于GPU的图分析通用优化方法及装置，解决了GPU并行图分析算法的性能瓶颈问题。本发明的方法包括：数据集预处理操作：去除图数据的冗余部分，并统一数据集格式；数据分块重排序操作：将数据集分块后，对块内顶点按照出度进行重排序，并将重排序后的图以CSR压缩格式表示；GPU共享内存缓存热顶点操作：利用重排序后的热顶点分布方式，将热顶点的属性数据缓存在GPU端的共享内存中。本方法可以增强图数据的空间局部性，实现图的热顶点共享同一缓存块并驻留在GPU端，避免了热顶点在内存不足时被频繁驱逐造成的性能损失，提高了图分析程序的运行效率。CN114117150ACN114117150A权利要求书1/1页1.一种基于GPU的图分析算法通用优化方法，其特征在于实施步骤为：(1)数据集预处理步骤，读取原始图数据集文件后，去除数据集中与图数据无关的内容及注释，统一数据行之间的分隔符，并将预处理后的数据集保存到CSV文件中，从而得到分析程序可识别的图数据集文件；(2)数据重排序阶段，将数据集等分为若干个数据块，并在数据块内对图顶点进行重排序；(3)热顶点缓存阶段，利用GPU高速共享内存进行热顶点数据的缓存设置，从而将热顶点驻留在GPU端。2.根据权利要求1所述的一种基于GPU的图分析算法通用优化方法，其特征在于本方法在数据集重排序阶段进行的以下操作：(1)将数据集等分为若干个数据块，并在数据块内部对图顶点按照出度进行分块重排序，从而在集中存储热顶点的同时尽可能保留图的原始时间空间缓存局部性；(2)数据集的分块数可根据数据集大小、图数据分布方式进行指定，本方法提供1、2、4、.......、512个分块数目的选择，每个数据块内的顶点个数为总顶点数/分块数。3.根据权利要求1所述的一种基于GPU的图分析算法通用优化方法，其特征在于本方法在热顶点缓存阶段中进行的以下操作：(1)在每个GPU的计算单元中都分配一块共享内存空间，用于热顶点数据的缓存操作；(2)通过对图数据的重用模式进行分析，将具有高重用性的热顶点的属性数据作为GPU缓存的目标数据；(3)利用重排序操作中生成的热顶点的分布方式，将不同数据块内的热顶点属性数据映射到不同GPU计算单元的共享内存中。2CN114117150A说明书1/7页一种基于GPU的图分析算法通用优化方法技术领域[0001]本发明涉及图计算技术领域，是一种面向CPU‑GPU异构存储系统的图分析通用优化方法及装置。具体涉及对图数据集进行重排序操作以增强数据的空间局部性，而后通过GPU共享内存缓存图的热顶点数据以提升图算法的执行效率。背景技术[0002]作为计算机科学中的一种重要的数据结构，图可以利用抽象的方式建模各类场景中的复杂关系，因此目前图处理与分析技术被广泛应用于社会生活的诸多领域中，例如计算机生物学、社交网络分析、神经网络等领域。[0003]为了应对众多领域中的大型图分析需求，研究人员致力于开发用于图处理操作的高效率并行图分析算法。由于图形处理单元GPU具有良好的可编程性以及高带宽、高吞吐量等特性，其已成为加速图处理与分析的重要平台。与基于CPU的最新图处理系统相比，基于GPU的图处理系统可以将程序性能提高多个数量级。[0004]虽然GPU在高效运行图分析算法方面展现出明显的优势，但是面对不断增长的图形大小，以及图数据分布的高度偏斜特性，GPU在处理大型图时仍面临巨大挑战。在许多图应用程序中进行分析的现实世界图，诸如交通路线网络图、社交关系网络图等，往往具有数十到数百GB大小，远远超出了当前GPU主流的内存大小，并且对这些图进行分析时GPU呈现出了高度不规则的内存访问模式。因此当输入的图数据大小超过GPU内存容量时，现有的基于GPU的图系统将无法处理或者处理效率急剧下降。[0005]除了大型图带来的挑战外，现实世界图数据集的另一个特性是顶点的连接数遵循偏态幂律分布，即大部分的节点只有较少的连接，而少数节点则有大量的连接。高度偏斜的分布特性决定了具有较多连接数的部分顶点在内存访问模式上表现出高重用性，这种顶点被称为图的热顶点。由于图的热顶点数据在内存中呈现出稀疏分布的特性，因此在读入GPU显存中时往往和