将分散索引转换为聚集索引的有效方法

Question

我正试图用SIMD内部函数编写一个流压缩（使用一个数组并去掉空元素）。循环的每次迭代一次处理8个元素（SIMD宽度）。

使用SSE内部函数，我可以使用_mm_shuffle_epi8（）非常有效地完成这项工作，该函数执行16项表查找（收集并行计算术语）。shuffle索引是预先计算的，并使用位掩码进行查找。

for (i = 0; i < n; i += 8)
{
  v8n_Data = _mm_load_si128(&data[i]);
  mask = _mm_movemask_epi8(&is_valid[i]) & 0xff;     // is_valid is byte array
  v8n_Compacted = _mm_shuffle_epi8(v16n_ShuffleIndices[mask]);
  _mm_storeu_si128(&compacted[count], v8n_Compacted);
  count += bitCount[mask];
}

我现在的问题是，我也想为Altivec SIMD实现这一点（不要问为什么——错误的商业决策）。Altivec没有与_mm_movemask_ep8（）等效的关键成分。所以，我需要找到一种方法

1. 仿真_mm_movemask_ep8（）-似乎很昂贵，几个班次和ORs

2. 直接高效生成混洗索引-

即，索引i将是未压缩数据中第i个有效元素的索引

element_valid:   0 0 1 0 1 0 0 1 0
gather_indices:  x x x x x x 6 4 1
scatter_indices: 3 3 2 2 1 1 1 0 0

串行操作很简单，但我需要它是并行的（SIMD）。生成带有前缀sum的散点索引似乎很容易，但由于AltiVec和SSE都没有散点指令，因此我需要收集索引。聚集索引是分散索引的反函数，但如何并行获得？我知道在GPU编程的先驱时代，将散射转换为聚集是一种常见的技术，但这两种方法似乎都不实用。

如果不坚持压缩保留元素顺序，也许会允许更有效的实现？我可以放弃。

Answer 1

如果你想模拟_mm_movemask_epi8，并且你只需要一个来自8字节元素的8位标量掩码，那么你可以使用AltiVec:来做这样的事情

#include <stdio.h>
int main(void)
{
    const vector unsigned char vShift = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0 };
                                            // constant shift vector
    vector unsigned char isValid = { 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
                                            // sample input
    vector unsigned char v1 = vec_sl(isValid, vShift);
                                            // shift input values
    vector unsigned int v2 = vec_sum4s(v1, (vector unsigned int)(0));
    vector signed int v3 = vec_sum2s((vector signed int)v2, (vector signed int)(0));
                                            // sum shifted values
    vector signed int v4 = vec_splat(v3, 1);
    unsigned int mask __attribute__ ((aligned(16)));
    vec_ste((vector unsigned int)v4, 0, &mask);
                                            // store sum in scalar
    printf("v1 = %vun", v1);
    printf("v2 = %#vlxn", v2);
    printf("v3 = %#vlxn", v3);
    printf("v4 = %#vlxn", v4);
    printf("mask = %#xn", mask);
    return 0;
}

这是5条AltiVec指令，而SSE中是1条。您可能会丢失vec_splat并将其降至4。