сортировка массива cuda с толчком, недостаточно памяти
Я пытаюсь отсортировать массив с помощью Thrust, но он не работает, если массив слишком большой. (У меня GTX460 1Гб памяти)
Я использую CUDA с C ++ интеграции на VS2012, вот мой код:
мой .cpp
extern "C" void thrust_sort(uint32_t *data, int n);
int main(int argc, char **argv){
int n = 2<<26;
uint32_t * v = new uint32_t[n];
srand(time(NULL));
for (int i = 0; i < n; ++i) {
v[i] = rand()%n;
}
thrust_sort(v, n);
delete [] v;
return 0;
}
мой .cu
extern "C"void thrust_sort(uint32_t *data, int n){
thrust::device_vector<uint32_t> d_data(data, data + n);
thrust::stable_sort(d_data.begin(), d_data.end());
thrust::copy(d_data.begin(), d_data.end(), data);
}
Программа перестает работать при запуске stable_sort ().
- Сколько еще памяти требуется stable_sort ()?
- Есть ли способ это исправить? (даже если это делает его немного медленнее или что-то в этом роде)
- Есть ли другой алгоритм сортировки, который не требует больше памяти, чем исходный массив?
Спасибо за вашу помощь 🙂
Решение
В лекции некоторые методы использовали его для решения проблемы сортировки данных, которые не помещаются в ОЗУ, таких как сохранение частичных значений в файлах и так далее. Итак, примеры => Сортировка действительно большого файла, Сортировка миллиона 32-разрядных целых чисел в 2 МБ ОЗУ с использованием Python
Ваша проблема менее сложна, так как ваш ввод умещается в ОЗУ, но это слишком «много» для вашего графического процессора. Вы можете решить эту проблему, используя стратегию parallel by Regular Sampling, Ты можешь видеть Вот пример этого последнего метода применяется на quicksort,
Короче говоря, вы в основном делите массив на меньшие вложенные массивы, которые можно разместить в памяти графического процессора. Затем вы сортируете каждый из под-массивов, в конце концов вы объединяете базу результатов на основе подхода регулярной выборки.
Вы можете использовать гибридный подход, сортируя некоторые подмассивы в ЦП, назначая каждый из них разному ядру (используя многопоточность), и в то же время отправляя другие подмассивы в графический процессор. Вы можете даже разделить эту работу на разные процессоры, используя интерфейс передачи сообщений, такой как MPI, Или вы можете просто отсортировать каждый под-массив один за другим в графическом процессоре и выполнить шаг окончательного слияния, используя процессор, используя или не пользуясь преимуществами многоядерности.
Другие решения
Других решений пока нет …