Сортировать элементы, идентифицированные идентификатором 2 на графическом процессоре ⇐ C++

[Anonymous]

Я новичок в программировании на графическом процессоре и наткнулся на реализацию алгоритма (лучше всего, чтобы вы помогли мне с вычислительным шейдером, а не с cuda). Вот описание проблемы:
Ввод: N неупорядоченных элементов в массиве с его ID с 0 на L-1, а его идентификатор корзины с 0 на M-1 (вся информация известна заранее).
Вывод: M корзины, каждый элемент внутри корзины должен быть отсортировано по его ID в порядке возрастания (обратите внимание, что некоторые идентификаторы могут отсутствовать).
Итак, я придумал решение:Решение:

• сканировать элементы, накапливать количество элементов для каждого сегмента, вывод в массив A (используйте атомарный счетчик ?)
• префикс-сумма над A, чтобы получить начальная позиция элементов, вывод в массив B
• кодирование идентификатора и идентификатора сегмента в новый ключ (беззнаковое целое число, 32 бита), помещение всех элементов в непрерывный массив C, используя собранную информацию
• сортировать C

Однако в моем случае L и M могут сильно различаться (оба могут превышать 10 тысяч).
Мой вопрос:< /p>

• Как отсортировать N элементов?
• Достаточно ли быстр атомный счетчик, чтобы меня можно было успокоить использовать его на шагах 1 и 2?

Подробнее здесь: https://stackoverflow.com/questions/791 ... -id-on-gpu