Developing Efficient Implementations of Bellman–Ford and Forward-Backward Graph Algorithms for NEC SX-ACE

Ilya V. Afanasyev, Alexander S. Antonov, Dmitry A. Nikitenko, Vadim V. Voevodin, Vladimir V. Voevodin, Kazuhiko Komatsu, Osamu Watanabe, Akihiro Musa, Hiroaki Kobayashi

Abstract


The main goal of this work is to demonstrate that the development of data-intensive appli- cations for vector systems is not only important and interesting, but is also very possible. In this paper we describe possible implementations of two fundamental graph-processing algorithms for an NEC SX-ACE vector computer: the Bellman–Ford algorithm for single source shortest paths computation and the Forward-Backward algorithm for strongly connected components detection. The proposed implementations have been developed and optimised in accordance with features and properties of the target architecture, which allowed them to achieve performance comparable to other traditional platforms, such as Intel Skylake, Intel Knight Landing or IBM Power processors.


Full Text:

PDF

References


Besta, M., Marending, F., Solomonik, E., Hoefler, T.: SlimSell: A vectorizable graph representation for breadth-first search. In: 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE (may 2017), DOI: 10.1109/ipdps.2017.93

Fleischer, L.K., Hendrickson, B., Pınar, A.: On identifying strongly connected components in parallel. In: Lecture Notes in Computer Science, pp. 505–511. Springer Berlin Heidelberg (2000), DOI: 10.1007/3-540-45591-4_68

Jiang, L., Chen, L., Qiu, J.: Performance characterization of multi threaded graph processing applications on many-integrated-core architecture. In: 2018 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE (apr 2018), DOI: 10.1109/ispass.2018.00033

Nepomniaschaya, A.S.: An associative version of the bellman-ford algorithm for finding the shortest paths in directed graphs. In: Lecture Notes in Computer Science, pp. 285–292. Springer Berlin Heidelberg (2001), DOI: 10.1007/3-540-44743-1_28




Publishing Center of South Ural State University (454080, Lenin prospekt, 76, Chelyabinsk, Russia)