Chr*_*ann 11 c++ x86 intrinsics avx2 avx512
AVX512CD包含内部函数,_mm512_conflict_epi32(__m512i a)它返回一个向量,a如果它具有相同的值,则为其中的每个元素设置.有没有办法在AVX2中做类似的事情？
我对extact位不感兴趣,我只需要知道哪些元素是左侧(或右侧)元素的重复.我只需要知道分散是否会发生冲突.
基本上我需要一个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(跨越通道),然后进行七次比较,屏蔽掉未经过的位,而不是将_mm256_or_si256()它们放在一起,这是非常慢的.
TL:DR:由于完全检测到哪些元素冲突是昂贵的,因此可能值得做更多的后备工作以换取更便宜的检测.这取决于您的冲突处理选项/策略.
我想出了一种相当有效的方法来检查是否存在冲突,而没有找到它们的位置,就像这个64位整数元素的答案一样.它实际上比Skylake-AVX512的微编码vpconflictd ymm更快,但它当然会为您提供更少的信息.(KNL很快vpconflictd).
如果存在任何冲突,您可以对所有元素使用完全标量回退.如果冲突非常罕见,分支错误预测不会破坏性能,那么这将很有效.(AVX2首先没有散射指令,所以我不确定你需要这个.)
唯一的左或仅右行为很难,但我的方法可以为您提供一个掩码,其中哪些元素与任何其他元素发生冲突(例如v[0] == v[3],这将导致两者conflict[0]并且conflict[3]为真).这只需要额外的1次洗牌,或者在重新设计时可能需要0次才能实现这一目标.
(我最初误读了这个问题;我认为你想要检查两个方向,而不是谈论大多数的两种不同的实现选项vpconflictd.实际上起初我以为你只是想要一个存在/不存在检查,比如bool any_conflicts(__m256i).)
发现是否存在任何冲突: bool any_conflicts32(__m256i)
8 choose 2共有28个标量比较.那是包装比较的3.5个向量.我们应该通过4个向量比较来实现它,这留下了一些冗余空间.
为这些比较创建输入将需要改组,其中一些必须是车道交叉.4个独特的比较需要至少4个向量(包括初始未洗牌的副本),因为3个选择2只有3个.
理想情况下,shuffle尽可能少的是交叉路径,并且有比较和比较结果的ORing 有很多ILP.如果shuffle不需要矢量shuffle-control,那也很好imm8.如果他们在AMD Ryzen上没有慢,那么也很好,其中256b指令被解码为多个128b uop.(有些洗牌比别人这更糟糕,比如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;
}
我是如何设计的:
我制作了一个表格,其中列出了需要检查的所有元素对,并制作了混乱操作数可以处理该要求的列.
我从一些可以廉价完成的洗牌开始,结果证明我早期的猜测运作得很好.
我的设计说明:
// 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
*/
事实证明,车道内rotr1 = =完全rotl2有很多冗余,因此不值得使用.事实证明,让所有允许的冗余v==hilo工作正常.
如果您关心哪个结果在哪个元素中(而不仅仅是检查是否存在),那么v == swap_hilo(lrotr1)可以使用而不是lrotr1 == hilo.但我们也需要swap_hilo(v),所以这意味着额外的洗牌.
我们可以在hilo == lrotr1之后改为洗牌,以获得更好的ILP.或者也许有一套不同的洗牌可以给我们带来一切.也许如果我们考虑使用矢量shuffle-control的VPERMD ......
Haswell有一个shuffle单元(在port5上).
# 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重新排序了我的内在函数的依赖结构,将更多东西依赖于最后一个shuffle结果的比较.)
这比Skylake-AVX512vpconflictd ymm更快,它具有17c延迟,每10c吞吐量一个.(当然,这会为您提供更多信息,而@ harold对它的仿真需要更多的指示).
幸运的是,gcc没有重新排序洗牌并引入潜在的回写冲突.(例如,放置vpshufd最后一个意味着以最旧的第一顺序将shuffle uops调度到port5将vpshufd在与第一个相同的周期中准备好vpermq(1c延迟与3c).)gcc为一个版本的代码执行此操作(其中我比较了错误的变量),所以似乎gcc -mtune=haswell没有考虑到这一点.(也许这不是什么大不了的事,我还没有看到对延迟的实际影响是什么.我知道调度程序很聪明地从预订站挑选uop以避免实际的回写冲突,但IDK有多聪明,即它是否会vpshufd提前运行vpermq以避免回写冲突,因为即使看到即将发生的回写冲突也不得不提前查看.更可能的是,它会vpshufd在调度之前延迟一个额外的周期. )
无论如何,这就是为什么我把它放在_mm_shuffle_epi32C源的中间,它使得执行OOO变得容易.
Clang 4.0变得狂暴,并将每个比较结果打包到128b向量(带vextracti128/ vpacksswb),然后vpor xmm在pmovmskb之前的三个之后扩展回256b .起初我认为它是因为这样做-mtune=znver1,但它也是如此-mtune=haswell.即使我们返回a bool,它也只是pmovmskb/ test在打包向量上执行此操作./捂脸.它还pessimizes希洛洗牌vperm2i128,即使-mtune=znver1(Ryzen),其中vperm2i128有8个微指令,但vpermq为3(昂纳雾的insn的表因某些原因错过了这些,所以我把这些数字从FP当量vperm2f128和vpermpd)
@harold表示使用add而不是or停止打包/打包,但vpaddd吞吐量低于vpor英特尔前Skylake.
对Ryzen来说更好,v == hilo比较只能做到一半.(即使用vpcmpeqd xmm2, xmm2, xmm3,只有1 uop而不是2 u).我们仍然需要完整hilo的hilo == lrot1,但.所以我们不能只用vextracti128 xmm2, xmm0, 1而不是vpermq洗牌. Ryzen vextracti128具有出色的性能:1 uop,1c延迟,0.33c吞吐量(可以在任何P0/1/3上运行).
由于我们将所有东西ORing在一起,所以在高半部分中使用零而不是冗余比较结果是很好的.
正如我在评论中指出的那样,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会从我的代码中创建一些有趣的asm -mavx512f -mavx512vl.它将EVEX vpcmpeqd用于掩码寄存器,korw并将它们合并.但随后它将其扩展为一个向量设置vpmovmaskb,而不是仅仅优化移动掩码并使用korw结果./捂脸.