Параллельное построение декартова дерева с логарифмической оценкой временной сложности

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 3:007
ПАРАЛЛЕЛЬНОЕ ПОСТРОЕНИЕ ДЕКАРТОВА ДЕРЕВА С ЛОГАРИФМИЧЕСКОЙ ОЦЕНКОЙ ВРЕМЕННОЙ СЛОЖНОСТИ
Ромм Я. Е., Чабанюк Д. А.
Таганрогский институт имени А. П. Чехова (филиал) РГЭУ (РИНХ), Таганрог, Россия (347 936, Ростовская
область, г. Таганрог, ул. Инициативная, 48), e-mail: romm@list. ru_
В статье выполнен синтез параллельного алгоритма построения декартова дерева с применением максимально параллельной модификации сортировки подсчетом на основе матриц сравнений. При параллельном построении поддеревьев используются взаимно независимые сравнения элементов по типу отдельных строк таких матриц, что аналогично операциям сортировки Хоара в параллельной форме. Для множества N пар элементов (Xl, Yl) временная сложность построения декартова дерева оценивается из
соотношения T® = O (log2N), где число процессоров R = (N2 — N)/2. Оценка получена на модели невет-вящихся параллельных программ без учета операций обмена. В статье приводятся примеры использования параллельной сортировки, а также пошаговой интерпретации работы параллельного алгоритма построения декартова дерева в процессе определения корней и ветвей поддеревьев. Предложенный алгоритм распараллеливается на уровне алгоритмических и разрядных операций. _
Ключевые слова: алгоритмы параллельных сортировок, структуры данных, декартово дерево, поразрядно-параллельное сравнение слов.
PARALLEL TREAP CONSTRUCTING WITH LOGARITHMIC ESTIMATE TIME COMPLEXITY
Romm Y.E., Chabanyuk D.A.
Taganrog Institute of Chekhov A.P. (branch) RGEU (RINH), Taganrog, Russia, (347 936, Rostovskaya obl., Taganrog,
Iniciativnaya str., 48), e-mail: romm@list. ru_
In this article gives the synthesis of a parallel algorithm for constructing of treap with use the modification counting sorting in the maximum parallel form on the basis of the comparison matrix. At the parallel construction of subtrees of treap used mutually independent comparisons of the elements according to the type of individual strings of the matrix, which is similar to the Hoare sorting in parallel form. For a set of N pairs of elements of (Xt, Y.) is the time complexity of construction of treap is estimated from the ratio of T® = O (log2N),
where the number of processors R = (N2 — N)/2. Estimate was obtained on the straight-line model of parallel programs without taking into account operations of the exchange. In this article gives examples of the use of parallel sorting, and made step by step interpretation of the parallel algorithm for constructing treap in the determination of the roots and branches of constructing subtrees of treap. The proposed algorithm is parallelized
at the level of algorithmic operations and bit operations. _
Keywords: parallel sorting algorithms, data structures, treap, bit by bit parallel comparison of words.
Постановка вопроса. Ускоряющаяся компьютеризация всех областей деятельности и информационных процессов, значительный рост объемов обрабатываемой информации приводит к трудностям при последовательном выполнении информационного поиска на основе традиционных алгоритмов [1, 3]. Древовидные структуры характеризуются эффективностью представления динамических данных для быстрого поиска информации. С целью дальнейшего увеличения эффективности целесообразна разработка и исследование алгоритмов параллельного построения древовидных структур данных. В таком аспекте ставится задача синтеза и оценки временной сложности параллельного алгоритма построения декартова дерева. Параллельные алгоритмы рассматриваются на модели
неветвящихся параллельных программ, согласно которой временная сложность Т (Я) алгоритма (кратко — время выполнения) измеряется количеством последовательных шагов без учета обмена, Я — число процессоров [9].
Сортировка подсчетом. На этапе построения декартова дерева ко всем компонентам будет применяться максимально параллельная сортировка подсчетом по матрице сравнений [5]. Модификация известного алгоритма заключается в следующем. Для одномерного массива, а = (а, а, к, а) сортируемых элементов составляется матрица сравнений, элемент, а у которой определяется из соотношений:
a, j = sign (a} -at) =
1(+), aj & gt- ai- 0, a: = ai-
J 1
-1(-), а& lt- а{- / = 1, п- ] = 1, п. Входной элемент с номером у получает номер к в отсортированном массиве по правилу: в у -м столбце матрицы подсчитывается количество нулей и плюсов сверху вниз до главной диагонали включительно и складывается с количеством только плюсов ниже диагонали в этом же столбце. Суммарное количество составит значение выходного номера к. Пусть, например, требуется отсортировать по неубыванию массив, а = (1, -1, 0, 3, -3, 5).
Матрица сравнений примет вид:
aj a2 a3 a4 a5 a6
1 — 1 0 3 -3 5
aj 1 0 — - + - +
a2 — + 0 + + - +
a3 0 + - 0 + - +
a4 3 — - - + - +
a5 — + + + 0 0 +
a6 5 0
Согласно правилу вставки получится: a1 = 1 ® & lt-(+++0) ® c4- a2 = -1 ® С (0 +) ® c2- a3 = 0 ® & lt- + 0 +) ® c3-
a4 = 3 ® & lt-(+ + + 0 +) ® c5- a5 = -3 ® С (0) ® c1- a6 = 5 ® c (+ + + + + 0) ® c6. Отсортированный массив примет вид: c = (-3, -1, 0, 1, 3, 5). Процедура сортировки в консольном приложении Delphi [3, 5]
при соответственном задании типа элементов и их индексов запишется в виде:
procedure sort (var n: integer- var a, c: vekt00- var e: vekt) —
var i, j, k: integer-
begin
for j:= 1 to n do begin k:= 0-
for i:= 1 to j do
if a[j] & gt-= a[i] then k:= k+1-
for i := j+1 to n do
if a[j] & gt- a[i] then k := k+1-
c[k] := a[j]- e[k] := j-
end-
end-
Сортировка сохраняет порядок равных элементов, операторы c[k]: =a[j]- e[k]: =j- в явном виде задают взаимно однозначное соответствие входных и выходных индексов сортируемых элементов. Сортировка обладает максимальным параллелизмом: все сравнения в матрице взаимно независимы и выполнимы параллельно за время T ((n2 — N)/2) = 0(1) [5].
Описание метода. Декартово дерево — это структура данных, хранящая в узлах пары элементов (X, Y) в виде двоичного дерева таким образом, что она является двоичным деревом по X и двоичной пирамидой по Y [1]. Двоичное дерево — это структура данных, для которой у левого потомка произвольной вершины значение элемента X меньше либо равно значения X его вершины, а у правого потомка произвольной вершины значение X строго больше, чем значение X его вершины. Двоичная пирамида — двоичное дерево, в каждой вершине которой хранится ключ, и для каждой вершины дерева с ключом Y у всех непосредственных потомков ключ не больше значения Y предка. Пусть задано некоторое множество пар элементов (X., Yi). Корнем декартова дерева является пара элементов, которая имеет максимальный Y (по условию двоичной пирамиды). Пусть (X., Yi) — пара с максимальным Y. Тогда все пары с меньшими X будут в левом поддереве, остальные — в правом поддереве. Каждое из поддеревьев строится аналогично. На рис. 1 изображен пример декартова дерева для массива пар чисел:
(1- 4), (1- 12), (4- 13), (9- 14), (4- 7), (6- 8), (7- 6), (12- 5), (13- 11), (14- 12), (18- 0). (1)
Рис. 1. Пример декартова дерева Построение декартова дерева с применением представленной максимально-параллельной сортировки (ниже МП-сортировки) выполняется следующим образом. Ко всем компонентам У. — элементов данного множества применяется МП-сортировка по неубыванию. При этом пары уже отсортированных по ^ элементов (X., У.) располагаются с сохранением входного индекса без изменения единичной оценки времени. Наибольший среди У. элемент
окажется в правом конце отсортированного массива вместе с входным индексом пары (X, У.). Пусть эта пара обозначена (Х{, У) ы, а ее входной индекс — Еы, Еы = ., таким образом, определен корень декартова дерева (X., У.)м. Далее, без изменения его местоположения во входном массиве, которое идентифицируется по индексу Ек, этот элемент объявляется серединным в данном входном массиве. Относительно середины выполняется упорядочение по X.: все элементы в левой части массива, которые меньше X. из (X., У.)ы, остаются в левом подмассиве с сохранением исходного взаимного порядка- все элементы в левой части массива, которые больше X. из (X., У.)ы, переносятся из левой части в правый подмассив, также с сохранением исходного взаимного порядка. Все элементы правой части массива, которые больше X. из (X., У.)ы, остаются в правом подмассиве с сохранением исходного взаимного порядка- все элементы правой части массива, которые меньше X. из (X., У.)м, переносятся из
правой части в левый подмассив, также с сохранением исходного взаимного порядка.
Излагаемый ниже способ упорядочения относительно середины аналогичен тому, который применяется для параллельного варианта сортировки Хоара [4].
Для примера (1) середина — пара (X., У.)ы = (9- 14),. = 4. Упорядочение относительно
X. = 9 выполняется параллельно по всем элементам по схеме МП-сортировки в одной строке:
а1 а2 а3 «4 а5 аб а7 а8 а9 а10 а11
1 1 4 9 4 6 7 12 13 14 18
«4 9 — - - 0 — - - + + + +
Все элементы со знаком сравнения & quot--"- из правого подмассива с сохранением индексов переносятся в левый подмассив. В результате получится:
а1 а2 а3 а5 аб а7 «4 а8 а9 а10 а11
1 1 4 4 6 7 9 12 13 14 18
«4 9 0 + + + +
Для левого подмассива элементы декартова дерева расположатся в виде:
а1 а2 а3 а5 аб а7
(1- 4) (1−12) (4- 13) (4- 7) (б- 8) (7- б)
В сформированном таким способом левом подмассиве повторяется МП-сортировка по У. В результате определяется корень поддерева в этом подмассиве: (4- 13) с исходным индексом I = 3. Относительно его положения в подмассиве выполняется упорядочение по изложенной схеме по X. :
а1 а2 «3 а5 аб а7
1 1 4 4 6 7
«3 4 — - 0 0 + +
В результате определились элементы нового поддерева искомого декартова дерева с корнем (4- 13):
а1 а2 «3 а5 аб а7
(1- 4) (1−12) (4- 13) (4- 7) (б- 8) (7- б)
Сравнение с серединным элементом выполняется параллельно по всем элементам исходного подмассива аналогично одной строке МП-сортировки за единичное время на процессорах, число которых равно числу N. элементов подмассива. Число процессоров для
определения корня поддерева равно Я = - N)2 N -1).
1 2
Параллельно с левым подмассивом исходного массива аналогично обрабатывается правый подмассив:
а8 а9 а10 аи
(12- 5) (13- 11) (14- 12) (18- 0)
Повторяется МП-сортировка по У.: в результате определяется корень поддерева: (14- 12) с исходным индексом 1 = 10. Относительно его исходного положения в данном правом под-массиве выполняется упорядочение по изложенной схеме относительно X. :
а8 а9 «10 а11
12 13 14 18
«10 14 — - 0 +
Тем самым, оказалось, что окончательно сформировано поддерево правого подмассива:
а8 а9 «10 аи
(12- 5) (13- 11) (14- 12) (18- 0)
На этом завершено полное построение декартова дерева, оно совпадает с деревом, изображенным на рис. 1.
В общем случае описанные действия параллельно повторяются отдельно в каждом подмассиве, при этом наибольший среди У. элемент левого подмассива окажется левым потомком корня декартова дерева (X., У.)N, наибольший среди У. элемент правого подмассива окажется правым его потомком.
Действия воспроизводятся в каждом новом подмассиве, образуемом потомком как корнем поддерева, причем параллельно по всем подмассивам, соответственным корням текущего уровня.
Шаги описанного параллельного алгоритма продолжаются до полного построения декартова дерева, их количество, очевидно, не превосходит N. Число процессоров в каждом поддереве для МП-сортировки по уровням корней располагается в последовательность:
^ _ м N2 — N N2 — N N2 — N N2 — N ^ - N ^ - N
N_NN 1 1 + 2 2 3 3 + 4 4 + 5 5 + 6 6 (2)
2, 2 2, 2 2 2 2 ^ -
В (2) нечетные индексы соответствуют поддеревьям левых подмассивов, четные — правых. С учетом N = N — N получится, что
^ - N + N 2 — N 2 _ ^ - N1 + (N — Ц)2 — (N — N1) & lt- N2 — N 2 2 2 2 2.
В общем случае, соответственно уровню корней поддеревьев с номером 1°§ 2 к, к & lt- N, количество сортируемых по всем подмассивам элементов удовлетворяет равенству
1°Б2 к
2 Ni _ N. Отсюда количество процессоров при параллельном по всем г выполнении МП-
г1
сортировки каждого подмассива из Ni элементов на уровне с номером 1°§ 2 к удовлетворяет соотношениям:
1°Б2 к 1 1°§ 2 к, 1 1°Б2 к,
22 Я _ - 22 Nг% -1)& lt--N 22 (К-l),
г1 г 2 г1 г 2 г1
поэтому
1°§ 2к 1 (1°§ 2к N2 — N
Iя & lt- 2 * {ЦN¦-1) _ 2.
Таким образом, с учетом единичного времени каждого последовательного шага и числа шагов 1°§ 2 N получается оценка временной сложности предложенного алгоритма:
Т2 — N)/2)_ 0(1°М2 N). (3)
Из изложенного вытекает
Теорема 1. Построение декартова дерева может быть выполнено с помощью детерминированного параллельного алгоритма за логарифмическое число шагов с временной сложностью (3), где N — число элементов входного множества пар (Хг, Уг).
Очевидной является возможность перемещения входных индексов пар (Хг, Уг) по уровням и подмассивам в соответствии шагам изложенного построения декартова дерева, что дает возможность адресоваться от элементов окончательно построенного декартова дерева непосредственно к элементам входного массива и обратно.
Замечание 1. В [6−8] рассматривается построение декартова дерева с учетом поразрядно-параллельных сравнений элементов без вычисления переноса на основе аналога арифметической обработки [2]. Учитывая время МП-сортировки Т (^2 — N)/2)= 0(1) и оценку (3), полное построение декартова дерева в максимально параллельной форме на данной основе можно выполнить с временной сложностью Т (2N2п) = 0(1о^ N) т0, где N — число элементов
входного множества пар (X., У.), п — число разрядов наибольшего по числу символов элемента в наборе, т0 — время одного сравнения двух бит.
В [б] даны результаты программного эксперимента с последовательным моделированием параллельного алгоритма построения декартова дерева, на выходе которого для произвольного множества пар входных данных всегда получается правильный результат.
Заключение. В статье изложен синтез алгоритма параллельного построения декартова дерева с применением максимально-параллельной сортировки подсчетом и аналога сортировки Хоара в параллельной форме. Временная сложность построения декартова дерева по данному алгоритму имеет оценку вида Т ((х2 — N)/2)= 0(^2 N). Предложенный алгоритм распараллеливается на уровне алгоритмических и разрядных операций, при этом достигает снижения оценки временной сложности известного аналога [10] построения декартова дерева. Приведены примеры использования сортировки и построения декартова дерева с помощью представленного алгоритма, правильность работы которого подтверждается программными экспериментами [б]. Представленный в статье подход может рассматриваться в качестве основы для увеличения эффективности параллельного построения древовидных структур данных.
Список литературы
1. Кнут Д. Искусство программирования для ЭВМ. Т. З. Сортировка и поиск. — М.: Вильямс, 2007. — 832 с.
2. Ромм Я. Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ. 1998. — № 6. — С. 146−162.
3. Ромм Я. Е., Белоконова С. С. Детерминированный информационный поиск на основе сортировки с распараллеливанием базовых операций. — М.: Научный мир, 2014. — 198 с.
4. Ромм Я. Е., Виноградский В. В. Преобразование сортировки Хоара в параллельную форму на основе матриц сравнений // Проблемы программирования. — 2008. — № 2−3. — С. 332−340.
5. Ромм Я. Е., Заика И. В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ. — 2011. — № 2. — С. 165−180.
6. Ромм Я. Е., Чабанюк Д. А. Параллельные алгоритмы обработки структур данных и последовательное моделирование параллельного построения декартова дерева / Таганрог. ин-т им. А. П. Чехова (филиал) ФГБОУ ВПО РГЭУ (РИНХ). — Таганрог, 2015. — 53 с. Деп. в ВИНИТИ 16. 01. 15, № 9 — В2015.
7. Ромм Я. Е., Чабанюк Д. А. Поразрядно-параллельное сравнение ключей в некоторых древовидных структурах данных / Таганрог. ин-т им. А. П. Чехова (филиал) ФГБОУ ВПО РГЭУ (РИНХ). — Таганрог, 2014. — 41 с. Деп. в ВИНИТИ 04. 09. 14, № 244 — В2014.
8. Ромм Я. Е., Чабанюк Д. А. Сравнение слов с единичной временной сложностью // Известия ЮФУ. Технические науки. — 2014. — № 7(156). — С. 230−238.
9. Солодовников В. И. Верхние оценки сложности решения систем линейных уравнений // В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. — Л., 1982. -Т. 118. — С. 159−187.
10. Blelloch G., Reid-Miller M. Fast set operations using treaps // Proc. 10th ACM Symp. Parallel Algorithms and Architectures, New York: ACM. — 1998. — P. 16−26.
Рецензенты:
Веселов Г. Е., д.т.н., директор Института компьютерных технологий и информационной безопасности, Инженерно-технологическая академия Южного федерального университета, г. Таганрог-
Турулин И. И., д.т.н., профессор, профессор кафедры информационных измерительных технологий и систем, Институт нанотехнологий, электроники и приборостроения Южного федерального университета, г. Таганрог.

ПоказатьСвернуть
Заполнить форму текущей работой