[ExaGraph] 超大規模グラフに対する最短路問題

David Bader のチームは共有メモリ型並列計算機 Cray MTA-2 上の40プロセッサで並列最短路アルゴリズムを実行し、１億頂点、10億辺のスケールフリーグラフ（有向辺）を10秒以内に解く。逐次版と比較し、30倍のスピードアップ。

http://www.cc.gatech.edu/~bader/papers/ShortestPaths.html

彼らの主張は以下の通りである。Cray XMTのような超巨大共有メモリ並列計算機が高性能なグラフ処理を実現するハードウェアプラットフォームであると主張。

Implementations of PRAM graph algorithms for arbitrary sparse graphs are typically memory intensive, and the memory accesses are fine-grained and highly irregular. This often leads to poor performance on cache-based systems. On distributed memory clusters, few parallel graph algorithms outperform the best sequential implementations due to long memory latencies and high synchronization costs [Bader et al. 2005]. Parallel shared memory systems are a more supportive platform. They offer higher memory bandwidth and lower latency than clusters, and the global shared memory greatly improves developer productivity.

Bader, D., Cong, G., and Feo, J. 2005. On the architectural requirements for efficient execution of graph algorithms. In Proc. 34th Int’l Conf. on Parallel Processing (ICPP). IEEE Computer Society, Oslo, Norway.

http://www.cc.gatech.edu/~bader/papers/ListRankMTA-ICPP2005.pdf

一方、2010 年に発表された Pregel (Google) の論文ではトータルで300コアからなる分散メモリ計算機上、10億頂点、1270億辺に対して10分で最短路問題 (シングルソース）を解いている。大規模グラフの個々の物理マシンへのマッピングはランダムハッシュを用いており（トポロジー構成を考慮したマッピングは考えていない）、かつ⊿ステッピングのような最適化されたアルゴリズムも用いていない。ただ、このようなナイーブな実装でも、Parallel BGL で解いた問題サイズと実行時間と同等以上であることを主張している。

Parallel BGL (http://osl.iu.edu/research/pbgl/) は MPI をベースにした C++の 分散メモリ用並列グラフ処理ライブラリである。2005年の OOPSLA で発表された "Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computation" の論文に基本アイデアが書かれている。

並列単一最短路問題 Delta-stepping のアルゴリズムは以下の2本の論文に記載されている。
Meyer, U. and Sanders, P. 2003. Δ-stepping: a parallelizable shortest path algorithm. J. Algs. 49, 1, 114–152.
Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel single source shortest path algorithm. In ESA ’98: Proceedings of the 6th Annual European Symposium on Algorithms, pages 393–404. Springer-Verlag, 1998.

GPU を用いた最短路問題を解く研究は前にも紹介したが以下の論文がある。1000万頂点から成る平均6次数のランダムグラフに対してはBFSを1秒で SSSP を1.5秒で解くことに成功している。但し、スケールフリー性がある（一部の頂点の次数は非常に多い）グラフやDIMACS チャレンジの実道路ネットワーク、CPUに対する優位性がほとんど得られていない。

Accelerating large graph algorithms on the GPU using CUDA Pawan Harish and P. J. Narayanan

何れにしても、オンメモリ上にグラフデータが存在することが仮定であり、Graph500 で想定しているようなペタバイトレベルのグラフに関しては当然扱った研究はない。