主页 / coding / 问题 / 77489397
Accepted
Carl
Asked: 2023-11-16 00:26:35 +0800 CST

SIMD 算法检查整数块是否“连续”。

  • 772

如何检查 16 的对齐块是否u32连续（并且递增）？

例如：[100, 101, 102, ..., 115]是。并且，[100, 99, 3 ...]不是。

我使用的是 AVX512f。这是我到目前为止所拥有的：

算法A：

* predefine DECREASE_U32, a u32x16 of [15,14,13,...0]
* let a = input + DECREASE_32 // wrapping is OK
* compare a to u32x16::splat(first_item(a))
* Return whether all true

替代方案（算法 B）

* let b = copy of A
* permute the elements of b by one position
* let b = a-b
* Is b all 1's (except for 1st position)

我在 Rust 中使用packed_simd板条箱执行此操作，但任何语言/伪代码都可以。（我希望有一个 SIMD 操作来减去相邻项。）

rust

2 个回答

  1. Best Answer

    我认为你的第一个想法可能是最好的，如果在一个循环内完成，可以分摊加载向量常量的成本。AVX-512 可以有效地做到这一点。

    要么使用矢量加载，然后使用 单独广播低元素vpbroadcastd，或者使用矢量加载和广播加载。例如vpaddd zmm16, zmm31, [rdi]{1to16}/ vpcmpeqd k1, zmm16, [rdi]。

    嗯，但是然后检查所有元素是否为真，我想也许kaddw用一个常量1并用 ? 检查低 16 位是否为零kortest？或者只是kmov与整数寄存器进行比较，0xffff就像我们对 SSE/AVX 所做的那样pmovmskb。我尝试过，clang 有一个更好的主意：比较不等于，并检查掩码是否全为零。（即通过检查每个元素是否不相等来检查它们是否相等。）这允许kortest掩码本身。我将 clang 的想法应用到我的内在函数中，这样 GCC 也可以做出更好的汇编。

    在 C++ 中：

    #include <immintrin.h>

// compare for not-equal, checking the mask for 0
bool check_contig(int *p)
{
    __m512i bcast_first = _mm512_set1_epi32(*p);
    __m512i desired = _mm512_add_epi32(bcast_first, _mm512_setr_epi32(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0));

    __m512i v = _mm512_loadu_si512(p);
    __mmask16 cmp = _mm512_cmpneq_epi32_mask(desired, v);
    return cmp == 0;
}

    Godbolt - 来自 GCC 和 clang 的 asm：

    # GCC
check_contig(int*):
        vmovdqa32       zmm0, ZMMWORD PTR .LC0[rip]
        vpaddd  zmm0, zmm0, DWORD PTR [rdi]{1to16}
        vpcmpd  k0, zmm0, ZMMWORD PTR [rdi], 4
        kortestw        k0, k0
        sete    al
        vzeroupper
        ret

    # clang
check_contig(int*):
        vpbroadcastd    zmm0, dword ptr [rdi]
        vpaddd  zmm0, zmm0, zmmword ptr [rip + .LCPI0_0]
        vpcmpneqd       k0, zmm0, zmmword ptr [rdi]
        kortestw        k0, k0
        sete    al
        vzeroupper
        ret

    因此，它们都选择加载两次而不是vpbroadcastd zmm1, xmm0，至少在不在循环中时如此，因此向量常量也必须从 加载.rodata。

    也许如果我以不同的方式写它，_mm512_broadcastd_epi32( _mm512_castsi512_si128(v))他们会更喜欢一次加载，但要付出额外的洗牌微指令的代价。（当您有 512 位 uops 运行时，情况可能会更糟，因此 Intel CPU 关闭端口 1 上的矢量 ALU，只留下端口 0 和 5。https://agner.org/optimize/ 和https ://uops .info/ )

    算法 B - 避免非平凡的向量常数

    valignd也许你的第二种方法也可以通过旋转向量来有效地完成；它需要的唯一向量常量是全一，可以更便宜地生成（vpternlogd）而不是加载。

    检查比较掩码可能需要一个kmov到整数的and+cmp来检查除一位之外的所有内容，除非我们可以使用 clang 所做的相同技巧并安排事物，以便我们实际上希望掩码在我们想要的位置全为零。在这种情况下，test eax, imm32可以检查我们想要的位，同时忽略我们不需要的位。

    • 2

  2. 我当前的 Rust 代码的核心现在是这个宏代码：

        const LAST_INDEX: usize = <$simd>::lanes() - 1;
    let (expected, overflowed) = $chunk[0].overflowing_add(LAST_INDEX as $scalar);
    if overflowed || expected != $chunk[LAST_INDEX] {
        return false;
    }


    let a = unsafe { <$simd>::from_slice_aligned_unchecked($chunk) } + $decrease;
    let compare_mask = a.eq(<$simd>::splat(a.extract(0)));
    compare_mask.all()

    其中 $scalar 是u32， $simd 是u32x16， $decrease 是 [15, 14 ... 0] 块。代码抽查的第一部分检查最后一个元素是否比第一个元素多 15（并处理溢出）。

    我请求一个智能工具来帮助我理解生成的 SIMD 程序集。它说：

    • vmovdqa64：该指令将 512 位数据向量移入 ZMM 寄存器。它在这里使用了两次： vmovdqa64 zmm0,zmmword ptr [...]：将 512 位向量从内存加载到 zmm0 中。vmovdqa64 zmm0,zmmword ptr [...]（代码后面）：将不同的 512 位向量加载到 zmm0 中。vpaddd：

    • vpaddd zmm0,zmm0,zmmword ptr [rax+40h]：执行 32 位整数的压缩整数加法。该指令将 zmm0 中的 512 位向量与另一个 512 位向量（从 rax + 40h 中的内存地址加载）相加，并将结果存储回 zmm0。vp广播：

    • vpbroadcastd zmm1,xmm0：在 zmm1 的所有通道上广播来自 xmm0（zmm0 的低 128 位）的 32 位整数。这会在 zmm1 中创建一个 512 位向量，其中所有元素都相同且等于 xmm0 中的值。vpcmpeqd：

    • vpcmpeqd k0,zmm0,zmm1：比较 zmm0 和 zmm1 中的 32 位整数是否相等。结果存储在掩码寄存器 k0 中，其中每一位代表每对元素的比较结果。vpternlogd：

    • vpternlogd zmm1,zmm1,zmm1,0FFh：对操作数的每一位执行按位三进制逻辑运算。具体操作由立即数 0xFF 决定，在本例中对应于按位或。vpmovm2d:

    • vpmovm2d zmm0,k0：将位掩码从掩码寄存器 k0 移至通用寄存器 zmm0。k0 的每一位都成为 zmm0 中的一个 32 位元素。vpcmpd：

    • vpcmpd k0,zmm0,zmm1,4：根据最后一个操作数提供的谓词（此处为 4，通常表示“小于”）比较 zmm0 和 zmm1 中的 32 位整数。结果存储在掩码寄存器k0中。vmovdqu64：

    • vmovdqu64 zmmword ptr [rsp+50h],zmm0：将zmm0中的512位向量移动到地址rsp+50h处的内存中。科测试：

    • kortestw k0,k0：测试掩码寄存器 k0 的内容并根据结果设置零标志。这通常用于基于 SIMD 比较结果的条件分支。

    • vzeroupper：该指令用于清除所有 YMM 寄存器的高 256 位，以避免混合 AVX-512 和旧版 SSE 代码时造成的损失。在调用可能无法识别 AVX-512 的函数之前使用此指令是一个很好的做法。

    • 1

相关问题