无符号 32 位整数在 SSE 中的水平最小值和位置

Question

我正在寻找一种方法来查找无符号 32 位整数的最小值及其在 SSE 中的位置（类似于 _mm_minpos_epu16）。我知道我可以通过一系列 _mm_min_epu32 和 shuffles/shifts 找到最小值，但这并没有让我找到位置。

有没有人有任何很酷的方法来做到这一点？

Answer 1

可能有更聪明的方法，但现在这里有一个蛮力方法：

#include <stdio.h>
#include <smmintrin.h> // SSE4.1

int main(void)
{
    __m128i v = _mm_setr_epi32(42, 1, 43, 2);

    printf("v     = %vlu\n", v);

    __m128i vmin = v;

    vmin = _mm_min_epu32(vmin, _mm_alignr_epi8(vmin, vmin, 4));
    vmin = _mm_min_epu32(vmin, _mm_alignr_epi8(vmin, vmin, 8));
                                                   // get min value in all elements of vmin

    printf("vmin  = %vlu\n", vmin);

    __m128i vmask = _mm_cmpeq_epi32(v, vmin);      // set min element(s) in mask to -1,
                                                   // all others to 0 [1]

    printf("vmask = %vld\n", vmask);

    int16_t mask = _mm_movemask_epi8(vmask);       // get mask as scalar [2]

    printf("mask  = %#x\n", mask);

    int pos = __builtin_ctz(mask) >> 2;            // convert scalar mask to index [3]

    printf("pos   = %d\n", pos);

    return 0;
}

如果你可以使用设置在最小元素位置的掩码，那么你可以在 [1] 处停止，否则继续 [3] 以获取 (最不重要）最小元素。

另请注意，__builtin_ctz 是特定于 gcc 的内在函数（尽管它也存在于其他 gcc 兼容编译器中）。如果您使用的是 MSVC，则需要使用等效的 Microsoft 内在函数 (_BitScanForward)。

Answer 2

一般来说，如果将水平运算符与 SIMD 结合使用，则表明 SIMD 未得到最佳使用。但是，水平操作在循环结束时很好，在这种情况下我会做

int result[4] __attribute__((aligned(16)));
_mm_store_si128((__m128i *) result, v);
for(int i=0; i<4; i++) if(result[i]<min) { min = result[i]; index = i; }

不过，这里有一些使用 SSE 的解决方案。我不知道他们是否比上面的代码更好。

第一个解决方案是 Paul R 答案的变体。

vmin = _mm_min_epu32(vmin, _mm_alignr_epi8(vmin, vmin, 4));
vmin = _mm_min_epu32(vmin, _mm_alignr_epi8(vmin, vmin, 8));
__m128i vmask = _mm_cmpeq_epi32(v, vmin);
vmask = _mm_xor_si128(vmask, _mm_set1_epi32(-1));
__m128i vpos = _mm_minpos_epu16(vmask);

vpos 中的第二个 16 位字包含两倍的位置。

这是使用 _mm_minpos_epu16 的另一种变体。它首先找到最小的高 16 位，然后屏蔽掉不在最小 16 位中的值（通过将它们全部设置为高），然后找到低 16 位的最小值以及位置。

__m128i mask1 = _mm_setr_epi8(0x0,0x1,0x4,0x5, 0x8,0x9,0xc,0xd, 0x0,0x1,0x4,0x5,  0x8,0x9,0xc,0xd);
__m128i mask2 = _mm_setr_epi8(0x2,0x3,0x6,0x7, 0xa,0xb,0xe,0xf, 0x2,0x3,0x6,0x7,  0xa,0xb,0xe,0xf);
__m128i mask3 = _mm_set1_epi32(0x01000100);

掩码是常量，因此可以在编译时或循环外计算。

__m128i lo = _mm_shuffle_epi8(v,mask1);            //lower 16-bits
__m128i hi = _mm_shuffle_epi8(v,mask2);            //upper 16-bits
__m128i t1 = _mm_minpos_epu16(hi);                 //upper 16-bits min
__m128i t2 = _mm_shuffle_epi8(t1, mask3);          //broadcast upper min
__m128i t3 = _mm_cmpeq_epi32(t2,hi);               //select equal
__m128i t4 = _mm_xor_si128(t3, _mm_set1_epi32(-1));//invert
__m128i t5 = _mm_or_si128(lo,t4);                   
__m128i t6 = _mm_minpos_epu16(t5);                 //lower 16-bits hi and position

最小值的高16位在t1的前16位，最小值的低16位在t6的前16位。位置在t6.

的后16位

无符号 32 位整数在 SSE 中的水平最小值和位置

Horizontal minimum and position in SSE for unsigned 32-bit integers

algorithm

optimization

performance

sse

simd