Есть ли алгоритм для сортировки массива строк для GPU?
Массив к виду имеет приблизительно один миллион строк, где каждая строка может иметь длину до одного миллиона символов.
Я ищу любую реализацию сортировки алгоритма для GPU.
У меня есть блок данных с размером приблизительно 1 МБ, и я должен создать суффиксный массив. Теперь Вы видите, как возможно иметь один миллион строк в действительно небольшом объеме памяти.
1 ответ
Состояние дел в области сортировки на GPU не особенно обнадеживает.
Для сортировки 32-битных целых чисел в следующей статье от 2009 года (2 автора которой являются исследователями Nvidia) утверждается только 23% прирост для лучшей сортировки CUDA на GTX280 по сравнению с лучшей сортировкой CPU на 4-ядерном Yorkfield.
http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf
При этом использовалась радиксная сортировка на GPU и сортировка слиянием на CPU. Для построения суффиксного массива нужна сортировка на основе сравнения, поэтому вместо GPU radix sort лучшей из приведенных в статье была бы GPU merge sort, которая достигла примерно половины скорости GPU radix sort (с 1 миллионом ключей) - то есть примерно на 40% медленнее, чем CPU merge sort.
Добавление ключей переменной длины, вероятно, приведет к рассинхронизации потоков в искривлении на GPU, поэтому производительность на GPU снизится больше, чем на CPU.
В целом, если ваша цель - построить эффективную систему, я бы рекомендовал использовать для этой задачи реализацию на CPU, потому что она будет быстрее и проще в написании.
Но если ваша цель - эксперимент или просто знакомство с GPU, то вы можете найти CUDA-реализацию merge sort из статьи в CUDA SDK:
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html