Альтернативы экономии памяти CUDA Thrust sort_by_key?

В cuda / thrust: Попытка sort_by_key 2,8 ГБ данных в 6 ГБ ОЗУ графического процессора вызывает ошибку bad_alloc, я читал, что sort_by_key потребляет большую часть памяти для рассматриваемого здесь тестового примера.

Есть ли альтернатива, которая может делать именно то, что делает sort_by_key, даже если она немного медленнее, но которая может сортировать большие наборы данных?


c++ cuda thrust
person Walter white    schedule 30.06.2014    source источник
comment
Я не очень разбираюсь в алгоритмах сортировки на GPU. Я помню, что в главе 46 GPU Gems 2 обсуждаются различные алгоритмы сортировки. Возможно, это даст вам некоторую полезную информацию об альтернативных, менее эффективных, но экономящих память подходах.   -  person Vitality    schedule 30.06.2014
comment
Как вы выяснили, thust позволяет использовать около 40% доступной памяти графического процессора для сортировки данных. Я рассмотрел некоторые другие подходы, такие как CUB, но не думаю, что вы будете может превышать 50% с любыми другими известными мне подходами. Вы можете отсортировать по кускам на устройстве, затем передать каждый фрагмент на хост и выполнить thrust::merge_by_key там, что может быть менее затратно, чем выполнение полной сортировки на хосте, но время передачи устройства хоста ‹-›, вероятно, сделало бы такой подход тоже неинтересно.   -  person Robert Crovella    schedule 01.07.2014
comment
Есть ли у вас какая-либо априорная информация, которую вы могли бы раскрыть в своей процедуре сортировки?   -  person Vitality    schedule 01.07.2014
comment
Большое спасибо :)! Джек и Роберт.   -  person Walter white    schedule 01.07.2014
comment
Джек, я не знаю, извините, получу ли я ваш вопрос. Я просто пытаюсь отсортировать свой вектор с помощью этой процедуры: thrust :: sort_by_key (Keys.begin (), Keys.end (), tempVector.begin ()); Он вылетал в случае, когда я пытаюсь вычислить 1,8 ГБ в узле Titan на 6,0 ГБ. Ключи и tempVector имеют одинаковый размер. Я могу попробовать проверить подход, который вы опубликовали, или CUB от Роберта, и проверить, могу ли я отсортировать немного больше данных.   -  person Walter white    schedule 01.07.2014
comment
Я пытаюсь сказать, что алгоритмы сортировки библиотек должны быть общими, а именно должны работать для произвольных массивов. Напротив, если у вас есть какая-либо информация о векторе, который вам нужно отсортировать (например, он частично отсортирован), вы можете попытаться найти компромисс между общностью и эффективностью: вы можете настроить алгоритм, который работает только для определенного класс массивов, но может сэкономить временное пространство для выделения памяти.   -  person Vitality    schedule 01.07.2014

Ответы (1)


arrow_upward
3
arrow_downward

Я немного искал, и я думаю, что следующий вариант ответа на ваш вопрос.

Цитата Н. Белла и Дж. Хоберока, «Thrust: ориентированная на производительность библиотека для CUDA», в GPU Computing Gems Jade Edition:

Thrust статически выбирает оптимизированный алгоритм Radix Sort для сортировки примитивных типов (char, int, float и double) с помощью стандартных операторов сравнения less и greater. Для всех других типов (например, определяемых пользователем типов данных) и операторов сравнения Thrust использует общий алгоритм сортировки слиянием. Поскольку сортировка примитивов с помощью Radix Sort значительно быстрее, чем сортировка слиянием, эта статическая оптимизация имеет большое значение.

Теперь для сортировки слиянием требуется O(N) памяти, см. Требования к пространству для сортировка слиянием.

Кроме того, Radix Sort по-прежнему требует O(N) памяти, см. Сравнение Bucket Sort и RADIX Сортировать.

Какой из двух потребляет больше памяти, не определено и зависит от входной последовательности, которую нужно отсортировать, а также от параметров настройки алгоритма, см. Комментарии к одному из ответов на Почему быстрая сортировка более популярна, чем Radix-сортировка?.

Напротив, Быстрая сортировка требует O(logN) памяти, если выполняется на месте, в противном случае требуется O(N). Для реализации CUDA алгоритма быстрой сортировки вы можете посмотреть Как Tesla K20 ускоряет быструю сортировку.

Для других алгоритмов сортировки на месте (стратегию на месте стоит изучить, поскольку она экономит память по сравнению с не на месте аналог), посмотрите Bitonic Sort, см. Быстрая сортировка на месте с помощью CUDA на основе битонной сортировки.

person Vitality    schedule 01.07.2014