AVX2 中冲突检测的回退实现

Fallback implementation for conflict detection in AVX2

AVX512CD 包含内在的 _mm512_conflict_epi32(__m512i a) 它 returns 一个向量,其中对于 a 中的每个元素,如果它具有相同的值,则会设置一个位。有没有办法在 AVX2 中做类似的事情?

我对精确位不感兴趣,我只需要知道哪些元素是其左侧(或右侧)元素的副本。我只需要知道散点图是否会发生冲突。

基本上我需要一个 AVX2 等价物

__mm256i detect_conflict(__mm256i a) {
  __mm256i cd = _mm256_conflict_epi32(a);
  return _mm256_cmpgt_epi32(cd, _mm256_set1_epi32(0));
}

我能想到的唯一方法是使用 _mm256_permutevar8x32_epi32() 将每个值右移 1(跨通道),而不是进行七次比较,屏蔽掉 unsed 位,然后 _mm256_or_si256() 它们加起来太慢了。

TL:DR:由于完全检测哪些元素冲突的成本很高,因此可能值得做更多的回退工作以换取更便宜的检测。这取决于您的冲突处理选项/策略。

我想出了一个相当有效的方法来检查 presence/absence 个冲突,而无需找到它们的位置,例如 . It's actually faster than Skylake-AVX512's micro-coded vpconflictd ymm,但当然它给你的信息要少得多。 (KNL有快vpconflictd).

如果有任何冲突,您可以对所有元素使用全标量回退。如果冲突很少见以至于分支预测错误不会影响性能,那么这会很有效。 (不过,AVX2 一开始就没有分散指令,所以我不确定你到底需要它做什么。)

仅左或仅右行为很难,但我的方法可以为您提供一个掩码,说明哪些元素与 任何 其他元素(例如 v[0] == v[3] 会导致 conflict[0]conflict[3] 都为真)。这只需要 1 次额外的洗牌,或者考虑到这个目标重新设计时可能需要 0 次。

(起初我误读了这个问题;我以为你 想要 检查两个方向,而不是谈论 vpconflictd 所做的大部分事情的两个不同的实现选项. 其实起初我以为你只是想要一个 presence/absence 支票,比如 bool any_conflicts(__m256i)。)


发现 presence/absence 任何冲突:bool any_conflicts32(__m256i)

8 choose 2 是 28 次标量比较。那是 3.5 个压缩比较向量。我们的目标应该是通过 4 次矢量比较来完成,这为一些冗余留出了空间。

为这些比较创建输入将需要洗牌,其中一些必须是车道交叉。 4个独特的比较需要至少4个向量(包括初始未打乱的副本),因为3选2只有3。

理想情况下,尽可能少的洗牌是跨车道的,并且有很多 ILP 用于比较和比较结果的 ORing。如果洗牌不需要向量洗牌控制,也很好,只需要 imm8。如果它们在 AMD Ryzen 上速度不慢也很好,其中 256b 指令被解码为多个 128b 微指令。 (有些洗牌比其他洗牌更糟糕,例如 vperm2i128 非常糟糕;交换单个向量的高半部分和低半部分比 vpermq 更糟糕。不幸的是,即使使用 -mtune=znver1,并尽可能将 _mm256_permute4x64_epi64 编译成 vperm2i128

我很早就找到了一个实现大部分目标的解决方案:3 次洗牌,4 次比较。洗牌之一是在车道上。它们都使用直接控制字节而不是向量。

// returns a 0 or non-zero truth value
int any_conflicts32(__m256i v)
{
    __m256i hilo       = _mm256_permute4x64_epi64(v, _MM_SHUFFLE(1,0,3,2));  // vpermq is much more efficient than vperm2i128 on Ryzen and KNL, same on HSW/SKL.
    __m256i inlane_rotr1 = _mm256_shuffle_epi32(v, _MM_SHUFFLE(0,3,2,1));
    __m256i full_rotl2 = _mm256_permute4x64_epi64(v, _MM_SHUFFLE(2,1,0,3));

    __m256i v_ir1 = _mm256_cmpeq_epi32(v, inlane_rotr1);
    __m256i v_hilo= _mm256_cmpeq_epi32(v, hilo);           // only really needs to be a 128b operation on the low lane, with leaving the upper lane zero.
                                                           // But there's no ideal way to express that with intrinsics, since _mm256_castsi128_si256 technically leaves the high lane undefined
                                                           // It's extremely likely that casting down and back up would always compile to correct code, though (using the result in a zero-extended register).
    __m256i hilo_ir1 = _mm256_cmpeq_epi32(hilo, inlane_rotr1);
    __m256i v_fl2 = _mm256_cmpeq_epi32(v, full_rotl2);

    __m256i t1 = _mm256_or_si256(v_ir1, v_hilo);
    __m256i t2 = _mm256_or_si256(t1, v_fl2);
    __m256i conflicts = _mm256_or_si256(t2, hilo_ir1);    // A serial dep chain instead of a tree is probably good because of resource conflicts from limited shuffle throughput

    // if you're going to branch on this, movemask/test/jcc is more efficient than ptest/jcc

    unsigned conflict_bitmap = _mm256_movemask_epi8(conflicts);  // With these shuffles, positions in the bitmap aren't actually meaningful
    return (bool)conflict_bitmap;
    return conflict_bitmap;
}

我是如何设计的:

我制作了一个 table 需要检查的所有元素对,并制作了洗牌操作数可以满足该要求的列。

我从一些可以很便宜地完成的洗牌开始,结果证明我早期的猜测很有效。

我的设计笔记:

    // 7 6 5 4 | 3 2 1 0

    // h g f e | d c b a
    // e h g f | a d c b    // inlanerotr1 = vpshufd(v)
    // f e d c | b a h g    // fullrotl2 = vpermq(v)

    // d c b a | h g f e    // hilo = vperm2i128(v) or vpermq.  v:hilo has lots of redundancy.  The low half has all the information.

          v:lrot1      v:frotr2     lrotr1:frotl2                (incomplete)
 * ab   [0]v:lrotr1                 [3]lr1:fl2
 * ac                  [2]v:frotl2
 * ad   [3]v:lrotr1                 [2]lr1:fl2
 * ae                                                                           [0,4]v:hilo
 * af                                           [4]hilo:lrotr1
 * ag                  [0]v:frotl2
 * ah                                           [3]hilo:lrotr1

 * bc   [1]v:lrotr1
 * bd                  [3]v:frotl2                               [5]hilo:frotl2
 * be                                           [0]hilo:lrotr1
 * bf                                                                           [1,5]v:hilo
 * bg                               [0]lr1:fl2  [5]hilo:lrotr1
 * bh                  [1]v:frotl2

 * cd   [2]v:lrotr1
 * ce                  [4]v:frotl2  [4]lr1:fl2
 * cf                                           [1]hilo:lrotr1
 * cg                                                                           [2,6]v:hilo
 * ch                               [1]lr1:fl2  [6]hilo:lrotr1

 * de                                           [7]hilo:lrotr1
 * df                  [5]v:frotl2                               [7]hilo:frotl2
 * dg                               [5]lr1:fl2  [2]hilo:lrotr1
 * dh                                                                           [3,7]v:hilo

 * ef   [4]v:lrotr1                 [7]lr1:fl2
 * eg                  [6]v:frotl2
 * eh   [7]v:lrotr1                 [6]lr1:fl2

 * fg   [5]v:lrotr1
 * fh                  [7]v:frotl2

 * gh   [6]v:lrotr1

 */

事实证明,in-lane rotr1 == full rotl2有很多冗余,所以不值得使用。事实证明,v==hilo 中所有允许的冗余都可以正常工作。

如果您关心哪个结果在哪个元素中(而不是仅仅检查 presence/absence), 那么 v == swap_hilo(lrotr1) 可以替代 lrotr1 == hilo。 但是我们还需要 swap_hilo(v),所以这意味着需要额外的洗牌。

我们可以改为在 hilo==lrotr1 之后随机播放,以获得更好的 ILP。 或者,也许有一组不同的洗牌可以为我们提供一切。 也许如果我们考虑带有矢量洗牌控制的 VPERMD...


编译器 asm 输出与最佳 asm

gcc6.3 -O3 -march=haswell produces:

Haswell 有一个洗牌单元(在端口 5 上)。

   # assume ymm0 ready on cycle 0
    vpermq  ymm2, ymm0, 78     # hilo ready on cycle 3 (execution started on cycle 0)
    vpshufd ymm3, ymm0, 57     # lrotr1 ready on cycle 2  (started on cycle 1)
    vpermq  ymm1, ymm0, 147    # frotl2 ready on cycle 5  (started on 2)
    vpcmpeqd  ymm4, ymm2, ymm0  # starts on 3, ready on 4
    vpcmpeqd  ymm1, ymm1, ymm0  # starts on 5, ready on 6
    vpcmpeqd  ymm2, ymm2, ymm3  # starts on 3, ready on 4
    vpcmpeqd  ymm0, ymm0, ymm3  # starts on 2, ready on 3
    vpor    ymm1, ymm1, ymm4    # starts on 6, ready on 7
    vpor    ymm0, ymm0, ymm2    # starts on 4, ready on 5
    vpor    ymm0, ymm1, ymm0    # starts on 7, ready on 8
         # a different ordering of VPOR merging could have saved a cycle here.  /scold gcc
    vpmovmskb       eax, ymm0
    vzeroupper
    ret

所以最好的延迟是 8 个周期来准备好单个向量,假设与此序列中的其他指令存在资源冲突,但假设与仍在流水线中的过去指令没有冲突。 (应该是 7 个周期,但是 gcc 重新排序了我的内在函数的依赖结构,将更多的东西依赖于上次洗牌结果的比较。)

这比 Skylake-AVX512's vpconflictd ymm 更快,延迟为 17c,每 10c 吞吐量一个。 (当然,这会给你更多的信息,@harold 的模拟需要更多的指令)。

幸运的是,gcc 没有重新排序随机播放并引入潜在的回写冲突。 (例如,将 vpshufd 放在最后意味着以最早的顺序将洗牌 uops 分派到端口 5 将使 vpshufd 在与第一个 vpermq 相同的周期中准备好(1c 延迟与 1c 延迟)。 3c).) gcc 为一个版本的代码做了这个(我在那里比较了错误的变量),所以 gcc -mtune=haswell 似乎没有考虑到这一点。 (也许这没什么大不了的,我还没有测量过对延迟的真正影响是什么。我知道调度程序很聪明地从保留站挑选微指令以避免实际的回写冲突,但 IDK 它有多聪明,即它是否会 运行 vpshufd 领先于后来的 vpermq 以避免回写冲突,因为它甚至必须向前看才能看到即将到来的回写冲突。更多它可能只会在发送之前延迟 vpshufd 一个额外的周期。)

无论如何,这就是为什么我把 _mm_shuffle_epi32 放在 C 源代码中间的原因,它使 OOO 的执行变得容易。

Clang 4.0 变得狂暴 并将每个比较结果压缩到 128b 向量(使用 vextracti128 / vpacksswb),然后在三个之后扩展回 256b vpor xmm 在 pmovmskb 之前。我一开始以为它是因为 -mtune=znver1 才这样做的,但它也是用 -mtune=haswell 这样做的。即使我们 return a bool 它也会这样做,这只会让它在打包向量上 pmovmskb / test 。 /捂脸。它还将 hilo shuffle 悲观化为 vperm2i128,即使使用 -mtune=znver1 (Ryzen),其中 vperm2i128 是 8 uops 但 vpermq 是 3。(Agner Fog's insn tables 对于某些原因错过了那些,所以我从 FP 等价物 vperm2f128vpermpd)

中获取了这些数字

@harold 说使用 add 而不是 or 会停止来自 packing/unpacking 的 clang,但是 vpaddd 在 Intel pre- 上的吞吐量低于 vpor天湖

Ryzen 更好,v == hilo 比较只能做低一半。 (即使用 vpcmpeqd xmm2, xmm2, xmm3,它只有 1 uop 而不是 2)。不过,我们仍然需要 hilo == lrot1 的完整 hilo。所以我们不能只使用 vextracti128 xmm2, xmm0, 1 而不是 vpermq 洗牌。 vextracti128 在 Ryzen 上具有 出色的 性能:1 uop,1c 延迟,0.33c 吞吐量(可以 运行 在任何 P0/1/3 上)。

由于我们将所有内容进行 OR 运算,所以在高半部分使用零而不是冗余比较结果很好。

正如我在评论中指出的,IDK 如何使用内在函数安全地编写它。显而易见的方法是使用 _mm256_castsi128_si256 (_mm_cmpeq_epi32(v, hilo)),但从技术上讲,这会使高车道未定义,而不是零。除了使用包含具有 128b 比较结果的 xmm 寄存器的全角 ymm 寄存器之外,编译器没有任何明智的方法可以做任何事情,但根据英特尔的文档,Deathstation-9000 编译器将垃圾放在那里是合法的。在高半部分获得零的任何明确方法都取决于编译器优化它。也许 _mm256_setr_si128(cmpresult, _mm_setzero_si128());.


当前没有带有 AVX512F 但没有 AVX512CD 的 CPU。但是,如果该组合有趣或相关,clang 会使用 -mavx512f -mavx512vl 从我的代码中生成一些有趣的 asm。它使用 EVEX vpcmpeqd 进入屏蔽寄存器,并使用 korw 合并它们。但随后它将其扩展回一个向量以设置 vpmovmaskb,而不是仅仅优化移动掩码并使用 korw 结果。 /facepalm.