并行归约算法的时间复杂度

Question

目前正在研究GPU架构及其概念。在并行 Reduction 技术中，按照 NVIDIA 指南第 29 张幻灯片显示的时间复杂度如何达到 O(N/P + log N)？我知道对于 N 个线程，它将是 O(log N)。如果我们有 P 个并行线程可用，那么时间复杂度应该是 O((N/P)*log P)。正确的？我哪里错了？

Parallel Reduction Techniques

Answer 1

我不熟悉 cuda，但通常你会进行并行归约

首先在每个处理器上进行局部归约，这需要 O(N/P)，然后
计算 P 个局部结果的缩减，这需要 O(log P) 步骤。

因此你得到 O(N/P + log P).

Answer 2

我想用一个例子来解释这个，考虑这个有 N=8 个元素的数组

1  2  3  4  5  6  7  8

并行缩减将在以下步骤中发生

1  2  3  4  5  6  7  8
  3    7      11   15
    10          26
          36

如果你计算归约操作的次数，我们在第一步、第二步和第三步分别有 4,2 和 1。所以我们的操作总数是 4+2+1=7=N-1，我们在 O(N) 中进行了所有的减少，我们还有 log(8)=3（这是以 2 为底数的 log）步骤所以我们为执行这些步骤付出了代价，即 O(logN)。因此，如果我们使用单个线程以这种方式减少，我们将两个成本相加，因为它们彼此分开发生，我们有 O(N+logN)。其中 O(N) 是执行所有操作的成本，O(logN) 是执行所有步骤的成本。现在没有办法并行化步骤的成本，因为它们必须按顺序发生。然而，我们可以使用多个线程来执行操作并将 O(N) 成本分摊到 O(N/P)。因此我们有

Total cost = O(N/P + logN)

并行归约算法的时间复杂度

Time complexity of Parallel Reduction Algorithm

parallel-processing

cuda

gpu

time-complexity

reduction