Какой алгоритм параллельной сортировки имеет лучшую среднюю производительность?

Сортировка принимает O (n log n) в серийном случае. Если у нас есть O (n) процессоры, мы будем надеяться на линейное ускорение. O (log n) существуют параллельные алгоритмы, но они имеют очень высокую константу. Они также не применимы к товарному оборудованию, у которого нет нигде рядом с процессорами O (n). С p-процессорами разумные алгоритмы должны принимать время O (n/p log n).

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

Я ищу сортировку списков от 1 миллиона до 100 миллионов элементов на языке JVM, работающих на 8 - 32 ядрах.

Ответ 1

Следующая статья (загрузка в формате PDF) представляет собой сравнительное исследование алгоритмов параллельной сортировки на разных архитектурах:

Алгоритмы параллельной сортировки по различным архитектурам

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

Обновить для адреса Отметить проблему возраста:

Вот более свежие статьи, в которых говорится о чем-то более новом (с 2007 года, который, кстати, по-прежнему сравнивается с образцом):

Улучшения в сортировке образцов
AA-Sort

Край кровотечения (около 2010 года, некоторые только пару месяцев):

Параллельный шаблон сортировки
Многоядерная параллельная сортировка на основе графического процессора
гибридный процессор/графический параллельный ролик
Рандомизированный алгоритм параллельной сортировки с экспериментальным исследованием
Высоко масштабируемая параллельная сортировка
Сортировка N-элементов с использованием естественного порядка: новый подход адаптивной сортировки

Обновление за 2013 год: Вот кратковременное кровотечение около января 2013 года. (Примечание: несколько ссылок связаны с документами на Citeseer и требуют бесплатной регистрации):

Ответ 2

Я работал как с алгоритмом Parallel Quicksort, так и с алгоритмом PSRS, который по существу объединяет quicksort параллельно с объединением.

С помощью алгоритма Parallel Quicksort я продемонстрировал почти линейное ускорение с до 4 ядер (двухъядерный с гиперпотоком), что ожидается с учетом ограничений алгоритма. Чистый Parallel Quicksort опирается на общий ресурс стека, который приведет к конфликту между потоками, что уменьшит любое усиление производительности. Преимущество этого алгоритма состоит в том, что он сортирует "на месте", что уменьшает объем требуемой памяти. Вы можете рассмотреть это при сортировке элементов выше 100M, как вы заявили.

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

Если вам интересно, вы можете использовать или изучать код Java для каждого из этих алгоритмов. Вы можете найти его на github: https://github.com/broadbear/sort. Код предназначен для замены Java Collections.sort(). Если вы ищете возможность выполнять параллельную сортировку в JVM, как указано выше, код в моем репо может помочь вам. API полностью обобщен для элементов, реализующих Comparable или реализующих ваш собственный Comparator.

Могу ли я спросить, для чего вы хотите отсортировать эти элементы? Мне интересно узнать о потенциальных приложениях для моего сортировочного пакета.

Ответ 3

Взгляните на эту статью: Масштабируемый алгоритм параллельной сортировки с использованием точного разделения. Он занимается более чем 32 ядрами. Однако он подробно описывает алгоритм, который имеет сложность времени выполнения O (n/p * log (n) + p * log (n) ** 2) и применим для произвольных компараторов.

Ответ 4

Документ " Сравнение алгоритмов параллельной сортировки на разных Архитектура " может быть хорошим местом для вас.