Быстрая сортировка в GLSL?

Question

Я рассматриваю перенос большого фрагмента обработки на GPU с использованием шейдера GLSL. Одна из проблем, с которыми я столкнулась, заключается в том, что на одном из этапов алгоритм должен поддерживать список элементов, сортировать их и брать несколько самых больших (какой номер зависит от данных). На CPU это просто делается с использованием вектора STL и qsort(), но в GLSL у меня нет таких возможностей. Есть ли способ справиться с этим недостатком?

Answer 1

Раскрытие информации: Я действительно не знаю GLSL. Я занимаюсь программированием GPGPU с помощью AMD Stream SDK, который имеет разные языки программирования.

От вас прокомментировать ответ Бьорна, я заключаю, что вы не заинтересованы в использовании GPU для сортировки огромной базы данных - как создать телефонную книгу реверса или любой другие, но вместо этого, у вас есть небольшой набор данных и каждые фрагмент имеет собственный набор данных для сортировки. Больше похоже на попытку срединной фильтрации пикселей?

Я могу только сказать, в общем:

Для небольших наборов данных алгоритм сортировки не имеет значения. В то время как люди потратили на себя карьеру, заботясь о том, какой алгоритм наилучшего сортирования для очень больших баз данных, для маленьких N действительно не имеет значения, используете ли вы Quick sort, Heap Sort, Radix Sort, Shell Sort, Optimized Bubble Sort, Unoptimized Bubble sort, и т. д. По крайней мере, это не имеет большого значения для процессора.

Графические процессоры являются SIMD-устройствами, поэтому им нравится, чтобы каждое ядро ​​выполняло те же операции на этапе блокировки. Расчеты дешевы, но ветви дороги и зависящие от данных отрасли, где каждое ядро ​​разветвляется по-другому, очень, очень, очень дорого.

Так что, если каждое ядро ​​имеет собственный небольшой набор данных для сортировки, а # данных для сортировки зависит от данных, и для каждого ядра может быть другим числом, вам, вероятно, лучше выбрать максимальный размер (если вы может), заполняя массивы бесконечностью или некоторым большим числом, и каждое ядро ​​выполняет тот же самый вид, который был бы неоптимизированным нераспространенным пузырьковым типом, например:

Псевдокод (поскольку я не знаю GLSL) , вроде 9 баллов

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; } 
for (size_t n = 8; n ; --n) { 
    for (size_t i = 0; i < n; ++i) { 
    TwoSort (A[i], A[i+1]); 
    } 
} 

Answer 2

Вы видели эту статью? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

Я не был уверен, что вы ищете алгоритм быстрого сортировки или алгоритм быстрой сортировки. Алгоритм в статье использует сортировку слияния ...

Answer 3

Я не получил каких-либо знаний о программировании GPU.

Я бы воспользовался использованием heapsort, а не quicksort, потому что вы сказали, что вам нужно всего лишь взглянуть на самые высокие значения. Куча может быть построена в O(n) времени, но получение верхнего значения - log(n). Поэтому, если вам нужно количество значений, которое вам нужно, значительно меньше, чем общее количество элементов, вы могли бы получить некоторую производительность.