在x86 SIMD向量中查找最大元素的索引

Question

我正在考虑为uint32_t实现8-ary heapsort.为此,我需要一个函数来选择8元素向量中的最大元素的索引,以便我可以将它与父元素进行比较,并有条件地执行swap和进一步的siftDown步骤.

(8 uint32_ts可以更改为例如16 uint32_ts或8 uint64_t或x86 SIMD可以有效支持的任何内容).

我有一些关于如何做到这一点的想法,但我正在寻找比非矢量化代码更快的东西,特别是我正在寻找一些能让我快速进行快速操作的东西.

我有clang ++ 3.3和Core i7-4670,所以我应该能够使用最新的x86 SIMD东西.

(顺便说一下:这是一个更大项目的一部分:https://github.com/tarsa/SortingAlgorithmsBenchmark,例如四元heapsort,所以在实施SIMD heapsort后我可以立即比较它们)

重复 - 问题是:计算x86 SIMD向量中最大元素索引的最有效方法是什么？

PS:这不是链接问题的重复 - 注意我要求的是最大元素的索引,而不仅仅是元素值.

Answer 1

水平操作对于SIMD来说是个坏消息,特别是AVX,其中大多数256位指令实际上被分成两个独立的128位操作.话虽如此,如果你真的必须在8个元素上做一个水平32位最大值,那么我认为一般的方法必须是:

• 找到最大值(通常是几次移位/置换和最大操作)
• splat第二个向量的所有8个元素的最大值(可以与之前的操作组合)
• 比较原始矢量和最大矢量(_mm256_cmpeq_epi32)
• 提取标量掩码(_mm256_movemask_epi8)
• 将标量掩码转换为索引

这是我刚刚放在一起的AVX2实现的第一次传递 - 我测试了它并在2.6 GHz Haswell上进行了基准测试,它以1.7 ns /向量运行(包括加载向量并存储结果索引):

uint8_t _mm256_hmax_index(const __m256i v)
{
    __m256i vmax = v;

    vmax = _mm256_max_epu32(vmax, _mm256_alignr_epi8(vmax, vmax, 4));
    vmax = _mm256_max_epu32(vmax, _mm256_alignr_epi8(vmax, vmax, 8));
    vmax = _mm256_max_epu32(vmax, _mm256_permute2x128_si256(vmax, vmax, 0x01));

    __m256i vcmp = _mm256_cmpeq_epi32(v, vmax);

    uint32_t mask = _mm256_movemask_epi8(vcmp);

    return __builtin_ctz(mask) >> 2;
}

Answer 2

在n路SIMD矢量上进行水平操作(点积,和,最大索引,等等)的最有效方法是一次转换它们,然后通过转置它们并使用垂直操作代替它们.某些SIMD架构对水平操作有更好的支持,但一般来说,块式转换方法将更加灵活和高效.