c++ - 在 C++ 中并行查找 vector 的 find_first

Question

我有一个相当大的 vector 。一些 vector 成员并行匹配某个条件。我想找到第一个符合条件的元素。

我的问题与这个问题(tbb: parallel find first element)非常相似，但我没有待定。检查条件非常繁琐(所以我不能按顺序对所有条件进行检查)。这就是为什么我想并行运行它。我不得不提一下，我想找到第一个元素(所以元素的索引位置对我来说很重要)。

例如，如果我有 4 个线程。

ThreadNr   Index      condition
1            0         Not Meet
2            1         Not Meet
3            2         Not Meet
4            3         Not Meet

ThreadNr   Index      condition
1            4         Not Meet
2            5          Meet
3            6         Not Meet
4            7          Meet

函数必须重新调整索引号 5。线程必须分布并在顺序迭代 block 上工作( block 大小可以大于 1。例如，线程 1 在前 4 个元素上工作，线程 2 在后 4 个元素上工作，依此类推)。

对于上面的例子，如果线程号 4(在索引 7 中)在线程号 2(在索引 5 中)之前找到成员，它必须等待所有线程完成工作。正如我之前所说，最低索引号是目标。

如果您有更好的算法，请指正。

注意:我可以使用外部库，例如 boost 1.62、OpenMP 2.0

Answer 1

由于 OpenMP 2.0 没有取消结构，您必须自己实现一个，例如，通过使用共享变量。这也意味着您不能使用 for 工作共享构造，因为不允许中断并行循环(这就是 OpenMP 4.0 引入取消构造的原因)。如果您在每个元素的评估之间实现取消检查，则可能会发生两个或多个线程找到符合条件的元素。因此，您应该对索引执行最小缩减:

int found = 0;
int first_index = INVALID_VALUE;
int iteration = 0;

#pragma omp parallel
{
   int my_index = INVALID_VALUE;
   int i;

   do
   {
      // Later versions of OpenMP allow for "atomic capture"
      // but OpenMP 2.0 requires a critical directive instead
      #pragma omp critical(iteration)
      {
         i = iteration++;
      }

      if (i < N && check(i))
      {
         found = 1;
         my_index = i;
      }
   } while (!found && i < N);

   #pragma omp critical(reduction)
   if (my_index != INVALID_VALUE)
   {
      if (first_index == INVALID_VALUE || my_index < first_index)
         first_index = my_index;
   }

   // Only needed if more code follows before the end of the region
   #pragma omp barrier

   ...
}

此代码假定检查第 i 个元素的条件 (check(i)) 不会改变元素的状态，因此，可能发生的最坏情况是线程找到匹配元素的线程可能必须等待所有其他线程完成检查它们当前正在处理的元素，并且等待时间将是所有处理时间的最大值。

在 do 循环中使用的 critical 结构是昂贵的。如果 check() 不会花费那么多时间，那么您可以考虑使用 block 而不是迭代:

do
{
   #pragma omp critical(chunk)
   {
       my_chunk = chunk++;
   }

   if (my_chunk >= N_chunks)
      break;

   for (i = my_chunk * chunk_size; !found && i < (my_chunk+1)*chunk_size; i++)
   {
      if (check(i))
      {
         found = 1;
         my_index = i;
         break;
      }
   }
} while (!found && my_chunk < N_chunks);

---

另一种解决方案在元素数量不是那么多且检查每个元素的成本很高时工作得相当好:

#pragma omp parallel
{
   #pragma omp for schedule(dynamic,x)
   for (i = 0; i < N; i++)
   {
      if (!found && check(i))
      {
         my_index = i;
         found = 1;
      }
   }

   // Min reduction from the solution above
   ...
}

一旦 found 变为真，其余的循环迭代将运行“空”体，因为 && 的快捷属性。