以下の論文が IPDPS 2014 で発表されました。個人的には一番面白かった発表です。
Scalable Single Source Shortest Path Algorithms forMassively Parallel Systems
Venkatesan T. Chakaravarthy, Fabio Checconi, Fabrizio Petrini, Yogish Sabharwal
Abstract―In the single-source shortest path (SSSP) problem,we have to find the shortest paths from a source vertex v to all
other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Deltastepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically
reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2^38 vertices and 2^42 edgeson 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.
Scalable Single Source Shortest Path Algorithms forMassively Parallel Systems
Venkatesan T. Chakaravarthy, Fabio Checconi, Fabrizio Petrini, Yogish Sabharwal
Abstract―In the single-source shortest path (SSSP) problem,we have to find the shortest paths from a source vertex v to all
other vertices in a graph. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Deltastepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically
reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. The extensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 2^38 vertices and 2^42 edgeson 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.
アクセス
トータル
