Developing Efficient Implementations of Bellman-Ford and Forward-Backward Graph Algorithms for NEC SX-ACE
Developing Efficient Implementations of Bellman-Ford and Forward-Backward Graph Algorithms for NEC SX-ACE
复制标题
为 NEC SX-ACE 开发 Bellman-Ford 和前向后向图算法的高效实现
DOI：
10.14529/jsfi180311
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Hiroaki Kobayashi
中科院分区：
文献类型：
--
作者：
I. Afanasyev;A. Antonov;D. Nikitenko;Vadim V. Voevodin;V. Voevodin;Kazuhiko Komatsu;Osamu Watanabe;A. Musa;Hiroaki Kobayashi
这项工作的主要目的是证明，数据密集型应用的发展不仅是重要和有趣的，而且是非常可能的。在本文中，我们描述了NEC SX-ACE向量计算机上两种基本的图形处理算法的可能实现：单源最短路径计算的Bellman-Ford算法和强连通分量检测的前后向算法。建议的实施是根据目标架构的功能和属性进行开发和优化的，这使它们能够获得与其他传统平台(如Intel Skylake、Intel Knight Landing或IBM Power处理器)相媲美的性能。
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.