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

Question

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

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

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 ) 添加更多线程不会跟上。

即使你确实有一堆线程。大多数 mega-thread 系统上的 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 );
}

现在我们有一堆排序的块。你只需要合并它们。

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)，因为最后一次合并必须是 single-threaded。委婉地说，绕过这个问题很棘手。

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

std::sort is way more fast than custom OpenMP parallel sorting algorithm

c++

parallel-processing

openmp