高效将散列索引转换为聚合索引的方法？

Question

我正在尝试使用SIMD指令编写流压缩程序（获取数组并摆脱空元素）。循环的每次迭代同时处理8个元素（SIMD宽度）。

使用SSE指令集，我可以使用_mm_shuffle_epi8()相当高效地完成此操作，该函数执行16个条目的表查找（在并行计算术语中称为gather）。洗牌索引是预先计算的，并使用位掩码查找。

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_epi8（）等效的东西，这是一个关键成分。因此，我需要找到一种方法，要么模拟_mm_movemask_epi8（）-似乎很昂贵，需要进行几次移位和或运算，要么直接有效地生成洗牌索引-即第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）执行。使用前缀和似乎很容易生成散布索引，但由于AltiVec和SSE都没有散布指令，所以我需要收集索引。收集索引是散布索引的反函数，但如何并行获取呢？我知道在GPU编程的开创时期，将散布转换为收集是一种常见技术，但这两种方法似乎都不实用。

也许放弃保留元素顺序可以使紧凑更有效率？我可以放弃这一点。

- Yale Zhang

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 = %vu\n", v1);
    printf("v2 = %#vlx\n", v2);
    printf("v3 = %#vlx\n", v3);
    printf("v4 = %#vlx\n", v4);
    printf("mask = %#x\n", mask);

    return 0;
}

这是5条AltiVec指令对比SSE的1条。你可能可以省略vec_splat指令，将其减少到4条。

- Paul R