矩阵乘法的性能优化

for (i=0; i<n; i++)  {
  for (j=0; j<n; j++) {
    sum = 0.0;
    for (k=0; k<n; k++) 
      sum += a[i][k] * b[k][j];
    c[i][j] = sum;
  }
}

N x N 矩阵相乘

矩阵元素类型是 doubles (8 字节)

总共 O(N3) 个操作

每个元素都要读 N次

每个目标中都要对 N 个值求和

但也可以保存在寄存器中

不命中率分析

假设:

块大小 = 32 B (足够大 4 倍)

矩阵的维数 (N)是非常大的

大约 1/N 为 0.0 (这个意思是，按列读的时候，下一行一定不在当前行的 cache 中，会重新覆盖，不存在空间局部性可以相邻读取)

缓存不是大到足够容纳多行

分析方法:

看内循环的的访问模式

安行访问才能更好地利用局部性