メモリアクセスを連続に

とりあえず、問題設定としてはNxNサイズの正方行列A,B,CについてC=ABと積を計算すること。
C=Oの初期化は別にされてるとして、それ以降の計算。基本的にはこうなる。

for( i = 0 ; i < N ; i++ ) {

  for( j = 0 ; j < N ; j++ ) {

    for( k = 0 ; k < N ; k++ ) {

      c[i][j] += a[i][k] * b[k][j];

    }

  }

}

これは見ての通り、i,j,k について対称な(どの演算を先にやっても結果は変わらない)ので、
順番を変えてみる。具体的には

for(i=0;i<N;i++)for(j=0;j<N;j++)for(k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];

for(i=0;i<N;i++)for(k=0;k<N;k++)for(j=0;j<N;j++)c[i][j]+=a[i][k]*b[k][j];

for(j=0;j<N;j++)for(i=0;i<N;i++)for(k=0;k<N;k++)c[i][j]+=a[i][k]*b[k][j];

for(j=0;j<N;j++)for(k=0;k<N;k++)for(i=0;i<N;i++)c[i][j]+=a[i][k]*b[k][j];

for(k=0;k<N;k++)for(i=0;i<N;i++)for(j=0;j<N;j++)c[i][j]+=a[i][k]*b[k][j];

for(k=0;k<N;k++)for(j=0;j<N;j++)for(i=0;i<N;i++)c[i][j]+=a[i][k]*b[k][j];

の6パターンの変化が考えられる。とりあえずこれを適当に実装して時間を計ってみた。

ijk	ikj	jik	jki	kij	kji
17.06	2.42	17.22	34.20	2.60	34.61

見ての通り、メモリを連続にアクセスしやすいikjやkijのループが速くなっている。