arrays - 使用SIMD操作进行可变长度数组扩展

Question

我想使用 SIMD 内在函数进行以下数组扩展。 我有两个数组:

• 聚类值 (v_i):10、20、30、40

• 簇长度 (l_i):3, 2, 1, 2

我想创建一个包含值的结果数组:v_i 重复 l_i 次，即:

结果:1​​0、10、10、20、20、30、40、40。

如何使用 SIMD 内在函数计算此值？

Answer 1

如果输入数组大小最多为 8，输出数组大小最多为 16，并且字节为数组值，则可以通过 SIMD 对此进行优化。至少需要 SSSE3。可以将此方法扩展到更大的数组/元素，但效率会很快降低。

1. 计算数组长度的前缀和。如果您将长度字节数组重新解释为单个 64 位 (32 位) 字，将其乘以 0x101010101010100，并将结果存储在 SIMD 寄存器中，则可以快速完成此操作。
2. 用平均索引(前缀和数组的一半大小)填充索引数组(在单个 SIMD 寄存器中)。
3. 对索引寄存器的每个字节执行二进制搜索以找到正确的索引(并行)。这可以通过使用 PSHUFB 指令提取前缀和寄存器的适当字节，使用 PCMPGTB(以及可选地使用 PCMPEQB)将提取的前缀值与字节数进行比较，然后添加/减去索引范围的一半来完成。
4. (可选)用 0xff 填充索引寄存器中所有未使用的字节。
5. 使用 PSHUFB 用索引寄存器索引的簇值数组中的值填充某些寄存器。

算法的主循环(二分查找)包含 PSHUFB、PCMPGTB 以及一些算术和逻辑运算。它被执行 log(input_array_size) 次，很可能是 2 或 3 次。

这是一个例子:

cluster value:      10 20 30 40
cluster length:      3  2  1  2
prefix sum:          0  3  5  6  8
indexes:             2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
prefix value:        5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
byte number:         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
mask:               ff ff ff ff ff  0  0  0  0  0  0  0  0  0  0  0
indexes:             1  1  1  1  1  3  3  3  3  3  3  3  3  3  3  3
prefix value:        3  3  3  3  3  6  6  6  6  6  6  6  6  6  6  6
byte number:         0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
mask:               ff ff ff  0  0 ff  0  0  0  0  0  0  0  0  0  0
indexes:             0  0  0  1  1  2  3  3  3  3  3  3  3  3  3  3
length constrained:  0  0  0  1  1  2  3  3 ff ff ff ff ff ff ff ff
cluster value:      10 10 10 20 20 30 40 40  0  0  0  0  0  0  0  0