Есть ли алгоритм сортировки массива строк для графического процессора?

Question

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

Я ищу любую реализацию алгоритма сортировки для графического процессора.

У меня есть блок данных размером примерно 1 МБ, и мне нужно создать массив суффиксов.Теперь вы можете увидеть, как можно хранить миллион строк в очень небольшом объеме памяти.

Answer 1

Состояние сортировки на графических процессорах не особенно обнадеживает.

Для сортировки 32-битных целых чисел в следующей статье 2009 года (с двумя авторами, исследователями из Nvidia) утверждается только 23%-ное увеличение лучшей сортировки CUDA на GTX280 по сравнению с лучшей сортировкой ЦП на 4-ядерном процессоре Yorkfield.

http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf

При этом использовалась поразрядная сортировка на графическом процессоре и сортировка слиянием на процессоре.Для создания суффиксного массива вам понадобится сортировка на основе сравнения, поэтому вместо поразрядной сортировки графического процессора лучшим из описанных в статье будет сортировка слиянием графического процессора, которая обеспечивает примерно половину скорости поразрядной сортировки графического процессора (с 1 миллионом ключей) - т.е. примерно на 40% медленнее, чем сортировка слиянием ЦП.

Добавление ключей переменной длины, скорее всего, приведет к рассинхронизации потоков в деформации на графическом процессоре, что снизит производительность графического процессора больше, чем процессора.

В целом, если ваша цель — построить эффективную систему, я бы рекомендовал вам использовать для этой задачи реализацию ЦП, потому что ее будет быстрее и проще писать.

Но если ваша цель — поэкспериментировать или просто узнать о графическом процессоре, то вы можете найти реализацию сортировки слиянием CUDA из статьи в CUDA SDK:

http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html