Как реализовать сортировку Radix на нескольких графических процессорах?

Question

Как реализовать сортировку Radix на нескольких графических процессорах - так же, как на одном графическом процессоре, т. Е. Разделить данные, затем построить гистограммы на отдельных графических процессорах, а затем использовать объединение данных обратно (например, набор карт)?

Answer 1

Этот метод будет работать, но я не думаю, что это будет самый быстрый подход. В частности, объединение гистограмм для каждых K битов (на данный момент K = 4 лучше) потребует обмена ключами между графическими процессорами 32 / K = 8 раз для сортировки 32-битных целых чисел. Поскольку пропускная способность памяти между графическими процессорами (~ 5 ГБ / с) намного ниже пропускной способности памяти на графическом процессоре (~ 150 ГБ / с), это снизит производительность.

Лучшей стратегией было бы разделение данных на несколько частей, параллельная сортировка каждой части на другом графическом процессоре, а затем объединение частей один раз в конце. Этот подход требует только одной передачи между GPU (против 8 выше), поэтому он будет значительно быстрее.

Answer 2

К сожалению, этот вопрос не задан должным образом.Это зависит от размера элемента, где элементы начинают жизнь в памяти и где вы хотите, чтобы отсортированные элементы в конечном итоге находились.

Иногда можно сжимать отсортированный список, сохраняя элементы в группах с одинаковым общим префиксом, или вы можете создавать уникальные элементы на лету, сохраняя каждый элемент в отсортированном списке с соответствующим количеством.Например, вы можете отсортировать огромный список 32-разрядных целых чисел в отдельные 64-разрядные списки 16-разрядных значений, что сократит ваши требования к памяти в два раза.

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

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

Я только начинаю понимать архитектуру графического процессора и не понимаю приведенный выше комментарий K = 4.Я еще никогда не видел архитектуру, где такой маленький К оказался бы оптимальным.

Я подозреваю, что объединение гистограмм также является неправильным подходом.Вероятно, я бы позволил элементам фрагментироваться в памяти, а не объединять гистограммы.Сложно ли управлять мезомасштабными списками разброса / сбора в матрице GPU?Я надеюсь, что нет.

Наконец, трудно понять причину, по которой вы захотите задействовать несколько графических процессоров для этой задачи.Скажем, у вашей карты 2 ГБ памяти и пропускная способность записи 60 ГБ / с (это то, что показывает моя карта среднего уровня).Для трехпроходной радикальной сортировки (11-битных гистограмм) требуется 6 ГБ полосы пропускания записи (вероятно, ваш фактор ограничения скорости) или около 100 мс для сортировки списка из 2 ГБ 32-разрядных целых чисел.Отлично, они отсортированы, что теперь?Если вам нужно отправить их куда-либо еще без какой-либо предварительной обработки или сжатия, время сортировки будет мелкой рыбой.

В любом случае, только что скомпилировал мои первые примеры программ сегодня.Там еще есть чему поучиться.Мое целевое приложение интенсивно переставляет, что тесно связано с сортировкой.Я уверен, что буду весить на эту тему снова в будущем.