除算と征服を使用した行列乗算

Question

問題は、速度が非常に遅く、ひどく遅く、小さなnの下であってもです。たとえば、n = 1024の場合、何か間違いがありますか？

私は関数呼び出しのたびに新しい行列Cを作成しませんでした。新しい結果を元の行列Cに格納されている元の結果に追加します。

int **matA,**matB,**matC; 

    void matmul_div_rec(int Arow,int Acol,int Brow,int Bcol,int n) { 
     if(n==1) 
     { 
      matC[Arow][Bcol]+=matA[Arow][Acol]*matB[Brow][Bcol]; 
     } 
     else 
     { 
      matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+0,n/2); 
      matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+0,n/2); 
      matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+0,n/2); 
      matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+0,n/2); 
      matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+n/2,n/2); 
     } 
     return; } 
int main() 
{ 
    matmul_div_rec(0,0,0,0,n); //n must be the power of 2 

} 

Answer 1

簡単にはで説明したように、例えば、this紙、ストラッセンのアルゴリズムの実装は、（それが正しくても）いくつかの追加のアイデアを使用している場合にのみ、競争力の性能を有しています。これらは、例えばサブマトリクスをアドレス指定するためのより簡単な方法を得るために、メモリ内のマトリクス記憶のためのいわゆるMorton orderレイアウトを使用し、より良いメモリ局所性を介してキャッシング動作を改善することを含む。さらに、再帰の基本ケースでの行列加算の並列化にSIMDを使用することで潜在的な改善があります。