スピードアップ

コンピュータアーキテクチャにおいて、スピードアップとは、同じ問題を処理する2つのシステムの相対的なパフォーマンスを測定する数値です。より技術的に言えば、異なるリソースを持つ2つの類似したアーキテクチャ上で実行されるタスクの実行速度の向上を指します。スピードアップの概念は、特に並列処理に焦点を当てたアムダールの法則によって確立されました。しかし、スピードアップは、あらゆるリソース増強後のパフォーマンスへの影響を示すために、より一般的に使用できます。

スピードアップは、レイテンシとスループットという2種類の量に対して定義できます。^{[ 1 ]}

アーキテクチャのレイテンシは、タスクの実行速度の逆数である。

${\displaystyle L={\frac {1}{v}}={\frac {T}{W}},}$

どこ

• vはタスクの実行速度です。
• Tはタスクの実行時間です。
• Wはタスクの実行ワークロードです。

アーキテクチャのスループットとは、タスクの実行速度のことである。

${\displaystyle Q=\rho vA={\frac {\rho AW}{T}}={\frac {\rho A}{L}},}$

どこ

• ρは実行密度（例えば、パイプラインアーキテクチャにおける命令パイプラインのステージ数）である。
• Aは実行能力（例えば、並列アーキテクチャにおけるプロセッサ数）を表します。

レイテンシは、実行ワークロード単位あたりの秒数で測定されることが多い。スループットは、1秒あたりの実行ワークロード単位で測定されることが多い。スループットの別の単位として、 1サイクルあたりの命令数（IPC）があり、その逆数である1命令あたりのサイクル数（CPI）は、レイテンシの別の単位となる。

スピードアップは無次元量であり、各量の種類ごとに異なる定義がなされているため、一貫性のある指標となる。

Sをタスクの実行速度向上率、s をアーキテクチャのリソース改善によって恩恵を受けるタスク部分の実行速度向上率とします。S = sの場合、線形速度向上、すなわち理想的な速度向上が得られます。線形速度向上でタスクを実行する場合、局所的な速度向上を 2 倍にすると、全体の速度向上も 2 倍になります。これは理想的な状態であるため、非常に優れたスケーラビリティであると考えられます。

効率とは、改善されたシステムの資源利用の指標であり、次のように定義される。

${\displaystyle \eta ={\frac {S}{s}}.}$

その値は通常0から1の間です。線形スピードアップのプログラムや単一プロセッサで実行されるプログラムの効率は1ですが、並列化が難しい多くのプログラムの効率は、プロセッサ数A = sが増加するにつれて0に近づく1/ln( s )などになります。

工学分野では、効率曲線はスピードアップ曲線よりもグラフによく使われる。

• グラフ上の領域全体が有用である（一方、スピードアップ曲線ではスペースの半分が無駄になっている）。
• システムの改善がどれほど効果的に機能しているかは容易に見て取れる。
• 「完璧な速度向上」曲線を描く必要はありません。

マーケティングの文脈では、加速曲線がより頻繁に使用される。これは主に、加速曲線が右肩上がりの形状をしているため、情報量の少ない人にとって見栄えが良いからである。

並列コンピューティングにおいて、 Aプロセッサを使用した場合にAを超える高速化が観測されることがあり、これは超線形高速化と呼ばれます。超線形高速化はまれにしか起こらず、 Aプロセッサを使用した場合の理論上の最大高速化はAであると考える初心者を混乱させることがよくあります。

低レベル計算で超線形的な高速化が起こる理由の一つとして、現代のコンピュータの異なるメモリ階層に起因するキャッシュ効果が挙げられます。並列計算では、プロセッサの数だけでなく、異なるプロセッサからの累積キャッシュのサイズも変化します。累積キャッシュのサイズが大きくなると、ワーキングセットの多く、あるいはすべてがキャッシュに収まり、メモリへのアクセス時間が劇的に短縮されるため、実際の計算による高速化に加えて、さらに高速化が実現します。^{[ 4 ]}

BLAST実装で検索されるゲノムデータのような大規模なデータセットを検索する場合にも同様の状況が発生します。クラスタ内の各ノードから蓄積されたRAMにより、データセットをディスクからRAMに移動できるため、例えばmpiBLASTが検索に必要な時間を大幅に短縮できます。^{[ 5 ]}

並列でバックトラッキングを実行すると、超線形的な高速化が発生することもあります。1 つのスレッドで例外が発生すると、他の複数のスレッドが例外に到達する前に早期にバックトラッキングを開始できます。^{[ 6 ]}

最適化のための分岐限定法の並列実装では、超線形的な高速化も発生する可能性があります。^{[ 7 ]} 1 つのプロセッサによる 1 つのノードの処理は、他のプロセッサが他のノードのために行う必要がある作業に影響を与える可能性があります。

• アムダールの法則
• グスタフソンの法則
• ブルックスの法則
• カープ・フラット計量
• 並行減速
• 拡張性