哪种内存访问模式对外部产品类型的双循环最有效？

Question

哪种访问模式对于编写最大限度利用数据数据位置的缓存高效的外部产品类型代码最有效？

考虑用于处理两个数组的所有元素对的代码块,例如:

for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
        out[i*M + j] = X[i] binary-op Y[j];

这是binary-op标量乘法时的标准矢量矢量外积,X并且Y是1d,但是这个相同的模式也是矩阵乘法,当X和Y是矩阵时,它binary-op是两个矩阵的第一i行和j第二列之间的点积.

对于矩阵乘法,我知道了优化布拉斯像OpenBLAS和MKL可以得到很多比你从上面的双循环式的代码获得更高的性能,因为它们处理成块的元素以这样的方式来利用CPU缓存等等.不幸的是,OpenBLAS内核是用汇编语言编写的,因此很难弄清楚发生了什么.

是否有任何好的"交易技巧"重新组织这些类型的双循环以提高缓存性能？

由于每个元素out只被击中一次,我们显然可以自由地重新排序迭代.直线遍历out是最容易编写的,但我不认为这是最有效的执行模式,因为你没有利用任何地方X.

我特别感兴趣的是设置where M和Nlarge,并且每个元素(X[i],和Y[j])的大小非常小(比如O(1)字节),因此讨论类似于vector-vector外积或乘法的东西由短而脂肪的基质组成的高而瘦的基质(例如N x D,D x M在哪里D很小).

Answer 1

足够大M,Y矢量将超过L1缓存大小.^* 因此,在每个新的外部迭代中,您Y将从主内存(或至少是较慢的缓存)重新加载.换句话说,你不会利用时间局部性Y.

你应该阻止访问Y; 这样的事情:

for (jj = 0; jj < M; jj += CACHE_SIZE) {        // Iterate over blocks
    for (i = 0; i < N; i++) {
        for (j = jj; j < (jj + CACHE_SIZE); j++) {   // Iterate within block
            out[i*M + j] = X[i] * Y[j];
        }
    }
}

上述内容对访问没有任何明智之处X,但新值只能1/CACHE_SIZE经常访问,因此影响可能微不足道.

_{*如果一切都足够小,已经适合缓存,那么你不能做得比现有的更好(尽管有矢量化机会).}