c++ - 向量化涉及短裤的条件

Question

我正在使用 2 个无符号短裤的紧凑结构，指示开始和结束位置。
我需要能够快速确定是否有任何长度(从开始到结束的差异)超过阈值的 Range 对象。

我将拥有大量对象，每个对象都有自己的 Range 数组，因此跟踪哪些 Range 对象超出阈值是不可行的列表或其他东西。此代码也将经常运行(每个数组每秒多次)，因此需要高效。

struct Range
{
 unsigned short start;
 unsigned short end;
}

我将始终拥有一个大小为 2^n 的 Range 数组。虽然我想在发现超过阈值的情况下立即中止，但我很确定将它们简单地或在一起并在最后检查会更快......假设我可以矢量化循环。尽管如果我可以对每个 vector 的结果 block 执行 if 语句，那就太棒了。

size_t rangecount = 1 << resolution;
Range* ranges = new Range[rangecount];

...

bool result = false;
for (size_t i = 0; i < ranges; ++i)
{
 result |= (range[i].end - range[i].start) > 4;
}

毫不奇怪，自动向量化器给出了 1202 错误，因为我的数据类型不是 32 位或 64 位宽。我真的不想将我的数据大小加倍并使每个字段都成为无符号整数。所以我猜自动矢量化器方法已经出局了。

是否有可以处理 16 位变量的 vector 指令？如果有，我如何在 C++ 中使用它们来矢量化我的循环？

Answer 1

您想知道是否有任何值大于 4？

是的，有这方面的 SIMD 指令。不幸的是，自动矢量化无法处理这种情况。这是一个矢量化算法:

diff_v = end_v - start_v; // _mm_hsub_epi16 
floor_v = max(4_v, diff_v); // _mm_max_epi16 
if (floor_v != 4_v) return true; // wide scalar comparison

使用 _mm_sub_epi16具有数组结构或 _mm_hsub_epi16具有一系列结构。

实际上自 start首先存储在内存中，您将处理 start_v - end_v , 所以使用 _mm_min_epi16和 -4 的 vector .

每条 SSE3 指令将一次执行 8 次比较。提前返回而不是循环仍然是最快的。然而，将循环展开得更多一点可能会给你带来额外的速度(将第一组结果传递到打包的最小/最大函数中以组合它们)。

所以你最终得到(大约):

most_negative = threshold = _mm_set_epi64(0xFCFCFCFCFCFCFCFC); // vectorized -4

loop:
    a = load from range;
    b = load from range;
    diff = _mm_hsub_epi16(a, b);
    most_negative = _mm_min_epi16(most_negative, diff);

    // unroll by repeating the above four instructions 4 times or so
    if (most_negative != threshold) return true;
repeat loop