Samplesort - Samplesort

Samplesort это алгоритм сортировки это разделяй и властвуй алгоритм часто используется в системах параллельной обработки.^[1] Обычные алгоритмы сортировки «разделяй и властвуй» разделяют массив на подинтервалы или сегменты. Затем сегменты сортируются по отдельности, а затем объединяются. Однако, если массив распределен неравномерно, производительность этих алгоритмов сортировки может быть значительно снижена. Samplesort решает эту проблему, выбирая образец размера s от п-элементной последовательности и определение диапазона сегментов путем сортировки выборки и выбора п−1 < s элементы из результата. Эти элементы (называемые разделителями) затем делят массив на п ведра примерно одинакового размера.^[2] Сортировка образцов описана в статье У. Д. Фрейзера и А. С. Маккеллара «Сортировка образцов: выборочный подход к минимальной сортировке дерева хранения».^[3]

Алгоритм

Samplesort - это обобщение быстрая сортировка. В то время как quicksort разделяет входные данные на две части на каждом шаге на основе одного значения, называемого сводной точкой, вместо этого для выборочной сортировки требуется образец из своего ввода и соответственно делит свои данные на сегменты. Как и быстрая сортировка, он затем рекурсивно сортирует ведра.

Чтобы разработать реализацию выборочной сортировки, нужно определиться с количеством сегментов. п. Когда это сделано, фактический алгоритм работает в три этапа:^[4]

1. Образец п−1 элементы из входа ( разветвители). Отсортируйте их; каждая пара смежных разделителей затем определяет ведро.
2. Перебирайте данные, помещая каждый элемент в соответствующую корзину. (Это может означать: отправить его в процессор в мультипроцессор система.)
3. Отсортируйте каждое ведро.

Полностью отсортированный результат - это объединение сегментов.

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

Псевдокод

Следующий листинг показывает вышеупомянутый трехэтапный алгоритм в виде псевдокода и показывает, как алгоритм работает в принципе.^[5] В следующих, А это несортированные данные, k - коэффициент передискретизации, обсуждаемый позже, и п количество разветвителей.

функция sampleSort (A [1..n], k, п) // если средний размер сегмента ниже порогового значения, например, быстрая сортировка если ${\displaystyle n/k<}$ порог тогда smallSort (A) / * Шаг 1 * / select ${\displaystyle S=[S_{1},\dots ,S_{(p-1)k}]}$ случайным образом из // выборки отсортировать S // сортируем образец ${\displaystyle [s_{0},s_{1},\dots ,s_{p-1},s_{p}]\leftarrow [-\infty ,S_{k},S_{2k},\dots ,S_{(p-1)k},\infty ]}$ // выбираем разделители / * Шаг 2 * / для каждого ${\displaystyle a\in A}$        найти j такой, что ${\displaystyle s_{j-1}<a\leq s_{j}}$        место а в ведре ${\displaystyle b_{j}}$    / * Шаг 3 и объединение * / вернуть ${\displaystyle {\texttt {concatenate}}({\texttt {sampleSort}}(b_{1}),\dots ,{\texttt {sampleSort}}(b_{k}))}$

Псевдокод отличается от исходного алгоритма Фрейзера и Маккеллара.^[3] В псевдокоде выборочная сортировка вызывается рекурсивно. Фрейзер и МакКеллар только один раз вызвали выборочную сортировку и использовали быстрая сортировка во всех последующих итерациях.

Сложность

Сложность, указанная в Обозначение Big O:

Найдите разветвители.

${\displaystyle O\left({\frac {n}{p}}+\log(p)\right)}$

Отправить в ведра.

${\displaystyle O(p)}$ для чтения всех узлов

${\displaystyle O(\log(p))}$ для трансляции

${\displaystyle O\left({\frac {n}{p}}\log(p)\right)}$ для бинарного поиска по всем ключам

${\displaystyle O\left({\frac {n}{p}}\right)}$ отправить ключи от ведра

Сортировка ведер.

${\displaystyle O(c/p)}$ где ${\displaystyle c}$ это сложность основного метода последовательной сортировки^[1]

Количество сравнений, выполняемых данным алгоритмом, приближается к теоретическому оптимуму информации. ${\displaystyle \log _{2}(n!)}$ для больших входных последовательностей. В экспериментах, проведенных Фрэзером и Маккелларом, алгоритм нуждался на 15% меньше сравнений, чем быстрая сортировка.

Выборка данных

Данные могут быть отобраны разными методами. Некоторые методы включают:

1. Выберите равномерно расположенные образцы.
2. Выберите случайно выбранные образцы.

Передискретизация

В передискретизация Коэффициент определяет, во сколько раз больше элементов данных следует брать в качестве выборок перед определением разделителей. Цель состоит в том, чтобы получить хорошее представление о распределении данных. Если значения данных широко распределены, то есть не так много повторяющихся значений, тогда достаточно небольшого коэффициента выборки. В других случаях, когда в распределении много дубликатов, потребуется больший коэффициент передискретизации. В идеальном случае после шага 2 каждое ведро содержит ${\displaystyle n/p}$ элементы. В этом случае ни одна из корзин не занимает больше времени для сортировки, чем другие, потому что все корзины имеют одинаковый размер.

После вытягивания ${\displaystyle k}$ в раз больше образцов, чем необходимо, образцы сортируются. После этого разделители, используемые в качестве границ ковша, представляют собой образцы в позиции ${\displaystyle k,2k,3k,\dots ,(p-1)k}$ выборочной последовательности (вместе с ${\displaystyle -\infty }$ и ${\displaystyle \infty }$ как левая и правая границы для самого левого и самого правого сегментов соответственно). Это обеспечивает лучшую эвристику для хороших разделителей, чем просто выбор ${\displaystyle p}$ разбивается случайным образом.

Оценка размера ведра

По полученному размеру выборки можно оценить ожидаемый размер корзины и особенно вероятность того, что корзина превысит определенный размер. Следующее покажет, что для коэффициента передискретизации ${\displaystyle S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)}$ вероятность того, что в ведре не более ${\displaystyle (1+\epsilon )\cdot {\dfrac {n}{p}}}$ элементы больше, чем ${\displaystyle 1-{\dfrac {1}{n}}}$.

Чтобы показать это, пусть ${\displaystyle \langle e_{1},\dots ,e_{n}\rangle }$ быть входом в виде отсортированной последовательности. Чтобы процессор получил больше, чем ${\displaystyle (1+\epsilon )\cdot n/p}$ элементов, должна существовать подпоследовательность ввода длины ${\displaystyle (1+\epsilon )\cdot n/p}$, из которых максимум S отбираются образцы. Эти случаи составляют вероятность ${\displaystyle P_{\text{fail}}}$. Это можно представить как случайную величину:

${\displaystyle X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}}$

Для ожидаемой стоимости ${\displaystyle X_{i}}$ держит:

${\displaystyle E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}}$

Это будет использоваться для оценки ${\displaystyle P_{fail}}$:

${\displaystyle P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))}$

С использованием граница Чернова теперь это можно показать:

${\displaystyle P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n}$

Множество одинаковых ключей

В случае множества идентичных ключей алгоритм проходит через множество уровней рекурсии, где последовательности сортируются, потому что вся последовательность состоит из идентичных ключей. Этому можно противодействовать, введя ведра равенства. Элементы, равный шарнир сортирует в их соответствующее равенстве ковша, который может быть реализован только один дополнительным условным переходом. Сегменты равенства не сортируются. Это работает, поскольку ключи встречаются более чем ${\displaystyle n/k}$ времена, вероятно, станут поворотными.

Используется в параллельных системах

Пример параллельной выборки на ${\displaystyle p=3}$ процессоров и коэффициент передискретизации ${\displaystyle k=3}$.

Samplesort часто используется в параллельных системах, включая распределенные системы такие как объемная синхронная параллель машины.^[6][4][7] Из-за переменного количества сплиттеров (в отличие от только одной опоры в Быстрая сортировка ), Samplesort очень хорошо подходит и интуитивно понятен для распараллеливания и масштабирования. Кроме того, Samplesort также более эффективно кэширует, чем реализации, например, быстрая сортировка.

Распараллеливание реализуется путем разделения сортировки для каждого процессора или узла, где количество сегментов равно количеству процессоров. ${\displaystyle p}$. Samplesort эффективен в параллельных системах, поскольку каждый процессор получает примерно одинаковый размер корзины. ${\displaystyle n/p}$. Поскольку сегменты сортируются одновременно, процессоры завершат сортировку примерно в одно и то же время, поэтому процессор не будет ждать других.

На распределенные системы, разветвители выбираются, принимая ${\displaystyle k}$ элементов на каждом процессоре, сортируя полученные ${\displaystyle kp}$ элементов с распределенным алгоритмом сортировки, принимая каждый ${\displaystyle k}$-го элемента и транслируем результат на все процессоры. Это стоит ${\displaystyle T_{\text{sort}}(kp,p)}$ для сортировки ${\displaystyle kp}$ элементы на ${\displaystyle p}$ процессоры, а также ${\displaystyle T_{\text{allgather}}(p,p)}$ для распространения ${\displaystyle p}$ выбранные сплиттеры ${\displaystyle p}$ процессоры.

С полученными разделителями каждый процессор помещает свои собственные входные данные в локальные сегменты. Это требует ${\displaystyle {\mathcal {O}}(n/p\log p)}$ с участием бинарный поиск. После этого локальные корзины перераспределяются процессорам. Процессор ${\displaystyle i}$ получает местные ведра ${\displaystyle b_{i}}$ всех других процессоров и сортирует их локально. Распределение занимает ${\displaystyle T_{\text{all-to-all}}(N,p)}$ время, где ${\displaystyle N}$ размер самого большого ведра. Локальная сортировка занимает ${\displaystyle T_{\text{localsort}}(N)}$.

Эксперименты, проведенные в начале 1990-х годов на Соединительная машина суперкомпьютеры показали, что выборочная сортировка особенно хороша при сортировке больших наборов данных на этих машинах, поскольку она не требует больших затрат на межпроцессорное взаимодействие.^[8] В последние дни GPU, алгоритм может быть менее эффективным, чем его альтернативы.^{[9][нужна цитата ]}

Эффективная реализация выборки

Анимированный пример Super Scalar Samplesort. На каждом этапе сравниваемые числа помечаются синим цветом, а числа, которые читаются или записываются иным образом, отмечаются красным.

Как описано выше, алгоритм выборочной сортировки разбивает элементы в соответствии с выбранными разделителями. В статье «Суперскалярная выборочная сортировка» предлагается эффективная стратегия реализации.^[5] В предлагаемой в статье реализации используются два массива размером ${\displaystyle n}$ (исходный массив, содержащий входные данные и временный) для эффективной реализации. Следовательно, эта версия реализации не является алгоритмом на месте.

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

Определение ковшей

В алгоритме сортировки на основе сравнения операция сравнения является наиболее важной частью производительности. В Samplesort это соответствует определению сегмента для каждого элемента. Это требует ${\displaystyle \log k}$ время для каждого элемента.

Суперскалярная выборочная сортировка использует сбалансированное дерево поиска, которое неявно хранится в массиве. т. Корень хранится в 0, левый преемник ${\displaystyle t_{i}}$ хранится в ${\displaystyle t_{2i}}$ и правопреемник хранится в ${\displaystyle t_{2i+1}}$. Учитывая дерево поиска т, алгоритм вычисляет номер ведра j элемента ${\displaystyle a_{i}}$ следующим образом (при условии ${\displaystyle a_{i}>t_{j}}$ оценивается в 1, если это правда и 0 в противном случае):

${\displaystyle j\leftarrow 1}$${\displaystyle {\texttt {repeat}}\log _{2}p\ {\texttt {times}}}$    ${\displaystyle j\leftarrow 2j+(a>t_{j})}$${\displaystyle j\leftarrow j-p+1}$

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

Разбиение

Для эффективного разделения элементов алгоритму необходимо заранее знать размеры сегментов. Чтобы разбить элементы последовательности и поместить их в массив, нам нужно заранее знать размер сегментов. Наивный алгоритм мог подсчитать количество элементов в каждой корзине. Затем элементы можно было вставить в другой массив в нужном месте. Используя это, нужно дважды определить корзину для каждого элемента (один раз для подсчета количества элементов в корзине и один раз для их вставки).

Чтобы избежать этого дублирования сравнений, суперскалярная выборочная сортировка использует дополнительный массив ${\displaystyle o}$ (называемый оракулом), который присваивает каждому индексу элементов ведру. Сначала алгоритм определяет содержимое ${\displaystyle o}$ путем определения ковша для каждого элемента и размеров ковша, а затем помещения элементов в ковш, определяемый ${\displaystyle o}$. Массив ${\displaystyle o}$ также требует затрат на место для хранения, но, поскольку это необходимо только для хранения ${\displaystyle n\cdot \log k}$ бит, эти затраты невелики по сравнению с размером входного массива.

Сортировка по месту

Ключевым недостатком эффективной реализации Samplesort, показанной выше, является то, что она не находится на месте и требует второго временного массива того же размера, что и входная последовательность во время сортировки. Эффективные реализации, например, быстрая сортировка на месте и, следовательно, более компактная. Однако выборочную сортировку также можно реализовать на месте.^[10]

Алгоритм на месте разделен на четыре этапа:

1. Отбор проб что эквивалентно выборке в вышеупомянутой эффективной реализации.
2. Местная классификация на каждом процессоре, который группирует входные данные в блоки, так что все элементы в каждом блоке принадлежат одному и тому же сегменту, но сегменты не обязательно непрерывны в памяти.
3. Блочная перестановка размещает блоки в глобально правильном порядке.
4. Очистка перемещает некоторые элементы по краям ведер.

Одним из очевидных недостатков этого алгоритма является то, что он считывает и записывает каждый элемент дважды: один раз на этапе классификации и один раз на этапе перестановки блоков. Тем не менее, алгоритм работает до трех раз быстрее, чем другие современные конкуренты на месте, и до 1,5 раз быстрее, чем другие современные последовательные конкуренты. Поскольку отбор проб уже обсуждался выше, три последующих этапа будут более подробно описаны ниже.

Местная классификация

На первом этапе входной массив разбивается на ${\displaystyle p}$ полосы блоков одинакового размера, по одной на каждый процессор. Каждый процессор дополнительно выделяет ${\displaystyle k}$ буферы равного размера блокам, по одному для каждого сегмента. После этого каждый процессор сканирует свою полосу и перемещает элементы в буфер соответствующей корзины. Если буфер заполнен, он записывается в полосу процессора, начиная с передней части. Всегда существует как минимум один размер буфера пустой памяти, потому что для записи в буфер (т. Е. Буфер заполнен) необходимо было просканировать по крайней мере полный размер буфера, состоящий из элементов, превышающих количество записанных обратно. Таким образом, каждый полный блок содержит элементы одной и той же корзины. Во время сканирования отслеживается размер каждой корзины.

Блокировка перестановки

Во-первых, выполняется операция суммирования префикса, которая вычисляет границы сегментов. Однако, поскольку на этом этапе перемещаются только полные блоки, границы округляются до кратного размера блока и выделяется один буфер переполнения. Перед началом перестановки блоков, возможно, придется переместить некоторые пустые блоки в конец его корзины. После этого указатель записи ${\displaystyle w_{i}}$ устанавливается на начало ковша ${\displaystyle b_{i}}$ подмассив для каждой корзины и указатель чтения ${\displaystyle r_{i}}$ устанавливается на последний непустой блок в корзине ${\displaystyle b_{i}}$ подмассив для каждого сегмента.

Чтобы ограничить количество рабочих конфликтов, каждому процессору назначается отдельная основная корзина ${\displaystyle b_{prim}}$ и два буфера подкачки, каждый из которых может содержать блок. На каждом шаге, если оба буфера подкачки пусты, процессор уменьшает указатель чтения. ${\displaystyle r_{prim}}$ своего основного сегмента и считывает блок в ${\displaystyle r_{prim-1}}$ и помещает его в один из своих буферов подкачки. После определения целевого сегмента ${\displaystyle b_{dest}}$ блока, классифицируя первый элемент блока, он увеличивает указатель записи ${\displaystyle w_{dest}}$, читает блок в ${\displaystyle w_{dest-1}}$ в другой буфер подкачки и записывает блок в целевую корзину. Если ${\displaystyle w_{dest}>r_{dest}}$, буферы подкачки снова пусты. В противном случае блок, оставшийся в буферах подкачки, должен быть вставлен в целевую корзину.

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

Очистка

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

Смотрите также

• Flashsort
• Быстрая сортировка

использованная литература

1. «Сортировка образцов с использованием стандартной адаптивной параллельной библиотеки шаблонов» (PDF) (Технический отчет). Техасский университет A&M.
2. Грама, Анант; Карипис, Джордж; Кумар, Випин (2003). «9.5 Сортировка по ведрам и пробам». Введение в параллельные вычисления (2-е изд.). ISBN  0-201-64865-2.
3. Frazer, W.D .; Маккеллар, А.С. (1970-07-01). "Samplesort: выборочный подход к минимальной сортировке дерева хранения". Журнал ACM. 17 (3): 496–507. Дои:10.1145/321592.321600.
4. Хилл, Джонатан М. Д.; Макколл, Билл; Стефанеску, Дэн С.; Goudreau, Mark W .; Ланг, Кевин; Рао, Сатиш Б .; Суэль, Торстен; Цантилас, Танасис; Бисселинг, Роб Х. (1998). «BSPlib: Библиотека программирования BSP». Параллельные вычисления. 24 (14): 1947–1980. CiteSeerX  10.1.1.48.1862. Дои:10.1016 / S0167-8191 (98) 00093-3.
5. Сандерс, Питер; Винкель, Себастьян (14 сентября 2004). Суперскалярная сортировка образцов. Алгоритмы - ESA 2004. Конспект лекций по информатике. 3221. С. 784–796. CiteSeerX  10.1.1.68.9881. Дои:10.1007/978-3-540-30140-0_69. ISBN  978-3-540-23025-0.
6. Gerbessiotis, Alexandros V .; Валиант, Лесли Г. (1992). «Прямые синхронно-массовые параллельные алгоритмы». J. Параллельные и распределенные вычисления. 22: 22–251. CiteSeerX  10.1.1.51.9332.
7. Хайтауэр, Уильям Л .; Prins, Jan F .; Рейф, Джон Х. (1992). Реализации рандомизированной сортировки на больших параллельных машинах (PDF). ACM Symp. по параллельным алгоритмам и архитектурам.
8. Блеллох, Гай Э.; Лейзерсон, Чарльз Э.; Мэггс, Брюс М .; Плэкстон, К. Грегори; Смит, Стивен Дж .; Загха, Марко (1991). Сравнение алгоритмов сортировки для машины соединений CM-2. ACM Symp. по параллельным алгоритмам и архитектурам. CiteSeerX  10.1.1.131.1835.
9. Сатиш, Надатур; Харрис, Марк; Гарланд, Майкл. Разработка эффективных алгоритмов сортировки для многоядерных графических процессоров. Proc. Международный симпозиум по параллельной и распределенной обработке IEEE. CiteSeerX  10.1.1.190.9846.
10. Акстманн, Майкл; Витт, Саша; Феризович, Даниэль; Сандерс, Питер (2017). «Параллельная суперскалярная сортировка образцов на месте (IPSSSSo)». 25-й ежегодный европейский симпозиум по алгоритмам (ESA 2017). 87 (Международные слушания Лейбница по информатике (LIPIcs)): 9: 1–9: 14. Дои:10.4230 / LIPIcs.ESA.2017.9.

внешние ссылки

Примеры сортировки Фрейзера и МакКеллара и производные:

• Оригинальная статья Фрейзера и Маккеллара
• DOI.org
• DOI.org

Адаптирован для использования на параллельных компьютерах:

• http://citeseer.ist.psu.edu/91922.html
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214