algorithm - GPU 上的线性排序。并行处理会改变 Big-O 吗？

Question

如果GPU真的能够并行计算代码。这个排序算法一定是正确的。

1. 创建二维比较矩阵

O(n)

values = [ 3, 1, 2 ]

                     # 3  1  2
comparisonMatrix = [ [ 0, 1, 1 ], # 3
                     [ 0, 0, 0 ], # 1
                     [ 0, 1, 0 ]] # 2

# Done on GPU
comparisonMatrix[rowIdx][columnIdx] = values[rowIdx] > values[columnIdx]

1. 计算行总和

O(n)

rowSums = [[ 1 ], # 3
           [ 0 ], # 1
           [ 2 ]] # 2

# Done on GPU
rowSums[rowIds] = comparisonMatrix[rowsIds][all]

1. 使用 rowSums 数组作为索引将初始 values 映射到 sortedArray

O(1)

sortedValues = [ 1, 2, 3 ]

# Done on GPU
sortedValues[rowIdx] = values[rowSums[rowIdx]]

总计:O(n + n + 1) = O(n)

反驳论点:

GPU 的内核数量有限，因此遍历数组的大 O 是 O(n/NUM_CORES) 而不是 O(1)。但是由于硬件不应包含在数学中，我们应该假设 NUM_CORES 为 1 或无穷大。无穷大会导致此算法正常，而假设 1 会导致 GPU 对复杂性没有数学影响。

---

注意事项:

这不是一个合理的运行算法，因为内存是 O(n^2) 它更像是一个证明。

值彼此都不同，否则这将导致两个 rowSums 相等。

虽然有一些方法可以更快地执行这些子步骤，但我坚持使用最简单的方法。

Answer 1

答案取决于您是否将处理器的数量视为复杂性分析的相关参数。如果是，那么您必须为处理器数量引入一个额外的参数，比如 p。

如果您的算法可扩展，这意味着时间复杂度与处理器数量成反比线性扩展，因此理想情况下您将得到 O(n/p) 而不是 O(n)案件。但这确实是理想情况，它被称为完美线性加速。 (有关详细信息，请参阅 here。)

但是说 O(n^2) 算法在并行机上运行 O(n) 绝对是错误的，因为假设处理器的数量随着输入的大小自动增长是不合理的。

如果您将处理器的数量视为常数，则什么都不会改变。