用于计数排序的向量指令（"vcl" 和 "ume"）

Question

我正在尝试使用库 "vcl" 和 "ume" 的矢量指令进行一种计数排序，它只返回位置

// icpc sort.cpp -xCORE_AVX2 -o c
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "vcl/vectorclass.h"
#include "umesimd/UMESimd.h"
using namespace UME::SIMD;

int main(void) {
    //scalar version as example __________________________________________
    int s0[4], k0 = 0, x0[4] = { 9,
                                 1,
                                 2,
                                 1};
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++)
            if (x0[j] == i) {
                s0[k0] = j;
                k0++; }
    for (int j = 0; j < 4; j++) printf("%i\n", s0[j]); printf("\n");

    int a[32] = {9, 1,  5,  2,  1,  6,  3,  5,
                1,  4,  0,  3,  4,  7,  1,  1,
                2,  2,  1,  4,  4,  7,  2,  5,
                1,  4,  0,  1,  6,  4,  6,  5};
    //vcl version _____________________________________________________________________
    Vec8i s1[4] = 0, k1 = 0, x1[4]; Vec8ib msk1;
    x1[0].load(a);  x1[1].load(a + 8);  x1[2].load(a + 16); x1[3].load(a + 24);
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", x1[i].extract(j)); printf("\n"); } printf("\n");
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++) {
            msk1 = (x1[j] == i);
            //s1[k1] = select(msk1, j, s1);
            k1 = select(msk1, k1 + 1, k1); }
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", s1[i].extract(j)); printf("\n"); } printf("\n");

    //ume version ______________________________________________________________________
    SIMD8_32i s2[4] = 0, k2 = 0, x2[4]; SIMDMask8 msk2;
    x2[0].load(a); x2[1].load(a + 8); x2[2].load(a + 16); x2[3].load(a + 24);
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", x2[i].extract(j)); printf("\n"); } printf("\n");
    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < 4; j++) {
            msk2 = x2[j].cmpeq(i);
            //s2[k2].assign(msk2, j);
            k2.assign(msk2, k2 + 1); }
    for (int i = 0; i < 4; i++) { for (int j = 0; j < 8; j++) printf("%i\t", s2[i].extract(j)); printf("\n"); } printf("\n");

    return 0;
}

不幸的是，我找不到任何库的解决方案，我需要帮助来解决它（注释行）

Answer 1

计数排序的难点是直方图问题。

直方图对于 SIMD 来说很难，因为您需要收集负载和分散存储，以及冲突检测（您的输入元素向量有重复项，因此您需要多次递增同一个桶）。 x86 只有 AVX512 有这个。

没有gather/scatter/conflict-detection，有一些标量技巧对少量的桶很有用。例如复制计数数组 4 次以缓解 store/reload store-forwarding 瓶颈，如果出现相同的输入数字，则暂时占大部分输入。（在乱序执行的情况下，不必 100% 连续就会导致问题。）

您可以使用 SIMD 在最后总结桶数组，例如_mm256_add_epi32 用于 32 位计数器。生成排序输出的 memset / std::fill 部分的手动 SIMD 优化有一定的范围，但通常这不是缓慢的部分。

进一步阅读：

Methods to vectorise histogram in SIMD? 显示 array-of-multiple-tables 技巧。
显示了实现此代码的代码，其中 gcc auto-vectorizes 带有 AVX2。以及 AVX512 的讨论。（但请注意，这是对 LUT 查找的结果进行直方图绘制，因此有一个额外的间接层，我们可以使用 AVX2 进行 SIMD 收集。计数排序不是这种情况）
用于直方图的 AVX512CD

用于计数排序的向量指令（"vcl" 和 "ume"）

vector instructions ("vcl" and "ume") for counting sort

c++

simd

histogram

avx2

counting-sort