Есть ли алгоритм сортировки массива строк для графического процессора?
-
16-09-2020 - |
Вопрос
Массив для сортировки содержит около миллиона строк, причем каждая строка может иметь длину до одного миллиона символов.
Я ищу любую реализацию алгоритма сортировки для графического процессора.
У меня есть блок данных размером примерно 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