グラフ問題に特化したバルク同期並列「Pregel」 「Pregel」はグラフ問題に特化したソリューションとしてグーグル社で開発され、「Bulk Synchronous Parallel(BSP、バルク同期並列)」の概念を用います。PregelでSSSP問題をどのように解決できるかを見ていきます。 BSPの概念 BSPは並列アルゴリズムを実行するための計算モデルで、「superstep」という処理単位を繰り返し実施し、分散環境で問題を解決する概念です。 処理の流れ Pregelの考えで、SSSP問題を解決する際の都市間でのデータ授受の流れ(BSPの各superstepにおける処理)を示します(分散環境では、各都市の処理は異なったプロセッサで処理され、スケーラブルな構成になります)。