Быстрая параллельная сортировка, чтобы упорядочить целые числа без знака?

Question

Я выполняю задачу сортировки довольно большого массива беззнаковых, 64-битных, случайных сгенерированных целых чисел (более 5E7 элементов). Можете ли вы указать мне алгоритм параллельной сортировки, который может демонстрировать почти линейное ускорение, по крайней мере, в случае случайных данных?

Я работаю с Java, если это имеет какое-либо значение для быстрой сортировки.

Изменить: Обратите внимание, что этот вопрос в первую очередь касается параллельных сортов, способных достичь почти линейного ускорения. (Это означает, что когда количество исполняющих ядер увеличивается с P до 2P , время, затрачиваемое на параллельную сортировку, падает до 55-50 процентов вычислений, выполненных на P ядер.)

Answer 1

Битоническая сортировка - алгоритм, предназначенный для параллельных машин.Вот последовательная версия Java и параллельная версия C ++ , чтобы помочь вам начать работу.

Answer 2

Скажем, у вас есть несколько компьютеров (5 на кластере Amazon, верно?), И вы хотите сортировку по возрастанию. Разделите ваш массив на более мелкие куски, чтобы он подходил для каждой машины. Предполагая, что у вас есть n блоков / массивов. У каждой машины быстрая сортировка своего куска. Эта сортировка будет параллельно (более или менее в зависимости от размера куска, скорости машины и т. д.)

Когда все будет сделано, пусть машины объединят куски;

Вы можете сделать это двумя способами:

• 2 машины одновременно (вы строите дерево слияния). Слияние произойдет, опять же, параллельно. Проблема в том, что массив будет увеличиваться из-за слияния, и вам придется кэшировать на диск, поэтому при повторном слиянии компьютер читает с диска. Так что некоторые штрафы здесь.
• Вы можете делать n машин одновременно. Имейте одну координирующую машину, которая берет мин от всех других машин. Таким образом, машина-координатор создает весь отсортированный массив, беря наименьшее число из каждого другого отсортированного массива.

Answer 3

Из статьи Википедии о Быстрая сортировка ,

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

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

Answer 4

Быстрая сортировка и сортировка слиянием довольно легко распараллелить. В Oracle есть целочисленная сортировка на основе разветвления / объединения здесь , которую вы, вероятно, могли бы использовать (если не как есть, то, по крайней мере, как вдохновение).

Answer 5

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