使用SSE实现水平方向的最小值和最大值

Question

我有一个使用SSE的函数来完成很多工作，分析器显示我用于计算水平最小值和最大值的代码部分占用了大部分时间。

例如，我一直在使用以下实现来获取最小值：

static inline int16_t hMin(__m128i buffer) {
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m1));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m2));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m3));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m4));
    return ((int8_t*) ((void *) &buffer))[0];
}

我需要计算16个1字节整数的最小值和最大值，正如您所看到的。

非常感谢任何好的建议 :)

谢谢

- user46317

---

“m1，m2，m3和m4的值是什么？” - Z boson

我不知道是否有更好的方法。如果没有水平最大最小运算符，则必须通过四个二进制步骤完成（我认为您正在执行此操作）：将8与8进行比较，然后是4与4，接着是2与2，最后是1与1。使用int4只需两个步骤：https://dev59.com/RWkw5IYBdhLWcg3wdKUv#18616825 - Z boson

是的，抱歉，我忘记了洗牌控制掩码。它们被假定为Z玻色子。 - user46317

正如Marat Dukhan的回答所强调的主要原因，获取SIMD向量的地址并不是将元素值提取到CPU寄存器的正确方式，因为这种方式会强制该值被写入内存。（直接访问“struct”的值也不是正确的方法。）将代码更改为_mm_cvtsi128_si32将是最好的选择。 - rwong

值得一提的是，如果你的调用代码中有超过16个1字节整数需要找到最小值，那么你可以通过将单个_mm_min_epi8操作的结果累加到一个__m128i值中来更快地完成此操作，然后在函数内部的步骤中一次性合并结果即可。 - Apriori

Answer 1

SSE 4.1有一条指令几乎可以做到你想要的。它的名称是PHMINPOSUW，C/C++内嵌函数是_mm_minpos_epu16。它仅适用于16位无符号值，不能提供最大值，但这些问题可以很容易地解决。

1. 如果需要查找非负字节的最小值，则不需要执行任何操作。如果字节可能为负，则每个字节加上128。如果需要最大值，则从127中减去每个字节。
2. 使用_mm_srli_pi16或_mm_shuffle_epi8，然后使用_mm_min_epu8获取在某个XMM寄存器的偶数字节中8个成对最小值和奇数字节中的零值。(这些零通过移位/洗牌指令产生，并且应该在_mm_min_epu8之后仍保持在原位)。
3. 使用_mm_minpos_epu16在这些值中找到最小值。
4. 使用_mm_cvtsi128_si32提取结果的最小值。
5. 撤销步骤1的影响，以获取原始字节值。

以下是返回16个有符号字节中的最大值的示例：

static inline int16_t hMax(__m128i buffer)
{
    __m128i tmp1 = _mm_sub_epi8(_mm_set1_epi8(127), buffer);
    __m128i tmp2 = _mm_min_epu8(tmp1, _mm_srli_epi16(tmp1, 8));
    __m128i tmp3 = _mm_minpos_epu16(tmp2);
    return (int8_t)(127 - _mm_cvtsi128_si32(tmp3));
}

- Evgeny Kluev

---

我在我的基准测试中也尝试了你的方法，确实比其他方法快一些。 - user46317

很好，我喜欢 _mm_min_epu8 在每个16位元素的高半部分保留零的方式，因为 unsigned_min(0,x) = 0。因此，在仅进行零扩展到16位时不需要花费指令。 - Peter Cordes

请注意，减去128与加上或使用128进行异或运算是相同的（因为没有地方可以放置进位）。pxor比psubb运行在更多的端口上（并且是可交换的，使优化器在寄存器分配方面具有更大的灵活性），因此当需要将范围转换为无符号时，应该优先选择它。 - Peter Cordes

Answer 2

我建议进行两个更改：

• Replace ((int8_t*) ((void *) &buffer))[0] with _mm_cvtsi128_si32.

• Replace _mm_shuffle_epi8 with _mm_shuffle_epi32/_mm_shufflelo_epi16 which have lower latency on recent AMD processors and Intel Atom, and will save you memory load operations:

  static inline int16_t hMin(__m128i buffer)
  {
      buffer = _mm_min_epi8(buffer, _mm_shuffle_epi32(buffer, _MM_SHUFFLE(3, 2, 3, 2)));
      buffer = _mm_min_epi8(buffer, _mm_shuffle_epi32(buffer, _MM_SHUFFLE(1, 1, 1, 1)));
      buffer = _mm_min_epi8(buffer, _mm_shufflelo_epi16(buffer, _MM_SHUFFLE(1, 1, 1, 1)));
      buffer = _mm_min_epi8(buffer, _mm_srli_epi16(buffer, 8));
      return (int8_t)_mm_cvtsi128_si32(buffer);
  }
  

- Marat Dukhan

---

我今天测试了这个方法，它对大多数情况都有效，但当最小值位于第一个位置时，它无法找到最小值。例如，如果您使用向量（0,1，..，15）进行测试，它将返回最小值为1。对于所有其他情况，它似乎都有效！ - user46317

@user46317 你说得对，确实有个bug。现在已经修复了。 - Marat Dukhan

Answer 3

这里有一个没有使用shuffle的实现，因为在某些情况下，AMD 5000 Ryzen 7上的shuffle速度较慢。

    float max_elem3() const {
        __m128 a = _mm_unpacklo_ps(mm, mm); // x x y y
        __m128 b = _mm_unpackhi_ps(mm, mm); // z z w w
        __m128 c = _mm_max_ps(a, b); // ..., max(x, z), ..., ...
        Vector4 res = _mm_max_ps(mm, c); // ..., max(y, max(x, z)), ..., ...
        return res.y;
    }

    float min_elem3() const {
        __m128 a = _mm_unpacklo_ps(mm, mm); // x x y y
        __m128 b = _mm_unpackhi_ps(mm, mm); // z z w w
        __m128 c = _mm_min_ps(a, b); // ..., min(x, z), ..., ...
        Vector4 res = _mm_min_ps(mm, c); // ..., min(y, min(x, z)), ..., ...
        return res.y;
    }

- Iyad Ahmed

---

shufps xmm, xmm, i8 在 Zen 1/2/3 上是一个带有 1 个周期延迟和 2/clock 吞吐量的 1 uop。在 Zen4 上为 3/clock。如果 _mm_shuffle_ps 的其他版本在某些情况下速度较慢，那可能不是因为 shufps。但与 unpcklps/hps 相比，它确实需要更多的代码大小，并且与 pshufd 不同，仍然需要一个 movaps 寄存器复制（如果您没有使用 AVX 进行编译）。 - Peter Cordes

这种洗牌模式，使用2个可以并行进行的原始数据洗牌，特别适用于Zen处理器，它可以在一个时钟周期内运行多个洗牌操作。(Ice Lake只有2/c shufps但只有1/c unpcklps) https://uops.info/。所以如果你只关心3个元素，并且`min/max(y,w)`总是保持`y`，那么这是一个好技巧。也许通过正确的操作数顺序进行洗牌，可以将`w`设置为NaN？ - Peter Cordes

非常棒的见解，我并不是SIMD方面的专家，但我想出了上述解决方案，幸运的是它运行良好。我仍在尝试优化程序的其他部分，您可以在此处找到完整的代码： https://github.com/iyadahmed/bvh - Iyad Ahmed