Многопоточная сортировка, эволюционный алгоритм

[bondkim137]

Возникла задача осуществлять сортировку огромного кол-ва элементов, причем интересует только около 10% рекордсменов, причем годятся они и в неотсортированном виде. Главная особенность - алгоритм должен быть многопоточный. Даже один раз линейно в один поток пройти по всему массиву - не устраивает. Очевидный способ - применить bitonic-sort, и взять рекордсменов. Не годится, нужно быстрее. В целом, годятся и вероятностные решения, но тут лишняя степень свободы появляется, и руками дополнительно махать придется.

Что б было легче понимать практическую ценность:
Применение: эволюционные алгоритмы
Платформа: видеокарты

[mihaild]

Про возможность реализации на GPU надо думать, но стандартный quick select можно распараллелить с небольшой хитростью для выбора очередного опорного элемента https://stanford.edu/~rezab/classes/cme ... 3_lec4.pdf.

[Legioner93]

https://nvidia.github.io/cccl/cub/api/s ... xSort.html
https://nvidia.github.io/cccl/cub/api/s ... dSort.html
https://nvidia.github.io/cccl/cub/api/s ... xSort.html
https://nvidia.github.io/cccl/cub/api/s ... eSort.html

-- Пн сен 23, 2024 00:54:48 --

bondkim137 в сообщении #1655639 писал(а):

Даже один раз линейно в один поток пройти по всему массиву - не устраивает

Ну скорость чтения всё равно будет $O(n)$, если только вы не умеете формировать этот массив на лету на той же видеокарте (и его размер не много больше vram) , тогда скорость может быть "почти" $O(1)$

-- Пн сен 23, 2024 01:09:07 --

А правда, какой размер данных (и тип числа)?

[bondkim137]

Legioner93 в сообщении #1655642 писал(а):

если только вы не умеете формировать этот массив на лету на той же видеокарте

Естественно, на ней исходные данные (и сами состояния и массив с оценками популяции) создаваться и будут, тут особо проблем нет. Тем более, когда каждое состояние рождает почти фиксированное, что-то около дюжины потомков

Legioner93 в сообщении #1655642 писал(а):

А правда, какой размер данных (и тип числа)?

На CPU сделали прототип с 10^6 популяций, хочется на 2-3 порядка его попробовать увеличить, ожидая качественного скачка =) Сортировать по метрике скалярной float-32 (можно привести к целочисленной и дискретизировать до 24 или даже 16 бит - там разброс почти равномерный).

-- 23.09.2024, 01:33 --

mihaild
С quick-sort-ом с отсечениями помучались, на CPU работало, но с GPU оно плохо параллелится на первых шагах. Merge-sort-наоборот, на последних. Плюс синхронизация итераций тоже дорогая. Как вероятностное решение, думаю попробовать разделить массив на N (~10K) одинаковых частей и параллельно отсортировать. Затем результат экспортировать в CPU в виде длинного фрагментированного индекса через DMA, а там отобрать рекордсменов (< 10%) merge-ем в один поток на быстром ядре попробовать. Но это гонять массив через шину, и нюансы с организацией массива есть, ибо весь индекс большой и кеш-промахи на чтение у CPU надо минимизировать.

[Legioner93]

bondkim137 в сообщении #1655647 писал(а):

На CPU сделали прототип с $10^6$ популяций, хочется на 2-3 порядка его попробовать увеличить, ожидая качественного скачка =)

ИМХО проверить качественный скачок на $10^{8.5}$ элементах можно с любой внешней реализацией gpu sort; упомянутый cub идёт в поставке Nvidia Toolkit -- ничего дополнительно скачивать не надо.

Но конечно, всё упирается в скорость итераций.

bondkim137 в сообщении #1655639 писал(а):

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

Содержательно по hpc задачке пока нечего прокомментировать

-- Пн сен 23, 2024 01:46:41 --

bondkim137 в сообщении #1655647 писал(а):

Сортировать по метрике скалярной float-32 (можно привести к целочисленной и дискретизировать до 24 или даже 16 бит - там разброс почти равномерный).

Не надо, оставьте float32

[bondkim137]

Legioner93 в сообщении #1655648 писал(а):

Не надо, оставьте float32

Это я на случай применения алгоритмов аля digital-sort. Но тут многопоточность, и мне нужны ссылки на конкретные состояния (относительно толстые), а не их гистограмма.

Legioner93 в сообщении #1655648 писал(а):

Но конечно, всё упирается в скорость итераций

10-100 в секунду. 1-10 минут окно рассматриваемое.
Хочется, конечно, в реальном времени, но пока не принципиально.