parallel-processing - アムダールの法則の例

Question

アムダールの法則では、1 プロセッサ システムから N プロセッサ システムへと、計算の分数 S を順次実行する必要がある場合の計算の最大スピードアップは、せいぜい 1 であると述べています。

                 1 / (S + [(1 - S) / N])

分数Sを決定するための重要な計算のために、コードの実際の分析が行われている本やメモを知っている人はいますか?

Answer 1

Parallel Programming with .NETに関する Microsoft Patterns and Practices book には、アムダールの法則に関する非常に優れた議論があります。

コードの詳細な分析を行うのは非常に困難です。状況はそれぞれ異なるためです。

ただし、同時実行の量を決定するメカニズムがあれば、簡単に概算できるものにする必要があります。S使用可能な同時実行数とプロファイリングを変更することで、方程式を逆に解いて推定できるはずです。

Answer 2

以下に役立つリンクをいくつか示します。

マイクロソフトリサーチ | マルチコア時代のアムダールの法則の考察

アマダール (およびグスタフソン) の法則の評価と分析

速度乗数の推定に関する要約 | アムダールの法則について簡単に説明します

彼らがあなたを助けてくれることを願っています。

Answer 3

関連する原則は、並列化に固有のものではありません。プログラムの時間の 25% が特定の操作に費やされている場合、その 25% 以外のすべてを (25% に影響を与えずに) 即座に実行すると、プログラムは元の時間の 25% を要し、したがって 4 倍高速になります。

アルゴリズムに並列化可能または不可能な明確なフェーズがある場合、上記の式の適用は簡単です。 t parallelizable は通常の速度で実行されます。実際には、ほとんどのアルゴリズムが完全に 100% 並列化可能または 100% シーケンシャルな部分で構成されているとは思いません。最も興味深いケースでは、アルゴリズムは大部分を並行して実行できますが、さまざまな順序の制約があります。場合によっては、正確な順序の制約がデータに依存することがあります。そのため、「並列化の割合」は、とりわけプロセッサの数に基づいて変動する可能性があるため、それを式に当てはめようとしてもあまり役に立ちません。