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

如果您使用 libstdc++（g++ 的标准）作为标准库实现，您可以依赖其内置的 "Parallel Mode"。

要使用它，您需要使用-fopenmp 进行编译，并在编译过程中定义_GLIBCXX_PARALLEL。 Here 您可以找到有关用法的更多信息以及 gcc 将考虑进行并行化的算法列表。

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

Note that the _GLIBCXX_PARALLEL define may change the sizes and behavior of standard class templates such as std::search, and therefore one can only link code compiled with parallel mode and code compiled without parallel mode if no instantiation of a container is passed between the two translation units. Parallel mode functionality has distinct linkage, and cannot be confused with normal mode symbols.

也可以显式调用每个单独的并行算法。您只需要使用 -fopenmp（而不是 _GLIBCXX_PARALLEL 标志）进行编译，并根据 this subsection 中列出的函数包含 parallel/numeric 或 parallel/algorithm文档。请注意，并行算法位于 __gnu_parallel 命名空间中。

Answer 2

并行排序是 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

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

更多详细信息：

有关算法讨论，请参阅：Which parallel sorting algorithm has the best average case performance?

C++并行排序

C++ parallel sort

c

c++

sorting

parallel-processing