バルク同期並列

バルク同期並列( BSP )抽象コンピュータは、並列アルゴリズムを設計するためのブリッジ モデルです。並列ランダム アクセス マシン(PRAM) モデルに似ていますが、PRAM とは異なり、BSP では通信と同期が当然のこととは見なされません。実際、必要な同期と通信を定量化することは、BSP アルゴリズムを分析する上で重要な部分です。

BSPモデルは1980年代にハーバード大学のレスリー・ヴァリアントによって開発されました。決定的な論文は1990年に出版されました。^[1]

1990 年から 1992 年にかけて、オックスフォード大学のレスリー・ヴァリアントとビル・マッコールは、プリンストンとハーバードで分散メモリ BSP プログラミング モデルのアイデアに取り組みました。1992 年から 1997 年にかけて、マッコールはオックスフォードで大規模な研究チームを率いて、さまざまな BSP プログラミング ライブラリ、言語、ツール、および多数の超並列 BSP アルゴリズムを開発しました。これには、高性能な通信回避並列アルゴリズム ^[2] や、最高のパフォーマンスと最適なパラメータ トレードオフを実現する再帰的な「不滅」並列アルゴリズムの初期の例が多数含まれています。^[3]

関心と勢いが高まるにつれ、マコールはオックスフォード大学、ハーバード大学、フロリダ大学、プリンストン大学、ベル研究所、コロンビア大学、ユトレヒト大学のグループを率いて、1996年にBSPプログラミング用のBSPlib標準を開発し、公開しました^。[4]

ヴァリアントは2000年代にBSPモデルの拡張を開発し、2011年にマルチBSPモデルを公開しました。^[5]

2017年に、マコールは、AI、アナリティクス、高性能コンピューティング（HPC）における大規模並列計算にフォールトトレランスとテールトレランスを提供するBSPモデルの主要な新しい拡張を開発しました。 ^{[6] [7]}も参照してください 。

BSP コンピュータは次の要素で構成されます。

• 処理および/またはローカルメモリトランザクションが可能なコンポーネント（プロセッサなど）
• このようなコンポーネントのペア間でメッセージをルーティングするネットワーク、および
• すべてのコンポーネントまたはコンポーネントのサブセットの同期を可能にするハードウェア機能。

これは通常、異なる計算スレッドに従う可能性のあるプロセッサのセットとして解釈され、各プロセッサは高速なローカル メモリを備え、通信ネットワークによって相互接続されています。

BSP アルゴリズムは 3 番目の機能に大きく依存しています。計算は一連のグローバルスーパーステップで進行し、これは次の 3 つのコンポーネントで構成されます。

• 同時計算: 参加しているすべてのプロセッサがローカル計算を実行できます。つまり、各プロセスはプロセッサのローカル高速メモリに格納されている値のみを使用できます。計算は他のすべての計算とは非同期に実行されますが、通信と重複する場合があります。
• 通信: プロセスはデータを交換して、リモート データの保存を容易にします。
• バリア同期: プロセスがこのポイント (バリア) に到達すると、他のすべてのプロセスが同じバリアに到達するまで待機します。

計算と通信のアクションは、時間順に並べる必要はありません。通信は通常、送信と受信のメッセージ パッシング呼び出しをペアにした双方向のものではなく、片側のPUTおよびGET リモート ダイレクト メモリ アクセス(RDMA) 呼び出しの形式をとります。

バリア同期はスーパーステップを終了し、すべての片側通信が適切に終了することを保証します。双方向通信に基づくシステムでは、送信されるすべてのメッセージに対してこの同期コストが暗黙的に含まれます。バリア同期方式は、BSP コンピュータのハードウェア機能に依存します。Valiant の元の論文では、この機能は現在のスーパーステップの終了がグローバルに到達したかどうかを定期的にチェックします。このチェックの期間は で示されます。^[1]${\displaystyle L}$

BSP モデルは、問題の過剰分解とプロセッサの過剰サブスクリプションを通じて、分散メモリ コンピューティングの自動メモリ管理にも適しています。計算は物理プロセッサの数よりも多くの論理プロセスに分割され、プロセスはプロセッサにランダムに割り当てられます。この戦略は、作業と通信の両方においてほぼ完璧な負荷分散につながることが統計的に示されています。

多くの並列プログラミング システムでは、メッセージの送受信やメモリ間の転送など、個々のアクションのレベルで通信が考慮されています。並列プログラムでは同時に多数の通信アクションが実行され、それらの相互作用が複雑になることが多いため、この作業は困難です。特に、単一の通信アクションが完了するまでにかかる時間について多くを語ることは困難です。

BSP モデルでは、通信アクションをまとめて考慮します。これにより、データ セットの通信にかかる時間の上限を指定できます。BSP では、スーパーステップのすべての通信アクションを 1 つの単位と見なし、この単位の一部として送信されるすべての個別のメッセージのサイズが固定されていると想定します。

スーパーステップの受信メッセージまたは送信メッセージの最大数は で示されます。通信ネットワークのデータ配信能力は、プロセッサがサイズ 1 のメッセージを配信するのにかかる時間として定義されるパラメータ によって表されます。 ${\displaystyle h}$${\displaystyle g}$${\displaystyle hg}$${\displaystyle h}$

長さのメッセージは、サイズ 1 のメッセージよりも送信に時間がかかることは明らかです。ただし、BSP モデルでは、メッセージの長さが のメッセージと長さが のメッセージとを区別しません。どちらの場合も、コストは であると言われています。 ${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle mg}$

パラメータは次の要素に依存します。 ${\displaystyle g}$

• 通信ネットワーク内で対話するために使用されるプロトコル。
• プロセッサと通信ネットワークの両方によるバッファ管理。
• ネットワークで使用されるルーティング戦略。
• BSPランタイム システム。

実際には、は各並列コ​​ンピュータごとに経験的に決定されます。は正規化された単一ワード配信時間ではなく、連続トラフィック条件下での単一ワード配信時間であることに注意してください。 ${\displaystyle g}$${\displaystyle g}$

BSP モデルの一方的な通信にはバリア同期が必要です。 バリアは潜在的にコストがかかりますが、循環的なデータ依存関係を作成できないため、デッドロックやライブロックの可能性を回避できます。それらを検出して処理するためのツールは不要です。バリアは、新しい形式のフォールト トレランスも可能にします^{[引用が必要]}。

バリア同期のコストは、いくつかの問題の影響を受けます。

• 参加している同時計算の完了時間の変動によって課せられるコスト。1 つを除くすべてのプロセスがこのスーパーステップの作業を完了し、完了すべき作業がまだたくさんある最後のプロセスを待っている例を考えてみましょう。実装でできる最善のことは、各プロセスがほぼ同じサイズの問題を処理するようにすることです。
• すべてのプロセッサでグローバルに一貫した状態に到達するためのコスト。これは通信ネットワークによって異なりますが、同期に使用できる専用ハードウェアがあるかどうか、およびプロセッサによる割り込みの処理方法によっても異なります。

バリア同期のコストは で表されます。BSPコンピュータの同期メカニズムがValiant ^[1]によって提案されているとおりである場合 、 の値は実際には経験的に決定されます。 ${\displaystyle l}$${\displaystyle l<L}$${\displaystyle l}$

大型コンピュータでは、バリアは高価であり、大規模になるとますます高価になります。BSP コンピューティングなどのコンテキストで、既存のアルゴリズムから同期ポイントを削除することに関する膨大な文献があります。たとえば、多くのアルゴリズムでは、ローカル情報とすでに受信したメッセージの数を比較するだけで、スーパーステップのグローバル終了をローカルに検出できます。これにより、通信に必要な最小限の遅延と比較して、グローバル同期のコストがゼロになります。^[8]しかし、この最小限の遅延は、将来のスーパーコンピュータ アーキテクチャとネットワーク相互接続でさらに増加すると予想されています。BSP モデルは、並列計算の他のモデルと同様に、この傾向に対処するために適応する必要があります。マルチ BSP は、BSP ベースのソリューションの 1 つです。^[5]

スーパーステップのコストは、次の 3 つの項の合計として決定されます。

• 最も長時間実行されるローカル計算のコスト
• プロセッサ間のグローバル通信のコスト
• スーパーステップ終了時のバリア同期のコスト

したがって、プロセッサ の 1 つのスーパーステップのコストは次のようになります。${\displaystyle p}$

${\displaystyle max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l}$ ここで、はプロセス におけるローカル計算のコスト、 はプロセス によって送信または受信されるメッセージの数です。ここでは同種のプロセッサが想定されていることに注意してください。式は と記述されるのが一般的です。ここで、 およびは最大値です。BSP アルゴリズム全体のコストは、各スーパーステップのコストの合計です。 ${\displaystyle w_{i}}$${\displaystyle i}$${\displaystyle h_{i}}$${\displaystyle i}$${\displaystyle w+hg+l}$${\displaystyle w}$${\displaystyle h}$

${\displaystyle W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl}$ ここで、スーパーステップの数です。 ${\displaystyle S}$

${\displaystyle W}$、、およびは通常、問題のサイズに応じて変化する関数としてモデル化されます。BSP アルゴリズムのこれら 3 つの特性は、通常、漸近記法、たとえばで記述されます。 ${\displaystyle H}$${\displaystyle S}$${\displaystyle H\in O(n/p)}$

BSPへの関心は急上昇しており、GoogleはPregelとMapReduceを介して大規模なグラフ分析の主要技術としてそれを採用しました。また、次世代のHadoopではMapReduceモデルがHadoopインフラストラクチャの残りの部分から切り離されているため、明示的なBSPプログラミングやその他の高性能並列プログラミングモデルをHadoop上に追加するオープンソースプロジェクトが活発に行われています。例としてはApache HamaやApache Giraphがあります。^[9]

BSPは、特定のアーキテクチャや計算パラダイムのモデル化にBSPが適していないという懸念に対処するために、多くの著者によって拡張されてきました。その一例が分解可能なBSPモデルです。このモデルは、Bulk Synchronous Parallel ML (BSML)、BSPLib、Apache Hama、^[9]、Pregelなど、多くの新しいプログラミング言語やインターフェースの作成にも使用されています。^[10]

BSPLib標準の注目すべき実装としては、パダーボルン大学のBSPライブラリ^[11]とジョナサン・ヒルのオックスフォードBSPツールセット^[12]があります。最新の実装には、BSPonMPI ^{[13] （}メッセージパッシングインターフェース上でBSPをシミュレートする）やMulticoreBSP ^{[14] [15]}（最新の共有メモリアーキテクチャを対象とした新しい実装）などがあります。C用のMulticoreBSPは、ネストされたBSP実行を開始し、明示的なマルチBSPプログラミングを可能にする機能が特に注目に値します。

• 自動相互排除
• アパッチ・ハマ
• アパッチ・ギラフ
• コンピュータ クラスター
• 同時実行コンピューティング
• 並行性（コンピュータサイエンス）
• データフロープログラミング
• グリッドコンピューティング
• LogPマシン
• 並列コンピューティング
• 並列プログラミングモデル

• DB Skillicorn、Jonathan Hill、WF McColl、「BSP に関する質問と回答」^{[永久リンク切れ‍ ]} (1996)
• BSPワールドワイド
• BSP関連論文
• (フランス語) Bulk Synchronous Parallel ML ( (英語)公式サイト)
• アパッチ・ハマ
• アパッチ・ギラフ
• パーダーボルン大学 BSP 図書館
• BSPonMPI
• マルチコアBSP