我在有序整数 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,但是再次保持订单似乎并不容易。