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

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

The natural 'slicing' direction of the tensor is along direction 1. This means the cache-lines extend in directions 3, 2 and finally 1, in that order. In other words, the indexing function looks like this: (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 分块无助于提高性能是否有原因？

Edit:

附加信息：

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

TL;DR：2D 分块代码并不更快，主要是因为缓存垃圾（还有一点是由于预取）。简单的实现和 2D 分块都是低效的。类似的效果描述于这个帖子 https://stackoverflow.com/questions/71818324/how-does-the-cpu-cache-affect-the-performance-of-a-c-program/71911346。您可以使用小 a 来缓解这个问题临时数组并使用提高性能寄存器平铺优化。额外的填充物也可能有帮助。

CPU缓存

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

  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 程序的性能？ https://stackoverflow.com/questions/71818324/how-does-the-cpu-cache-affect-the-performance-of-a-c-program/71911346.

缓存对转置的影响

你提到过block_size最多可达 256 个n1 and n3可以被 256 整除，因为提供的代码已经做出了隐含的假设：n1 and n3可以被整除block_size我期望n2当然也能被 256 整除。这意味着沿维度 3 的直线的大小为p * 256 * (2 * 8) = 4096p bytes = 64p cache lines where 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肯定能被二的幂整除。由于以下原因，处理器无法减轻延迟：缺乏并发性（即可以同时预取的可用缓存线）。这会导致带宽浪费，更不用说非连续访问已经降低了吞吐量。这种效果在二的较小幂中应该已经可见block_size值如上一篇相关文章（上面链接）所示。

预取的影响

像您一样的 Intel Skylake SP 处理器prefetch在这种情况下，每次访问至少同时有 2 个高速缓存行（128 字节）。这意味着一个block_sizetens。因此，太小了block_size由于预取而浪费带宽，太大也会浪费带宽，但由于缓存垃圾。我期待最好的block_size接近8。

如何解决这个问题

一种解决方案是将每个块存储在一个小的临时二维数组中，然后转置它，然后写入。乍一看，由于更多的内存访问，它看起来会更慢，但通常会快得多。事实上，如果块大小相当小（例如

添加另一个阻塞级别应该有助于提高性能，因为 L2 缓存得到了更有效的使用（例如，使用block_size设置128~256）。勒贝格曲线 https://en.wikipedia.org/wiki/Z-order_curve可以用来实现快速缓存遗忘算法，尽管它使代码更加复杂。

另一种优化包括添加另一个阻塞级别来执行称为的优化寄存器平铺。这个想法是使用 2 个嵌套循环来操作一个带有小块的图块编译时常数让编译器展开循环并生成更好的指令。例如，对于大小为 4x4 的图块，这使编译器能够生成以下代码（请参阅Godbolt https://godbolt.org/z/j1d6TfP4o):

..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 的处理器实现更快的切片转置。

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