c++ - OpenMP 并行线程

Question

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

 #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));
}

在这种情况下，循环没有并行化，因为它使用了迭代器，编译器不能 了解如何切开它。

你能帮帮我吗？

Answer 1

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

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并且将为每个任务创建迭代器的拷贝(即在每次迭代中)。这不是你想要的。
• 每个线程在其私有(private)部分执行部分归约 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)。