c++ - 在4个__m256d寄存器中找到4个最小值

Question

我不知道如何实现:

__m256d min(__m256d A, __m256d B, __m256d C, __m256d D)
{
    __m256d result;

    // result should contain 4 minimal values out of 16 : A[0], A[1], A[2], A[3], B[0], ... , D[3]
    // moreover it should be result[0] <= result[1] <= result[2] <= result[2]

     return result;
}

关于如何以一种聪明的方式使用_mm256_min_pd，_mm256_max_pd和shuffle / permutes的任何想法？

==================================================

在此之后，我到现在为止:

    __m256d T = _mm256_min_pd(A, B);
    __m256d Q = _mm256_max_pd(A, B);
    A = T; B = Q;
    T = _mm256_min_pd(C, D);
    Q = _mm256_max_pd(C, D);
    C = T; D = Q;
    T = _mm256_min_pd(B, C);
    Q = _mm256_max_pd(B, C);
    B = T; C = Q;
    T = _mm256_min_pd(A, B);
    Q = _mm256_max_pd(A, B);
    A = T; D = Q;
    T = _mm256_min_pd(C, D);
    Q = _mm256_max_pd(C, D);
    C = T; D = Q;
    T = _mm256_min_pd(B, C);
    Q = _mm256_max_pd(B, C);
    B = T; C = Q;

我们有 :
A [0] A [1] A [2] A [3]
所以最小值在A的中间，第二个最小值在A或B的中间，...
不知道从那里去哪里...

================================================== ======

第二个想法是问题可以自行解决，但需要2次输入
__m256个元素。如果可以做到这一点，那么只需执行min4(A，B)-> P，min4(C，D)-> Q，min4(P，Q)->返回值即可。

不知道如何对两个 vector :)

================================================== =====================

更新2:问题已基本解决-以下函数计算了4个最小值。

__m256d min4(__m256d A, __m256d B, __m256d C, __m256d D)
{
    __m256d T;
    T = _mm256_min_pd(A, B);
    B = _mm256_max_pd(A, B);            
    B = _mm256_permute_pd(B, 0x5);
    A = _mm256_min_pd(T, B);            
    B = _mm256_max_pd(T, B);            
    B = _mm256_permute2f128_pd(B, B, 0x1);
    T = _mm256_min_pd(A, B);
    B = _mm256_max_pd(A, B);
    B = _mm256_permute_pd(B, 0x5);
    A = _mm256_min_pd(A, B);

    T = _mm256_min_pd(C, D);
    D = _mm256_max_pd(C, D);            
    D = _mm256_permute_pd(D, 0x5);
    C = _mm256_min_pd(T, D);            
    D = _mm256_max_pd(T, D);            
    D = _mm256_permute2f128_pd(D, D, 0x1);
    T = _mm256_min_pd(C, D);
    D = _mm256_max_pd(C, D);
    D = _mm256_permute_pd(D, 0x5);
    C = _mm256_min_pd(C, D);

    T = _mm256_min_pd(A, C);
    C = _mm256_max_pd(A, C);            
    C = _mm256_permute_pd(C, 0x5);
    A = _mm256_min_pd(T, C);            
    C = _mm256_max_pd(T, C);            
    C = _mm256_permute2f128_pd(C, C, 0x1);
    T = _mm256_min_pd(A, C);
    C = _mm256_max_pd(A, C);
    C = _mm256_permute_pd(C, 0x5);
    A = _mm256_min_pd(A, C);

    return A;
};

剩下的就是在返回之前对A中的值进行升序排序。

Answer 1

最好进行一些SIMD比较以减少到8或4个候选对象(如您现在所拥有的)，然后解压缩为 vector 寄存器中的标量 double 。这不必涉及内存往返:vextractf128高半部分(_mm256_extractf128_pd)，然后转换低半部分。也许使用movhlps(_mm_movehl_ps)将__m128的高半部分降低到低半部分(尽管在具有AVX的CPU上，您只保存了一个或两个代码字节，而不是立即进行混洗；这样做并不快)在某些旧CPU上)。

不论是拆开包装还是简单地存放，IDK都是必经之路。也许同时使用这两种方法，则可以使shuffle端口和store / load端口保持繁忙状态会很好。显然，每个 vector 中的低倍数已经作为标量存在，因此您不必加载它。 (而且，编译器不擅长查看标量的存储和重载以利用此优势，甚至无法访问本地数组。)

即使没有大大缩小候选集的范围，在拆包之前，某些SIMD比较器仍可以减少分支标量代码预期的交换/混洗数量，从而减少分支错误预测的惩罚。

正如我在Paul R的答案评论中所描述的那样，在标量代码中，插入排序类型的算法可能会做得很好。但这更像是优先级队列:仅插入前4个元素。如果新的候选人大于现有的最大候选人，那就继续前进。否则，将其插入到按排序顺序维护的4个候选列表中。

我发现了really nice paper on SIMD sorting networks, with specific discussion of AVX。当使用SIMDpacked-min / packed-max指令对几个数据 vector 寄存器进行排序时，它们详细介绍了所需的洗牌。他们甚至在示例中使用诸如_mm512_shuffle_epi32之类的内在函数。他们说，即使在示例中使用AVX-512掩码寄存器，其结果也适用于AVX。

这只是他们讨论合并以将小类别用作大并行类别的基础的最后一部分。我在任何地方都找不到他们的实际代码，因此也许他们从未发布过基准测试的完整实现以制作图表。 :(

顺便说一句，我以前写过一个answer with some not-very-great ideas，它按float成员对64位结构进行排序，但这在这里并不适用，因为我只解决了处理有效负载(您没有的负载)的复杂性。

我现在没有时间完成这个答案，所以我只发布我的想法的摘要:

使该纸张的2寄存器方法适应AVX(或AVX2)。我不确定如何最好地模仿其AVX512屏蔽的最小/最大指令。 :/我可能稍后再更新。您可能想向作者发送电子邮件，并询问他们用于基准化台式机CPU的代码。

无论如何，对成对的寄存器使用2寄存器功能，将其从4减少到2，然后再减少到1。与您的版本不同，他们的版本会生成完整排序的输出寄存器。

尽量避免跨车道改组可能很棘手。我不确定通过改组使用shufpd(__m256d _mm256_shuffle_pd (__m256d a, __m256d b, const int select);)合并来自两个源reg的数据是否可以获得任何好处。 256b版本可以使用4位imm8而不是2位在每个通道上进行不同的混洗。

这是一个有趣的问题，但不幸的是，我不应该花时间自己编写完整的解决方案。如果我有时间，我想比较插入排序优先级队列和相同队列的排序网络完全展开的实现，每个队列分别包含4、8、12和16个元素。 (在进入标量之前，不同级别的SIMD分类网络)。

我找到的链接:

Another paper on SSE sorting，其中一些代码使用palignr将两个两个单独排序的 vector 合并为一个排序的8元素 vector 对。不适用于256b double vector 。

Another paper on SSE sorting，包含来自Core2 CPU的测试结果。由于shufps的局限性，它在两个 vector 之间使用低效的blend / blend / shuffle进行混洗。车道内shufpd的限制略有不同。 本文可能值得仔细研究。它们具有适用于实际SSE vector 的算法，并具有可用的随机播放操作。

Xiaochen, Rocki, and Suda's paper linked already

What looks like a chapter on sorting networks中的

the CLR algorithms textbook。

Sorting network generator，可以选择算法。不是特定于SIMD的

https://en.wikipedia.org/wiki/Bitonic_sorter示例图具有一个16输入的排序网络。 Bitonic排序使用可以在某种程度上进行SIMD的模式。网络末端的上部可以省略，因为我们只关心最低4的顺序。

Fastest sort of fixed length 6 int array。一个有很多答案的热门问题。