Parallel-algorithm-models
並列アルゴリズム-モデル
並列アルゴリズムのモデルは、データと処理方法を分割する戦略を検討し、適切な戦略を適用して相互作用を削減することにより開発されます。 この章では、次の並列アルゴリズムモデルについて説明します-
- データ並列モデル
- タスクグラフモデル
- ワークプールモデル
- マスタースレーブモデル
- 生産者消費者またはパイプラインモデル *ハイブリッドモデル
データ並列
データ並列モデルでは、タスクはプロセスに割り当てられ、各タスクは異なるデータに対して同様のタイプの操作を実行します。* データの並列性*は、複数のデータ項目に適用される単一の操作の結果です。
データ並列モデルは、共有アドレススペースとメッセージパッシングパラダイムに適用できます。 データ並列モデルでは、局所性保存分解を選択するか、最適化された集団相互作用ルーチンを使用するか、計算と相互作用を重複させることにより、相互作用のオーバーヘッドを削減できます。
データ並列モデルの問題の主な特徴は、データ並列性の強度が問題のサイズとともに増加することです。これにより、より大きな問題を解決するためにより多くのプロセスを使用できるようになります。
例-密行列の乗算。
タスクグラフモデル
タスクグラフモデルでは、並列性は*タスクグラフ*で表されます。 タスクグラフは、自明または非自明のいずれかです。 このモデルでは、タスク間の相関関係を利用して、局所性を促進したり、相互作用コストを最小化します。 このモデルは、タスクに関連付けられた計算の数と比較して、タスクに関連付けられたデータの量が膨大になる問題を解決するために実施されます。 タスクは、タスク間のデータ移動のコストを改善するために割り当てられます。
例-並列クイックソート、スパースマトリックス因数分解、および分割統治アプローチによる並列アルゴリズム。
ここでは、問題はアトミックタスクに分割され、グラフとして実装されます。 各タスクは、1つ以上の先行タスクに依存する独立したジョブ単位です。 タスクの完了後、先行タスクの出力は依存タスクに渡されます。 先行タスクを持つタスクは、その先行タスク全体が完了したときにのみ実行を開始します。 グラフの最終出力は、最後の依存タスクが完了すると受信されます（上の図のタスク6）。
ワークプールモデル
ワークプールモデルでは、負荷を分散するために、タスクがプロセスに動的に割り当てられます。 したがって、任意のプロセスが任意のタスクを実行する可能性があります。 このモデルは、タスクに関連付けられたデータの量がタスクに関連付けられた計算よりも比較的少ない場合に使用されます。
プロセスにタスクを事前に割り当てる必要はありません。 タスクの割り当ては集中化または分散化されます。 タスクへのポインターは、物理的に共有されたリスト、優先度キュー、またはハッシュテーブルまたはツリーに保存されます。また、物理的に分散されたデータ構造に保存することもできます。
タスクは最初に使用可能になるか、動的に生成されます。 タスクが動的に生成され、タスクの分散割り当てが行われる場合、すべてのプロセスが実際にプログラム全体の完了を検出し、他のタスクの検索を停止できるように、終了検出アルゴリズムが必要です。
例-並列ツリー検索
マスタースレーブモデル
マスタースレーブモデルでは、1つ以上のマスタープロセスがタスクを生成し、スレーブプロセスに割り当てます。 次の場合、タスクを事前に割り当てることができます-
- マスターがタスクのボリュームを推定できる、または
- ランダムな割り当てにより、負荷を分散するのに十分なジョブを実行できます。または
- スレーブには、異なる時間にタスクの小さな部分が割り当てられます。
通常、このモデルは shared-address-space または message-passing paradigms に適しています。これは、相互作用が自然に2つの方法であるためです。
場合によっては、タスクを段階的に完了する必要があり、次の段階のタスクを生成する前に各段階のタスクを完了する必要があります。 マスタースレーブモデルは、*階層*または*マルチレベルマスタースレーブモデル*に一般化できます。このモデルでは、最上位レベルのマスターがタスクの大部分を第2レベルのマスターに送ります。タスク自体の一部を実行できます。
マスタースレーブモデルを使用する際の注意事項
マスターが輻輳ポイントにならないように注意する必要があります。 タスクが小さすぎる場合や、作業者が比較的速い場合に発生する可能性があります。
タスクは、タスクの実行コストが通信のコストと同期のコストを支配するように選択する必要があります。
非同期の相互作用は、相互作用とマスターによる作業生成に関連する計算の重複を支援する場合があります。
パイプラインモデル
また、*生産者-消費者モデル*として知られています。 ここでは、一連のデータが一連のプロセスを介して渡され、各プロセスが何らかのタスクを実行します。 ここでは、新しいデータの到着により、キュー内のプロセスによる新しいタスクの実行が生成されます。 プロセスは、サイクルの有無にかかわらず、線形または多次元配列、ツリー、または一般的なグラフの形のキューを形成できます。
このモデルは、生産者と消費者のチェーンです。 キュー内の各プロセスは、キュー内で先行するプロセスの一連のデータ項目のコンシューマー、およびキュー内で後続のプロセスのデータのプロデューサーと見なすことができます。 キューは線形チェーンである必要はありません。有向グラフにすることができます。 このモデルに適用できる最も一般的な相互作用最小化手法は、計算との相互作用の重複です。
例-並列LU分解アルゴリズム。
ハイブリッドモデル
問題を解決するために複数のモデルが必要な場合は、ハイブリッドアルゴリズムモデルが必要です。
ハイブリッドモデルは、階層的に適用される複数のモデル、または並列アルゴリズムの異なるフェーズに順次適用される複数のモデルのいずれかで構成されます。
例-並列クイックソート
