c++ - 为什么添加填充可以让你的循环更快？

Question

人们告诉我，添加填充有助于获得更好的性能，因为它以更好的方式使用缓存。

我不明白如何通过扩大数据量来获得更好的性能。

有人能理解为什么吗？

Answer 1

数组填充

数组填充技术包括增加数组维度的大小，以减少访问高速缓存时的冲突未命中。当映射到同一集合的访问元素的数量大于缓存的关联度时，就会发生这种类型的未命中。填充会更改数据布局，并且可以应用于 (1) 变量之间(Inter-Variable Padding)或 (2) 到变量(Intra-Variable Padding):

1。变量间填充

float x[LEN], padding[P], y[LEN];

float redsum() {
    float s = 0;

    for (int i = 0; i < LEN; i++)
        s = s + x[i] + y[i];

    return s;
}

如果我们有一个直接映射的缓存并且元素 x[i] 和 y[i] 被映射到同一个集合中，访问 x 将从 y 中逐出一个 block ，反之亦然，导致高错失率和低性能。

2。变量内填充

float x[LEN][LEN+PAD], y[LEN][LEN];

void symmetrize() {
    for (int i = 0; i < LEN; i++) {
        for (int j = 0; j < LEN; j++)
            y[i][j] = 0.5 *(x[i][j] + x[j][i]);
    }
}

在这种情况下，如果将列的元素映射到少量集合中，则它们的访问顺序可能会导致冲突未命中，从而无法利用空间局部性。

例如，假设在外循环的第一次迭代期间，包含 x[0][0] x[0][1] ... x[0][15] 被逐出以存储包含元素 x[k][0] 的 block 。然后，在第二次迭代开始时，对 x[0][1] 的引用将导致缓存未命中。

此技术文档分析了快速傅立叶变换 (FFT) 的性能与计算中使用的矩阵大小的函数关系:

https://www.intel.com/content/www/us/en/developer/articles/technical/fft-length-and-layout-advisor.html

引用资料

加布里埃尔·里维拉 (Gabriel Rivera) 和曾秋文 (Chau-Wen Tseng)。用于消除冲突缺失的数据转换。 PLDI 1998. DOI:https://doi.org/10.1145/277650.277661

Changwan Hong 等人。多维数组的有效填充以避免缓存冲突未命中。 PLDI 2016. DOI:https://doi.org/10.1145/2908080.2908123