Strassen Matrix乗数がなぜとても速いのですか？

Question

実験として、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マトリックスでさえも良いと思われました！

私はスピードアップのこの多くを説明することができる唯一の方法は、私のアルゴリズムは、より多くのキャッシュフレンドリーであることである - すなわち、それは行列の小片に焦点を当てたため、データがより局所的です。おそらく、可能であれば、すべての母集団の算術演算を少しずつ行うべきです。

なぜこれが速いのか他の理論は？

Answer 1

最初の質問は「結果は正しいのですか？」です。もしそうなら、あなたの "従来の"方法は良い実装ではないようです。

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

標準行列ライブラリは、データ・キャッシュのサイズを考慮はるかにキャッシュにやさしい方法を実装します。

ます。また、標準の行列積の再帰バージョンを実装する場合があります（半分のサイズですmatriciesの2x2のマトリックスに細分化）。これにより、最適なキャッシュパフォーマンスに近いものが得られます。これは、strassenが再帰的になるのを防ぎます。

これは間違っているか、従来のコードが最適化されていないかのどちらかです。

Answer 2

シュトラッセの再帰的な性質は、そのためには、画像の一部であってもよい、より良いメモリの局所性、 を持っています。再帰的な規則的な 行列の乗算は、おそらく合理的なものです と比較する。

Answer 3

従来の乗算のループ次数はどのくらいですか？

for (int i = 0; i < new_height; ++i) 
{ 
    for (int j = 0; j < new_width; ++j) 
    { 
     double sum = 0.0; 
     for (int k = 0; k < common; ++k) 
     { 
      sum += lhs[i * common + k] * rhs[k * new_width + j]; 
     } 
     product[i * new_width + j] = sum; 
    } 
} 

この場合、非連続的な方法で右側のマトリックスにアクセスしているため、キャッシュにはあまり適していません。並べ替え後、

for (int i = 0; i < new_height; ++i) 
{ 
    for (int k = 0; k < common; ++k) 
    { 
     double const fixed = lhs[i * common + k]; 
     for (int j = 0; j < new_width; ++j) 
     { 
      product[i * new_width + j] += fixed * rhs[k * new_width + j]; 
     } 
    } 
} 

最内ループの2つの行列へのアクセスは連続し、1つは固定されています。良いコンパイラはおそらく自動的にこれを行うでしょうが、私はデモンストレーションのために明示的に取り除くことを選択しました。

あなたは、言語を指定していないが、C++用として、先進的なコンパイラは、さらにいくつかの構成で非友好的なループの順序を認識し、それらを並べ替えます。