C ++并行排序 [英] C++ parallel sort

问题描述

我需要对存储在结构数组中的数据块进行排序.结构没有指针.每个块都有其计数器编号和数组中等于结构块的数据块所在位置的坐标.例如，如果我们有一个可以划分为4个NxN块的数据数组，则在结构块的索引数组中有4个结构块，并且每个块在数据数组中都有自己的编号和位置，我们可以借助它们来计算使用索引块的数据数组中块的指针.应该使用比较器完成排序，比较器以这样的方式比较两个块，即两个块中的最少一个具有第i个数据.例如比较器:

I need to sort data blocks which are stored in an array of structures. Structures have no pointers. Each block has its counter number and coordinates of the place in an array where the data block equal to the structure block is. For example if we have a data array which we can divide in 4 blocks of NxN, we have 4 structure blocks in index array of structure blocks and each of them has its own number and position in data array with the help of which we can compute the pointer of the block in data array using index block. Sorting should be done with the comparer that compares two blocks in such way that the least of two blocks shold have least i-th number of data. For example comparer:

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 ++标准库)?代码或伪代码也将有所帮助.

where a and b are pointers to the blocks of data array which we can get due to index array and pointer of the start of data array. Sorting shouldn't sort data array but index array. So the question is: what parallel algorithm can I use (except frameworks, libraries, I need exactly algorithms or standard language kits, like pthread or qt libs, or c/c++ standard libs) to avoid synchronization errors? The code or pseudocode would be helpful too.

推荐答案

如果您使用libstdc ++(g ++的标准)作为标准库实现，则可以依赖其内置的 .

If you are using libstdc++ (g++'s standard) as your standard library implementation, you can rely on its built in "Parallel Mode".

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

To use it, you need to compile with -fopenmp and have _GLIBCXX_PARALLEL defined during compilation. Here you can find more information on the usage as well as a list of the algorithms that gcc will consider for parallization.

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

Be aware of the following warning from the usage site:

请注意，_GLIBCXX_PARALLEL定义可能会更改标准类模板(例如std :: search)的大小和行为，因此，如果未传递容器的实例化，则只能链接使用并行模式编译的代码和不使用并行模式编译的代码.在两个翻译单元之间.并行模式功能具有独特的链接，不能与常规模式符号混淆.

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标志)进行编译，并根据

Each individual parallel algorithm can also be called explicitly. You only need to compile with -fopenmp (and not the _GLIBCXX_PARALLEL flag), and include the parallel/numeric or parallel/algorithm depending on the function listed in this subsection of the documentation. Be aware that the parallel algorithms are in the __gnu_parallel namespace.

这篇关于C ++并行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！