0. 概要

大規模計算を行うにあたって並列計算処理が必要となる。一般的に並列計算を語る上で「メモリ」及び「プロセッサ」をどのように配置するかが重要となる。よく見るアーキテクチャ形式としては、Parallel Random Access Machine(PRAM)と呼ばれる共有メモリを1つ置いて、複数のプロセッサが演算結果をそこで共有し合うような形式が多い。PRAMは理想的なアーキテクチャであるものの、その実現は難しく多くの場合はBulk synchronous parallel(BSP)形式による実現となる。今回はこのBSPに入門していきたい。BSPは際立って新しい理論でなく、歴史古く1980年代にハーバード大学のLeslie Valiantによって開発された。

かなり有名なモデルではあるものの日本語の解説記事が少ない・・・。
何か他の呼ばれ方があるのだろうか。

1. BSPモデル

BSPモデルのアーキテクチャについて説明する。

必要な用語としては以下である:

メモリ: 演算結果の保存
PU(Process Unit): 演算
SuperStep: 1つあたりの演算

PRAM

BSPを理解する上でPRAMの説明は必要ないが、比較しておくと違いが分かりやすいと思うので説明したい。

PRAMは以下のように複数のプロセッサが演算を行うための入力値や一時変数、演算結果等を全て共有メモリに保存する形式である。
基本的には演算順序がおかしくならないよう1命令毎に同期が取られているものだとする。

複数のプロセッサで同じ資源を使う場合があるので、デッドロック等の発生には気を付ける必要がある。

BSP

PRAMと比較してBSPは以下のようにメモリとプロセッサが完全に別れており、
デッドロック等の発生が起こらない設計になっている。

Local computeの領域は完全に独立して動作する。
ここで所定の演算を行えるようにメモリ上に情報を展開しておく必要がある。

データ共有

しかし、並列計算なのに独立していては入力値、一時変数、演算結果の共有が出来ない。
そこで各PUは演算が終了次第他のプロセスに必要なデータを共有する。よって、以下のような形式となる。

よくネットワーク層がメモリ側についている場合があるが、あるPUがどこのPUにデータを送るか等のインテリジェントな判断をメモリ側がするとは思えないのでこのような構成としている。意味合い的には同じである。

バリア同期

次にデータ共有において、共有のタイミングを同期する必要がある。これをBSPではバリア同期という。
換言すると、各PUの演算時間であるLocal computeは各PUによって時間が異なるため、
そのギャップを埋める必要がある。

以下のようにPU処理の後に全PUの処理時間が同じになるようにバリア同期を入れる。

他の表現では、各PUの演算処理が終わった直後に通信を行い、
次の演算が開始するまでの時間をそろえるためにバリア同期を入れている。

因みに、次の演算が開始するまでの時間をSuper stepという。

2. 例題: BSPモデルを適用したPrefix Sum

Cudaの並列処理の資料などを見ているとPrefix sumが並列処理でいうところのHello worldのようである。
Prefix sumとは[3, -1, 4, 1, 5, 9, 2, 6, 5]のような数列が与えられた時に前から順に足し算していくことである。
これにPU=3のBSPモデルを適用すると以下のような演算となる。

引用: BSP(Bulk synchronous parallel)モデル再訪