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

Authors

  • Ilya V. Afanasyev Lomonosov Moscow State University
  • Alexander S. Antonov Lomonosov Moscow State University
  • Dmitry A. Nikitenko Lomonosov Moscow State University
  • Vadim V. Voevodin Lomonosov Moscow State University
  • Vladimir V. Voevodin Lomonosov Moscow State University
  • Kazuhiko Komatsu Tohoku University
  • Osamu Watanabe Tohoku University
  • Akihiro Musa Tohoku University
  • Hiroaki Kobayashi Tohoku University

DOI:

https://doi.org/10.14529/jsfi180311

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.

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

Downloads

Published

2018-11-20

How to Cite

Afanasyev, I. V., Antonov, A. S., Nikitenko, D. A., Voevodin, V. V., Voevodin, V. V., Komatsu, K., Watanabe, O., Musa, A., & Kobayashi, H. (2018). Developing Efficient Implementations of Bellman–Ford and Forward-Backward Graph Algorithms for NEC SX-ACE. Supercomputing Frontiers and Innovations, 5(3), 65–69. https://doi.org/10.14529/jsfi180311

Issue

Vol. 5 No. 3 (2018)

License

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-Non Commercial 3.0 License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

Most read articles by the same author(s)

1 2 3 > >>