CPUアクセス局所性原理に基づくマトリクス乗算実現

1  for(i=0;i<n;++i)
2     for(j=0;j<n;++j)
3     {
4         double sum=0;
5         for(k=0;k<n;++k)
6             sum+=a[i][k]*b[k][j];
7         c[i][j]+=sum;
8     }

1 for(i=0;i<n;++i)
2     for(k=0;k<n;++k)
3     {
4         r=a[i][k];
5         for(j=0;j<n;++j)
6             c[i][j]+=r*b[k][j];
7     }

よく見ると、この2つの実現の意味は等価であるが、後者の実際の運行効率は前者より高いことがわかる.
どうしてそうなったの?
それはCPUがデータを読むとき、メモリに直接アクセスするのではなく、キャッシュにデータがあるかどうかを確認し、ある場合はキャッシュから直接読み出すからです.キャッシュからのデータの読み取りは、メモリからのデータの読み取りよりもずっと速い.
データがキャッシュに含まれていない場合、CPUはデータを含む1つのデータブロックをキャッシュに読み込み、プログラムが良好な空間局所性を持っている場合、最初のcache miss後、その後の数回のデータアクセスは直接キャッシュで完了することができる.空間的局所性(プログラムは現在のデータに隣接するデータを参照する傾向がある)に加えて、時間的局所性(プログラムは最近参照されたデータを参照する傾向がある)もある.
行列乗算に戻ります.(内循環のみを考慮)
前者はマトリクスAに対して、良好な空間局所性があり、一度に4つの要素をキャッシュできると仮定すると、反復ごとにAに対して0.25回のmissしかないが、Bに対してはそうではないため、Bは列ごとにアクセスし、毎回アクセスするとmissになるため、反復ごとに総miss数は1.25である.後者は行列Cと行列Bに対して良好な局所性を有し,反復のたびに0.25語missしかないため,全miss数は0.5であった.後者は反復ごとに記憶を1回多くする(C[i][j]への書き込み)が、それでも後者の実行効率は前者より高い. 
要するに、プログラムが速く走るためには、プログラムの中で局所性を多く利用し、キャッシュholdにデータを保存させ、訪問回数を減らす必要があります.CPUは3クロック周期でL 1 cacheにアクセスでき,10クロック周期程度でL 2 cacheにアクセスできることを知る.メモリにアクセスするには100クロックサイクル以上かかりますが、どちらが速いか、どちらが遅いかはよくわかりますよね?
原文住所:http://www.cnblogs.com/lisperl/archive/2012/11/17/2774782.html