以下の論文が 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.
