V Международная студенческая научная конференция Студенческий научный форум - 2013

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

Постановка вопроса. Ставится задача построения алгоритма устойчивой параллельной сортировки на основе бинарного дерева с использованием параллельного слияния по матрицам сравнений. Цель такой постановки – совместить свойства и назначение схем поиска на основе дерева и на основе слияния для получения единого параллельного алгоритма сортировки. Требуется, помимо построения, представить способ адресации по ссылкам к входным элементам, а также дать оценку временной сложности полученной сортировки.

При сравнении равных элементов за меньший принимается элемент с меньшим номером во входном массиве. Количество элементов последовательности, если не оговорено иное, предполагается целой степенью по основанию два.

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

(1)

длиной .

Для последовательности (1) строится дерево выбора согласно способу из [1, с. 269]. Получим следующее:

Уровни дерева пронумерованы сверху вниз. Их номера соответствуют последовательным показателям степени двойки. В результате построения дерева выбора, видим, что на 1-м уровне находятся два сравниваемых элемента ( и), они являются начальными для двух упорядоченных в результате построения массивов, которые в дальнейшем будут подлежать слиянию: и , соответственно.

Данные массивы получаются следующим образом. По ходу последовательного спуска от начального (в данном случае от 1-го) уровня, а затем от текущего уровня на уровень с большим номером, выбирается тот элемент, за счет которого был совершен подъем на уровень с меньшим номером при построении дерева, то есть, в массив, упорядочиваемый для последующего слияния, добавляется больший из двух сравниваемых элементов.

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

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

У всех элементов последовательности Aиз (1) фиксируются входные индексы, они проставлены на рис. 2 под элементами массива в нижнем ряду (4-й уровень). На первом шаге («шаг 1» слева на рис. 2) сравниваются между собой элементы всех подряд 8 пар 4-го уровня. Первая пара – и , индексы , соответственно. В результате сравнения на уровень выше поднимается элемент вместе со своим индексом и к этому индексу присоединяется слева направо индекс того элемента, за счет которого произошел подъем –. Таким образом, на втором снизу, т.е. на 3-м уровне элемент будет хранить список индексов . Аналогично для других пар, и, далее, как на первом шаге, так и на последующих, происходит подъем на уровень вверх элемента с сопоставленным ему новым списком индексов. В частности, на втором шаге («шаг 2» слева на рис. 2) после сравнения, на уровень вверх поднимаются элементы с новыми списками, которые состоят из собственного индекса поднявшегося элемента и списка большего элемента в паре сравнения (элемента за чей счет произошел подъем вверх). Таким образом, переходя на следующий снизу вверх уровень, элемент присоединяет только свой собственный индекс, подставляя его в начало списка индексов большего при сравнении с ним элемента.

Замечание 2. Список индексов при подъеме элемента вверх обрывается, если элемент переходит второй раз подряд на следующий снизу вверх уровень. Этот элемент в дальнейшем сохраняет лишь собственный индекс (присоединяя его при необходимости к новому списку в процессе дальнейших сравнений), а сформированный при предыдущем его подъеме – до двух подряд шагов – список индексов сохраняется только за тем элементом, за счет которого был совершен первый из двух подряд шагов снизу вверх, причем в этот список не войдет индекс поднявшегося элемента.

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

Тем самым одновременно с формированием бинарного дерева окажутся сформированными все массивы для последующего слияния.

Таким образом, на 4-м снизу уровне («1 уровень» на рис. 2 справа) имеем два элемента со списками индексов двух упорядоченных по возрастанию массивов. Элемент образует упорядоченный числовой массив элементов , ему соответствует список индексов . Аналогично, элемент образует упорядоченный числовой массив элементов, соответствующий массиву список индексов .

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

Данные непосредственно выше два упорядоченные массива покрывают 8 из 16 элементов последовательности A. На 2-м уровне имеются не задействованные элементы, которые также хранят списки индексов, по которым можно восстановить упорядоченные массивы с началом в данных элементах. Таким образом, на 2-м уровне имеем два упорядоченных массива и , которые покрывают еще 4 элемента последовательности A. В результате оказалось покрыто 12 из 16 элементов.

На нижнем уровне остались незадействованные элементы в массивах, которые образуют 4 массива, содержащих по одному элементу. Таким образом, покрыты еще 4 элемента последовательности. В результате покрыто 16 из 16 элементов, то есть все элементы последовательности A вошли в упорядоченные массивы.

По изложенному построению упорядоченных для слияния массивов списки индексов в каждой ветви дерева формируются независимо друг от друга.

Описание алгоритма параллельного слияния. Выполняется проход снизу вверх по дереву выбора, на каждом последовательном шаге прохода производится попарное параллельное слияние одновременно нескольких пар массивов. При этом слияние выполняется по матрицам сравнений. Для пары сливаемых массивов это делается следующим образом [4]:

Матрица сравнений (МС) определяется следующим образом [4].

Пусть по отношению  требуется упорядочить массив целых чисел

. (2)

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

, (3)

сливаются в единый отрезок длины m + n

, (4)

то каждый из отрезков (3) называется сливаемым, отрезок (4) – слитым. Для отрезков (3) МС определяется [4] как таблица вида

	a0	a1	. . .	am	am+1
b0	00	01	. . .	0m	0(m+1)
b1	10	11	. . .	1m	1(m+1)
. (5) . .	. . .	. . .	. . .	. . .	. . .
	n0	n1	. . .	nm	n(m+1)
bn+1	(n+1)0	(n+1)1	. . .	(n+1) m	(n+1) (m+1)

В (5) сливаемые отрезки дополнены ограничителями , и для n+1  i  0  j  m+1

(6)

В дальнейшем под МС понимается собственно матрица (n+2)(m+2) элементов (6); в примерах сливаемые отрезки над МС и слева от нее приводятся для наглядности. Значения из (6) могут заменяться символами "+", "0", "-" и, соответственно, называться "плюсами", "нулями" и "минусами". Строки , столбцы в (5) задают сравнения с  . В этих строках и столбцах по определению полагается

₀₀ = 0 = (n_+1)(m+1), (7)

а для остальных элементов –

_0j = _{i (m+1)} = 1, _i0 = (n_+1)j = -1. (8)

Набор всех элементов (7), (8) при n+1  i  0  j  m+1 определяется как окаймление в МС, строки и столбцы с этими элементами называются окаймляющими. МС без окаймления будет называться основной (МС_о). Окаймление не зависит от сливаемых отрезков и состоит из постоянных элементов (7), (8). При m = n в (3) – (8) МС и МС_о являются квадратными матрицами. Они обозначаются МС_к и МС_кo, а с указанием числа строк и столбцов – МС_к((n+2)(n+2)), МС_кo(nn).

Пример 2. Для отрезков

,

MC_к(66) и MC_кo (44) имеют вид

	1	6	8	10
2	-	+	+	+	1
7	-	-	+	+	2
14	-	-	-	-	3
15	-	-	-	-	4
	1	2	3	4

	-	1	6	8	10	
-	0	+	+	+	+	+	0
2	-	-	+	+	+	+	1
7	-	-	-	+	+	+	2
14	-	-	-	-	-	+	3
15	-	-	-	-	-	+	4
+	-	-	-	-	-	0	5
	0	1	2	3	4	5

Вводится понятие смены знака (СМЗН). В строке МС за СМЗН принимается пара соседних элементов, левый из которых "минус", правый – "ноль" или "плюс". В столбце за СМЗН принимается пара соседних элементов, верхний из которых "ноль" или "плюс", нижний – "минус". Данные определения СМЗН с естественными оговорками переносятся на случай МС_кo. Каждая строка и столбец МС, исключая окаймляющие, необходимо содержат СМЗН. Если, в тех же случаях, имеется СМЗН, то с единственностью, так как функция (6) нестрого монотонна по номерам элементов строки и столбца. Ввиду той же монотонности справа от СМЗН в строке и сверху в столбце – только "нули" или "плюсы", справа и сверху от "плюсов" – "плюсы", слева и снизу от СМЗН – "минусы".

Адрес вставки элемента в выходной массив задается соотношениями

(9)

где – произвольно взятые индексы при ограничениях

.

Следующий пример иллюстрирует обход неотрицательных элементов.

П

с₁₊₀=b₁=3, c₁₊₁=a₁=3,

с ₂₊₁=b₂=4,

с₃₊₁=b₃=4, c₃₊₂=a₂=4,

c₄₊₂=a₃=4,

с₄₊₃=b₄=8, c₄₊₄=a₄=8,

c₄₊₅=a₅=9,

с₄₊₆=a₆=9, c₅₊₆=b₅=11.

ример 3. ; ;

 

Стрелка указывает на анализируемый элемент, аддитивная индексация иллюстрирует изменение индексов.

Длительность слияния по МС (5) обозначается , R – количество (процессорных элементов) ПЭ. В оценках , как и в оценках T(R), учитывается только количество последовательных сравнений. В частности,

, (10)

где  – время бинарного сравнения на одном ПЭ. Очевидно,

, (11)

где  из (10).

Слияние по МС на процессорах выполняется за время :

, (12)

где .

Сортировка слиянием организуется по классической схеме [1]: слияние пар соседних элементов из (2), затем слияние пар по два, по четыре и т.д. – до завершения сортировки на последнем шаге слияния.

Параллельное слияние на дереве. Время параллельного слияния, аналогично, параллельной сортировки будет обозначаться , где – количество процессоров.

На 1-м шаге (4 уровень на рис. 1) в слиянии участвуют 8 массивов , при этом, минимальная длина сливаемых массивов равна 1, максимальная – . В итоге, на 1-м шаге имеем 4 слитых (упорядоченных) массива, максимальная длина которых не превышает .

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

На входе 3-го шага имеем упорядоченных массивов длиной не более . После слияния получим один массив, длина которого будет меньше либо равна .

В рассматриваемом случае на последнем 3-м шаге мы получили массив, в которой вошли все элементы последовательности. Длина этого массива , полученная оценка завышена: .

По индукции на шаге количество сливаемых массивов – . Длина сливаемых массивов будет не превосходить , а длина затем слитого массива на этом шаге не превзойдет числа .

Каждое слияние пары массивов будет выполняться максимально параллельно по матрице сравнений [4], синхронно и взаимно независимо по всем парам сливаемых массивов на -м шаге при каждом значении номера .

Временная сложность (время) параллельной сортировки по дереву выбора на основе параллельного слияния. Оценка построения дерева выбора: число шагов для построения – (последний шаг практически не нужен). Все шаги выполняются синхронно и взаимно независимо (параллельно). Каждый шаг выполняется за время одного сравнения . Наибольшее число процессоров на шаге , время построения дерева (рис. 1) определяется из равенства . Отсюда

. (13)

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

Предположим, на время рассуждения, что сливаемые массивы разбиты на 1-м шаге на не более чем групп, в каждой группе они расположены по неубыванию длины, их длины в группах на шаге 1 имеют значения: .

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

На шаге 2 длины сливаемых массивов не более чем удваиваются по отношению к предыдущему шагу: .

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

.

На шаге 3 длины не более чем удваиваются: . Количество слияний вдвое уменьшается, число процессоров при каждом слиянии не превосходит . В результате число процессоров на шаге 3 удовлетворяет неравенству:

.

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

или

, .

В итоге максимальное число процессоров удовлетворяет неравенству:

. (14)

Время максимально параллельного слияния по отдельной МС составит . На каждом шаге все слияния пар упорядоченных массивов выполняются параллельно, число шагов . Время рассматриваемой части алгоритма оценивается из соотношения: , где из (14).

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

, (15)

где из (14).

Имеет место

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

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

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

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

Замечание 4. В результате данной адресации, каждый элемент входного массива принадлежит, однократно, одному и только одному сливаемому массиву. Поэтому он останется отображенным на дереве один раз. Все пути этого элемента с дерева исчезнут (рис. 5). Длина массива, в который он входит, или единичная, или, во всяком случае, не больше высоты (числа уровней) дерева .

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

Литература

1. Кнут Д. Искусство программирования. Т. 3. – М.: МИР, Вильямс, 2001. – 800 с.

2. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – т. 118. – С. 159 - 187.

3. Гаврилкевич М.В., Солодовников В.И. Эффективные алгоритмы решения задач линейной алгебры над полем из двух элементов // Обозрение прикладной и промышленной математики. – 1995. – 2, №3. – С. 399 - 439.

4. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений . I // Кибернетика и системный анализ. – 1994. - № 5. – С. 3 - 23.

5. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.

Код для цитирования: Скопировать