0

我已经实现了快速排序的顺序版本和并行版本。

我已经在我的实现中验证了快速排序的最坏情况的加速：源数组已经排序，在我的情况下，枢轴始终是数组的第一个元素。

因此，分区生成两个集合，一个包含小于枢轴的元素，另一个包含高于枢轴的元素，即 n - 1 个元素，其中 n 是作为快速排序函数的参数传递的数组元素的数量。递归深度的大小为 N -1，其中 N 是作为快速排序函数的参数传递的原始数组的元素数。

Obs：集合实际上由两个变量表示，其中包含数组部分的初始位置和最终位置，对应于元素小于枢轴和元素高于枢轴。整个划分都在原地进行，这意味着没有在进程中创建新数组。并行的顺序的区别在于并行版本中创建了多个数组，其中元素在它们之间平均分配（按顺序情况排序）。对于并行情况下的元素连接，使用了算法合并。

获得的加速比理论值高，这意味着与顺序版本相比，使用两个线程实现的加速比超过 2 倍（更准确地说是 3 倍），而使用 4 个线程的加速比是 10 倍。

我运行线程的计算机是运行 Ubuntu Linux 10.04、64 位的 4 核机器（Phenom II X4），如果我没记错的话。编译器是 gcc 4.4，除了包含用于并行实现的库 pthread 之外，没有为编译器传递任何标志；

那么，有人知道实现超线性加速的原因吗？有人可以指点一下吗？

4

2 回答 2

2

最好使用一些性能分析器来更详细地研究这一点，但我的第一个猜测是，这种超线性加速是由于如果添加线程可以获得更多缓存空间这一事实。这样，将从缓存中读取更多数据。由于内存传输的成本非常高，因此可以轻松提高性能。

您是否使用阿姆达尔定律来评估您的最大加速比？

希望这可以帮助。

于 2012-06-25T03:35:10.127 回答
2

如果你看到两个线程对 1 个线程的 3 倍加速，以及 4 个线程对 1 个线程的 10 倍加速，那么事情就很可疑了。

Amdahl 定律指出加速比为 1/(1-P+P/S)，其中 P 是算法的并行部分，S 是并行部分的加速因子。假设四个核心的 S=4（可能的最佳结果），我们发现 P=2.5，这是不可能的（它必须在 0 和 1 之间，包括 0 和 1）。

换句话说，如果您可以使用 4 个内核获得 10 倍的改进，那么您可以简单地使用一个内核来模拟四个内核，仍然可以获得 2.5 倍的改进（或大约）。

换句话说，四个核心在一秒内执行的操作比一个核心在十秒内执行的操作更少。所以并行版本实际上执行的操作更少，如果是这种情况，串行版本没有理由不能也执行更少的操作。

可能的结论：

  • 您的顺序版本可能有问题。也许它优化得很差。

  • 您的并行版本可能有问题。他们可能是不正确的。

  • 测量可能执行不正确。这很常见。

不可能的结论：

  • 该算法超线性缩放。
于 2012-06-25T03:41:24.517 回答