大量缓存未命中，稀疏矩阵乘法

Question

亲爱的地球人您好！

这是概述：

我正在做一个稀疏矩阵乘法，其中我有两个密集矩阵，但我只对输出的某些元素感兴趣。我有两个矩阵和一个二维索引数组：

float * A:[M*K]
float * B:[N*K]
int [][] idx: [M][nSelection] (that is there are nselection rows in B, per row in matrix A that I want to multiply)

我想计算：

out=A*B' // but of course only for the indices i,j where idx[i][k]=j for some k.

这就是事情的本质： 我想在乘法时将内容保存在 cpu 缓存中我一次乘以 16 个浮点数：

for (int kk = 0; kk < K; kk+=KK){
    int begin = 0;
    int end = M;
        for (int i = begin; i < end; i++){
            for (int j = 0; j < numberToAccept; j++){
                int theid = idx[i * numberToAccept + j];
                tempOut[i*numberToAccept+j] += blas_function_for_dotProduct(KK, A+i*K + kk, 1, B+theid*K + kk, 1);
            }
        }
    }

我正在使用的号码是：

M = 2048; N=10240; K=4096; nSelection=100;

所以我的想法是，如果我一点一点地解析矩阵（在 KK 的方向上，以 16 个浮点数 = 1 个高速缓存行的块为单位），我将只能加载两个矩阵一次。也就是说，矩阵 A 是按顺序加载的，因此除了每一行的第一个加载之外，所有其他加载都应该是命中。矩阵 B 以随机顺序加载，但因为我以 64 字节（16 个浮点数）的块处理它，所以它应该需要 640KB。我有 6 MB L1，所以如果 CPU 使用 LRU，它应该留在那里。

我使用 valgrind 查看缓存未命中，这是我得到的结果：

==3264== D   refs:      2,383,524,642  (2,272,927,073 rd   + 110,597,569 wr)
==3264== D1  misses:      114,096,428  (  113,982,278 rd   +     114,150 wr)
==3264== LLd misses:       95,822,173  (   95,736,938 rd   +      85,235 wr)
==3264== D1  miss rate:           4.7% (          5.0%     +         0.1%  )
==3264== LLd miss rate:           4.0% (          4.2%     +         0.0%  )

如果访问是可预测的（向上计数），我也会得到相同的结果。

我得到与 N=512 相同的结果。但是在 N=256 时我突然得到缓存命中（随机访问）：

==16546== D   refs:      2,383,525,914  (2,272,928,002 rd   + 110,597,912 wr)
==16546== D1  misses:      114,096,557  (  113,982,392 rd   +     114,165 wr)
==16546== LLd misses:        1,372,862  (    1,287,624 rd   +      85,238 wr)
==16546== D1  miss rate:           4.7% (          5.0%     +         0.1%  )
==16546== LLd miss rate:           0.0% (          0.0%     +         0.0%  )

问题是我的移动核心 i7 上有 6MB 缓存。 512 * 16 * float 大小为 23 KB。那么为什么我会错过这么多？ ( 昨晚写了大半，今天终于找到答案了

Answer 1

是缓存的关联性。我的l3是12路结合，我没算过，把K改成4*1024+16就一路命中！

大量缓存未命中，稀疏矩阵乘法

Lots of cache miss, Sparse matrix multiplication

caching

matrix

cpu

multiplication

sparse-matrix