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

user_7466809 0
Viewed 165

If a GPU is really able to calculate code in parallel. This sorting algorithm must be correct.

  1. Create a 2D comparison matrix

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. Calculate row sums

O(n)

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

# Done on GPU
rowSums[rowIds] = comparisonMatrix[rowsIds][all]
  1. Mapping the initial values to a sortedArray using the rowSums array as an index

O(1)

sortedValues = [ 1, 2, 3 ]

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

Total: O(n + n + 1) = O(n)

Counter argument:

GPU's have a finite number of cores so the big-O of iterating over an array is O(n/NUM_CORES) instead of O(1). But since hardware should not be included in mathmatics we should either assume NUM_CORES is 1 or infinate. Being infinate would cause this algorithm to be OK, while assuming 1 would cause GPU's to have no mathmatical impact on complexity.

Notes:

This is not a reasonable algorithm to run since memory is O(n^2) it is more of a proof.

Values are all different from eachother, otherwise this would cause two rowSums to be equivalent.

Although there are ways of doing these substeps faster, I stuck with the most strait forward ones.

math big-o gpu sorting algorithm
3 Answers

The answer depends on whether you regard the number of processor's as a relevant parameter of your complexity analysis. If yes, then you have to introduce an extra parameter, say p, for the number of processors.

If your algorithm is scalable, this means that the time complexity scales inversely linearly with the number of processors, so instead of O(n) you would get O(n/p) in the ideal case. But that's really the ideal case, and it's called perfect linear speedup. (See here for more details.)

But it's definitely wrong to say that an O(n^2) algorithm would run in O(n) on a parallel machine since it's unreasonable to assume that the number of processors automatically grows with the size of the input.

If you regard the number of processors as a constant, then nothing changes.

user_6899230

You can certainly include the finite number of cores in the calculation, even if you don't know the actual number. It's just multiplying by a constant, which doesn't affect the big-O by definition.

It's great that you can sort n < NUM_CORES elements in O(n) time, but big-O is always calculated by taking the limit to infinity. This means the input size will always exceed the number of GPU cores you have available. And the question is: what do you do then? For example, you could sort chunks of NUM_CORES elements at a time, and then do repeated merge sort steps on those sorted chunks, but that brings you back to the (theoretically optimal) O(n log n) of other sorting algorithms.

So while your algorithm might possibly run faster than a non-parallel algorithm on small inputs, it's still not O(n).

user_146370

That's not how asymptotic runtime complexity works.

For sorting the usual approach is to count the number of comparisons. And that's one problem with your approach. You seem to count the general number of cycles required and count m comparisons executed in parallel as O(1). The algorithm is still O(n^2). The fact that it's running parallelized isn't changing much about that with the standard approach.

In addition the point about asymptotic runtime complexity is to model the behavior of your algorithm for lim n->inf. The fact that your GPU is compromised of a meager few thousand cores (best case) doesn't matter at all in that consideration. It's just a constant factor that disappears no matter what underlying model you use.

user_46686060
Related