問題の各パーティションが完全に適合するため、複数のプロセッサを使用すると、キャッシュ効果により超線形スピードアップが発生し、数回スワップインおよびスワップアウトするシーケンシャルアルゴリズムよりもメモリトランザクションが高速化されることが知られています。私は何十もの例を見てきましたが、背後にあるロジックは非常に明確で、並列部分についてよく説明されています。
ただし、シーケンシャル アルゴリズムと比較するたびに、シーケンシャル アルゴリズムは 0...N からの大きなループを伴う非常に単純なソリューションです。
シーケンシャル ソリューションは、パラレル ソリューションと同じトリックを実行できると考えられていましたか?? (つまり、問題を分割し、キャッシュに収まるように各分割を順番に解決します)。つまり、1 つのスレッドで並列ソリューションを実行するだけです。これを行うことで、当初考えていた超線形ではなく、線形の高速化が期待できます。
ここで何が欠けていますか？このカウンター ロジックは、何十年も前からある概念には単純すぎるように思えます。
この質問は、先生が私に「スーパーリニアスピードアップは不可能です。シーケンシャルスピードアップをいつでも改善できるので、再びリニアスピードアップできる」と言った後に出てきました。逆に証明できませんでした。