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

Question

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

创建二维比较矩阵

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]

计算行总和

O(n)

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

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

使用 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) 在理想情况下。但这确实是理想情况，它被称为完美线性加速。（有关详细信息，请参阅 here。）

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

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

Answer 2

您当然可以在计算中包括有限数量的核心，即使您不知道实际数量。它只是乘以一个常数，根据定义它不会影响 big-O。

你可以在 O(n) 时间内对 n < NUM_CORES 元素进行排序，这很棒，但是 big-O总是通过取无穷大来计算。这意味着输入大小将始终超过可用的 GPU 核心数。问题是：那你会怎么做？例如，您可以一次对 NUM_CORES 元素的块进行排序，然后对这些排序的块重复执行合并排序步骤，但这会让您回到（理论上最优的）O(n log n) 其他排序算法。

因此，虽然您的算法可能运行在小输入上比非并行算法快，但它仍然不是 O(n).

Answer 3

这不是渐近运行时复杂性的工作原理。

对于排序，通常的做法是计算比较的次数。这是您的方法存在的一个问题。您似乎计算了所需的一般周期数，并将 m 并行执行的比较计算为 O(1)。算法还是O(n^2)。运行并行化的事实与标准方法相比并没有太大改变。

此外，关于渐近运行时复杂性的要点是为 lim n->inf 的算法行为建模。考虑到这一点，您的 GPU 受到几千个内核（最好的情况）的影响这一事实根本无关紧要。它只是一个不变的因素，无论您使用什么底层模型，它都会消失。

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

Linear sort on GPU. Does parallel processing change Big-O?

sorting

algorithm

math

big-o

gpu