Что такое хороший алгоритм сортировки на CUDA?

Question

У меня есть массив struct, и мне нужно отсортировать этот массив в соответствии со свойством struct (N). Объект выглядит так:

 struct OBJ
 { 
   int N; //sort array of OBJ with respect to N
   OB *c; //OB is another struct
 } 

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

Какой самый простой и «хороший» способ сортировки этого массива? Мне не нужен сложный алгоритм, который требует много времени для реализации (так как количество элементов в массиве мало), мне просто нужен простой алгоритм.

Примечание. Я читал некоторые статьи об алгоритмах сортировки с использованием графических процессоров, но прирост скорости в этих документах проявляется только при очень большом размере массива. Поэтому я не пытался реализовать их алгоритмы, потому что размер моего массива невелик. Мне нужен только простой способ параллельной сортировки массива. Спасибо.

Answer 1

Что означает «большой» и «маленький»?

Под «большим» я предполагаю, что вы имеете в виду что-то из> 1M элементов, в то время как маленький - достаточно маленький, чтобы фактически поместиться в разделяемой памяти (вероятно, <1Kэлементы).Если мое понимание «маленького» совпадает с вашим, я бы попробовал следующее: </p>

• Использовать только один блок для сортировки массива (это может быть частью более крупного ядра CUDA)
• Битоновая сортировка - одна из хороших задач, которую можно использовать для параллельного алгоритма.

Некоторые страницы по битонической сортировке:

• Битоновая сортировка (хорошее объяснение, апплет для визуализации и исходный код Java, который не занимает слишком много места)
• Википедия (слишком краткое объяснение на мой вкус, но больше исходных кодов - немного абстрактного языка иJava)
• Примеры кода NVIDIA (Пример источника в CUDA. Я думаю, что он немного сфокусирован на убийстве банковских конфликтов. Я полагаю, что более простой код может действительно работать быстрее)

Однажды я также реализовал пузырьковую сортировку (смеется!) Для одной деформации для сортировки массивов из 32 элементов.Благодаря своей простоте на самом деле это не так плохо.Хорошо настроенная битовая сортировка будет работать быстрее.

Answer 2

Почему именно ты направляешься в CUDA?Я имею в виду, пахнет, как будто твоя проблема не из тех, в которых CUDA очень хорош.Вы просто хотите отсортировать массив из 512 элементов и позволить некоторым указателям ссылаться на другое местоположение.В этом нет ничего особенного, для этого используйте простой последовательный алгоритм, например, Quicksort, Heapsort или Mergesort.

Кроме того, подумайте о накладных расходах, необходимых для копирования данных из вашей кучи / стека на ваше устройство CUDA.Использование CUDA имеет смысл, когда вычисления достаточно интенсивны, так что COMPUTING_TIME_ON_CUDA+COPY_DATA_FROM_HEAP_TO_CUDA_DEVICE+COPY_DATA_FROM_CUDA_DEVICE_TO_HEAP < COMPUTING_TIME_ON_HOST_CPU.

Кроме того, CUDA невероятно мощен в математических вычислениях с большими векторами и матрицами и довольно простыми типами данных (числами), потому что этоОдна из проблем, которая часто возникает на GPU: вычисление графики.

Answer 3

Используйте сортировочные вызовы, доступные в библиотеке CUDPP или Thrust .

Если вы используете cudppSort , обратите внимание, что он работает только с целыми числами или числами с плавающей запятой. Чтобы отсортировать массив структур, вы можете сначала отсортировать ключи вместе с индексным массивом. Позже вы можете использовать отсортированный индексный массив, чтобы переместить структуры в их окончательное отсортированное местоположение. Я описал, как сделать это для алгоритма сжатия cudppCompact в блоге здесь . Шаги аналогичны для сортировки массива структур с использованием cudppSort.

Answer 4

Да, я бы полностью согласился, что накладные расходы на сортировку небольших массивов (<5k элементов) убивают возможное ускорение, которого вы достигнете с помощью «точно настроенного» алгоритма параллельной сортировки, реализованного в CUDA.Я бы предпочел сортировку на основе процессора для такого небольшого размера ... </p>