A Bridging Model for parallel Computation (1990)

December 11, 2021

バッチ処理グラフの最適化を目的として演算処理のバルク同期並列(bulk synchronous parallel、 BSP)を提唱した。 BPSは、Apache Giraph, Spark の GraphX API, Gelly APIで採用され、なかでもGoogleのPregelで知られるようになった*1。 BPSの目的は、ハードウェアと並列計算の高水準なプログラミングモデルがどちらもBPSに準ずることで、高水準なプログラミングモデルで実装された並列計算を多様なハードウェア上で動かすことにある。 フォン・ノイマンモデル型のコンピュータであれば、ハードウェアの種類を意識することなく、その上で逐次計算をおこなう多様なソフトウェアを動かせる。 フォン・ノイマンモデルは、多様なハードウェアと多様なソフトウェアをつなぐ。 BPSは、並列計算用のハードウェアと高水準な並列計算のプログラミングモデルをつなぐためにある。

BPSモデルは、複数のコンポーネント, router, 同期機構からなる。 各コンポーネントは逐次処理やメモリとして機能する。 ルータはコンポーネントから別のコンポーネントにメッセージを配信する。 同期機構は、パラメタ\(L\)で指定した一定間隔で、複数のコンポーネントの同期をとる。 間隔\(L\)の間に、各コンポーネントで逐次計算を実行し、routerはコンポーネント間のメッセージを交換する。 \(L\)時間経過したあとで、すべてのコンポーネントの処理が終了していれば、コンポーネント全体を次の計算に進める。 そうでなければ、終わっていないコンポーネントの計算を\(L\)時間続け、終わるまでこれをくりかえす。

論文をこちらからダウンロードできます。