Параллельное построение двоичного дерева на основе сортировки

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

Метод параллельного построения двоичного дерева. Для массива A = ( a₀, a ₁, ..., a n _₁ ) матрица сравнений строится в соответствии с [1, 2]. Элемент a_ij этой матрицы определяется как

+,

a ij

—

a j >  a i a j = a i a j < a i

где i , j = 1, 2, ..., n .

Элемент a j в отсортированном массиве C = ( с ₀,

n c1, ..., cn_1) получает номер k = ^aij , где aij >0

i = 1

при i <  j , a ij >  0 при i >  j . Все сравнения взаимно независимы, сортировка устойчива и максимально парал-

( N2 — N лельна с оценкой временной сложности TI------

= O ( 1 ) . На этой основе можно выполнить параллельное

построение двоичного дерева [3, 4]. Пусть дано множество из N элементов Xi , все элементы которого представлены в виде одномерного массива. На множестве предполагается заданным отношение порядка <. Требуется преобразовать массив в двоичное дерево. Для этого выполняется описанная сортировка массива. Середин-

ный элемент массива C имеет индекс j ср

и принимается за корень дерева [3]. Все элементы массива C

слева от C образуют левое поддерево (левый подмассив). Элементы справа от C образуют правое поддере-ср                                                                                                                                                                          ср во (правый подмассив). Левый подмассив интерпретируется как новый массив. В нем аналогично находится

. При этом C_j    — ближайший слева потомок корня дерева

индекс корня j ср. _Лев. 1/2 =

N

— 1

C . Все элементы подмассива слева от C      не превосходят C     , все элементы подмассива справа не jср                                                                                                       jср. лев. 1/2                                                  jср. лев. 1/2

меньше      C_j    .    Одновременно    определяется    индекс    корня    правого    подмассива

j ср. прав. 1/2

. При этом C jср. прав. 1/2

— ближайший справа потомок корня дерева

C . Процесс рекуррентно возобновляется в каждой паре прилегающих подмассивов: ср

ср. лев. 1/2 i , 1

j                   1

J ср. лев. 1/2

J ср. лев. 1/2 i ,2      сер. лев. 1/2 i ¹ ""*""

^ер. прав.1/2 i ,1     ^ер. прав. 1/2 i ¹

ер.прав.1/2 i ,2     ^ер. прав. 1/2 i ¹ "*"

j          — 1

ер. лев. 1/2 ¹

ер. прав. 1/2 i ¹        ер. прав. 1/2 i ²

ер.прав. 1/2 i ¹        ер. прав. 1/2 i ²

i = 1, 2

, log₂ N .

В результате за время O ( 1 ) формируютея вее элементы нижеетоящего уровня двоичного дерева. Процесс можно продолжать до исчерпания log₂ N уровней двоичного дерева.

Число шагов алгоритма построения двоичного дерева в параллельной форме складывается из шага сортировки и последовательности шагов при расчете индексов корней поддеревьев. Отсюда T ( R ) = log₂ N Т + т = O ( log₂ N ) , где R — чиело процеееорных элементов, т — время бинарного еравнения, Т — время вычисления одного индекса корня. Число процессоров R определяется максимально параллельной сортировкой N входных элементов, а затем вычислением индексов с удвоением по числу уровней дерева. При вычиелении индекеов это чиело не превзойдет 2^log 2 N ^{— 1} = N /2, поэтому чиела процеееоров, задейетвованных

N2 — N сортировкой, достаточно. В итоге R не превзойдет         [3]. Окончательно, временная сложность парал лельного алгоритма построения двоичного дерева составит

T ( N 2 N ] = O ( log 2 N ) .

Пример      [3].     Двоичное     дерево     для     массива     из     15      элементов

X = ( 14, 9, 24, 7,11, 20, 28, 3, 8,10,13, 17, 21, 25, 30 ) етроитея еледующим образом.

Результатом сортировки является массив

С = ( 3, 7, 8, 9,10,11,13,14,17, 20, 21, 24, 25, 28, 30 ) .

Корнем двоичного дерева является серединный элемент массива C : j

= 8,

С 8 = 14. Левый

подмассив имеет корень

j ср. лев. 1/2

= 4, элемент С 4 = 9 — корень левого поддерева, который являетея

ближайшим слева  потомком  серединного элемента C . Правый подмассив имеет корень ср

^j ер. прав. 1/2    ^{8 +}

8 — 1

= 12 , элемент С ₁₂ = 24 являетея корнем правого поддерева и ближайшим еправа потом-

ком корня C j _ср . Далее, j _{ср.лев.1/4,1}

= 2 , элемент С₂ = 7 — корень поддерева елева и являетея ближай-

шим слева  потомком  корня поддерева   C_j    . В правом поддереве корень имеет номер

^j ер. лев. 1/4,2    ^{4 +}

4 — 1

= 6, элемент С ₆ = 11 — корень правого поддерева и ближайший еправа потомок

Информатика, вычислительная техника и управление

C,    . Аналогично, слева от C,     определяется корень j         = 12 - jср. лев.1/2                                                   jср. прав.1/2                                               ср. прав. 1/4,1

12 - 8 - 1

= 10, элемент C ₁₀ = 20

— корень левого от него поддерева и ближайший слева потомок корня поддерева Cj     . Для смежного с рас- смотренным правым подмассивом корень имеет номер

j ср. прав. 1/4,2    ¹² +

12 - 8 - 1

= 14, элемент

C 14 = 28 —

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

0 уровень

C 8

j ср

= 8

= 14

i        = 4

ср. лев. 1/2

1 уровень jср. лев. 1/4,1

2 уровень      C 2

C 4 = 9

j ср. прав. 1/2

C 12 = 24

= 12

= 2

C 3 = 8

C 5 = 10

j ср. лев. 1/8,2     ³

j ср. лев. 1/4,2     ⁶

j ср. прав. 1/4,1

= 10

i          = 14

ср. прав. 1/4, 2

C 6 =11

C 7 = 13

C 10 =

C 9 = 17

C 14 = 28

j ср. лев. 1/8,3     ⁵

j ср. лев. 1/8, 4

= 7

i „ = 9 j ср. прав. 1/8,1

C 11 j ср. прав

=21        C 13 = 25       C 15 = 30

.1/8,2    ³³      j ср. прав. 1/8,3    ^³ j ср. прав. 1/8,4

Рис. 1. Пример построения двоичного дерева на основе сортировки

Имеет место

Теорема 1 [3]. Для одномерного массива из N элементов двоичное дерево может быть построено па-

( N 2 )

раллельно при помощи сортировки с временной сложностью T I -^- I = O ( log ₂ N ) .

Использованная сортировка устойчива, как следствие двоичное дерево строится с единственностью. Индексы всех серединных элементов (всех корней поддеревьев) можно идентифицировать [3]. С учетом этой модификации все индексы из предыдущего примера для N значений поддеревьев можно вычислить синхронно и взаимно независимо. Это приводит к единичной оценке времени построения двоичного дерева. Для каждого конкретного N все значения индексов узлов дерева можно вычислить априори и хранить в памяти компьютера. С их помощью отсортированные элементы можно синхронно и взаимно независимо адресовать по всем узлам дерева. Формулы вычисления индексов узлов зависят только от общего количества N входных элементов и никак не зависят от их взаимного расположения после устойчивой сортировки. Для упрощения адресации памяти вычисленные индексы можно упорядочить на каждом уровне и расположить по возрастанию уровней. Тогда по ключу N считывается вся совокупность упорядоченных индексов узлов. Остается только по счита-ным адресам расположить отсортированные элементы дерева. На основании изложенного имеет место

Теорема 2. Для одномерного массива из N элементов двоичное дерево может быть построено парал-

( N 2 )

лельно при помощи сортировки и априорного вычисления индексов с временной сложностью T I -^- I = O ( 1 ) .

Ниже представлена единая таблица, содержащая формальные оценки временной сложности последовательных и параллельных алгоритмов построения двоичного дерева в сопоставлении с предложенными алгоритмами.

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

Таблица 1

Алгоритм построения двоичного дерева	Временная сложность алгоритма	Ускорение при использовании алгоритма с единичной временной сложностью	Ускорение при использовании алгоритма с логарифмической временной сложностью
Algorithm of Lagana A., Kumar V. (2004) [5]	T = O f N k + 1 ) [5]	(   k + 1 T = O - I T *           1 V     J	T=O	(     k + 1 N-k— = O ( N ln2 ) log2 N      V      ’ V       J
Algorithm of Chalermsook P. (2015) [6]	T = O ( N 2 ) [6]	T = O ( N 1)	T - o :	—— ) = O ( N 2ln2 ) log2 N J    v       ’
Полиномиальный алгоритм (2016) [7]	T = O ( N 3) [7]	T = o ( N ’)	T - -i:	——1 = On 3ln2) log2 N J    v       7
Алгоритм «left child – right sibling» (2014) [8]	T = O ( N 2 ) [8]	- ■ = ° ( N 1 )	T - - I:	—N —1 = O2ln2) log2N J    v       7
Pattern-based algorithm (1991) [9]	T = O (| D log2 D ) [9]	OD f 1 D log 2 D ) T *      V      1      7	L = O f 1 D log 2 D ) T    V log 2 N J
Представленный алгоритм с логарифмической оценкой временной сложности (2015) [3]	T = O ( log 2 N ) [3]	–	–
Представленный алгоритм с единичной оценкой временной сложности (2015) [3]	T * = O ( 1 )	—	—

В таблице 1 D — мощность словаря шаблонов, N — число входных элементов двоичного дерева, k — размерность пространства, в котором выполняется сортировка.

Из таблицы видно, что предложенный алгоритм с логарифмической оценкой временной сложности абстрактно улучшает оценки известных алгоритмов. Минимальное ускорение достигается по отношению к алгоритму из [5]: ^ = O(N2 ln2), или, ^ = O(N), а максимальное ускорение достигается относительно полиноми-T J N3 1 T ального алгоритма из [7]: — = O         или — = O (N3). В случае с предложенным алгоритмом с единичной

T    Vlog2 NJ T оценкой временной сложности также улучшаются оценки известных алгоритмов. В данном случае минималь-T ное ускорение достигается относительно алгоритма из [5]: — = O(N), максимальное ускорение достигается относительно полиномиального алгоритма из [7]: ^* = O (N3).

Заключение. Разработанные алгоритмы отличаются от известных способов [5–7, 10, 11] построения двоичного дерева тем, что используется максимально параллельная сортировка для вычисления индексов узлов. При этом для построения дерева либо затрачивается логарифмическое число шагов, либо вообще не затрачивается дополнительное время, если значения индексов априори рассчитаны для всех значений N в некоторых реальных границах и хранятся в памяти компьютера. Предложенный параллельный алгоритм построения двоичного дерева может использоваться с целью организации эффективных способов динамической обработки баз данных.

Информатика, вычислительная техника и управление