Developing Efficient Implementations of Shortest Paths and Page Rank Algorithms for NEC SX-Aurora TSUBASA Architecture
- Authors: Afanasyev I.V.1, Voevodin V.V.1, Voevodin V.V.1, Komatsu K.2, Kobayashi H.2
-
Affiliations:
- Research Computing Center of Moscow State University
- Tohoku University
- Issue: Vol 40, No 11 (2019)
- Pages: 1753-1762
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/206038
- DOI: https://doi.org/10.1134/S1995080219110039
- ID: 206038
Cite item
Abstract
The main goal of this paper is to demonstrate that the newest generation of NEC SX-Aurora TSUBASA architecture can perform large-scale graph processing extremely efficiently. This paper proposes approaches, which can be used for the development of high-performance vector-oriented implementations of page rank and shortest paths algorithms, including vectorised graph storage format, efficient vector-friendly graph traversals, optimised cache-aware memory accesses and efficient load-balancing. The developed implementations are optimised according to the most important features and properties of SX-Aurora architecture, which allows them achieve up to 15 times better performance compared to the optimised Intel Skylake parallel implementations and up to 5 times better performance compared to NVGRAPH library implementations for Pascal GPU architecture.
Keywords
About the authors
I. V. Afanasyev
Research Computing Center of Moscow State University
Author for correspondence.
Email: afanasiev_ilya@icloud.com
Russian Federation, Moscow, 119234
Vad. V. Voevodin
Research Computing Center of Moscow State University
Author for correspondence.
Email: vadim@parallel.ru
Russian Federation, Moscow, 119234
Vl. V. Voevodin
Research Computing Center of Moscow State University
Author for correspondence.
Email: voevodin@parallel.ru
Russian Federation, Moscow, 119234
Kazuhiko Komatsu
Tohoku University
Author for correspondence.
Email: komatsu@tohoku.ac.jp
Japan, Sendai, Miyagi, 980-8579
Hiroaki Kobayashi
Tohoku University
Author for correspondence.
Email: koba@tohoku.ac.jp
Japan, Sendai, Miyagi, 980-8579