| 张萍* ** ***,曹华伟* **,杨莫凡****,梁彦* **,安学军* **.VS-NRM：基于数据划分的PageRank并行图算法优化[J].高技术通讯(中文),2025,35(6):579~589 |
| VS-NRM：基于数据划分的PageRank并行图算法优化 |
| VS-NRM: optimization of parallel PageRank based on graph partitioning |
| |
| DOI：10. 3772 / j. issn. 1002-0470. 2025. 06. 002 |
| 中文关键词: PageRank； 图数据划分； 节点排序； 重编号； 高度数节点优先 |
| 英文关键词: PageRank, graph partitioning, vertex sorting, remapping, high-degree vertices priority |
| 基金项目: |
| 作者 | 单位 | | 张萍* ** *** | （*处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（**中国科学院大学计算机科学与技术学院北京 100049）
（***北京科技职业大学集成电路学院(人工智能学院)北京 100176）
（****北京航空航天大学计算机学院北京 100191） | | 曹华伟* ** | （*处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（**中国科学院大学计算机科学与技术学院北京 100049）
（***北京科技职业大学集成电路学院(人工智能学院)北京 100176）
（****北京航空航天大学计算机学院北京 100191） | | 杨莫凡**** | （*处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（**中国科学院大学计算机科学与技术学院北京 100049）
（***北京科技职业大学集成电路学院(人工智能学院)北京 100176）
（****北京航空航天大学计算机学院北京 100191） | | 梁彦* ** | （*处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（**中国科学院大学计算机科学与技术学院北京 100049）
（***北京科技职业大学集成电路学院(人工智能学院)北京 100176）
（****北京航空航天大学计算机学院北京 100191） | | 安学军* ** | （*处理器芯片全国重点实验室（中国科学院计算技术研究所）北京 100190）
（**中国科学院大学计算机科学与技术学院北京 100049）
（***北京科技职业大学集成电路学院(人工智能学院)北京 100176）
（****北京航空航天大学计算机学院北京 100191） |
|
| 摘要点击次数: 14 |
| 全文下载次数: 16 |
| 中文摘要: |
| PageRank算法是用于评估图中节点重要性的核心算法，应用范围十分广泛，然而PageRank图数据处理算法访存局部性差的问题严重制约算法运行效率。本文提出了顶点排序重映射方法(vertex sort-node ReMap，VS-NRM)：基于图数据划分的PageRank并行图算法优化，通过提高访存局部性优化PageRank算法性能。首先，提出了基于均匀分区的目的-源节点排序数据划分方法，该方法在均匀分区的基础上，把目的节点相同的边划分到同一分区；根据目的节点对每个节点集的传出边进行排序，对于相同目的节点的边集按照源节点进行局部排序，从而提升访存的局部性。其次，提出了基于宽度优先的重编号局部映射数据划分方法，该方法能够有效降低相邻节点编号的跳跃性，减少同一目的节点的多个源节点编号差距太大产生的随机访存。最后，提出了基于幂图性质的高度数节点优先编号数据划分方法，该方法优先给高度数节点编号，提高大量低度数节点编号的顺序性，进一步提高了访存局部性。测试结果显示，该算法优化后比典型图计算算法性能提高20%以上。 |
| 英文摘要: |
| PageRank is a crucial algorithm for assessing the significance of vertices within a graph. Nevertheless, the weak locality of PageRank severely restricts its efficiency. This paper proposes an optimized parallel PageRank algorithm based on graph partitioning, named vertex sort-node ReMap (VS-NRM), which boosts the performance of PageRank by enhancing memory performance. Firstly, a data partitioning algorithm based on destination-source vertex sorting is introduced. This algorithm partitions edges with the same destination into the same partition on the basis of uniform partitioning. Subsequently, it arranges the outgoing edges of each vertex set according to the destination vertices and sorts the source vertices of the edge sets with the same destination to minimize random memory access. Secondly, a breadth-first number remapping data partitioning method is proposed. This method can effectively reduce the discontinuity of adjacent vertices, thereby cutting down on random memory access that arises from significant differences between source vertices sharing the same destination. Finally, a high-degree vertices priority numbering data partitioning method based on power graph properties is presented. This method gives priority to high-degree vertices to improve the sequence of low-degree vertices, further enhancing memory access locality. Experimental results demonstrate that VS-NRM attains over a 20% performance enhancement in comparison to the state-of-the-art methods. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
