Yum*_*Yum 3 algorithm optimization simd
我编写了一个算法来获得 std::vector 中两个元素之间的最大差异，其中两个值中较大的值必须比较低的值在更高的索引处。
unsigned short int min = input.front();
unsigned short res = 0;
for (size_t i = 1; i < input.size(); ++i)
{
if (input[i] <= min)
{
min = input[i];
continue;
}
int dif = input[i] - min;
res = dif > res ? dif : res;
}
return res != 0 ? res : -1;
是否可以使用 SIMD 优化此算法？我是 SIMD 的新手，到目前为止我没有成功
您没有指定任何特定的架构，因此我将使用英文描述的算法保持这个主要架构的中立性。但它需要一个 SIMD ISA，它可以有效地对 SIMD 比较结果进行分支以检查通常为真的条件，例如 x86 但不是真正的 ARM NEON。
这不适用于 NEON，因为它没有等效的 movemask，并且 SIMD -> integer 会导致许多 ARM 微体系结构上的停顿。
循环数组时的正常情况是元素或元素的整个 SIMD 向量不是new min，也不是diffCandidate。我们可以快速浏览这些元素，只有在有新的min. 这就像 SIMDstrlen或 SIMD memcmp，除了不是在第一次搜索命中时停止，我们只是对一个块进行标量然后继续。
对于v[0..7]输入数组的每个向量（假设每个向量有8 个int16_t元素（16 字节），但这是任意的）：
SIMD 比较vmin > v[0..7]，并检查是否有任何元素为真。（例如 x86 _mm_cmpgt_epi16/ if(_mm_movemask_epi8(cmp) != 0)） 如果min某处有新的，我们有一个特殊情况：旧的最小值适用于某些元素，但新的最小值适用于其他元素。并且向量中可能有多个 new-min 更新，并且在任何这些点都有 new-diff 候选。
所以用标量代码处理这个向量（更新一个diff不需要与向量同步的标量，diffmax因为我们不需要位置）。
广播最终min到vmin时你就大功告成了。或者做一个 SIMD 水平，min这样以后的 SIMD 迭代的乱序执行就可以开始，而无需等待vmin来自标量。如果标量代码是无分支的，那么应该可以很好地工作，因此标量代码中没有导致后续向量工作被丢弃的错误预测。
作为替代方案，SIMD 前缀-和类型的事物（实际上是前缀-最小）可以产生一个vmin，其中每个元素都是该点之前的最小。 （与 SSE 的并行前缀（累积）总和）。你总是可以这样做以避免任何分支，但如果新的最小候选者很少，那么它很昂贵。尽管如此，它在分支困难的 ARM NEON 上仍然可行。
如果没有新的 min ，SIMD 会打包 maxdiffmax[0..7] = max(diffmax[0..7], v[0..7]-vmin)。（如果您使用 unsigned max 来处理整个范围，请使用饱和减法，这样您就不会产生较大的无符号差异。）
在循环结束时，执行diffmax向量的 SIMD 水平最大值。请注意，由于我们不需要最大差值的位置，因此当找到新的候选时，我们不需要更新循环内的所有元素。我们甚至不需要保持标量特殊情况diffmax和 SIMDvdiffmax彼此同步，只需在最后检查以获取标量和 SIMD 最大差异的最大值。
SIMD min/max 与水平总和基本相同，只是您使用了packed-max 而不是packed-add。对于 x86，请参阅在 x86上进行水平浮点向量求和的最快方法。
或者在带有 SSE4.1 的 x86 上用于 16 位整数元素，phminposuw/_mm_minpos_epu16可用于最小值或最大值、有符号或无符号，并对输入进行适当的调整。 max = -min(-diffmax). 您可以将 diffmax 视为无符号，因为已知它是非负的，但 使用 SSE 的水平最小值和最大值显示了如何将符号位翻转为范围移位有符号到无符号并返回。
每次我们找到一个新的min候选人时，我们可能都会得到一个分支预测错误，否则我们min经常寻找新的候选人，这会导致效率低下。
如果min经常需要新的候选者，使用较短的向量可能是好的。或者在发现min当前向量中有一个新元素时，然后使用更窄的向量来仅对更少的元素进行标量。在 x86 上，您可以使用bsf(bit-scan forward) 来查找哪个元素具有第一个 new-min。这使您的标量代码对向量比较掩码具有数据依赖性，但如果其分支被错误预测，则比较掩码将准备就绪。否则，如果分支预测可以以某种方式找到向量需要标量回退的模式，则预测+推测执行将打破该数据依赖性。
未完成/损坏（由我）示例改编自 @harold 删除的完全无分支版本的答案，该版本为 x86 SSE2 动态构建最小到那个元素的向量。
（@harold 用 suffix-max 而不是 min 写了它，这就是我想他删除它的原因。我部分地将它从 max 转换为 min。）
一个网点内在版本的x86可看的东西是这样的。但是分支可能更好，除非您期望某种斜率或趋势使新min值频繁出现。
// BROKEN, see FIXME comments.
// converted from @harold's suffix-max version
int broken_unfinished_maxDiffSSE(const std::vector<uint16_t> &input) {
const uint16_t *ptr = input.data();
// construct suffix-min
// find max-diff at the same time
__m128i min = _mm_set_epi32(-1);
__m128i maxdiff = _mm_setzero_si128();
size_t i = input.size();
for (; i >= 8; i -= 8) {
__m128i data = _mm_loadu_si128((const __m128i*)(ptr + i - 8));
// FIXME: need to shift in 0xFFFF, not 0, for min.
// or keep the old data, maybe with _mm_alignr_epi8
__m128i d = data;
// link with suffix
d = _mm_min_epu16(d, _mm_slli_si128(max, 14));
// do suffix-min within block.
d = _mm_min_epu16(d, _mm_srli_si128(d, 2));
d = _mm_min_epu16(d, _mm_shuffle_epi32(d, 0xFA));
d = _mm_min_epu16(d, _mm_shuffle_epi32(d, 0xEE));
max = d;
// update max-diff
__m128i diff = _mm_subs_epu16(data, min); // with saturation to 0
maxdiff = _mm_max_epu16(maxdiff, diff);
}
// horizontal max
maxdiff = _mm_max_epu16(maxdiff, _mm_srli_si128(maxdiff, 2));
maxdiff = _mm_max_epu16(maxdiff, _mm_shuffle_epi32(maxdiff, 0xFA));
maxdiff = _mm_max_epu16(maxdiff, _mm_shuffle_epi32(maxdiff, 0xEE));
int res = _mm_cvtsi128_si32(maxdiff) & 0xFFFF;
unsigned scalarmin = _mm_extract_epi16(min, 7); // last element of last vector
for (; i != 0; i--) {
scalarmin = std::min(scalarmin, ptr[i - 1]);
res = std::max(res, ptr[i - 1] - scalarmin);
}
return res != 0 ? res : -1;
}
如果我们处理最后一个完整向量之间的重叠，我们可以用最终未对齐的向量替换标量清理min。