アムダールの法則

アムダールの法則は、処理の一部だけを並列化・高速化するとき、全体の高速化率は高速化できない部分によって上限が決まることを示す法則です。並列度を無限に増やしても逐次部分は残ります。

■ 試験で押さえるポイント

• 全処理のうち並列化可能な割合をp、使用するプロセッサ数をnとすると、理想高速化率$S=\dfrac{1}{(1-p)+p/n}$です。通信・同期オーバヘッドを無視した上限です。

• nを無限大にすると$p/n$は0へ近づき、Sの上限は$1/(1-p)$です。逐次部分が10%なら、理論上の最大高速化は10倍です。

• 高速化対象の割合が小さいほど効果は限定されます。まず全体時間に占めるボトルネックを測り、頻繁な部分を改善する必要があります。

• 実システムでは通信、同期、負荷不均衡、メモリ帯域の競合が加わるため、実測は理想値以下になりやすいです。問題規模を増やす場合は別のスケーリング則も考慮します。

■ 選択肢での判断ポイント

$S=\dfrac{1}{\text{逐次割合}+\text{並列割合}/\text{台数}}$を使い、割合を百分率から小数へ直します。台数倍の性能が必ず得られるという選択肢は誤りです。

例: 90%を10台で並列化すると、$S=1/(0.1+0.9/10)=1/0.19\approx5.26$倍です。10台でも10倍にはなりません。