Developing Efficient Implementations of Connected Component Algorithms for NEC SX-Aurora TSUBASA
Authors:
- 1 August 2020
- journal article
- research article
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 41 (8) , 1417-1426
Abstract
Modern vector architectures are tend to be equipped with high-bandwidth memory, what makes them an interesting candidate for solving large-scale graph processing problems. However, highly irregular structure of real-world graphs makes it extremely challenging to map fundamental graph-processing problems on vector systems. This paper describes the world-first attempt, aimed to create efficient vector- friendly implementations of various connected components algorithms for modern NEC SX-Aurora TSUBASA architecture, which provides high performance computational power together with a world-highest bandwidth memory. In order to develop fast implementations, supercomputer co-design principles are used, including: the selection of vector-friendly graph algorithms, adapting these algorithms for target architecture, selecting vectorized graph storage format and applying various optimisations aimed to improve the efficiency of using memory hierarchy of target platform. In addition, current paper analyses if similar implementation approaches can be used for modern NVIDIA GPU architectures, which have many common properties and features with SX-Aurora TSUBASA. Finally, a comprehensive comparative performance analysis is presented for all algorithms, architectures and optimisations, discussed in the paper.Keywords
This publication has 13 references indexed in Scilit:
- Performance Evaluation of a Vector Supercomputer SX-Aurora TSUBASA2018
- Developing Efficient Implementations of Bellman–Ford and Forward-Backward Graph Algorithms for NEC SX-ACESupercomputing Frontiers and Innovations, 2018
- Potential of a modern vector supercomputer for practical applications: performance evaluation of SX-ACEThe Journal of Supercomputing, 2017
- Gunrock2016
- Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server2015
- SOME GPU ALGORITHMS FOR GRAPH CONNECTED COMPONENTS AND SPANNING TREEParallel Processing Letters, 2010
- Parallel connected-component labeling algorithm for GPGPU applications2010
- R-MAT: A Recursive Model for Graph Mining2004
- A comparison of parallel algorithms for connected components1994
- An Optimal Randomized Parallel Algorithm for Finding Connected Components in a GraphSIAM Journal on Computing, 1991