並列アルゴリズムの分析

コンピュータ サイエンスにおいて、並列アルゴリズムの分析とは、並列に実行されるアルゴリズムの計算の複雑さ、つまり、アルゴリズムを実行するために必要な時間、ストレージ、またはその他のリソースの量を調べるプロセスです。多くの点で、並列アルゴリズムの分析は順次アルゴリズムの分析に似ていますが、複数の連携実行スレッドの動作について推論する必要があるため、一般的にはより複雑です。並列分析の主な目的の 1 つは、プロセッサの数が変更されると、並列アルゴリズムのリソースの使用 (速度、スペースなど) がどのように変化するかを理解することです。

いわゆる作業時間 (WT) (作業深度または作業スパンと呼ばれることもある) フレームワークは、もともと Shiloach と Vishkin ^[1]によって 並列アルゴリズムの概念化と記述のために導入されました。WT フレームワークでは、並列アルゴリズムは最初に並列ラウンドの観点から記述されます。各ラウンドでは、実行される操作が特徴付けられますが、いくつかの問題は抑制できます。たとえば、各ラウンドの操作数は明確である必要はなく、プロセッサについて言及する必要はなく、ジョブへのプロセッサの割り当てに役立つ可能性のある情報は考慮する必要はありません。次に、抑制された情報が提供されます。抑制された情報を含めることは、この記事の後半で説明する Brent ^[2]によるスケジューリング定理の証明によって導かれます。WT フレームワークは、並列アルゴリズムの初期記述を大幅に簡素化できる一方で、その初期記述で抑制された詳細を挿入することはそれほど難しくないことが多いため便利です。例えば、WTフレームワークは、並列アルゴリズムの本（並列ランダムアクセスマシンPRAMモデル用） ^[3] や^[4] 、 および授業ノート^[5]の基本的なプレゼンテーションフレームワークとして採用されました。以下の概要では、WTフレームワーク内で説明されていない場合でも、より一般的な並列アルゴリズムを分析するためにWTフレームワークをどのように使用できるかを説明しています。

p 個のプロセッサを持つ マシンで計算が実行されるとします。T _{p は}計算の開始から終了までの時間を表します。計算の実行時間の分析では、次の概念に重点が置かれます。

• p個のプロセッサによって実行される計算の作業量は、プロセッサが実行する基本操作の合計数です。^[6]プロセッサの同期による通信オーバーヘッドを無視すると、これは単一のプロセッサで計算を実行するのに使用される時間（T ₁と表記）に等しくなります。
• 深さまたはスパンは、データの依存関係により順番に実行する必要がある最長の一連の操作の長さです（深さは計算のクリティカルパス長とも呼ばれる。 [ 7]^深さ/スパンを最小化することは並列アルゴリズムの設計において重要である。深さ/スパンによって実行時間が最短になるからである。^[8]無限数のプロセッサを持つ理想的なマシンを使用して計算に費やされる時間T _∞として定義することもできる^[9]
• 計算コストは​​pT pという量で表されます。これは_、すべてのプロセッサが計算と待機に費やした合計時間を表します。^[6]

作業、スパン、コストの定義から、いくつかの有用な結果が得られます。

• 作業法則。コストは常に作業以上である：pT _p ≥ T _1。これはp個のプロセッサが最大でp個の操作を並列に実行できるという事実から導かれる。^{[6] [9]}
• スパンの法則。有限個のプロセッサpは無限個のプロセッサよりも性能が優れているわけではなく、T _p ≥ T _∞となる。^[9]

これらの定義と法則を使用すると、次のようなパフォーマンスの尺度が与えられます。

• スピードアップとは、並列実行によって逐次実行に比べて得られる速度の向上です。S _p = T ₁ / T _{p 。p}個のプロセッサに対してスピードアップがΩ( p )の場合( big O 記法を使用)、スピードアップ_{は線形であり、作業法則により}T ₁ / T _p ≤ pとなるため、単純な計算モデルでは最適です(メモリ階層効果により、実際には超線形のスピードアップが発生する可能性があります)。T 1 / T _p = pの状況は、完全な線形スピードアップと呼ばれます。 ^{[9]線形のスピードアップを示すアルゴリズムは、}スケーラブルであると言われています。 ^[6]この本では、多くの重要な並列アルゴリズムのスピードアップに関する解析式が紹介されています。 ^[10]
• 効率はプロセッサあたりの速度向上、S _p / pである。^[6]
• 並列性はT ₁ / T _∞の比率で、任意の数のプロセッサで可能な最大のスピードアップを表します。スパンの法則により、並列性はスピードアップを制限します。p > T ₁ / T _∞の場合、次のようになります。^[9] $${\displaystyle {\frac {T_{1}}{T_{p}}}\leq {\frac {T_{1}}{T_{\infty }}}}<p.}$$
• スラックネスはT ₁ / ( pT _∞ )である。スラックネスが1未満の場合、（スパンの法則により）p個のプロセッサでは完全な線形高速化は不可能であることを意味する。^[9]

並列アルゴリズムの分析は、通常、プロセッサの数が無制限であるという仮定の下で行われます。これは非現実的ですが、問題ではありません。なぜなら、N個のプロセッサで並列に実行できる計算は、各プロセッサに複数の作業単位を実行させることで、 p < N 個のプロセッサで実行できるからです。ブレントの法則と呼ばれる結果によると、このような「シミュレーション」は、次の式で制限される時間T _pで実行できます。 ^[11]

${\displaystyle T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},}$

あるいは、あまり正確ではないが、^[6]

${\displaystyle T_{p}=O\left(T_{N}+{\frac {T_{1}}{p}}\right).}$

この法則の別の表現では、 T _{p の}上限と下限は次のように 定められています。

${\displaystyle {\frac {T_{1}}{p}}\leq T_{p}\leq {\frac {T_{1}}{p}}+T_{\infty }}$。

スパン（深さ）T∞と作業T1_{の組み合わせが}計算時間に妥当な境界を与えることを示している。^[2]