標準行列乗算アルゴリズムの効率を改善しますか？

Question

標準の行列乗算アルゴリズムの効率をどのように改善できますか？

このアプローチに関わる主な操作は次のとおりです。C[i][j]+=A[i][p]*B[p][j]

アルゴリズムの効率を改善するために何ができますか？

Answer 1

あなたは、特にインテルが自分MKL hereを提供し、BLAS（基本線形代数サブルーチン）ライブラリを使用して見ているしたい場合があり、AMDは自分のACML hereを持っているし、（オープンソース）後藤BLAS hereもあります。

（稠密な）マトリックス - マトリックス乗算カーネルは、?GEMMコールであり、?は浮動小数点タイプを示します。たとえば、DGEMMはdoubleルーチンを呼び出します。

低レベルの最適化を行っていることがわかっていない限り、これらのライブラリはおそらく手作業でコード化できるものよりも優れたパフォーマンスを発揮します。これを自分自身のコーディングに行くにしたいならば

、あなたは以下の点を考慮することもできます。

1. 使用「ベクター」の指示を。 SSE, SSE2..4命令が広くサポートされていますが、より新しいバージョンのCPUはAVX命令もサポートします。
2. 浮動小数点演算とロード/ストア演算の比率を最大にするネストループアンローリング。
3. 効果的なキャッシュ使用を保証するブロック単位のアルゴリズム。
4. マルチスレッド。 - K後藤レベル3 BLASの

   高性能実装：

このリファレンスは、あなたに物事の現在の状態のアイデアを与えるかもしれません。

これが役に立ちます。

Answer 2

この正確な質問に対処するGolub and Van Loanの第1章を読むことをお勧めします。

Answer 3

1. キャッシュブロック - あなたは適切に使用してキャッシュに
2. より良いアルゴリズムを値を再利用していることを確認すること - 行列を乗算する「バイ定義」方法が最適ではない、Strassen's algorithm
3. を見てみましょう並列化 - あなたのマシンに複数のコアおよび/またはプロセッサを持っている場合は、分割し
4. SIMDを征服することができます - 現代のCPUアーキテクチャに
5. GPGPUをSSEベクトル命令を活用 - 現代のGPUはのちょうどこの種を行うために最適化されていますもの。 CUDAとOpenCLを参照してください。

これらの方法を使用しても、パフォーマンスは向上しません。大幅な高速化が必要なチューニングがたくさんあります。マトリックスに素早く乗じる方法を考え出すためには、たくさんのお金があります。そのため、雑誌の記事が不足することはありません。

Answer 4

複数の行列乗算 - M1 x M2 x ... x Mn - については、別のボールゲームのような動的プログラミングに基づく別の最適化手法があります。これは、2つの行列の乗算効率を向上させるためには適用されないことに注意してください。ただし、3つ以上の行列をペアごとに掛け合わせると、さらに高いレベルで最適化することができます。ちょうど私は情報を丸めるためにヒープにこの答えを投げると思った。

Answer 5

まあ、そこにはStrassen's Algorithmがあります。これは、あなたのマトリックスのサイズにもよりますが、あなたがリストアップした標準アルゴリズムよりもわずかに速いです。もちろんeven faster algorithmsがありますが、実装が簡単ではありません。

標準アルゴリズムはO（N^3）である、 StrassenののアルゴはO（N^2.8）、 で、銅細工-ウィノグラードはO（N^2.3）