如何使用OpenMP并行化通过C++ std :: list的for循环？

Question

我想使用OpenMP以并行方式遍历std :: list中的所有元素.循环应该能够改变列表的元素.有一个简单的解决方案吗？当迭代器是随机访问迭代器时,似乎OpenMP 3.0支持并行for循环,但不是其他.无论如何,我更喜欢使用OpenMP 2.0,因为我无法完全控制哪些编译器可供我使用.

如果我的容器是矢量,我可能会使用:

#pragma omp parallel for
for (auto it = v.begin(); it != v.end(); ++it) {
    it->process();
}

我知道我可以将列表复制到矢量中,执行循环,然后将所有内容复制回来.但是,如果可能的话,我想避免这种复杂性和开销.

Answer 1

如果您决定使用Openmp 3.0,您可以使用该task功能:

#pragma omp parallel
#pragma omp single
{
  for(auto it = l.begin(); it != l.end(); ++it)
     #pragma omp task firstprivate(it)
       it->process();
  #pragma omp taskwait
}

这将在一个线程中执行循环,但将元素的处理委托给其他人.

没有OpenMP 3.0最简单的方法就是编写列表中元素的所有指针(或者向量中的迭代器并迭代那个.这样你就不必复制任何东西,避免复制元素本身的开销,所以它不应该不需要太多开销:

std::vector<my_element*> elements; //my_element is whatever is in list
for(auto it = list.begin(); it != list.end(); ++it)
  elements.push_back(&(*it));

#pragma omp parallel shared(chunks)
{
  #pragma omp for
  for(size_t i = 0; i < elements.size(); ++i) // or use iterators in newer OpenMP
      elements[i]->process();
}

如果你想避免复制指针,你总是可以手动创建一个并行化的for循环.您可以让线程访问列表中的交错元素(由KennyTM提出),也可以在迭代和迭代之前将范围拆分为大致相等的连续部分.后者似乎更可取,因为线程避免访问当前由其他线程处理的列表节点(即使只有下一个指针),这可能导致错误共享.这看起来大致如下:

#pragma omp parallel
{
  int thread_count = omp_get_num_threads();
  int thread_num   = omp_get_thread_num();
  size_t chunk_size= list.size() / thread_count;
  auto begin = list.begin();
  std::advance(begin, thread_num * chunk_size);
  auto end = begin;
  if(thread_num = thread_count - 1) // last thread iterates the remaining sequence
     end = list.end();
  else
     std::advance(end, chunk_size);
  #pragma omp barrier
  for(auto it = begin; it != end; ++it)
    it->process();
}

不严格需要屏障,但是如果process改变处理过的元素(意味着它不是const方法),如果线程迭代已经被突变的序列,则可能存在某种错误共享而没有它.这种方式将在序列上迭代3*n次(其中n是线程数),因此对于大量线程,缩放可能不是最优的.

为了减少开销,可以将范围的生成放在其外部#pragma omp parallel,但是您需要知道将形成并行部分的线程数.所以你可能不得不手动设置num_threads,或者使用omp_get_max_threads()和处理创建的线程数少于omp_get_max_threads()(这只是一个上限)的情况.最后一种方法可以通过在这种情况下分配每个线程的severa块来处理(使用#pragma omp for应该这样做):

int max_threads = omp_get_max_threads();
std::vector<std::pair<std::list<...>::iterator, std::list<...>::iterator> > chunks;
chunks.reserve(max_threads); 
size_t chunk_size= list.size() / max_threads;
auto cur_iter = list.begin();
for(int i = 0; i < max_threads - 1; ++i)
{
   auto last_iter = cur_iter;
   std::advance(cur_iter, chunk_size);
   chunks.push_back(std::make_pair(last_iter, cur_iter);
}
chunks.push_back(cur_iter, list.end();

#pragma omp parallel shared(chunks)
{
  #pragma omp for
  for(int i = 0; i < max_threads; ++i)
    for(auto it = chunks[i].first; it != chunks[i].second; ++it)
      it->process();
}

这将只需要三次迭代list(两次,如果你可以获得列表的大小而不进行迭代).我认为这是关于非随机访问迭代器可以做的最好的事情,而不使用tasks或迭代一些不合适的数据结构(如指针向量).