如何使用 Intel C++ 编译器和 OpenMP 4.5 库实现并行“稳定”三路快速排序
如何使用 Intel C++ 编译器和 OpenMP 4.5 库，在上一篇文章已讨论的并行代码基础上，实现并行的“稳定”三路快速排序的现代代码。
注意：可选地，您可以使用预装了并行排序可执行文件的 CentOS 64 位虚拟机环境来评估本文讨论的快速并行排序程序。 （登录：root 密码：intel）
引言
在上一篇文章中，我讨论了实现高效的并行三路快速排序，用于对具有整数或浮点数等基本数据类型的元素数组进行排序。尽管这种排序方式很少使用。通常，我们对具有更复杂数据类型的元素数组进行排序，以便数组中的每个元素都是用户定义抽象数据类型 (ADT) 的对象。反过来，一个对象是多个值的集合，每个值都具有特定的基本数据类型。
显然，我们需要进行更复杂的排序来重新排序上述对象数组。为此，我们通常使用“稳定”排序算法，该算法允许我们按多个值对对象数组进行排序。大多数现有的“稳定”排序算法由于计算复杂度通常很高而效率不高，而“快速排序”的现有变体本质上根本不是“稳定”的。
在本文中，我将介绍一种能够实现高效“稳定”三路快速排序的方法。具体来说，我将为一个重新排序存储在更复杂数据结构中的数据制定一个算法，以执行并行稳定排序。正在讨论的稳定排序的整个过程非常类似于在 SQL 中执行 GROUP BY 操作，其中数据按一个以上变量的值进行排序。
同样，我将讨论如何使用 Intel C++ 编译器和 OpenMP 4.5 库来实现基于上一篇文章已讨论的并行代码的并行“稳定”三路快速排序的现代代码。
作为实际排序的示例，我将实现一个样本程序，该程序对数组进行排序，数组的每个元素都是一个存储两个变量（“键”或“值”）的对象。此外，通过使用此程序，我将评估所实现的稳定排序的整体性能，并将其与传统的 qsort( ... ) 或 std::sort( ... ) 函数的性能进行比较。
为什么高效的三路快速排序不是“稳定”的……
快速排序算法和堆排序一样，被称为“不稳定”，因为在按第一个变量的值对对象数组进行排序时，它不会保持对象按第二个变量的值的相对顺序。在大多数情况下，按键排序的对象会根据枢轴的值进行交换，具有相同键的对象的特定顺序会被简单地忽略。
具体来说，仅使用 internal::parallel_sort( ... ) 或常规的 std::sort( ... ) 函数执行“稳定”排序是不可能的，例如
std::sort(v.begin(), v.end(), [&](const ITEM& iteml, const ITEM& item2) {
return (iteml.key == item2.key) && (iteml.value < item2.value);
});
std::parallel_sort(v.begin(), v.end(), [&](const ITEM& iteml, const ITEM& item2) {
return (iteml.key == item2.key) && (iteml.value < item2.value);
});
执行不当或不一致排序的基本结果是由快速排序和堆排序算法本身的性质引起的。此外，快速排序的已知实现未能提供执行更复杂、更“稳定”的排序的能力。
这实际上就是为什么我将介绍并制定一个算法，该算法可以通过数组分区和一些简单排序，使用相同的 internal::parallel_sort( ... ) 或 std::sort( ... ) 函数来实现稳定排序。
“稳定”排序算法
稳定排序的整个过程非常直观简单，可以表述为以下算法
- 按特定键对数组中的所有对象进行排序；
- 将数组划分为具有相同键的 k 个子集；
- 独立地按其值对每个对象子集进行排序；
首先，我们选择一个对象的变量，该变量称为“键”，并使用 std::sort( ... ) 或 intemal::parallel_sort( ... ) 函数对整个对象数组按键进行排序，就像我们对具有基本数据类型的数组排序时所做的那样。
由于数组中的所有对象都已按键重新排序，因此我们需要将整个排序数组划分为 k 个分区，每个分区包含具有相同键的对象。要划分数组，将应用以下算法
- 令
arr[O .. N]- 一个按“键”排序的对象数组，N - 数组中的对象数； - 初始化 First 和 Last 变量为第一个对象的索引（First = Last = O）；
- 初始化变量
i为第一个对象的索引（i = O）； - 对于数组中的每个 i 个对象（
i < (N - 1 )），执行以下操作将第 i 个对象
arr[i].key的键与数组中后一个对象arr[i+1].key的键进行比较（在要分区的数组中）- 如果这些对象的键不相等（
arr[i].key != arr[i + 1].key），
则将索引(i + 1)赋值给变量Last (Last = i + 1 )； - 按其值对
arr[First..Last]范围内的所有对象进行排序； - 将变量
Last的值赋给变量First (First = Last)；
- 如果这些对象的键不相等（
以下算法的主要目标是找到每个分区中第一个和最后一个对象的索引，然后按其值对 arr[First..Last] 范围内的所有对象进行排序。该算法主要基于顺序查找这些分区的思想，使得当前分区最后一个对象的索引正好匹配下一个要排序的分区第一个对象的索引。它维护两个索引，分别代表第一个和最后一个对象。最初，这些变量被赋值为数组中第一个对象的索引。然后，它遍历每个对象，执行简单的线性搜索以查找两个键不相等的相邻对象。如果找到这样的对象，它将索引 (i + 1) 赋给变量 Last，然后对当前分区中索引属于 First 到 Last 区间的所有对象按其值进行排序。之后，索引变量 First 的值将更新为变量 Last 的特定值，并且分区将继续查找下一个要排序的分区中最后一个对象的索引，依此类推。
下面列出的 C++11 代码实现了正在讨论的分区算法
template<class BidirIt, class _CompKey, class _CompVals>
void sequential_stable_sort(BidirIt _First, BidirIt _Last,
_CompKey comp_key, _CompVals comp_vals)
{
std::sort(_First, _Last, comp_key);
BidirIt _First_p = _First, _Last_p = _First_p;
for (BidirIt _FwdIt = _First + 1; _FwdIt != _Last; _FwdIt++)
{
if ((comp_key(*_FwdIt, *(_FwdIt - 1)) || (comp_key(*(_FwdIt - 1), *_FwdIt))))
{
_Last_p = _FwdIt;
if (_First_p < _Last_p)
{
std::sort(_First_p, _Last_p, comp_vals);
_First_p = _Last_p;
}
}
}
std::sort(_First_p, _Last, comp_vals);
}
以下方法结合了上面介绍的稳定排序算法的步骤 2 和 3。顺序分区的计算复杂度始终为 O(n)，但通过使用 Intel C++ 编译器和 OpenMP 4.5 库进行一些并行优化，可以显著提高其性能。
并行运行“稳定”快速排序
在实现稳定三路快速排序的并行版本代码中，我们首先按选定的键重新排序对象数组。这通常通过生成一个单独的 OpenMP 任务来完成，使用 #pragma omp task untied mergeable {} 指令，该指令调用 intemal::parallel_sort( ... ) 函数
#pragma omp task mergeable untied
internal::parallel_sort(_First, _Last, comp_key);
在对象数组成功按键排序后，它会并行启动分区。与顺序分区算法变体不同，它不再维护相应的 First 和 Last 索引，因为这通常会导致数据流依赖问题，因此无法并行执行分区过程。相反，它执行一个简单的线性搜索来查找数组中所有键不相等的相邻对象的索引。它执行一个单一的循环，在每次迭代中，它都会验证当前 i 个对象和相邻的 (i+1) 个对象的键是否不相等。如果是，它只是将索引 (i + 1) 添加到向量 std::vector<std::size_t> pv
#pragma omp parallel for
for (BidirIt _FwdIt = _First + 1; _FwdIt != _Last; _FwdIt++)
if ((comp_key(*_FwdIt, *(_FwdIt - 1)) || (comp_key(*(_FwdIt - 1), *_FwdIt))))
{
omp_set_lock(&lock);
pv.push_back(std::distance(_First, _FwdIt));
omp_unset_lock(&lock);
}
此算法的并行修改通常需要额外的空间，例如 O(k)，其中 k 是要排序的分区数。由于此算法变体不产生数据流依赖，因此以下循环的每次迭代都将通过其自己的线程并行执行，使用 #pragma omp parallel for 指令构造。然后，使用 internal::parallel_sort( ... ) 函数对索引向量 pv 进行排序，以保留每个分区索引的顺序
internal::parallel_sort(pv.begin(), pv.end(),
[&](const std::size_t item1, const std::size_t item2) { return item1 < item2; });
在这种情况下，使用 std::vector<std::size_t> 显然不是线程安全的。这就是为什么我们需要使用 OpenMP 库中实现的 omp_set_lock( ... ) 和 omp_unset_lock( ... ) 函数来进行适当的同步。当两个相邻对象满足上述条件时，它会设置一个锁，确保将特定索引添加到向量 pv 的操作仅由一个线程一次完成。将索引添加到向量 pv 后，它将释放该锁，并继续执行循环的下一次并行迭代。此技术类似于使用关键区域来同步并行代码执行
omp_set_lock(&lock);
pv.push_back(std::distance(_First, _FwdIt));
omp_unset_lock(&lock);
最后，为了按其值对整个对象数组进行排序，它执行另一个并行循环，在该循环的每次迭代中，它会从向量 pv 中获取一对索引。第一个索引完全对应于当前分区中第一个对象的索引，而第二个索引对应于最后一个对象的索引。之后，它使用相同的 internal::parallel_sort( ... ) 函数独立地对索引属于从第一个到最后一个范围内的数组中的所有对象进行排序
#pragma omp parallel for
for (auto _FwdIt = pv.begin(); _FwdIt != pv.end() - 1; _FwdIt++)
internal::parallel_sort(_First + *_FwdIt, _First + *(_FwdIt + 1), comp_vals);
如下面代码所示，调用 parallel_stable_sort( ... ) 函数
// Perform the parallel sorting
internal::parallel_stable_sort(array_copy.begin(), array_copy.end(),
[&](const gen::ITEM& item1, const gen::ITEM& item2) { return item1.key < item2.key; },
[&](const gen::ITEM& item1, const gen::ITEM& item2) { return item1.value < item2.value; });
与传统的 std::sort 或 internal::parallel_sort 不同，以下函数接受两个 lambda 函数作为其参数。第一个 lambda 函数用于按键排序对象数组，第二个 lambda 函数分别用于按每个对象的 a 值进行排序。
评估并行稳定排序
在交付了现代并行代码后，我运行了一系列严格的评估测试。具体来说，我使用 Intel V-Tune Amplifier XE 2019 工具检查了代码的性能效率
从上图可以看出，现代代码在具有对称多核 Intel CPU 的机器上运行时几乎完美地扩展，提供了并行“稳定”排序本身的效率。此外，并行运行的数组分区过程实际上并不影响排序的整体性能，与使用上一篇文章中讨论的传统 std::sort( ... ) 或 internal::parallel_sort( ... ) 相比，其性能仍然快 2-6 倍。
关注点
本文介绍的快速高效并行排序，如果我们将本文讨论的 OpenMP 性能库与其他多线程库和包结合使用，将可以更快。例如，在这种情况下，我们还可以使用 Intel® Threading Building Blocks 来提高本文介绍的代码的性能。为此，我们可以开发一个基于 tbb:parallel_for 模板函数的代码包装器，类似于 tbb::parallel_sort 的实现，然后使用本文讨论的执行并行快速排序的代码，而不是使用 std::sort C++ 模板函数，以提高排序过程的性能。
历史
- 2017 年 11 月 19 日 - 本文最终修订版发布