排序网络成本和延迟

Question

根据我的阅读，我无法弄清楚成本和延迟是如何计算的。

• 成本：棍子或比较交换块的数量。
• 延迟：顺序比较交换的次数。

我已经在下方发布了示例

Answer 1

据我所知，你的回答是正确的。

Cost 是排序网络中完成的比较交换总数。我相信这里是 28.

Delay是必须按顺序完成的阶段数，即有数据依赖。在示例中，延迟为 13.

为什么我们关心差异？成本表示我们必须在串行实现中完成的工作量 然而 使用排序网络的好处是许多比较交换可以并行完成。当您的可用并行度与单个阶段中的比较交换一样多时，您可以同时计算该阶段。

在一个完美的并行系统中，算法的延迟将与延迟而不是成本相关。在一个完全串行的系统中，延迟将与成本相关，而不是延迟。