Высокопроизводительная сортировка (radix) на CUDA

GPGPU*

Реальное доказательство того, что GPU может осуществлять сортировку данных (алгоритм radix) в несколько раз быстрее, чем CPU.

Дуэйн Мэррилл (Duane Merrill) и Эндрю Гримшоу (Andrew Grimshaw) с кафедры вычислительной техники Виргинского университета в Шарлотсвилле опубликовали под свободной лицензией свой метод сортировки SRTS Radix Sort, в котором GTX 480 показывает скорость сортировки более 1 млрд 32-битных ключей в секунду: примерно вчетверо быстрее, чем на процессоре Core i7.

Метод подходит для любых CUDA-устройств. Текущая версия поддерживает сортировку любых встроенных числовых типов данных C/C++ (например, signed char, float, unsigned long long), а также автоматическую оптимизацию в случаях, если все ключи имеют одинаковую длину (ускорение сортировки в пять раз).

+18

30 августа 2010, 13:18

alizar 2280,1 G+

комментарии (22)

liq 30 августа 2010, 13:39 #

И не слова про то что это может быть бесполезным. Во первых такие скорости достигаются на объемах более 2М чисел. Вот лично я на практике больше 64К никогда не сортировал. Может ктонибудь из присудствующих сортирует 2М чисел? Было бы интересно услышать. Во вторых перед сортировкой эти данные еще отправить на GPU надо.

PS Реализация неплохая конечно, уделывает radixSort из сэмплов в раза 1.5 на моем GTX470.

b00taNik 30 августа 2010, 14:18 # ↑

Задачи анализа статистики часто требуют сортировки огромных массивов информации — и для такого класса задач это просто мана небесная :)

dimag0g 31 августа 2010, 02:21 # ↑

А можно пример?

b00taNik 31 августа 2010, 15:43 # ↑

конечно можно.

У Вас в кеш-хранилище информация о 10 миллионах пользователей (подключений, ставок, etc) (несортированная, т.к. это мгновенный слепок активности), которую нужно перекинуть в анализатор статистики.

Известно, что анализатор статистики в несколько раз быстрее работает с сортированными данными (у него даже ключик специальный есть, значительно улучшающий скорость работы за счет использования других алгоритмов)

Надеяться на сортировщик анализатора нет смысла — так как анализатор довольно слабая машина, да и вообще — его задача хранить эту статистику, а не заниматься ее упорядочиванием.

Поэтому втыкаем в кешер одну видяшку и отдаем ей на откуп статистику.

Конечно, когда у Вас 1 кешер и один анализатор, разница между 1мс и 0.3мс незаметна, но когда стоит уже 10кешеров на один анализатор, такой буст уже играет роль.

Где это используется?
Скажу по секрету всей хабре — в крупных букмекерских конторах, например.

dimag0g 31 августа 2010, 16:00 # ↑

Спасибо. Меня как раз интересовал пример статистического алгоритма, который требует отсортированных данных на входе.

b00taNik 31 августа 2010, 18:22 # ↑

Таких алгоритмов навалом — бинарный поиск, системы оценки погрешностей результатов, задачи приближенного моделирования.

Тут ниже обсуждение, что это не для серверов — так это еще как для серверов (хотя, если быть до конца точным, для мощных вычислительных кластеров)

dimag0g 31 августа 2010, 18:44 # ↑

А зачем в статистике бинарный поиск? Система оценки погрешностей — можно ссылку на такую систему, использующую отсортированные данные?

b00taNik 9 января 2011, 17:42 # ↑

Извините, что долго не отвечал, только сейчас поднял старые комментарии.

Бинарный поиск нужен скорее не для самой статистики, а для быстрого раскладывания по диапазонам.

А на систему оценки погрешностей ссылку дать не могу, т.к. это штука сугубо индивидуальная для каждой компании.

Nakilon 30 августа 2010, 14:21 #

Я конечно не спорю, что это информативный эксперимент, в очередной раз показывающий применимость и эффективность графических ускорителей.
Однако, вы только представьте, сколько начинающих «программистов» теперь, почитав эту новость, укрепились в уверенности, что сортировка есть божественная операция, и будут теперь ее тыкать везде, где есть CUDA, опираясь на то, как она быстра. Вспомните, сколько раз на вопрос «найти максимальный элемент в массиве» вы слышали «отсортируем по убыванию и возьмем первый...»
Страшно представить, какой это толчок ламерству…

Scratch 30 августа 2010, 14:33 # ↑

ламеры это даже не прикрутят к своим поделкам )

pil0t 30 августа 2010, 15:37 #

кроме, в большей части академических, достижений CUDA хочется более реальных вещей:
например утилита для прикручивания CUDA сортировки(может и не только сортировки) к MSSQL/Oracle/MySQL/Postgres

A_HREF 30 августа 2010, 19:21 # ↑

Ага, и еще видяхи поставить на сервер :)

FTDeBUGgeR 30 августа 2010, 19:41 # ↑

один в один, такие же комментарии были на ЛОРе =)

beeruser 30 августа 2010, 22:33 # ↑

CUDA — это 99% рендер и HPC
Сервера — это немного «не в кассу»

Grox 31 августа 2010, 03:28 # ↑

А как же Tesla?

beeruser 31 августа 2010, 09:02 # ↑

Tesla это железка, а CUDA это язык программирования

Grox 31 августа 2010, 11:00 # ↑

Tesla это серверное железо для работы с CUDA. Почему сервера то «не в кассу»?
Да и с чего CUDA рендер? Посмотрите на gpgpu.org.

beeruser 31 августа 2010, 18:06 # ↑

>> Почему сервера то «не в кассу»
Веб-сервера. Упомянутые выше MSSQL/Oracle/MySQL/Postgres и т.д.
CUDA ориентирована на плотные параллельные вычисления — рендер/HPC а не на pointer-chasing и 1-поточный код.
Любите микроскопом гвозди забивать? Вперёд

>>Посмотрите на gpgpu.org
Ну и посмотрите на своей странице список тегов.
Никакого веба и «серверных» задач
Математика/hpc/рендер

beeruser 31 августа 2010, 18:12 # ↑

* Веб-сервера и базы данных

noonesshadow 30 августа 2010, 19:29 #

Каким будет первый движок баз данных с поддержкой CUDA?

stas_agarkov 30 августа 2010, 22:21 # ↑

давайте напишем его сами

noonesshadow 30 августа 2010, 22:47 # ↑

Не спс. Это не мое направление

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.