Developing Efficient Implementations of Shortest Paths and Page Rank Algorithms for NEC SX-Aurora TSUBASA Architecture

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...

Full description

Saved in:
Bibliographic Details
Published in:Lobachevskii journal of mathematics 2019-11, Vol.40 (11), p.1753-1762
Main Authors: Afanasyev, I. V., Voevodin, Vad. V., Voevodin, Vl. V., Komatsu, Kazuhiko, Kobayashi, Hiroaki
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Analysis
Computer architecture
Geometry
Mathematical Logic and Foundations
Mathematics
Mathematics and Statistics
Probability Theory and Stochastic Processes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1995-0802
1818-9962
DOI:10.1134/S1995080219110039