Блог

Если графический процессор действительно способен вычислять код параллельно. Этот алгоритм сортировки должен быть правильным.

1. Создайте 2D-матрицу сравнения

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]
 

2. Вычисление сумм строк

O (n)

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

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

3. Сопоставление начального values значения с a sortedArray с использованием rowSums массива в качестве индекса

O (1)

 sortedValues = [ 1, 2, 3 ]

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

Итого: O (n n 1) = O (n)

Встречный аргумент:

Графические процессоры имеют конечное число ядер, поэтому значение big-O при итерации по массиву равно O (n / NUM_CORES) вместо O (1). Но поскольку аппаратное обеспечение не должно быть включено в математику, мы должны либо предположить, что NUM_CORES равно 1, либо infinate. Быть бесконечным приведет к тому, что этот алгоритм будет в порядке, при условии, что 1 приведет к тому, что GPU не окажет математического влияния на сложность.

Примечания:

Это не разумный алгоритм для запуска, поскольку память равна O (n ^ 2), это скорее доказательство.

Все значения отличаются друг от друга, в противном случае это привело бы к эквивалентности двух строк.

Хотя есть способы выполнить эти подэтапы быстрее, я придерживался самых простых.

Ответ зависит от того, считаете ли вы количество процессоров релевантным параметром вашего анализа сложности. Если да, то вам нужно ввести дополнительный параметр, скажем, p, для количества процессоров.

Если ваш алгоритм масштабируемый, это означает, что временная сложность обратно пропорционально линейно зависит от количества процессоров, поэтому вместо O (n) вы получите O (n / p) в идеальном случае. Но это действительно идеальный случай, и это называется идеальным линейным ускорением. (Подробнее см. Здесь.)

Но определенно неправильно говорить, что алгоритм O (n ^ 2) будет выполняться в O (n) на параллельной машине, поскольку неразумно предполагать, что количество процессоров автоматически увеличивается с размером входных данных.

Если вы рассматриваете количество процессоров как константу, то ничего не меняется.

Вы, конечно, можете включить конечное число ядер в вычисление, даже если вы не знаете фактического числа. Это просто умножение на константу, которая по определению не влияет на big-O.

Здорово, что вы можете сортировать n < NUM_CORES элементов за O (n) время, но big-O всегда вычисляется, принимая предел до бесконечности. Это означает, что размер входных данных всегда будет превышать количество доступных вам ядер GPU. И вопрос в том, что вы делаете тогда? Например, вы можете сортировать фрагменты NUM_CORES элементов за раз, а затем выполнять повторные шаги сортировки слиянием для этих отсортированных фрагментов, но это возвращает вас к (теоретически оптимальному) O (n log n) других алгоритмов сортировки.

Итак, хотя ваш алгоритм может работать быстрее, чем непараллельный алгоритм на небольших входных данных, он все равно не O (n) .

Это не так, как работает асимптотическая сложность времени выполнения.

Для сортировки обычным подходом является подсчет количества сравнений. И это одна из проблем вашего подхода. Кажется, вы подсчитываете общее количество требуемых циклов и подсчитываете m сравнения, выполняемые параллельно, как O(1) . Алгоритм по-прежнему O(n^2) . Тот факт, что он работает параллельно, не сильно меняет это при стандартном подходе.

Кроме того, суть асимптотической сложности времени выполнения заключается в моделировании поведения вашего алгоритма для lim n->inf . Тот факт, что ваш графический процессор скомпрометирован скудными несколькими тысячами ядер (в лучшем случае), не имеет никакого значения при этом рассмотрении. Это просто постоянный фактор, который исчезает независимо от того, какую базовую модель вы используете.