C++并行排序

Question

我需要对存储在结构数组中的数据块进行排序。结构体没有指针。每个块都有其计数器编号以及数组中数据块与结构块相等的位置的坐标。例如，如果我们有一个数据数组，我们可以将其分为 4 个 NxN 块，那么在结构块的索引数组中我们有 4 个结构块，每个结构块在数据数组中都有自己的编号和位置，借助它们我们可以计算使用索引块的数据数组中块的指针。排序应该使用比较器来完成，比较器比较两个块，使得两个块中最少的块应具有最少第 i 个数据。例如比较器：

for( i = 0; i < N * N; ++i )
{
    if( a[i] < b[i] ) return -1;
    if( a[i] > b[i] ) return 1;
}

其中

a

和

b

是指向数据数组块的指针，我们可以通过索引数组和数据数组开头的指针来获取这些数据数组块。 排序不应该对数据数组进行排序，而应该对索引数组进行排序。 所以问题是：我可以使用什么并行算法（除了框架、库，我需要算法或标准语言工具包，如 pthread 或 qt 库，或 c/c++ 标准库）来避免同步错误？代码或伪代码也会有帮助。

Answer 1

并行排序是 C++17 的一部分

在实现方面，从 Ubuntu 19.10 开始一切都已一致，您可以执行以下操作：

#include <execution>
#include <algorithm>

std::sort(std::execution::par_unseq, input.begin(), input.end());

并构建并运行：

sudo apt install gcc libtbb-dev
g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic -o main.out main.cpp -ltbb
./main.out

该函数调用会自动为您生成执行并行排序的线程。

更多详细信息请参见：C++17 并行算法已经实现了吗？

有关算法讨论，请参阅：哪种并行排序算法具有最佳的平均情况性能？

Answer 2

如果您使用 libstdc++（g++ 的标准）作为标准库实现，您可以依赖其内置的 “并行模式”。

要使用它，您需要使用

-fopenmp

进行编译，并在编译过程中定义

_GLIBCXX_PARALLEL

。 在这里您可以找到有关用法的更多信息以及 gcc 将考虑进行并行化的算法列表。

请注意使用网站上的以下警告：

请注意，_GLIBCXX_PARALLEL 定义可能会更改标准类模板（例如 std::search）的大小和行为，因此，如果在类模板之间没有传递容器的实例化，则只能链接使用并行模式编译的代码和不使用并行模式编译的代码。两个翻译单元。并行模式功能具有明显的联系，不能与普通模式符号混淆。

每个单独的并行算法也可以显式调用。您只需使用

-fopenmp

（而不是

_GLIBCXX_PARALLEL

标志）进行编译，并根据文档的

本小节

中列出的函数包含

parallel/numeric

或 parallel/algorithm 。请注意，并行算法位于

__gnu_parallel

命名空间中。

Answer 3

如果你的编译器不支持C++17的并行

std::sort

（或者如果您无法使用 GCC 或 Clang 链接到 TBB）

poolSTL是一些并行C++17算法的单头实现，包括排序：

#include <poolstl/poolstl.hpp>

std::sort(poolstl::par, vec.begin(), vec.end());