c - 通过 C 中的循环阻塞进行优化

Question

我目前正在研究 C 语言的优化，并且过去有一项任务是优化一段代码。在其他优化(展开循环和强度降低)中，我根据缓存大小使用了阻塞(遵循英特尔关于此事的教程):

https://software.intel.com/en-us/articles/how-to-use-loop-blocking-to-optimize-memory-use-on-32-bit-intel-architecture .

现在我想我明白了为什么这种技术在那种情况下有效，在步幅为 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];
            }
          }
        }
      }
    }

Answer 1

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 中改变)。逐出脏缓存行比逐出干净的行并稍后重新读取它的代价更高。