1

実験として、Strassen Matrix Multiplication Algorithm を実装して、大きな n に対して本当に高速なコードが得られるかどうかを確認しました。

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

驚いたことに、n が大きいほど高速でした。たとえば、n=1024 の場合、従来の方法を使用すると 17.20 秒かかりましたが、Strassen 方法 (2x2.66 GHz Xeon) を使用すると 1.13 秒しかかかりませんでした。なんと -- 15 倍のスピードアップ!? わずかに高速になるだけです。実際、小さな 32x32 行列にも同じように適しているように見えました!?

これほどの高速化を説明できる唯一の方法は、アルゴリズムがよりキャッシュに適しているということです。つまり、アルゴリズムは行列の小さな断片に焦点を当てているため、データがよりローカライズされています。可能であれば、すべての行列演算を少しずつ行う必要があるかもしれません。

なぜこれがとても速いのかについての他の理論はありますか?

4

3 に答える 3

3

Strassen の再帰的な性質により、メモリの局所性が向上するため、それが全体像の一部である可能性があります。再帰的な通常の行列乗算は、おそらく比較するのに妥当なものです。

于 2012-03-17T02:44:39.170 に答える
1

最初の質問は「結果は正しいですか？」です。もしそうなら、あなたの「従来の」方法は適切な実装ではない可能性があります。

従来の方法は、ネストされた 3 つの FOR ループを使用して、数学の授業で学習した順序で入力をスキャンすることではありません。簡単な改善の 1 つは、右側の行列を転置して、行ではなく列が一貫してメモリに収まるようにすることです。この代替レイアウトを使用するように乗算ループを変更すると、大規模なマトリックスでより高速に実行されます。

標準のマトリックス ライブラリは、データ キャッシュのサイズを考慮した、よりキャッシュに適したメソッドを実装しています。

標準行列積の再帰バージョンを実装することもできます (半分のサイズの行列の 2x2 行列に分割します)。これにより、strassen が再帰的に得られる最適なキャッシュ パフォーマンスに近いものが得られます。

したがって、間違っているか、従来のコードが最適化されていません。

于 2011-10-19T21:20:14.073 に答える