具有独特矩阵转置问题的 2D 分块

Question

struct complex {double real = 0.0; double imag = 0.0;};我有以 3 阶张量形式组织的类型的复杂值数据。底层容器具有与内存页边界对齐的连续内存布局。

张量的自然“切片”方向是沿着方向 1。这意味着缓存行按方向 3、2 和最后 1 的顺序延伸。换句话说，索引函数如下所示：(i, j, k) -> i * N2 * N3 + j * N3 + k。

我需要沿方向 2 转置切片。在上面的第一张图像中，红色矩形是我希望转置的张量的切片。

我的 C++ 代码如下所示：

for (auto vslice_counter = std::size_t{}; vslice_counter < n2; ++vslice_counter)
    {        
        // blocked loop
        for (auto bi1 = std::size_t{}; bi1 < n1; bi1 += block_size)
        {
            for (auto bi3 = std::size_t{}; bi3 < n3; bi3 += block_size)
            {
                for (auto i1 = std::size_t{}; i1 < block_size; ++i1)
                {
                    for (auto i3 = std::size_t{}; i3 < block_size; ++i3)
                    {
                        const auto i1_block = bi1 + i1;
                        const auto i3_block = bi3 + i3;
                        tens_tr(i3_block, vslice_counter, i1_block) = tens(i1_block, vslice_counter, i3_block);
                    }
                }
            }
        }
    }

用于测试的机器：双路Intel(R) Xeon(R) Platinum 8168，带

1. 24 核 @ 2.70 GHz 和
2. L1、L2 和 L3 缓存大小分别为 32 kB、1 MB 和 33 MB。

我绘制了该函数相对于块大小的性能图，但令我惊讶的是没有变化！事实上，简单的实现的性能与此一样好。

问题：在这种情况下，2D 分块无助于提高性能是否有原因？

---

编辑：

附加信息：

1. 使用的编译器是Intel C++编译器。
2. block_size是输入参数而不是编译时间常数。
3. 在测试过程中，我将值block_size从 4 更改为 256。这分别转换为 256 B 和 1 MB 的块，因为这些块是边长的正方形block_size。我的目标是用块填充 L1 和/或 L2 缓存。
4. 用于优化的编译标志：-O3;-ffast-math;-march=native;-qopt-zmm-usage=high

Answer 1

TL;DR：2D 阻塞代码并不更快，主要是因为缓存垃圾（还有一点是由于预取）。简单的实现和 2D 分块都是低效的。这篇文章中描述了类似的效果。您可以使用小型临时数组来缓解此问题，并使用寄存器平铺优化来提高性能。额外的填充物也可能有帮助。

CPU缓存

首先，现代CPU缓存都是组相联缓存。多路关联高速缓存可以被视为具有包含高速缓存行块的集合的n x m矩阵。内存块首先被映射到一个集合，然后放置到目标集合的任意缓存行中（关于缓存替换策略）。当算法（如转置）执行跨步内存访问时，处理器通常访问相同的集合，并且可以使用的目标高速缓存行的数量要少得多。对于步长为 2 的大幂（或者更准确地说，可被 2 的大幂整除）的步幅尤其如此。可以使用模算术或基本模拟来计算可以访问的可能的高速缓存行的数量。在最坏的情况下，所有访问都在同一高速缓存行集（包含高速缓存行）上完成。在这种情况下，每次访问都会导致处理器逐出该组中的一个高速缓存行，以使用通常不完美的替换策略在其中加载新的高速缓存行。您的英特尔(R) 至强(R) Platinum 8168 处理器具有以下缓存属性：nmmm

  Level     Size (KiB/core)    Associativity    # Sets
-------------------------------------------------------
L1D Cache           32             8-way           64
 L2 Cache         1024            16-way         1024
 L3 Cache         1408            11-way         2048

* All cache have 64-byte cache lines

这意味着，如果您以可被 4096 字节（即 256 个复数）整除的步长执行访问，则所有访问都将映射到 L1D 缓存中的同一 L1D 缓存集，从而导致冲突未命中，因为只能加载 8 个缓存行同时地。这会导致称为缓存垃圾的影响，从而显着降低性能。这篇文章提供了更完整的解释：CPU 缓存如何影响 C 程序的性能？。

缓存对转置的影响

您提到block_size最多可以是 256，并且n1可以n3被 256 整除，因为提供的代码已经隐式假设n1并且n3被 整除block_size，并且我预计n2也可以被 256 整除。这意味着沿维度 3 的直线的大小为p * 256 * (2 * 8) = 4096p bytes = 64p cache lines其中p = n3 / block_size。这意味着所有行的第 i 项将被映射到完全相同的 L1D 缓存集。

由于您在维度 1 和维度 3 之间执行转置，这意味着行之间的空间更大。两个后续行的第 i 个项目之间的间隙是G = 64 * p * n2高速缓存行。假设n2可被 16 整除，则G = 1024 * p * q缓存行其中q = n2 / 16.

存在这样的差距是一个大问题。事实上，您的算法读取/写入同一块中许多行的许多第 i 个项目。因此，此类访问将被映射到 L1D 和 L2 缓存中的同一组，从而导致缓存垃圾。如果block_size> 16，缓存行将几乎系统地重新加载到 L2（4 次）。我预计 L3 在这种情况下不会有太大帮助，因为它主要是为内核之间共享数据而设计的，它的延迟相当大（50-70 个周期）并且p * q肯定可以被 2 的幂整除。由于缺乏并发性（即可以同时预取的可用缓存行），处理器无法减轻延迟。这会导致带宽浪费，更不用说非连续访问已经降低了吞吐量。block_size如上一篇相关文章（上面链接）所示，这样的效果应该已经可以在两个值的较小幂中看到。

预取的影响

在这种情况下，每次访问时，像您这样的 Intel Skylake SP 处理器会同时预取至少 2 个缓存行（128 字节）。这意味着 a block_size< 8 不足以完全使用 的预取缓存行tens。因此，太小会block_size因预取而浪费带宽，太大也会浪费带宽，但会因缓存垃圾而浪费。我预计最好的block_size接近8。

如何解决这个问题

一种解决方案是每个块存储在一个小的临时二维数组中，然后转置它，然后写入它。乍一看，由于更多的内存访问，它看起来会更慢，但通常会快得多。事实上，如果块大小相当小（例如 <= 32），则小型临时数组可以完全适合 L1 高速缓存，因此在转置期间不会受到任何高速缓存垃圾的影响。该块可以高效地读取，但可以更高效地存储（即更连续的访问）。

添加另一个阻塞级别应该有助于提高性能，因为 L2 缓存可以得到更有效的使用（例如设置block_size128~256）。勒贝格曲线可用于实现快速缓存遗忘算法，尽管它使代码更加复杂。

另一种优化在于添加另一个阻塞级别来执行称为寄存器平铺的优化。这个想法是使用 2 个嵌套循环来操作一个具有小的编译时常量的图块，以便编译器展开循环并生成更好的指令。例如，对于大小为 4x4 的图块，编译器可以生成以下代码（请参阅Godbolt）：

..B3.7:
        vmovupd   xmm0, XMMWORD PTR [rdx+r8]
        vmovupd   XMMWORD PTR [r15+rdi], xmm0 
        inc       r14 
        vmovupd   xmm1, XMMWORD PTR [16+rdx+r8]
        vmovupd   XMMWORD PTR [r15+r10], xmm1 
        vmovupd   xmm2, XMMWORD PTR [32+rdx+r8]
        vmovupd   XMMWORD PTR [r15+r12], xmm2 
        vmovupd   xmm3, XMMWORD PTR [48+rdx+r8]
        vmovupd   XMMWORD PTR [r15+r13], xmm3 
        vmovupd   xmm4, XMMWORD PTR [rdx+r9]
        vmovupd   XMMWORD PTR [16+r15+rdi], xmm4 
        vmovupd   xmm5, XMMWORD PTR [16+rdx+r9]
        vmovupd   XMMWORD PTR [16+r15+r10], xmm5 
        vmovupd   xmm6, XMMWORD PTR [32+rdx+r9]
        vmovupd   XMMWORD PTR [16+r15+r12], xmm6 
        vmovupd   xmm7, XMMWORD PTR [48+rdx+r9]
        vmovupd   XMMWORD PTR [16+r15+r13], xmm7 
        vmovupd   xmm8, XMMWORD PTR [rdx+r11]
        vmovupd   XMMWORD PTR [32+r15+rdi], xmm8 
        vmovupd   xmm9, XMMWORD PTR [16+rdx+r11]
        vmovupd   XMMWORD PTR [32+r15+r10], xmm9 
        vmovupd   xmm10, XMMWORD PTR [32+rdx+r11]
        vmovupd   XMMWORD PTR [32+r15+r12], xmm10 
        vmovupd   xmm11, XMMWORD PTR [48+rdx+r11]
        vmovupd   XMMWORD PTR [32+r15+r13], xmm11 
        vmovupd   xmm12, XMMWORD PTR [rdx+rbp]
        vmovupd   XMMWORD PTR [48+r15+rdi], xmm12 
        vmovupd   xmm13, XMMWORD PTR [16+rdx+rbp]
        vmovupd   XMMWORD PTR [48+r15+r10], xmm13 
        vmovupd   xmm14, XMMWORD PTR [32+rdx+rbp]
        vmovupd   XMMWORD PTR [48+r15+r12], xmm14 
        vmovupd   xmm15, XMMWORD PTR [48+rdx+rbp]
        vmovupd   XMMWORD PTR [48+r15+r13], xmm15 
        add       r15, rsi 
        add       rdx, 64 
        cmp       r14, rbx 
        jb        ..B3.7

而不是这个（重复8次以上）：

..B2.12:
        vmovupd   xmm0, XMMWORD PTR [rsi+r14]
        vmovupd   XMMWORD PTR [rbx+r15], xmm0
        inc       rax
        vmovupd   xmm1, XMMWORD PTR [16+rsi+r14]
        vmovupd   XMMWORD PTR [rbx+r13], xmm1
        add       rbx, r9
        add       rsi, 32
        cmp       rax, rcx
        jb        ..B2.12

最后，可以使用 AVX/AVX-2/AVX-512 内在函数为仅限 x86-64 的处理器实现更快的切片转置。

请注意，在每行末尾添加一些填充，以便它们不能被 的幂整除，也应该显着有助于减少缓存垃圾。话虽这么说，一旦应用了上述优化，这可能就没用了。