c++ - SSE 优化循环，在数组中查找零并切换标志 + 更新另一个数组

Question

一段 C++ 代码确定零的出现次数，并为每个检查的数字保留一个二进制标志变量。每次在一维数组中遇到零时，标志的值都会在 0 和 1 之间切换。

我正在尝试使用 SSE 来加速它，但我不确定如何去做。我读过，评估 __m128i 的各个字段效率低下。

C++中的代码是:

int flag = 0;
int var_num2[1000];
for(int i = 0; i<1000; i++)
{  
    if (var[i] == 0)
    {
        var_num2[i] = flag;
        flag = !flag;  //toggle value upon encountering a 0
     }
}

我应该如何使用 SSE 内在函数来解决这个问题？

Answer 1

您必须认识到这个问题，但这是一个众所周知的问题的变体。我先做个理论上的描述

如果 var 包含 0 和 0，则引入一个包含 1 的临时数组 not_var[] 否则。引入一个临时数组 not_var_sum[]，其中包含 partial sum not_var 的。var_num2 现在是 not_var_sum[]

的 LSB

第一个和第三个操作可以简单地并行化。并行化部分和是 only a bit harder .

在实际实现中，您不会构造not_var[]，而是在第 2 步的所有迭代中将 LSB 直接写入 var_num2。这是有效，因为您可以丢弃较高的位。只保留 LSB 相当于对结果取模 2，并且 (a+b)%2 == ((a%2) + (b%2))%s。