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;
}

where a和b是指向数据数组的指针,由于索引数组和数据数组开始的指针,我们可以得到它们.排序不应该排序数据数组而是排序索引数组.所以问题是:我可以使用哪种并行算法(除了框架,库,我需要完全算法或标准语言工具包,如pthread或qt libs,或c/c ++标准库)以避免同步错误？代码或伪代码也会有所帮助.

Answer 1

如果您使用libstdc ++(g ++的标准)作为标准库实现,则可以依赖其内置的"并行模式".

要使用它,您需要编译-fopenmp并_GLIBCXX_PARALLEL在编译期间定义.在这里,您可以找到有关使用情况的更多信息,以及gcc将考虑进行并行化的算法列表.

请注意使用网站发出以下警告:

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

也可以明确地调用每个单独的并行算法.您只需要使用-fopenmp(而不是_GLIBCXX_PARALLEL标志)进行编译,并包含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

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

更多详细信息，请访问：C++17 并行算法是否已经实现？

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