1

我问这个问题是为了确保一些并行计算概念的概念。

让我们举一个简单的例子：我们有一组n数字，如果我们至少有n/3并行计算机，那么从中搜索一个项目的最佳运行时间是多少？

我认为这仍然是O(n)，但不确定我是否正确。既然大哦表达式的常数部分可以抹去？

谢谢

4

2 回答 2

3

它可以是 O(1) 或 O(ln n)。

给定您的每台 n/3 台计算机 n/(n/3) 个数字；他们基本上都得到了 3 个值。它们需要单独的恒定时间来搜索它们的恒定大小集并返回结果（“0 --> not found”，如果在数组中的第 k 个位置找到 k，如果每个给定 K*(n/3) 为要开始的数组中的索引）。因此，该值在时间 O(1)中找到。

问题在于报告答案。在 n/3 台机器的响应中进行了选择，以选择一个独特的结果。通常，这需要在机器子集之间进行“重复”选择，您可以在 O(n) 时间内完成，但在并行系统中，通常使用“归约”运算符（例如 SUM 或 MAX 或 ...）来完成。这样的归约算子可以（并且通常）使用归约树来实现，它是对数的。

一些并行硬件具有非常快的减少硬件，但它仍然是对数的。奇怪的是，如果你有 n/1000 个 CPU，你仍然会得到 O(1) 的搜索时间（一个很大的常数），以及 O(ln n) 的减少时间和一个非常小的常数。如果你忽略 O 符号，它会“看起来”像常数时间。

于 2012-05-15T10:40:20.020 回答
0

这严格取决于底层并行模型。实际上，每个处理器定义一个标志Found x并且所有处理器执行并行归约的最终归约步骤可能具有不同的复杂性。特别参见 COMMON CRCW PRAM 案例。

对于消息传递设置：

  • T(n) = O(n/p + log p) 对于 p < n
  • T(n) = O(log n) 对于 p = O(n)

对于共享内存设置：

a) EREW 婴儿车

  • T(n) = O(n/p + log p) 对于 p < n
  • T(n) = O(log n) 对于 p = O(n)

b) 乘员婴儿车

并发读取无济于事：最终的缩减步骤仍然需要 O(log p) 时间

  • T(n) = O(n/p + log p) 对于 p < n
  • T(n) = O(log n) 对于 p = O(n)

c) 普通 CRCW 婴儿车

并发写入确实有帮助：最后的缩减步骤现在需要 O(1) 时间，那些带有Found x标志的处理器可以同时在共享位置写入相同的值

  • T(n) = O(n/p) 对于 p < n
  • T(n) = O(1) 对于 p = O(n)
于 2012-05-17T07:58:20.187 回答