Developing Efficient Implementations of Shortest Paths and Page Rank Algorithms for NEC SX-Aurora TSUBASA Architecture
- Autores: Afanasyev I.1, Voevodin V.1, Voevodin V.1, Komatsu K.2, Kobayashi H.2
-
Afiliações:
- Research Computing Center of Moscow State University
- Tohoku University
- Edição: Volume 40, Nº 11 (2019)
- Páginas: 1753-1762
- Seção: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/206038
- DOI: https://doi.org/10.1134/S1995080219110039
- ID: 206038
Citar
Resumo
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.
Palavras-chave
Sobre autores
I. Afanasyev
Research Computing Center of Moscow State University
Autor responsável pela correspondência
Email: afanasiev_ilya@icloud.com
Rússia, Moscow, 119234
Vad. Voevodin
Research Computing Center of Moscow State University
Autor responsável pela correspondência
Email: vadim@parallel.ru
Rússia, Moscow, 119234
Vl. Voevodin
Research Computing Center of Moscow State University
Autor responsável pela correspondência
Email: voevodin@parallel.ru
Rússia, Moscow, 119234
Kazuhiko Komatsu
Tohoku University
Autor responsável pela correspondência
Email: komatsu@tohoku.ac.jp
Japão, Sendai, Miyagi, 980-8579
Hiroaki Kobayashi
Tohoku University
Autor responsável pela correspondência
Email: koba@tohoku.ac.jp
Japão, Sendai, Miyagi, 980-8579