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

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

6 голосов
/ 05 апреля 2009

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

Ответы [ 3 ]

14 голосов
/ 15 апреля 2009

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

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

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

Для небольших наборов данных алгоритм сортировки действительно не имеет значения. В то время как люди потратили карьеру, заботясь о том, какой алгоритм сортировки является наилучшим для очень больших баз данных, для малых N действительно не имеет значения, используете ли вы Быструю сортировку, Сортировку кучи, Сортировку по кругу, Сортировку оболочки, Оптимизированную сортировку по пузырькам, Неоптимизированную сортировку по пузырькам и т. д. По крайней мере, это не имеет большого значения для процессора.

Графические процессоры являются 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]);
  }
}
5 голосов
/ 05 апреля 2009

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

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

2 голосов
/ 26 апреля 2009

У меня нет никаких знаний о программировании на GPU.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...