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

doi:10.14529/jsfi180311

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

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

The main goal of this work is to demonstrate that the development of data-intensive applications 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.

Original language	English
Pages (from-to)	65-69
Number of pages	5
Journal	Supercomputing Frontiers and Innovations
Volume	5
Issue number	3
DOIs	https://doi.org/10.14529/jsfi180311
Publication status	Published - 2018

Keywords

Data-intensive applications
Graph algorithms
NEC SX-ACE
Vector computing

Access to Document

10.14529/jsfi180311

Cite this

@article{477f29dc9bae45ecae43ea61615518ca,

title = "Developing efficient implementations of Bellman-Ford and Forward-Backward graph algorithms for NEC SX-ACE",

abstract = "The main goal of this work is to demonstrate that the development of data-intensive applications 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.",

keywords = "Data-intensive applications, Graph algorithms, NEC SX-ACE, Vector computing",

author = "Afanasyev, {Ilya V.} and Antonov, {Alexander S.} and Nikitenko, {Dmitry A.} and Voevodin, {Vadim V.} and Voevodin, {Vladimir V.} and Kazuhiko Komatsu and Osamu Watanabe and Akihiro Musa and Hiroaki Kobayashi",

note = "Publisher Copyright: {\textcopyright} The Authors 2018.",

year = "2018",

doi = "10.14529/jsfi180311",

language = "English",

volume = "5",

pages = "65--69",

journal = "Supercomputing Frontiers and Innovations",

issn = "2409-6008",

publisher = "South Ural State University",

number = "3",

}

TY - JOUR

T1 - Developing efficient implementations of Bellman-Ford and Forward-Backward graph algorithms for NEC SX-ACE

AU - Afanasyev, Ilya V.

AU - Antonov, Alexander S.

AU - Nikitenko, Dmitry A.

AU - Voevodin, Vadim V.

AU - Voevodin, Vladimir V.

AU - Komatsu, Kazuhiko

AU - Watanabe, Osamu

AU - Musa, Akihiro

AU - Kobayashi, Hiroaki

N1 - Publisher Copyright: © The Authors 2018.

PY - 2018

Y1 - 2018

N2 - The main goal of this work is to demonstrate that the development of data-intensive applications 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.

AB - The main goal of this work is to demonstrate that the development of data-intensive applications 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.

KW - Data-intensive applications

KW - Graph algorithms

KW - NEC SX-ACE

KW - Vector computing

UR - http://www.scopus.com/inward/record.url?scp=85057576866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057576866&partnerID=8YFLogxK

U2 - 10.14529/jsfi180311

DO - 10.14529/jsfi180311

M3 - Article

AN - SCOPUS:85057576866

SN - 2409-6008

VL - 5

SP - 65

EP - 69

JO - Supercomputing Frontiers and Innovations

JF - Supercomputing Frontiers and Innovations

IS - 3

ER -

Developing efficient implementations of Bellman-Ford and Forward-Backward graph algorithms for NEC SX-ACE

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this