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 )，否则添加更多线程将无法跟上。

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

与简单的 std::sort 相比，可能加快工作速度的一个示例是将数据拆分为 K 块，

std::sort

K 块中的每一个，然后对这些块进行并行合并。

int data_count = 100000;
auto get_block_edge = [data_count](int i, int n) {
  return data_count * i / n;
};
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 );
  }
}

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

现在，对于无限数量的线程来说，这仍然是 O(n)，因为最后一次合并必须是单线程的。温和地说，解决这个问题很棘手。