通过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,它加载到缓存块中并减少访问内存中下一个位置时的未命中数.但是在我的代码中dst[dim * jj + ii]似乎遍布整个地方,因为它jj在最里面的循环中被乘以.缓存是如何解释的？dim乘以0然后是1然后2等在某个时刻它将超过块可以容纳的并且优化将是毫无意义的.我明白了吗？

然而在实践中,当我只用于拦截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没有花费任何带宽来驱逐脏线执行L2,然后将其带回L1d以用于下一个存储.

通过阻止两个维度,下一个商店将在block_size更多商店之后发生dst[ dim*(jj+1..block_size-1) + ii ].(循环的下一次迭代ii.)

如果dim并且block_size都是2的幂,那么由于冲突,该线可能会被驱逐.地址4kiB分开到L1d中的相同集合,尽管有问题的步幅对于L2更大.(英特尔的L1d缓存是32kiB和8路组关联,因此同一组中多8个存储可能会驱逐一条线.但L3缓存使用散列函数进行集索引,而不是使用范围的简单模数地址位直接.IDK缓冲区的位数,或者整个矩阵在L3缓存中保持热点.)

但是如果其中一个dim或block_size两个不是2的幂,则所有64组8行64字节(L1d)起作用.因此,高达64*8 = 512条脏线可能在L1d缓存中.但请记住,仍然会按顺序加载数据,这将占用一些空间.(并不多,因为您从每行加载的数据中连续读取16个整数,并使用它来清除16个不同的目标数据行.)

只有一维阻塞,在你回到目的地线之前你会做更多的商店,所以它可能已被驱逐到L2或L3.

顺便说一句,我把你的代码放在Godbolt编译器资源管理器(https://godbolt.org/g/g24ehr)上,而gcc -O3x86并没有尝试做任何特别的事情.它使用向量加载到XMM寄存器中,并使用shuffle解压缩并执行4个单独的int存储.

clang6.0做了一些有趣的事情,涉及复制256字节的块.IDK如果这样做是为了解决别名(因为没有int *restrict dst它不知道src和dst不重叠).

BTW,连续写入和分散读取可能会更好.(即反转你的内部两个循环,所以ii改变最内层的循环而不是jj).驱逐一个脏缓存行比驱逐一条干净的线更昂贵,稍后再重新读取它.