我目前正在研究 C 语言的优化,并且过去有一项任务是优化一段代码。在其他优化(展开循环和强度降低)中,我根据缓存大小使用了阻塞(遵循英特尔关于此事的教程):
现在我想我明白了为什么这种技术在那种情况下有效,在步幅为 1 的情况下,它会将 block 加载到缓存中并减少访问内存中下一个位置时的未命中数。但在我的代码中,dst[dim * jj + ii]
似乎到处跳来跳去,因为它在最内层的循环中乘以 jj
。缓存如何解决这个问题? dim 乘以 0 然后 1 然后 2 等在某个时候它会超过 block 可以容纳的东西并且优化将毫无意义。我的理解对吗?
然而,在实践中,当我只对 jj
变量使用阻塞时,我并没有像在 ii
和jj
。所以我让它更快但不知道为什么。作业已经过去了,但我仍然不明白,这很令人沮丧。
在此先感谢您容忍这个可能非常愚蠢的问题。
void transpose(int *dst, int *src, int dim)
{
int i, j, dimi, jj,ii;
dimi = 0;
for(i=0; i < dim; i+=block_size)
{
for(j=0; j<dim; j+=block_size)
{
for(ii = i; ii < i+block_size; ii++)
{
dimi = dim * ii;
for(jj = j; jj < j+block_size; jj++)
{
dst[dim*jj + ii] = src[dimi + jj];
}
}
}
}
}
最佳答案
dst
中的空间局部性很差,但是对于两个维度都进行了阻塞,在时间和空间上仍然有足够的局部性,因此当您存储下一个 时,缓存行通常在 L1d 缓存中仍然很热>int
.
假设 dst[dim*jj + ii]
是缓存行中的第一个 int
。 dst[dim*jj + ii + 1]
的存储将在同一缓存行中。如果该行在 L1d 缓存中仍然很热,则 CPU 没有花费任何带宽来驱逐脏行 do L2,然后将其带回 L1d 以进行下一次存储。
对于两个维度的阻塞,下一次存储将在 block_size
更多存储到 dst[ dim*(jj+1..block_size-1) + ii ]
之后发生. (ii
循环的下一次迭代。)
如果 dim
和 block_size
都是 2 的幂,该行可能会因为冲突而被逐出。相距 4kiB 的地址进入 L1d 中的同一组,尽管 L2 的问题步幅更大。 (Intel 的 L1d 缓存是 32kiB 和 8 路集合关联的,因此同一个集合中再多 8 个存储可能会逐出一行。但是 L3 缓存使用散列函数进行集合索引,而不是使用范围的简单模数地址位直接。IDK 你的缓冲区是多少位,或者你的整个矩阵可以在你的 L3 缓存中保持热。)
但是如果 dim
或 block_size
不是 2 的幂,那么所有 64 组 8 行 64 字节 (L1d) 都会起作用。因此 L1d 缓存中最多可能有 64*8 = 512 个脏行。但请记住,仍然有数据按顺序加载,这会占用一些空间。 (不多,因为您从每行加载的数据中连续读取 16 个整数,并使用它来弄脏 16 个不同的目标数据行。)
仅在 1 维中进行阻塞,在返回目标行之前您要进行更多存储,因此到那时它可能已被逐出到 L2 或 L3。
顺便说一句,我将您的代码放在 Godbolt 编译器资源管理器 ( https://godbolt.org/g/g24ehr ) 上,而 x86 的 gcc -O3
不会尝试做任何特别的事情。它使用 vector 加载到 XMM 寄存器中,并通过随机播放解包并进行 4 次独立的 int
存储。
clang6.0 做了一些有趣的事情,包括复制一个 256 字节的 block 。 IDK 如果它这样做是为了解决别名问题(因为没有 int *restrict dst
它不知道 src 和 dst 不重叠)。
顺便说一句,连续写入和分散读取可能会更好。 (即反转你的内部两个循环,所以 ii
在最里面的循环而不是 jj
中改变)。逐出脏缓存行比逐出干净的行并稍后重新读取它的代价更高。
关于c - 通过 C 中的循环阻塞进行优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50671488/