使用AVX对64位结构进行排序？

Question

我有一个64位结构,代表几个数据,其中一个是浮点值:

struct MyStruct{
    uint16_t a;
    uint16_t b;
    float f;
}; 

我有四个这样的结构,让我们说一个 std::array<MyStruct, 4>

是否可以使用AVX对浮动成员进行数组排序MyStruct::f？

Answer 1

对不起,这个答案很乱; 它并不都是立刻写的,而且我很懒.有一些重复.

我有4个不同的想法:

1. 正常排序,但将结构移动为64位单位
2. 矢量化插入排序作为qsort的构建块

3. 排序网络,使用比较实施cmpps/ blendvpd而不是minps/ maxps.但额外的开销可能会扼杀加速.

4. 对网络进行排序:加载一些结构,然后进行混洗/混合以获得一些只有浮点数的寄存器和一些仅有效负载的寄存器.使用Timothy Furtak的技术进行正常minps/ maxps比较,然后cmpeqps min,orig- >屏蔽xor-swap对有效载荷.这为每个比较器分配了两倍的数据,但确实需要在比较器之间的两个寄存器上进行匹配混洗.完成后还需要重新交错(但是如果你安排你的比较器,那么通过unpcklps/unpckhps这很容易,那么那些通道内解压缩将以正确的顺序放置最终数据).

   这也避免了某些CPU在对有效载荷中的比特模式进行FP比较时可能会出现的减速,这些比特模式表示非正规数,NaN或无穷大,而不需要在MXCSR中设置非正规数为零的位.

   Furtak的论文建议在使用向量进行大部分排序之后进行标量清理,这样可以减少大量的洗牌次数.

正常排序

使用常规排序算法时,通过使用64位加载/存储移动整个结构,并在FP元素上进行标量FP比较,可以获得至少一个小的加速.为了使这个想法尽可能地工作,首先使用float值来命令你的struct,然后你可以movq将整个struct添加到xmm reg中,并且float值将在low32中ucomiss.然后你(或者可能是一个智能编译器)可以用一个存储结构movq.

看看Kerrek SB链接到的asm输出,编译器似乎在高效复制结构方面做得相当糟糕:

icc似乎分别移动两个uint值,而不是在64b加载中挖出整个结构.也许它不包装结构？ gcc5.1大多数时候似乎没有这个问题.

加快插入排序

对于足够小的问题,大排序通常采用插入排序进行分而治之. 插入排序将数组元素复制一个,仅当我们发现我们已到达当前元素所属的位置时停止.所以我们需要将一个元素与一个打包元素序列进行比较,如果对任何元素的比较为真,则停止.你闻到了矢量吗？我闻到了矢量.

# RSI points to  struct { float f; uint... payload; } buf[];
# RDI points to the next element to be inserted into the sorted portion
# [ rsi to rdi ) is sorted, the rest isn't.
##### PROOF OF CONCEPT: debug / finish writing before using!  ######

.new_elem:
vbroadcastsd ymm0, [rdi]      # broadcast the whole struct
mov rdx, rdi

.search_loop:
    sub        rdx, 32
    vmovups    ymm1, [rdx]    # load some sorted data
    vcmplt_oqps ymm2, ymm0, ymm1   # all-ones in any element where ymm0[i] < ymm1[i] (FP compare, false if either is NaN).
    vmovups    [rdx+8], ymm1  # shuffle it over to make space, usual insertion-sort style
    cmp        rdx, rsi
    jbe     .endsearch        # below-or-equal (addresses are unsigned)
    movmskps   eax, ymm2
    test       al, 0b01010101 # test only the compare results for 

    jz      .search_loop      # [rdi] wasn't less than any of the 4 elements

.endsearch:
# TODO: scalar loop to find out where the new element goes.
#  All we know is that it's less than one of the elements in ymm1, but not which
add           rdi, 8
vmovsd         [rdx], ymm0
cmp           rdi, r8   # pointer to the end of the buf
jle           .new_elem

  # worse alternative to movmskps / test:
  # vtestps    ymm2, ymm7     # where ymm7 is loaded with 1s in the odd (float) elements, and 0s in the even (payload) elements.
  # vtestps is like PTEST, but only tests the high bit.  If the struct was in the other order, with the float high, vtestpd against a register of all-1s would work, as that's more convenient to generate.

这肯定充满了错误,我应该用C语言用内在函数编写它.

这是一个插入排序,可能比大多数开销更多,由于处理前几个元素(不填充向量)的额外复杂性,以及找出哪里可能会因为非常小的问题大小而失去标量版本在断开检查多个元素的向量搜索循环之后放置新元素.

可能是对循环进行流水线操作,因此我们ymm1在下一次迭代(或中断后)之前不会存储,这样可以节省冗余存储.通过移位/混洗它们来进行寄存器中的比较,而不是字面上进行标量加载/比较可能是一个胜利.这可能最终导致太多不可预测的分支,而且我没有看到一个很好的方式来结束一个注册表中的高4 vmovups和另一个注册表中的低点vmovsd.

我可能已经发明了一种插入排序,这是两个世界中最糟糕的:由于在突破搜索循环后更多的工作,因此对于小数组来说很慢,但它仍然是插入排序:由于O(n ^ 2),大型数组的速度很慢.但是,如果searchloop之外的代码可以变得非常糟糕,那么这可能是qsort/mergesort的小数组端点.

无论如何,如果有人确实将这个想法发展成实际的调试和工作代码,请告诉我们.

更新:Timothy Furtak的论文描述了一种用于排序短数组的SSE实现(用作较大排序的构建块,如此插入排序).他建议使用SSE生成部分排序的结果,然后使用标量操作进行清理.(在大多数排序的数组上插入排序很快.)

这导致我们:

排序网络

这里可能没有任何加速.Xiaochen,Rocki和Suda在Xeon Phi卡上报告的标量加速率为3.7倍 - > AVX-512为32位(int)元素,单线程mergesort.使用更宽的元素,更少适合矢量注册.(这对我们来说是4倍:256b中的64b元素,512b中的32b元素.)它们还利用AVX512掩码仅比较一些通道,这是AVX中没有的功能.此外,由于较慢的比较器功能与混洗/混合单元竞争,我们已经处于更糟糕的状态.

可以使用SSE/AVX打包比较指令来构造排序网络.(更常见的是,使用一对有效执行一组打包的2元素排序的最小/最大指令.)可以通过成对排序的操作构建更大的排序. 来自东京U的Tian Xiaochen,Kamil Rocki和Reiji Suda的这篇论文有一些真正的AVX代码用于排序(没有有效载荷),并讨论了它如何使用向量寄存器很棘手,因为你无法比较同一寄存器中的两个元素(因此分拣网络必须设计成不要求).他们使用pshufd排列元素进行下一次比较,以便对几个充满数据的寄存器进行排序.

现在,诀窍是根据仅半个元素的比较来做一对打包的64b元素.(即使用排序键保持有效负载.)我们可以通过对数组进行排序来(key, payload)对这些方式进行排序,其中有效负载可以是索引或32位指针(mmap(MAP_32bit)或x32 ABI).

所以让我们自己建立一个比较器.在排序网络用语中,这是一个对一对输入进行排序的操作.所以它要么在寄存器之间交换元素,要么不是.

# AVX comparator for SnB/IvB
# struct { uint16_t a, b; float f; }  inputs in ymm0, ymm1
# NOTE: struct order with f second saves a shuffle to extend the mask

vcmpps    ymm7, ymm0, ymm1, _CMP_LT_OQ  # imm8=17: less-than, ordered, quiet (non-signalling on NaN)
     # ymm7 32bit elements = 0xFFFFFFFF if ymm0[i] < ymm1[i], else 0
# vblendvpd checks the high bit of the 64b element, so mask *doesn't* need to be extended to the low32
vblendvpd ymm2, ymm1, ymm0, ymm7
vblendvpd ymm3, ymm0, ymm1, ymm7
# result: !(ymm2[i] > ymm3[i])  (i.e. ymm2[i] < ymm3[i], or they're equal or unordered (NaN).)
#  UNTESTED

您可能需要设置MXCSR以确保int位不会减慢FP操作,如果它们碰巧表示非正规或NaN浮点数.我不确定这是否仅适用于mul/div,或者它是否会影响比较.

• Intel Haswell:延迟:5个周期ymm2准备好,7个周期ymm3.吞吐量:每4个循环一个.(p5瓶颈).
• 英特尔Sandybridge/Ivybridge:延迟:ymm2准备5个周期,6个周期ymm3.吞吐量:每2个循环一个.(p0/p5瓶颈).
• AMD Bulldozer/Piledriver :( vblendvpd ymm:2c lat,2c recip tput):lat:4c for ymm2,6c for ymm3.或者更糟糕的是,在cmpps和blend之间存在旁路延迟.tput:每4c一个.(矢量P1上的瓶颈)
• AMD Steamroller :( vblendvpd ymm:2c lat,1c recip tput):lat:4c for ymm2,5c for ymm3.或者由于旁路延迟而可能高一级.tput:每3c一个(矢量端口P0/1上的瓶颈,用于cmp和混合).

VBLENDVPD是2 uops.(它有3个reg输入,因此它不能是1 uop:/).两个uops只能在shuffle端口上运行.在Haswell,这是唯一的port5.在SnB上,那是p0/p5.(IDK为什么Haswell比SnB/IvB减少了混洗/混合吞吐量.)

如果AMD设计具有256b宽的矢量单元,那么它们的低延迟FP比较和3输入指令的单宏操作解码将使它们领先.

通常的minps/maxps对是3和4个周期的延迟(ymm2/3),每2个周期一个吞吐量(英特尔).(FP add/sub/compare单元的p1瓶颈).最公平的比较可能是排序64位双打.如果没有多对独立寄存器需要进行比较,额外的延迟可能会受到影响.Haswell减少了一半的吞吐量将大大减少任何加速.

还要记住,比较器操作之间需要进行混洗,以便将正确的元素排成一行进行比较.min/maxps使shuffle端口不被使用,但是我的cmpps/blendv版本使它们饱和,这意味着改组不能与比较重叠,除非是为了填补数据依赖性留下的空白.

使用超线程,另一个可以保持其他端口忙碌的线程(例如端口0/1 fp mul/add单元或整数代码)将与这个混合瓶颈版本共享核心.

我尝试了Haswell的另一个版本,它使用按位AND/OR运算"手动"进行混合.然而,它最终变慢了,因为两个来源必须在组合之前双向掩盖.

# AVX2 comparator for Haswell
# struct { float f; uint16_t a, b; }  inputs in ymm0, ymm1
#
vcmpps ymm7, ymm0, ymm1, _CMP_LT_OQ  # imm8=17: less-than, ordered, quiet (non-signalling on NaN)
     # ymm7 32bit elements = 0xFFFFFFFF if ymm0[i] < ymm1[i], else 0
vshufps ymm7, ymm7, ymm7, mask(0, 0, 2, 2)  # extend the mask to the payload part.  There's no mask function, I just don't want to work out the result in my head.
vpand    ymm10, ymm7, ymm0       # ymm10 = ymm0 keeping elements where ymm0[i] < ymm1[i]
vpandn   ymm11, ymm7, ymm1       # ymm11 = ymm1 keeping elements where !(ymm0[i] < ymm1[i])
vpor     ymm2, ymm10, ymm11      # ymm2 = min_packed_mystruct(ymm0, ymm1)

vpandn   ymm10, ymm7, ymm0       # ymm10 = ymm0 keeping elements where !(ymm0[i] < ymm1[i])
vpand    ymm11, ymm7, ymm1       # ymm11 = ymm1 keeping elements where ymm0[i] < ymm1[i]
vpor     ymm3, ymm10, ymm11  # ymm2 = max_packed_mystruct(ymm0, ymm1)

# result: !(ymm2[i] > ymm3[i])
#  UNTESTED

这是8 uops,而blendv版本为5 uops.在最后的6和/和/或指令中有很多并行性. cmpps但是有3个周期的延迟.我认为ymm2将在6个周期ymm3内准备好,而在7个就绪.(并且可以与操作重叠ymm2).跟随比较器操作的insn可能会改组,将数据放入正确的元素中进行下一次比较.对于整数域逻辑,即使对于整数域逻辑,也没有来自/来自混洗单元的转发延迟vshufps,但结果应该出现在FP域中,准备好用于a vcmpps.使用vpand而不是vandps对吞吐量至关重要.

Timothy Furtak的论文提出了一种使用有效负载对密钥进行排序的方法:不要使用密钥包装有效负载指针,而是从比较中生成掩码,并以相同的方式在密钥和有效负载上使用它.这意味着您必须在数据结构中或每次加载结构时将有效负载与密钥分开.

见其论文的附录(图12).他使用键上的标准最小值/最大值,然后用于cmpps查看哪些元素已更改.然后他在xor-swap中间对该掩码进行操作,最终只交换交换密钥的有效负载.