1

我需要并行化这个循环，我虽然使用它是一个好主意，但我以前从未研究过它们。 

 #pragma omp parallel for

for(std::set<size_t>::const_iterator it=mesh->NEList[vid].begin();
        it!=mesh->NEList[vid].end(); ++it){

    worst_q = std::min(worst_q, mesh->element_quality(*it));
}

在这种情况下，循环没有并行化，因为它使用迭代器并且编译器无法理解如何分割它。

你能帮助我吗？

4

2 回答 2

1

OpenMP 要求并行循环中的控制谓词具有for以下关系运算符之一：<、<=或。只有随机访问迭代器提供这些运算符，因此 OpenMP 并行循环仅适用于提供随机访问迭代器的容器。仅提供双向迭代器。您可以使用显式任务来克服该限制。可以通过首先对每个线程变量的私有部分进行部分归约，然后对部分值进行全局归约来执行归约。>>=std::set

double *t_worst_q;
// Cache size on x86/x64 in number of t_worst_q[] elements
const int cb = 64 / sizeof(*t_worst_q);

#pragma omp parallel
{
   #pragma omp single
   {
      t_worst_q = new double[omp_get_num_threads() * cb];
      for (int i = 0; i < omp_get_num_threads(); i++)
         t_worst_q[i * cb] = worst_q;
   }

   // Perform partial min reduction using tasks
   #pragma omp single
   {
      for(std::set<size_t>::const_iterator it=mesh->NEList[vid].begin();
          it!=mesh->NEList[vid].end(); ++it) {
         size_t elem = *it;
         #pragma omp task
         {
            int tid = omp_get_thread_num();
            t_worst_q[tid * cb] = std::min(t_worst_q[tid * cb],
                                           mesh->element_quality(elem));
         }
      }
   }

   // Perform global reduction
   #pragma omp critical
   {
      int tid = omp_get_thread_num();
      worst_q = std::min(worst_q, t_worst_q[tid * cb]);
   }
}

delete [] t_worst_q;

（我假设mesh->element_quality()返回double）

一些关键点：

  • 该循环仅由一个线程串行执行，但每次迭代都会创建一个新任务。这些很可能排队等待由空闲线程执行。
  • 在构造的隐式屏障处等待的空闲线程在single创建任务后立即开始使用它们。
  • 指向的值it在任务主体之前被取消引用。如果在任务主体内取消引用，it将会firstprivate为每个任务（即在每次迭代中）创建迭代器的副本。这不是你想要的。
  • 每个线程在其私有部分执行部分缩减t_worst_q[]。
  • 为了防止由于错误共享而导致性能下降t_worst_q[]，每个线程访问的元素被间隔开，以便最终在单独的高速缓存行中结束。在 x86/x64 上，缓存行是 64 字节，因此线程数乘以cb = 64 / sizeof(double).
  • 全局最小值减少在critical构造内部执行，以防止worst_q同时被多个线程访问。这仅用于说明目的，因为减少也可以通过并行区域之后的主线程中的循环来执行。

请注意，显式任务需要支持 OpenMP 3.0 或 3.1 的编译器。这排除了所有版本的 Microsoft C/C++ 编译器（它仅支持 OpenMP 2.0）。

于 2013-03-04T23:13:02.527 回答
0

随机存取容器

最简单的解决方案是将所有内容放入一个随机访问容器（如std::vector）并使用 OpenMP 青睐的基于索引的循环：

// Copy elements
std::vector<size_t> neListVector(mesh->NEList[vid].begin(), mesh->NEList[vid].end());

// Process in a standard OpenMP index-based for loop
#pragma omp parallel for reduction(min : worst_q)
for (int i = 0; i < neListVector.size(); i++) {
    worst_q = std::min(worst_q, complexCalc(neListVector[i]));
}

除了非常简单之外，在您的情况下（size_t可以轻松复制的微小类型元素），这也是具有最佳性能和可扩展性的解决方案。

避免复制

但是，在与您的情况不同的情况下，您可能拥有不容易复制的元素（较大的元素）或根本无法复制。在这种情况下，您可以将相应的指针放入随机访问容器中：

// Collect pointers
std::vector<const nonCopiableObjectType *> neListVector;
for (const auto &entry : mesh->NEList[vid]) {
    neListVector.push_back(&entry);
}

// Process in a standard OpenMP index-based for loop
#pragma omp parallel for reduction(min : worst_q)
for (int i = 0; i < neListVector.size(); i++) {
    worst_q = std::min(worst_q, mesh->element_quality(*neListVector[i]));
}

这比第一个解决方案稍微复杂一些，在小元素上仍然具有相同的良好性能，并且在较大元素上具有更高的性能。

任务和动态调度

由于其他人在他的回答中提出了 OpenMP 任务，我想对此发表评论。任务是一个非常强大的结构，但它们有巨大的开销（甚至随着线程数量的增加而增加），在这种情况下只会让事情变得更加复杂。

为了min减少使用 Tasks 是不合理的，因为在主线程中创建一个 Task 的成本远远超过了std::min它本身！

对于更复杂的操作mesh->element_quality，您可能认为 Tasks 的动态特性可以帮助您解决负载平衡问题，以防mesh->element_quality迭代之间的执行时间差异很大并且您没有足够的迭代来平衡它。但即使在这种情况下，也有一个更简单的解决方案：只需在我以前的解决方案之一中将schedule(dynamic)指令添加到您的行中，即可使用动态调度。parallel for它实现了相同的行为，但开销要少得多。

于 2015-06-06T15:16:33.877 回答