10.1.1 速度向上 — 何を期待するか

4 つのプロセッサ上で動作するようにプログラムを並列化した場合、そのプログラムは、1 つのプロセッサ上で動作させるときの約 1/4 の時間で処理できる (4 倍の速度向上になる) と期待できるでしょうか。

おそらく、答えは「ノー」です。プログラムの全体的な速度向上は、並列実行しているコード中で消費される実行時間の割り合いによって厳密に制限されると証明できます (アムダールの法則)。適用されるプロセッサがいくつになろうとも、これは常に真です。事実、並列実行した実行プログラムの合計時間のパーセンテージを p とすると、理論的な速度向上の制限は 100/(100–p) となります。したがって、プログラムの 60% だけが並列実行した場合、プロセッサの数にかかわらず、速度向上は最大 2.5 倍です。そして、プロセッサが 4 つの場合、このプログラムの理論的な速度向上は (最大限の効率が発揮されたと仮定しても) 1.8 倍です。4 倍にはなりません。オーバーヘッドがあれば、実際の速度向上はさらに小さくなります。

最適化のことを考えると、ループの選択は重要です。プログラムの合計実行時間のほんの一部としか関わらないループを並列化しても、最小の効果しか得られません。効果を得るためには、実行時間の大部分を消費するループを並列化しなければなりません。したがって、どのループが重要であるかを決定し、そこから始めるのが第一歩です。

問題のサイズも、並列実行するプログラムの割合を決定するのに重要な役割を果たし、その結果、速度向上にもつながります。問題のサイズを増やすと、ループの中で行われる作業量も増えます。3 重に入れ子にされたループは、作業量が 3 乗になる可能性があります。入れ子の外側のループを並列化する場合、問題のサイズを少し増やすと、並列化していないときのパフォーマンスと比べて、パフォーマンスが大幅に向上します。