CUDA сортировка многих векторов / массивов

Question

У меня много (200 000) векторов целых чисел (около 2000 элементов в каждом векторе) в памяти графического процессора.

Я пытаюсь распараллелить алгоритм, который должен сортировать, вычислять среднее, стандартное отклонение и асимметрию длякаждый вектор.

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

Я хотел бы спроситькто-то более опытный, что является лучшим подходом для распараллеливания этого алгоритма.

Можно ли отсортировать более одного вектора одновременно?

Может, лучше не распараллеливать сортировку, а весь алгоритм как один поток?

Answer 1

200 000 векторов целых чисел ... 2000 элементов в каждом векторе ... в памяти графического процессора.

2000 целых чисел звучит так, как если бы один блок графического процессора легко справлялся.Они поместились бы в его общей памяти (или в его регистровом файле, но это было бы менее полезно по разным причинам), поэтому вам не нужно будет сортировать их в глобальной памяти.200 000 векторов = 200 000 блоков;но у вас не может быть 2000 блочных потоков - это чрезмерно

Возможно, вы сможете использовать cubs sortx , как подсказывает @talonmies, но я не слишком уверен, что это правильновещь которую нужно сделать.Возможно, вы сможете сделать это с помощью Thrust, но есть также хороший шанс, что у вас будет много служебного и сложного кода (хотя я могу ошибаться).Серьезно подумайте над адаптацией существующего (битонического) ядра сортировки или даже над написанием собственного - хотя это сложнее сделать правильно.

В любом случае, если вы пишете свое собственное ядро, вы можете написать свой «следующий шаг»после сортировки данных.

Может быть, лучше не распараллеливать сортировку, а весь алгоритм как один поток?

Это зависит от того, сколько времени ваше приложение тратит на этисортировка усилий на данный момент, относительно всего времени работы.См. Также Закон Амдала для более формального изложения вышесказанного.Сказав это - обычно стоит распараллелить сортировку, когда у вас уже есть данные в памяти GPU.