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

Question

我有一个表示几个数据的64位结构，其中一个是浮点值:

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

我有四个这样的结构，可以说一个 std::array<MyStruct, 4>
是否可以使用AVX根据float成员 MyStruct::f对数组进行排序？

Answer 1

对不起，这个答案很困惑。并非一次都写完，我很懒。有一些重复。

我有4个独立的想法:

正常排序，但是将结构作为64位单元移动

矢量化插入排序作为qsort的构建基块

对网络进行排序，并使用cmpps/blendvpd而不是minps/maxps进行比较器实现。不过，额外的开销可能会降低速度。

排序网络:加载一些结构，然后洗牌/混合以获取一些仅包含浮点数的寄存器和一些仅包含有效载荷的寄存器。使用蒂莫西·富尔塔克(Timothy Furtak)的技术进行普通的minps/maxps比较器，然后在有效负载上执行cmpeqps min,orig-> masked xor交换。每个比较器对数据的排序量是原来的两倍，但确实需要在比较器之间的两个寄存器上进行匹配混洗。完成后还需要重新交织(但是对于unpcklps/unpckhps来说，这很容易，如果您安排比较器，以便那些车内解包将最终数据按正确的顺序放置)。

这也避免了某些CPU在对表示不正常，NaN或无穷大的有效载荷中的位模式进行FP比较时可能会出现的潜在速度变慢，而无需在MXCSR中设置不正常为零位。

Furtak的论文建议在将事物主要用 vector 排序后进行标量清理，这将减少大量改组。

正常排序

通过使用64位加载/存储移动整个结构，并在FP元素上进行标量FP比较，使用常规的排序算法时，至少可以获得较小的加速。为了使此想法尽可能有效， 首先使用浮点值对结构进行排序，然后可以将整个结构movq编码为xmm reg ，浮点值在 ucomiss的low32中。然后，您(或者可能是聪明的编译器)可以使用 movq存储该结构。

查看Kerrek SB链接到的asm输出，编译器似乎在有效地复制以下结构方面做得相当糟糕:
icc似乎分别移动两个uint值，而不是在64b加载中获取整个结构。也许它不打包结构？ gcc 5.1似乎大多数时候都没有这个问题。

加快插入排序

大型排序通常使用插入排序进行分而治之，以解决足够小的问题。 Insertion sort将数组元素复制一个，仅在我们发现当前元素所属的位置时才停止。因此，我们需要将一个元素与一系列打包元素进行比较，如果任何比较都为真，则停止。你闻到载体吗？我闻到载体。

# 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编写了它。

这是一种插入排序，其开销可能比大多数开销大，由于处理前几个元素(不填充 vector )以及找出位置的复杂性，对于非常小的问题大小，它可能会丢失为标量版本。在突破检查多个元素的 vector 搜索循环后放置新元素。

大概对循环进行流水线处理，以便直到下一次迭代(或在中断之后)将保存冗余存储之前，我们才存储 ymm1。通过移位/改组在寄存器中进行比较，而不是执行标量加载/比较可能会是一个胜利。这可能会导致太多无法预测的分支，而我看不到有一种好方法来结束为 vmovups封装一个高4位，而为 vmovsd封装另一个注册表中的低位。

我可能已经发明了两种情况中最差的一种插入排序:小数组慢，因为脱离搜索循环后需要做更多的工作，但它仍然是插入排序:大数组由于O(n ^ 2)而慢。但是，如果可以使searchloop之外的代码不恐怖，那么这对于qsort/mergesort的小数组端点可能很有用。

无论如何，如果有人确实将此想法发展为实际的调试和工作代码，请告诉我们。

更新: Timothy Furtak's paper描述了一种SSE实现，用于对短数组进行排序(用作更大的排序的构造块，例如此插入排序)。他建议使用SSE生成部分有序的结果，然后使用标量操作进行清理。 (对排序最多的数组进行插入排序很快。)

这导致我们:

分类网络

这里可能没有任何提速。 Xiaochen，Rocki和Suda仅报告说，在Xeon Phi卡上，对于单线程mergesort的32bit(int)元素，标量-> AVX-512的速度提高了3.7倍。元素越宽， vector reg中的拟合就越少。 (对我们来说，这是4的倍数:256b中的64b元素，而512b中的32b元素。)它们还利用AVX512掩码仅比较某些 channel ，这在AVX中不可用。另外，具有较慢的比较器功能(可以竞争混洗/混合单元)，我们的状况已经变差了。

可以使用SSE/AVX打包比较指令构造 Sorting networks。 (通常，使用一对最小/最大指令有效地执行一组打包的2元素排序。)可以从执行成对排序的操作中构建更大的排序。 This paper by Tian Xiaochen, Kamil Rocki and Reiji Suda at U of Tokyo具有一些用于排序(没有有效载荷)的真实AVX代码，并讨论了如何使用 vector 寄存器进行棘手的处理，因为您无法比较同一寄存器中的两个元素(因此，排序网络必须设计成不需要这样) 。他们使用 pshufd排列元素以进行下一次比较，从而从仅对几个充满数据的寄存器进行排序中获得了更大的排序。

现在， 的诀窍是根据仅对元素的一半进行比较，以对成对的打包64b元素进行排序。 (即，将有效负载保留为sort键。)我们可以通过对 (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位恰好表示异常或NaN float ，则它们不会降低FP ops的速度。我不确定这是否仅适用于mul/div，否则是否会影响比较。

Intel Haswell:延迟:准备ymm2需要5个周期，准备ymm3需要7个周期。吞吐量:每4个周期一次。 (p5瓶颈)。

英特尔Sandybridge/Ivybridge:延迟:准备ymm2需5个周期，准备ymm3需6个周期。吞吐量:每2周期一次。 (p0/p5瓶颈)。

AMD Bulldozer/Piledriver :( vblendvpd ymm:2c lat，2c reput):lat:ymm2 4c，ymm3 6c。或更糟糕的是，cmpps和blend之间存在旁路延迟。 tput:每4c一次。 ( vector P1上的瓶颈)

AMD Steamroller:(vblendvpd ymm:2c lat，1c reput):lat:ymm2为4c，ymm3为5c。或由于旁路延迟而提高了1。 tput:每3c个( vector 端口P0/1上的瓶颈，用于cmp和blend)。

VBLENDVPD是2微码。 (它有3个reg输入，所以不能是1 uop:/)。这两个uops只能在shuffle端口上运行。在Haswell上，这只是port5。在SnB上，这是p0/p5。 (IDK为什么Haswell与SnB/IvB相比，混洗/混合吞吐量减少了一半。)

如果AMD设计具有256b宽的 vector 单元，则它们的低延迟FP比较和3输入指令的单宏运算解码将使它们领先。

通常的minps/maxps对为3和4个周期的延迟( ymm2/3)，每2个周期的吞吐量为1个(Intel)。 (FP Add/Sub/Compare单元上的p1瓶颈)。最公平的比较可能是对64位double进行排序。如果没有多对独立寄存器要比较，则额外的延迟可能会受到伤害。 Haswell的一半吞吐量将大大削减任何加速。

还请记住，比较器操作之间需要改组以使正确的元素排列起来以便进行比较。 min/maxps保留了shuffle端口未使用，但我的cmpps/blendv版本使它们饱和，这意味着shuffle不能与比较重叠，除非可以弥补数据依赖性留下的空白。

使用超线程，可以使其他端口繁忙的另一个线程(例如端口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微妙，而blendv版本是5微妙。最后6和/和///指令中有很多并行性。 cmpps具有3个周期延迟。我认为 ymm2将在6个周期内准备就绪，而 ymm3在7个周期内已准备就绪(并且可以与 ymm2上的操作重叠)。比较器op之后的insns可能会被改组，以将数据放入正确的元素中以进行下一次比较。对于整数域逻辑，即使对于 vshufps，也没有往返于shuffle单元的转发延迟，但结果应该在FP域中出来，准备使用 vcmpps。对于吞吐量，使用 vpand而不是 vandps是必不可少的。

蒂莫西·弗塔克(Timothy Furtak)的论文提出了一种对带有有效载荷的键进行排序的方法:不要将有效载荷指针与键打包在一起，而是从比较中生成一个掩码，并以相同的方式在键和有效载荷上使用它。这意味着您必须在数据结构中或每次加载结构时将有效负载与键分开。

参见他的论文的附录(图12)。他在键上使用标准的最小/最大值，然后使用 cmpps查看已更改的元素。然后，他在异或交换中间屏蔽那个掩码，最终仅将有效载荷交换为交换的 key 。