algorithm - 多个 CPU 的快速和合并排序

Question

两者 merge sort和 quick sort可以并行工作。每次我们将一个问题拆分为两个子问题时，我们都可以并行运行这些子问题。然而，它看起来并不理想。

假设我们有 4 个 CPU。在第一次迭代中，我们只将问题拆分为 2 个子问题，并且两个 CPU 空闲。在第 2 次迭代中，所有 CPU 都很忙，但在第 3 次迭代中，我们没有足够的 CPU。因此，我们应该针对 CPUs << log(N) 的情况调整算法。 .

是否有意义？您将如何使排序算法适应这些情况？

Answer 1

首先，最好的并行实现将高度依赖于环境。需要考虑的一些因素:

共享内存(一台 4 核计算机)与不共享(4 台单核计算机)

要排序的数据大小

比较两个元素的速度

交换/移动两个元素的速度

可用内存

每台计算机/内核是否相同，或者在速度、部件之间通信的网络延迟、缓存效果等方面是否存在差异。

容错:如果一台计算机/核心在操作过程中发生故障怎么办。

等等。

现在回到理论:

假设我有 1024 张卡片，还有 7 个人帮我整理它们。

归并排序

我迅速将堆栈分成大小相等的 8 个部分。因为我走得很快，所以它不会完全相等。实际上，因为我的 friend 们一拿到他们的部分就可以开始整理他们的部分，所以我应该给我的第一个 friend 一个比其他人大的堆栈，并在最后变小。

每个人按他们喜欢的顺序对他们的部分进行排序。 (基数排序、快速排序、归并排序等)

现在是困难的部分......合并。

在现实生活中，我可能会让前两个准备好的人组成一对并开始合并他们的套牌。也许他们可以一起工作，一个人从前面合并，另一个从后面合并。也许他们可以一边喊他们的号码一边从前面工作。

很快，其他人将完成他们的个人排序，并可以开始合并。当他们觉得方便时，我会让它们成对并继续前进，直到所有卡片都合并为止。

快速排序

这里真正的技巧是尝试并行化分区，因为其余的很容易做到。

我将首先将堆栈分成 8 部分，然后将一部分分发给每个 friend 。在执行此操作时，我将选择一张看起来可能最终位于已排序甲板中间的卡片。我叫出那个号码。

我的每个 friend 都会把他们较小的筹码分成三堆，小于被叫数，等于被叫数，大于被叫数。如果一个 friend 比其他人快，他/她可以从邻近的 friend 那里偷一些卡片。

当他们完成后，我将所有小于的收集成一堆，并将其交给 0 到 3 的 friend ，我将等于的放在一边，将较大的交给 friend 4 到 7。

0 到 3 的 friend ，将他们的筹码分成四等份，将选择一张牌进行分区，并在他们之间重复这个过程。

如此重复，直到每个 friend 都有自己的筹码。

(注意，如果分区卡没选好，与其把工作分成50-50，我可能只分配2个 friend 做小于的工作，而让其他6个做大于的工作。)

最后，我只是按照正确的顺序收集所有堆栈，以及分区卡。

结论

虽然有些方法在计算机上比在现实生活中更快，但我认为前面的方法是一个好的开始。除非您在硬件中实现排序，否则不同的计算机或内核或线程将以不同的速度执行它们的工作。 (如果是，您可能需要查看“排序网络”和/或“最佳排序网络”)。

如果您正在对数字进行排序，您将需要一个大型数据集来对其进行并行化处理。

但是，如果您通过比较相应像素红绿蓝值之间的曼哈顿距离总和来对图像进行排序。您会发现使用 k 个 cpu 将速度提高不到 k 倍并不困难。

最后，您需要对顺序版本进行计时，并在进行时进行比较，因为缓存效果、内存使用、网络成本等可能会有所不同。