アルゴリズムを並列化することで、線形速度の向上以上の効果が得られるケースはありますか?
2 に答える
5
理論的な観点から到達できる最大値は、線形の高速化です。実際には、超線形の高速化が可能です。たとえば単一コアのキャッシュに収まらないなどの理由で、プロセッサ キャッシュの効果を利用できるように問題を分散できる場合、問題は線形よりもうまくスケーリングできます。
于 2009-05-24T10:56:34.490 に答える
1
理論的にはありませんが、実際にはそうなる可能性があります (基盤となるハードウェアと特定の問題によって異なります)。並列コードと順次コードを比較するのは簡単ではありません (単一のプロセッサ/スレッドで実行されている並列実装だけでなく、最速の順次実装を並列実装と比較する必要があります)。
それでも、誰かが線形以上のスピードアップについて話すとき、私はいつも疑っています。彼らはそれを正しく測定しなかったか（上記を参照）、アーティファクトを測定し（ハードウェア/OSに依存）、それに応じて文書化する必要があります。または、これは問題/実装/ハードウェアの特定の組み合わせに対してのみ機能します。
于 2009-05-24T10:56:47.563 に答える