Scholarlink

The breadth-first search (BFS) algorithm is a fundamental algorithm in graph theory, and it’s parallelization can significantly improve performance. Therefore, there have been numerous efforts to leverage the powerful parallel computing capabilities of hardware like GPGPU to implement high-performance BFS algorithms. However, the energy efficiency is relatively low due to the high power consumption of the platforms on which the algorithm is adapted to. To deal with these challenges, this paper introduces PEbfs that is a high-performance BFS algorithm based on the PEZY-SC3s efficient processor. We integrated three search algorithms, two algorithm optimization strategies, and a directional optimization scheme into PEbfs. Through multiple evaluations of the performance of PEbfs on the public SNAP dataset, the results demonstrate that the average energy efficiency ratio of PEbfs is higher than that of Enterprise and Tigr, the two most advanced implementations on Nvidia’s GPGPU: It achieves 3.08 \(\times \) the average energy efficiency ratio of Enterprise and 4.53 \(\times \) that of Tigr.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

PEbfs: Implement High-Performance Breadth-First Search on PEZY-SC3s

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Weihao Guo,
  • Qinglin Wang,
  • Xiaodong Liu,
  • Muchun Peng,
  • Shun Yang,
  • Yaling Liang,
  • Yongzhen Shi,
  • Ligang Cao,
  • Jie Liu

摘要

The breadth-first search (BFS) algorithm is a fundamental algorithm in graph theory, and it’s parallelization can significantly improve performance. Therefore, there have been numerous efforts to leverage the powerful parallel computing capabilities of hardware like GPGPU to implement high-performance BFS algorithms. However, the energy efficiency is relatively low due to the high power consumption of the platforms on which the algorithm is adapted to. To deal with these challenges, this paper introduces PEbfs that is a high-performance BFS algorithm based on the PEZY-SC3s efficient processor. We integrated three search algorithms, two algorithm optimization strategies, and a directional optimization scheme into PEbfs. Through multiple evaluations of the performance of PEbfs on the public SNAP dataset, the results demonstrate that the average energy efficiency ratio of PEbfs is higher than that of Enterprise and Tigr, the two most advanced implementations on Nvidia’s GPGPU: It achieves 3.08 \(\times \) the average energy efficiency ratio of Enterprise and 4.53 \(\times \) that of Tigr.