TY - GEN
T1 - Developing an efficient vector-friendly implementation of the breadth-first search algorithm for NEC SX-aurora tsubasa
AU - Afanasyev, Ilya V.
AU - Voevodin, Vladimir V.
AU - Komatsu, Kazuhiko
AU - Kobayashi, Hiroaki
N1 - Funding Information:
This project was partially supported by JSPS Bilateral Joint Research Projects program, entitled “Theory and Practice of Vector Data Processing at Extreme Scale: Back to the Future” and by MEXT Next Generation High-Performance Computing Infrastructures and Applications R&D Program, entitled “R&D of A Quantum-Annealing-Assisted Next Generation HPC Infrastructure and its Applica-tions”. The reported study was funded by RFBR, project number 19-31-27001. The reported study was supported by the Russian Foundation for Basic Research, project No. 18-29-03230. The research is carried out using the equipment of the shared research facilities of HPC computing resources at Lomonosov Moscow State University.
Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - Breadth-First Search (BFS) is an important computational kernel used as a building-block for many other graph algorithms. Different algorithms and implementation approaches aimed to solve the BFS problem have been proposed so far for various computational platforms, with the direction-optimizing algorithm being the fastest and the most computationally efficient for many real-world graph types. However, straightforward implementation of direction-optimizing BFS for vector computers can be extremely challenging and inefficient due to the high irregularity of graph data structure and the algorithm itself. This paper describes the world’s first attempt aimed to create an efficient vector-friendly BFS implementation of the direction-optimizing algorithm for NEC SX-Aurora TSUBASA architecture. SX-Aurora TSUBASA vector processors provide high-performance computational power together with a world-highest bandwidth memory, making it a very interesting platform for solving various graph-processing problems. The implementation proposed in this paper significantly outperforms the existing state-of-the-art implementations both for modern CPUs (Intel Skylake) and NVIDIA V100 GPUs. In addition, the proposed implementation achieves significantly higher energy efficiency compared to other platforms and implementations both in terms of average power consumption and achieved performance per watt.
AB - Breadth-First Search (BFS) is an important computational kernel used as a building-block for many other graph algorithms. Different algorithms and implementation approaches aimed to solve the BFS problem have been proposed so far for various computational platforms, with the direction-optimizing algorithm being the fastest and the most computationally efficient for many real-world graph types. However, straightforward implementation of direction-optimizing BFS for vector computers can be extremely challenging and inefficient due to the high irregularity of graph data structure and the algorithm itself. This paper describes the world’s first attempt aimed to create an efficient vector-friendly BFS implementation of the direction-optimizing algorithm for NEC SX-Aurora TSUBASA architecture. SX-Aurora TSUBASA vector processors provide high-performance computational power together with a world-highest bandwidth memory, making it a very interesting platform for solving various graph-processing problems. The implementation proposed in this paper significantly outperforms the existing state-of-the-art implementations both for modern CPUs (Intel Skylake) and NVIDIA V100 GPUs. In addition, the proposed implementation achieves significantly higher energy efficiency compared to other platforms and implementations both in terms of average power consumption and achieved performance per watt.
KW - Breadth-First Search
KW - Graph algorithms
KW - NEC SX-Aurora TSUBASA
KW - Vectorisation
UR - http://www.scopus.com/inward/record.url?scp=85089315610&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089315610&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-55326-5_10
DO - 10.1007/978-3-030-55326-5_10
M3 - Conference contribution
AN - SCOPUS:85089315610
SN - 9783030553258
T3 - Communications in Computer and Information Science
SP - 131
EP - 145
BT - Parallel Computational Technologies - 14th International Conference, PCT 2020, Revised Selected Papers
A2 - Sokolinsky, Leonid
A2 - Zymbler, Mikhail
PB - Springer
T2 - 14th International Scientific Conference on Parallel Computational Technologies, PCT 2020
Y2 - 27 May 2020 through 29 May 2020
ER -
