c++ - std::sort 比自定义 OpenMP 并行排序算法快得多

Question

我一直在使用 OpenMP 测试并行排序。我实现了比没有 OpenMP 快 3 倍的奇偶排序算法。然而，std::sort 仍然更快:seq - 100s，parallel - 20s，std::sort - 0.05s

我尝试将#pragma omp parallel for 移动到 i-cycle 但效果更差并且没有对 vector 进行排序

for (int i = 0; i < 100000; i++) {
        #pragma omp parallel for
        for (int j = (i % 2) ? 0 : 1; j < 100000 - 1; j += 2) {
            if (vec_[j] > vec_[j + 1]) {
                std::swap(vec_[j], vec_[j + 1]);
            }
        }
    }

老实说，我原以为并行奇偶排序是最快的，但现在我想知道 - 我做错了什么还是只是 std::sort 如此高效？

Answer 1

您的算法完成的总工作量为 O(n^2)。使用 k 个线程，这最多使其成为 O(n^2/k)。

std::sort 是 O(n lg n)。除非 k 是 O( n/lg n )，否则添加更多线程将跟不上。

即使您确实有成堆的线程。大多数巨线程系统上的 NUMA 意味着你的内存将是一个严重的痛苦。线程不会在每个循环中访问相同的内存，实际上会不断地来回传递数据。

与简单的 std::sort 相比，可能可以加快您的工作速度的一个示例是将数据分成 K 个部分，std::sort K 个片段中的每一个，然后对这些片段进行并行合并。

int data_count = 100000;
auto get_block_edge = [data_count](int i, int n) {
  return data_count * n / i;
};
int blocks = 0;
#pragma omp parallel
{
  blocks = omp_get_num_threads();
  int block = omp_get_thread_num();
  int start = get_block_edge( block, blocks );
  int finish = get_block_edge( block+1, blocks );
  std::sort( std::begin(vec_)+start, std::begin(vec_)+finish );
}

现在我们有一堆排序好的 block 。您只需要合并它们。

for (int merge_step = 1; merge_step < blocks; merge_step *= 2 )
{
  #pragma omp parallel for
  for (int i = 0; i < (blocks/2/merge_step); ++i) {
    int start = get_block_edge(i*2*merge_step, blocks);
    int mid = get_block_edge(i*2*merge_step+merge_step, blocks);
    int finish = get_block_edge(i*2*merge_step+2*merge_step, blocks);
    finish = std::min(finish, data_count);
    auto b = std::begin(vec_);
    std::inplace_merge( b+start, b+mid, b+finish );
  }
}

我认为这应该是一个高度并行的合并。或者，更有可能是段错误，因为我有一个 off-by-1 错误。

现在，这仍然是 O(n) 和无限数量的线程，因为最后的合并必须是单线程的。委婉地说，绕过这个问题很棘手。