我在有序整数 vector 上有一个循环。在循环内部,我对整数进行了一些操作,以确定在程序的其余部分是否保留或丢弃它们。循环之后,我需要一个包含保持整数的 vector ,该整数也有序。

由于整数的 vector 很大(可能约为500亿),因此我使用openmp来使循环并行化,并提出了以下代码。为了保持良好的整数有序,我使用了static子句和私有(private) vector ,它们在循环完成之后合并。

std::vector<unsigned> large_int_vector;
// vector filling and ordered...

std::vector<std::vector<unsigned> > good_int_threads;
#pragma omp parallel
{
  int num_threads = omp_get_num_threads();
  int i_thread = omp_get_thread_num();
  #pragma omp single
  {
    good_int_threads.resize(num_threads);
  }
  #pragma omp for schedule(static)
  for (std::size_t i = 0; i < large_int_vector.size(); i++) {
    bool is_good_int = true;
    // some operations on large_int_vector[i]
    if (is_good_int)
      good_int_threads[i_thread].push_back(large_int_vector[i]);
  }
}

std::vector<unsigned> good_int;
for (unsigned i = 0; i != good_int_threads.size(); i++) {
  good_int.insert(good_int.end(),good_int_threads[i].begin(),good_int_threads[i].end());
}

这可以正常工作,但伸缩性不好。原因是大部分(取决于线程数,但通常大于50%,如果仅使用2个或3个线程,则最多可达100%)好整数位于large_int_vector的“开始”位置。

更准确地说,在for循环中完成的工作是对整数应用某些操作。如果单个整数失败,则整数将被丢弃,我们可以立即移至下一个整数。另一方面,要保留整数,它必须通过所有操作。显然,这会导致工作失衡,这说明缩放比例很差。

good_int的大小通常为〜large_int_vector / 50,因此约为10亿。

如何改善我的代码?

最佳答案

为每个线程本地的每个线程分配 vector ,并像这样在块上运行:

std::vector<unsigned> large_int_vec;
std::size_t n = large_int_vec.size();
std::size_t chunk = n/10;  //10 chunks, adjust by performance.
#pragma omp parallel
{
  std::vector<unsigned> good_int_local;
  for(std::size_t j = 0; j < n; j += chunk) {
    std::size_t n2 = (j + chunk) >= n ? n - j : chunk;
    #pragma omp for nowait schedule(static)
    for (std::size_t i = 0; i < n2; i++) {
      bool is_good_int = true;
      // some operations on large_int_vec[i]
      if (is_good_int) good_int_local.push_back(large_int_vec[j + i]);
    }
    #pragma omp for schedule(static) ordered
    for(int i=0; i<omp_get_num_threads(); i++) {
      #pragma omp ordered
      good_int.insert(good_int.end(), good_int_local.begin(), good_int_local.end());
    }
    good_int_local.clear();
  }
}

这样可以更好地平衡负载并保持顺序。您也许可以使用schedule(static, chunk)提供一个解决方案,该解决方案无需使用外部循环即可保持顺序,但对我而言似乎并不重要。另外,您也许可以提出一个custom dynamic solution,但是再次保持订单似乎并不容易。

10-07 18:55
查看更多