矩阵乘法速度问题

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

有一段时间,我认为那些可能是对齐问题 - 任何矩阵的行都与32个字节对​​齐N%8==0(第一个问题 - 为什么特别是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
    }
}

与你的情况类似的是这里。本演示很好地解释了如何优化此类代码以及它为何以这种方式工作。我希望你能找到你需要的一切。