VGL: a high-performance graph processing framework for the NEC SX-Aurora TSUBASA vector architecture

• Published in: The Journal of supercomputing 2021, Vol.77 (8), p.8694-8715
• Main Authors: Afanasyev, Ilya V., Voevodin, Vladimir V., Komatsu, Kazuhiko, Kobayashi, Hiroaki
• Format: Article
• Language: English
• Subjects: Algorithms; Central processing units; Compilers; Computer architecture; Computer Science; CPUs; Graphs; Interpreters; Optimization; Parallel Computing Technologies 2020; Performance evaluation; Processor Architectures; Programming Languages; Shortest-path problems; Supercomputers
• ISSN: 0920-8542; 1573-0484
• DOI: 10.1007/s11227-020-03564-9

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are frequently used in various real-world applications. Graph algorithms typically belong to the data-intensive class, and thus using architectures with high-bandwidth memory potentially allows to solve many graph problems significantly faster compared to modern multicore CPUs. Among other supercomputer architectures, vector systems, such as the SX family of NEC vector supercomputers, are equipped with high-bandwidth memory. However, the highly irregular structure of many real-world graphs makes it extremely challenging to implement graph algorithms on vector systems, since these implementations are usually bulky and complicated, and a deep understanding of vector architectures hardware features is required. This paper presents the world first attempt to develop an efficient and simultaneously simple graph processing framework for modern vector systems. Our vector graph library (VGL) framework targets NEC SX-Aurora TSUBASA as a primary vector architecture and provides relatively simple computational and data abstractions. These abstractions incorporate many vector-oriented optimization strategies into a high-level programming model, allowing quick implementation of new graph algorithms with a small amount of code and minimal knowledge about features of vector systems. In this paper, we evaluate the VGL performance on four widely used graph processing problems: breadth-first search, single source shortest paths, connected components, and page rank. The provided comparative performance analysis demonstrates that the VGL-based implementations achieve significant acceleration over the existing high-performance frameworks and libraries: up to 14 times speedup over multicore CPUs (Ligra, Galois, GAPBS) and up to 3 times speedup compared to NVIDIA GPU (Gunrock, NVGRAPH) implementations.