c++ - 矩阵乘法速度问题

Question

我正在研究缓存未命中如何影响计算速度。我知道有很多算法可以更好地乘以两个矩阵(即使简单交换下面的两个循环也会有所帮助)，但请考虑以下代码:

float a[N][N];
float b[N][N];
float c[N][N];
// ...
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            float sum = 0.0;
            for (int k = 0; k < N; k++) {
                sum = sum + a[i][k] * b[k][j];
            }
            c[i][j] = sum;
        }
    }
}

我已经针对许多 N 值重新编译了这段代码，并测量了运行它的时间。我预计会在 N=1250 左右发现时间突然增加，此时矩阵 c 不再适合缓存(c 的大小然后是 1250*1250*sizeof(float)=6250000，或大约 6MB，这是我的 L3 缓存的大小)。

事实上，总体趋势是在那之后，平均时间与之前的推断时间相比大约增加了三倍。但是N%8的值似乎对结果有很大的影响。例如:

1601 - 11.237548
1602 - 7.679103
1603 - 12.216982
1604 - 6.283644
1605 - 11.360517
1606 - 7.486021
1607 - 11.292025
1608 - 5.794537
1609 - 11.469469
1610 - 7.581660
1611 - 11.367203
1612 - 6.126014
1613 - 11.730543
1614 - 7.632121
1615 - 11.773091
1616 - 5.778463
1617 - 11.556687
1618 - 7.682941
1619 - 11.576068
1620 - 6.273122
1621 - 11.635411
1622 - 7.804220
1623 - 12.053517
1624 - 6.008985

有一段时间，我认为这些可能是对齐问题 - 当 N%8==0 时，任何矩阵的行都对齐到 32 字节(第一个问题 - 为什么特别是 32 字节？SSE 说明，例如 movaps 可以处理 16B 对齐的数据)。

另一个想法是，这可能以某种方式连接到缓存关联性(在我的机器上，L1 和 L2 为 8 路，L3 为 12 路)。

但后来我注意到对于 N 的某些值，例如 1536，会出现意想不到的尖峰(即使在这些情况下对齐应该非常好 - 1536==256*6，关联性也不是问题 - 1536==128*12==192*8)。例如:

1504 - 4.644781
1512 - 4.794254
1520 - 4.768555
1528 - 4.884714
1536 - 7.949040
1544 - 5.162613
1552 - 5.083331
1560 - 5.388706

时间非常一致，因此处理器负载的峰值不是问题。我在启用优化 (-O2) 的情况下编译代码。不幸的是，我的想法已经用完了。这种行为的原因可能是什么？

Answer 1

对于您的示例来说最重要的是 - CPU 缓存行大小。对于 CPU，它通常是 64 字节。即使您的程序读取或写入 1 个字节，CPU 也会对所有行(64 字节)进行读取/写入。这就是为什么，如果您的程序命中缓存行，您的性能就会很好。如果未命中，则读/写内存会产生额外的开销。 L3 缓存的大小不是那么重要。

你的代码

// all your stack variables are good. Compiler will optimize them well. 
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        float sum = 0.0;
        for (int k = 0; k < N; k++) {
            sum = sum + 
                  a[i][k] *  // here you are good, you read memory sequentially 
                  b[k][j]; // here, you are not good, every read comes from different cache line
        }
        c[i][j] = sum; // here doesn't matter, it is rare operation
    }
}

类似于你的情况is here .该演示文稿很好地解释了如何优化此类代码以及它为何以这种方式工作。我希望你会找到你需要的一切。