时间戳

首页 > 解决方案 > 并行减少算法的时间复杂度

parallel-processing - 并行减少算法的时间复杂度

问题描述

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

平行归约技术

标签： parallel-processingcudatime-complexitygpureduction

解决方案

我想用一个例子来解释一下，考虑这个包含 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）步骤所以我们为执行这些步骤付出了代价，即 O(logN)。因此，如果我们使用单个线程以这种方式减少，我们将两个成本相加，因为它们彼此分开发生并且我们有 O(N+logN)。其中 O(N) 是执行所有操作的成本，O(logN) 是执行所有步骤的成本。现在没有办法并行化步骤的成本，因为它们必须按顺序发生。但是，我们可以使用多个线程来执行操作并将 O(N) 成本除以 O(N/P)。因此我们有

Total cost = O(N/P + logN)

推荐阅读