Преобразование информационных данных и двоичных структур с минимизацией временной сложности на основе алгоритмов сортировки Чабанюк Денис Андреевич

Содержание к диссертации

Введение

Глава 1. Использование взаимно независимых разрядных преобразований на основе вертикальной обработки данных при выполнении операций сравнения для информационного поиска 36

1.1. Описание метода вертикальной обработки 36

1.2. Вертикальное сложение двоичных чисел в знакоразрядном коде 47

1.3. Взаимно независимая обработка разрядов для сравнения чисел 55

1.4. Поразрядно-параллельный способ сравнения слов строкового типа 61

1.5. Поиск по маске подстроки в строке на основе взаимно независимой обработки разрядов при выполнении сравнений 67

1.5.1. Поиск подстроки в строке с минимальной временной сложностью 69

1.6. Способы выделения старшего ненулевого разряда 72

1.6.1. Выделение старшего ненулевого разряда на основе сортировки подсчетом по матрице сравнений 73

1.6.2. Выделение старшего ненулевого разряда на основе логических операций 76

1.6.3. Минимизация временной сложности выделения старшего ненулевого разряда по аналогии с нормализацией двоичной мантиссы 78

1.7. Сравнение предложенного метода с известными аналогами 83

1.8. Выводы 85

Глава 2. Детерминированное построение декартова дерева с логарифмической временной сложностью для ускорения обработки данных 87

2.1. Предварительное описание декартова дерева 87

2.2. Построение декартова дерева с применением устойчивой адресной сортировки 88

2.3. Характеристика существующих комплексов реляционных структур данных 94

2.4. Сопоставление параллельного построения декартова дерева с построением в реляционной структуре данных Oracle Database 103

2.5. Сравнение временной сложности предложенного построения декартова дерева с известными алгоритмами 110

2.6. Выводы 113

Глава 3. Методы минимизации временной сложности построения двоичного дерева на основе устойчивой адресной сортировки 115

3.1. Построение двоичного дерева с логарифмическим числом шагов 115

3.1.1. Извлечение структурных закономерностей из произвольного расположения входных данных на основе сортировки 123

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

3.2. Минимизация временной сложности построения двоичного дерева с применением взаимной независимости разрядных преобразований при сравнении элементов 128

3.3. Сравнение выполнения базовых операций с известными методами 130

3.4. Сравнение временной сложности построения двоичного дерева с известными алгоритмами 136

3.4.1. Сравнение предложенного построения двоичного дерева с известными алгоритмами 137

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

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

3.5. Оценки ускорения с учетом взаимной независимости разрядных преобразований при выполнении операций сравнения 148

3.6. Выводы 152

Заключение 154

Список литературы 158

Приложения 173

• Вертикальное сложение двоичных чисел в знакоразрядном коде
• Характеристика существующих комплексов реляционных структур данных
• Сравнение выполнения базовых операций с известными методами
• Оценки ускорения с учетом взаимной независимости разрядных преобразований при выполнении операций сравнения

Введение к работе

Актуальность темы. Развитие компьютерных технологий и создание высокопроизводительных процессоров обуславливает разработку структур данных, адаптированных к массовому параллелизму. При существующем многообразии архитектур процессоров и способов представления информации одной из важнейших задач является ускорение обработки данных на основе эффективно распараллеливаемых алгоритмов. Большинство существующих методов параллельных вычислений направлено на решение сложных задач адаптации вычислительного алгоритма к архитектурам многопроцессорных вычислительных систем. В качестве одной из таких задач целесообразно рассматривать параллельное построение и обработку древовидных структур данных. Распараллеливание организуется как средство повышения эффективности представления и обработки динамических данных с целью быстрого поиска информации. Известны различные способы построения структур данных, включая параллельные, реализуемые под конкретные задачи. Классическим структурам данных посвящены работы Д.Э. Кнута, А. Ахо, Дж. Ульмана, Н. Вирта, R. Seidel, C. Aragon. Предложенные в этих работах структуры данных и методы выполнения в них базовых операций создали основу современных технологий информационного поиска. Исследование классических структур и возможности их адаптации к параллелизму представлено в работах А.А. Могилко, А.А. Плетнева, Л.И. Тимченко, С.А. Харченко, A. Lagana, V. Kumar, C. Tan, P. Chalermsook, A. Amir, M. Farach и др. Наряду с тем созданы комплексы и системы структур данных, которые используют параллельные вычисления: Oracle Database, IBM DB2, Microsoft SQL Server, MySQL и др. При этом остается актуальной проблема адаптации структур и средств обработки данных к быстро развивающимся архитектурам параллельных и последовательных вычислительных систем, к технологиям создания современных информационных систем. В качестве стимула сохраняется необходимость быстрой и эффективной обработки огромных объемов сложно структурированной информации, характеризующихся неуклонным ростом. Наличие множества исследований наряду с технологическими факторами подтверждает актуальность создания эффективных, обладающих достаточной простотой программной реализации, алгоритмов построения и обработки параллельных структур данных.

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

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

4 котором не используется операция вычисления переноса и выполняется взаимно независимый анализ разрядов данных.

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

2. Разработать алгоритм ускоренного построения двоичного дерева информационных данных на основе устойчивой адресной сортировки, который выполнялся бы с временной сложностью 0(log₂N) .

3. Разработать алгоритм ускоренного построения двоичного дерева информационных данных на основе сортировки и априорного вычисления хранимых индексов корней поддеревьев, который выполнялся бы с оценкой временной сложности Г(1) = 0(1).

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

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

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

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

Научная новизна

1. Предложен способ сравнения данных числового и строкового типа на основе вертикальной обработки в качестве компонента информационного поиска. Способ отличается от известных отсутствием вычисления переноса и взаимной независимостью анализа разрядов данных, что позволяет выполнять сравнение с временной сложностью о(1) независимо от числа символов строк (С. 55 - 72).

2. Разработан алгоритм построения декартова дерева информационных данных на основе устойчивой адресной сортировки, отличающийся от аналогов структурой и логарифмическим количеством последовательных шагов, что позволяет достигать ускорения относительно аналогов o(N), где jv - число данных (С. 87 - 93,

103 - 113).

3. Разработан алгоритм построения двоичного дерева информационных данных на основе устойчивой адресной сортировки, отличающийся от аналогов структурой и логарифмической оценкой временной сложности, что позволяет достигать ускорения относительно аналогов о(лг), а>1 (С. 115 - 122, 130 - 142).

4. Разработан алгоритм построения двоичного дерева информационных данных на основе сортировки и априорного вычисления хранимых индексов корней поддеревьев, который отличается от известных структурой и оценкой временной сложности г(і) = <9(і), что позволяет достигать ускорения относительно аналогов

o(N"), а>1 (С. 115 - 123, 130 - 136, 143 - 145).

5. Показано, что на основе предложенного алгоритма из произвольного расположения данных в массиве можно извлечь полную информацию об экстремальных закономерностях и, аналогично, информацию о структурных закономерностях двоичного дерева, априори скрытую во входных данных. Способ отличается от аналогов точным решением с помощью конструктивного детерминированного алгоритма (С. 123 - 126).

6. Показано, что предложенные алгоритмы построения декартовых и двоичных деревьев информационных данных получают дополнительное ускорение за счет отсутствия вычисления переноса и взаимной независимости обработки разрядов данных при выполнении операций сравнения, что позволяет увеличить ускорение относительно известных аналогов до о («№}, а>1, где и - количество разрядов

данных (С. 128 - 130, 148 - 152).

Основные положения, выносимые на защиту

1. Способ сравнения данных числового и строкового типа на основе вертикальной обработки в качестве компонента информационного поиска, отличающийся отсутствием вычисления переноса и взаимной независимостью анализа разрядов данных, позволяющий выполнять сравнения с временной сложностью <9(l) независимо от числа символов строк.

2. Алгоритм построения структуры декартова дерева информационных данных на основе устойчивой адресной сортировки с логарифмическим количеством последовательных шагов.

3. Алгоритм построения структуры двоичного дерева информационных данных из jv элементов на основе устойчивой адресной сортировки с временной сложностью T(N>) = 0(lo_e2N) .

4. Алгоритм построения двоичного дерева информационных данных на основе сортировки и априорного вычисления хранимых индексов корней поддеревьев.

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

6. Способ дополнительного ускорения алгоритмов построения декартовых и двоичных деревьев информационных данных за счет отсутствия операций вычисления переноса и взаимной независимости обработки разрядов данных при выполнении сравнений.

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

Практическая ценность диссертационного исследования заключается в

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы:

1. В АО НКБ ВС (г. Таганрог, Ростовская обл.) приняты к использованию способ сравнения слов числового и строкового типа на основе вертикальной обработки данных; алгоритм построения декартова дерева на основе устойчивой адресной сортировки; алгоритм построения двоичного дерева на основе устойчивой адресной сортировки с временной сложностью T(N²} = o(log₂N); алгоритм построения

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

2. В учебном процессе кафедры информатики Таганрогского института имени А.П. Чехова (филиал) ФГБОУ ВО "РГЭУ (РИНХ)" в курсах «Базы данных», «Программирование», «Основы алгоритмизации и программирования», «Информационные системы», «Теория алгоритмов».

Апробация работы. Основные результаты работы докладывались на следующих семинарах и конференциях:

V Международной научно-практической конференции «Информационные ресурсы и системы в экономике, науке и образовании» (г. Пенза, апрель 2015);

Пятьдесят девятой научно-теоретической конференции профессорско-преподавательского состава Таганрогского института имени А.П. Чехова (филиала) РГЭУ (РИНХ) (г. Таганрог, апрель 2015);

XVI Всероссийском симпозиуме по прикладной и промышленной математике (летняя сессия) (г. Челябинск, 21-27 июня 2015 г.);

Международной научно-практической конференции «Вопросы образования и науки: теоретический и методический аспекты» (г. Тамбов, июнь 2015);

II Международных научных чтениях (памяти С.Ф. Ковалевской) (г. Москва, 19.09.2016);

Всероссийской научно-практической конференции с международным участием «Аспекты развития науки, образования и модернизации промышленности» (г. Таганрог, 20-21 апреля 2017);

- XXXII Международной научно-практической конференции (г. Москва, 10.07.2017).

Публикации. По материалам диссертационной работы опубликовано 13 печатных работ, в том числе 3 статьи в рецензируемых журналах, входящих в Перечень ведущих научных журналов и изданий, утвержденных ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и приложения, включающего код программы и акты о внедрении. Основное содержание работы изложено на 172 страницах, включая 10 таблиц, 14 рисунков и библиографии из 179 наименований.

Вертикальное сложение двоичных чисел в знакоразрядном коде

Чтобы применить изложенный метод вертикальной обработки для упорядочения и поиска слов (с целью ускорения этих операций), необходимо дать его модификацию для случая бинарного сложения целочисленных двоичных слагаемых [91, 92].

Возможен еще один способ тривиального определения знака алгебраической суммы двух (и более) (п + 1)-разрядных слагаемых, основанный на вертикальном суммировании и знакоразрядном представлении чисел [92].

Описание способа поразрядно-параллельного суммирования чисел в знакоразрядном коде без изменений заимствовано из [80]. Пусть рассматриваются два целочисленных двоичных полинома, коэффициенты которых могут иметь различные знаки

Разряды ниже понимаются алгебраически: в і-м разряде размещаются р, или у, из (1.24) вместе со знаками. Расположив Р1 и Р2 в двух входных разрядных сетках ( PC ), РС и РС , номера ячеек которых совпадают с индексами коэффициентов из (1.24), сложение можно провести в 4 шага.

Шаг 1. СВН-параллельно по всем номерам разрядов j из входного набора (1.25) выполняется операция Р-+у- суммирования по вертикали (СВ ). Результат СВу представляется в однорядном знакоразрядном коде

(1.26) Коэффициенты Aej для всех из (1.26) не должны иметь противоположных друг другу знаков ни при каком произвольно фиксированному :

Ограничения для формул (1.26) и (1.27) для данного случая не существенны. При каждом 7 = const А0; и Аъ из (1.26), (1.27) располагаются по диагонали двух выходных PC , - РСв ы х и РС(в ы х , образуя диагональную от у-го разряда запись (Дозапись) вида:

За результат шага 1 принимается промежуточный набор разрядных значе-из схемы диагональной записи и

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

Данный предварительно выполненный шаг дает возможность упростить (или «обойти») вычисление переноса в параллельном сумматоре. Основой упрощения служит тот факт, что все переносы в промежуточном наборе (1.29) оказываются взаимно отделенными вертикальными парами нулей. Вертикальной парой нулей k -го разряда (k -парой нулей) будет называться пара нулевых значений веса k -го разряда Лемма 1.2 [77, 92]. В промежуточном наборе (1.29), полученном в результате шага 1, любая -пара единиц отделена от произвольно выбранной /-пары единиц при i хотя бы одной промежуточной к -парой нулей при некотором к, к г.

Доказательство. Пусть формально введены ограничители для промежуточного набора (1.29): слева - -пара нулей (1.30) при к = п+2, справа - при к = -\. Тогда для доказательства леммы достаточно показать, что между двумя ближайшими друг к другу вертикальными парами нулей может образоваться не более одной промежуточной пары единиц. Пусть произвольные /, , к таковы, что -пара и /-пара нулей из (1.29) оказались ближайшими друг к другу, ниже они помечены верхними индексами "0", - а между ними образовалась к -пара единиц, отмечаемая верхним индексом "1", (±1) ±1

Пусть вначале к-1, і к+\. Между /-парой и -парой нулей в этом случае может оказаться не более одной к -пары единиц из (1.32) вследствие того, что наличие последней в промежуточном наборе (1.29) необходимо влечет комбинацию разрядных значений следующего вида где A._15 A._2, ..., At+1, а также Vtl, Vt2, ..., WM равны ±1. В самом деле, если хоть одно из данных значений Аг и Vq было бы нулевым, то вертикальные пары нулей из (1.32) не были бы взаимно ближайшими, вопреки предположению. Если же хоть один из разрядов с нулевым значением в (1.33), например, у -й при k + \ j i-\ или при + \ j k-\ заменить на ±1, то он с необходимостью порождал бы Д . -запись одного из видов

Первые две (верхние) Д -записи из (1.34) невозможны, согласно ограничению (1.27); две вторые (нижние) соответствуют результату СВ-, при котором в (1.26) р; + у; = д„. +A1J21 = 3 , в то время как р,. 1 и у, 1 , откуда з = р, + у, р, + у, 2 , что невозможно. Случай i = k+\, = к-\ тривиально дает искомое утверждение; в случаях / = к+\, к-\ или =к-\, і к+\ сохраняются проделанные рассуждения. Лемма доказана.

Следствие 1.2 [78, 92]. В результате выполнения шага 1 ни в один произвольно фиксированный разряд промежуточного набора (1.29) не могут прийти одновременно две или более единиц переноса. Следствие 1.2 исключает взаимное наложение переносов; по некоторой аналогии со случаем вертикального суммирования с промежуточным набором (свойством бесконфликтности распространения переноса). В силу бесконфликтности, после шага 1 все переносы могут распространяться одновременно и по взаимно независимым схемам - СВН-параллельно. Это даст возможность завершить в дальнейшем их распространение за время О (і).

Замечание 1.3 [78, 92]. Лемма 1.2 и следствие 1.2 сохраняются для частного случая слагаемых (1.24), у которых все коэффициенты неотрицательны. Иными словами, данные утверждения переносятся на случай сложения неотрицательных целочисленных двоичных полиномов в прямом коде.

Шаг 2. За исключением каждого ненулевого разряда, располагающегося непосредственно перед соседним старшим нулевым разрядом (такими исключениями будут, в частности, Ап из (1.29) и Аг х из (1.33)), все остальные разряды, имеющие значение Ау 0 , из РС (и только из РСв ы х ) в промежуточном наборе (1.29) подвергаются тождественному преобразованию A,. =2A,.-A,., 7 = 0, 1, ...,п. (1-35)

При этом правая часть (1.35) размещается в 7-й ячейке PCJы х и в 0 + і)-й ячейке РС в порядке Д,-записи для всех номеров 7 преобразуемых разрядов: у (0) PCвых

Схемная реализация (1.35), (1.36) сводится к перезаписи А. из 7-го разряда РСв ы х в (7 + і)-й разряд РС(в ы х и одновременно к инверсии знака перед А. в 7-м разряде РС . К выполнению Д, -записи (1.36) не возникнет препятствий, поскольку под каждой + единицей из РС по диагонали от нее исключены все комбинации вида (1.34), так что А. в (1.36) всегда будет записываться на место нуля в (/ + і)-й разряд РС(в ы х. Преобразование выполняется СВН-параллельно по всем j = 0,1,.../7. Все возможные переносы априори (с учетом формальных ограничителей из доказательства леммы 1.2) после шага 1 заключены в комбинациях вида (1.33). Каждая такая комбинация в результате (1.35), (1.36) перейдет в комбинацию вида

Совокупность наборов вида (1.37) принимается за результат шага 2, в каждом из них все /-пары и -пары нулей остаются неизменными по отношению к шагу 1 и продолжают взаимно отделять переносы; неизменно также содержимое РС и pcjы х справа от -пары единиц до ближайшей -пары нулей. Слева от к-пары единиц, включая Д , до ближайшей /-пары нулей все разряды в РС поменяли знак на противоположный, за исключением Аг-_І, а все нули, исключая v0), заменились на единичные значения. Таким образом, каждый набор вида (1.37), начиная с к -пары единиц, состоит из вертикальных пар единиц старших разрядов, между которыми нет пропуска, вплоть до ближайшей / -пары нулей.

Шаг 3. Содержимое PCJы х и РС(в ы х без изменений переводится в PCJJ и РС, затем принимается за входной набор, над которым повторяются все операции шага 1. В результате каждый набор вида (1.37) перейдет в набор вида

Такой переход произойдет по следующим причинам. До сих пор предпола галось, что в (1.33) пара представляет собой k -пару единиц. При сохране нии этого предположения в наборе (1.37) она перейдет в k -пару единиц вида слева от нее – аналогичные вертикальные пары единиц вплоть до бли 53 жайшей /-пары нулей. Поэтому при каждом j = k,k + l,..., /-1, в разрядах с номером j вследствие СВj будет получаться

Шаг 4. СВН-параллельно по всем j = О, 1, .., п, п +1 ненулевые значения разрядов РС(в ы х с сохранением веса переписываются в РС , где, таким образом, сформируется окончательное значение вычисляемой суммы Рх и Р2 из (1.24) (то же достигалось бы повтором шага 1 применительно к (1.38)).

Характеристика существующих комплексов реляционных структур данных

Ниже выполнен анализ реляционных структур данных, основанных на наиболее распространенном языке – SQL (Structured Query Language) [155], который предоставляет не только средства для спецификации и обработки запросов на выборку данных, но также и функции по созданию, обновлению, управлению доступом и т.д. [69].

Ниже выполнен анализ структуры данных Oracle Database версии 12с (2013), являющейся лидером среди структур, доля которой составляет 60% (2012) от мирового рынка [60].

Преимуществом Oracle Database является: высокая надежность [116], возможность разбиения структуры на разделы при работе с большими объемами данных [116, 150], распараллеливание операций в запросе [158], эффективные методы максимального повышения скорости обработки запросов [116], поддержка большого объема памяти и симметричной многопроцессорной обработки [132], позволяющая управлять приложениями с высокими нагрузками, связанными с большим объемом транзакций.

В Oracle Database хранятся не строки, либо их версии, а блоки данных, которые являются наименьшей единицей информации для рассматриваемой структуры данных. При выполнении любой транзакции в рассматриваемой структуре, необходимо прочитать из памяти блок данных целиком, а лишь затем из прочтенного блока нужную строку [116]. В Oracle Database на этапе создания базы задается размер блока данных. Причем для каждой таблицы может быть предложен индивидуальный размер блока. Например, для табличных пространств с малыми и часто изменяющимися элементами – меньший размер блока данных, а для табличных пространств с большим объемом данных и редко изменяющимися элементами – больший размер блока данных. Такое распределение размера блоков данных для таблиц в Oracle Database существенно влияет на производительность [50]. Например [163], в Oracle Database для чтения одной строки из таблицы объ 95 емом 200 байт необходимо прочитать из базы данных весь блок размером 8000 байт, после чего извлечь из него нужную строку. При этом 7800 байт были прочитаны безрезультатно. Или, например, необходимо прочитать все строки таблицы в Oracle Database. В этом случае, чем больше строк и больше размер одной строки в структуре данных, тем больше блоков вынуждена прочитать система, т.е. Oracle Database экономичней прочитать один блок объемом 32 килобайта, чем считать четыре блока по 8 килобайт.

В предложенной в п. 2.2 структуре на основе декартова дерева, при выполнении любой транзакции прочитываются сразу строки [85], что позволяет снизить время выполнения операций и, в целом, нагрузку. Размер блока с наименьшей единицей информации равен одному биту, что увеличивает нагрузку и приводит к росту числа процессорных элементов, но снижает время доступа к данным.

Для оптимизации построения иерархической структуры в Oracle Database поддерживаются различные типы индексов, которые обеспечивают существенный прирост производительности в случаях обработки данных с низкой селективностью [116], т.е. с небольшим количеством различающихся значений в таблице. Например, при использовании "Bitmap-индекса", оптимизатор в Oracle Database поддерживает динамическое преобразование и может эффективно обрабатывать запросы, включающие битовые операции [132]. Существенным недостатком использования "Bitmap-индекса" для оптимизатора в Oracle Database является предпочтение полного сканирования данных в таблице для всех различных наборов значений [132, 151], что приводит к увеличению количества требуемых операций ввода/вывода, выполняемых для извлечения результата.

Таким образом, использование представленного типа индекса – один из путей улучшения производительности в системах баз данных Oracle Database. Однако использование структуры на основе декартова дерева, которая описана в п. 2.2, в Oracle Database позволяет избегать предварительной обработки данных, что приводит к улучшению оценок временной сложности. Более подробный сравнительный анализ оценок временной сложности построения дерева в реляционной структуре данных Oracle Database и структуры из п. 2.2 описан в следующем параграфе.

В Oracle Database на этапе построения базы данных реализован механизм материализованных представлений (автоматическая перезапись данных) [132, 158], т.е. данные постоянно находятся в синхронном состоянии со всеми таблицами, на которые они ссылаются. Это сказывается на общей производительности, т.к. транзакция, меняющая таблицу, реконструирует и результат материализованного представления [162].

При выполнении поиска в Oracle Database механизм материализованных представлений позволяет сохранять результаты сложных SQL-запросов [93], что позволяет снизить временную задержку на анализ данных в таблице при исполнении таких запросов и выборку готовых результатов их материализованного представления. При этом данный механизм в структуре данных блокирует все данные, от которых зависит результат выполнения запроса. Особенно сильно это проявляется при объединении нескольких таблиц, потому как блокируются все строки таблиц влияющих на результат запроса [138].

Таким образом, при использовании сложных запросов с объединениями таблиц при построении материализованных представлений, может образоваться большое число блокировок [32], которые приводят к снижению производительности и увеличению оценки временной сложности. Для повышения производительности Oracle Database создаются не только материализованные представления, но и на уровне программного обеспечения операций ввода-вывода изменяется доступ к данным [50].

При построении декартова дерева, в представленной в п. 2.2 структуре, не требуется этап интерпретации и разбора данных на типы, что позволяет значительно ускорить обработку входных данных относительно Oracle Database. Также все данные в порядке расположения, в предложенной в п. 2.2 структуре, представлены в двоичном коде как единое числовое значение. В результате, в такой структуре существенно ускоряется работа основных операций над данными: поиска, вставки, удаления [87].

Согласно результатам синтетических тестов, которые производились с помощью TPC-С Benchmark [95, 100] реальная работа базы данных Oracle Database при небольшом объеме входных данных и при выполнении идентичных операций уступает в производительности таким структурам данных как MS SQL Server или MySQL (рис. 12). Это связано с тем, что Oracle Database относится к структурам промышленного уровня [69, 126, 164], предполагающие работу с большими объемами данных. Подробнее такие структуры с оценками временной сложности рассмотрены ниже.

Из анализа синтетических тестов TPC-С Benchmark (рис. 12) следует, что производительность реляционных структур увеличивается при возрастании обрабатываемого объема данных.

Из рис. 12 следует, что лидерами в производительности являются Oracle Database и IBM DB2. Тест показывает максимальную пиковую производительность, т.к. вся таблица помещается в оперативной памяти и доступ к элементам таблицы обычно быстрый. Однако в работе, которая предусматривает одновременно различные по характеру нагрузки на структуру данных, производительность Oracle Database значительно снижается. Обратной стороной такой производительности является конкретная область применения рассматриваемой структуры данных.

Часто при поисковом запросе в структуре Oracle Database для обработки большого объема элементов требуется распознать образ в упорядоченном потоке данных. При этом неизвестно как много строк назад или вперед в результирующем наборе следует просмотреть. Для решения этой задачи в Oracle Database анализ выполняется с помощью функций LAG и LEAD [150] – множеством вынужденных проходов по таблице данных, требующих большое число рефлексивных соединений и повторных сортировок. Эти функции возвращают значение выражения, вычисленного для предыдущей строки (LAG) или следующей строки (LEAD) результирующего набора соответственно.

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

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

В аспекте сравнения отметим, что в предложенной в п. 2.2 структуре весь объем входных данных посредством параллелизма обрабатывается за единичное время. Причем единичная оценка времени обработки элементов формально сохраняется при неограниченном росте их числа. Эффективность достигается за счет исключения горизонтальных шагов, как в промежуточной, так и в завершающей стадии обработки всех элементов структуры данных. При этом в структуре из п. 2.2 отсутствуют вынужденные проходы [85] при обработке входных данных, в отличие от аналогичной операции в Oracle Database.

Сравнение выполнения базовых операций с известными методами

Ниже выполнено сравнение оценок временной сложности основных операций - поиска, вставки и удаления элемента в алгоритмах двоичного дерева с предложенным методом параллельного построения двоичного дерева из п. 3.1, реализуемый с единичной оценкой временной сложности и реализуемый с логарифмической оценкой временной сложности.

По алгоритму из [40] для поиска элемента в двоичном дереве в качестве параметра используется корень дерева и маска. Для рассматриваемой операции в каждом узле двоичного дерева выполняется сравнение значения элемента с заданной маской. Если выявляется совпадение, то указывается ссылка на текущий узел.

Пусть необходимо проверить, есть ли узел с элементом К в двоичном дереве Р, и если он имеется, то указать ссылку на этот узел. Тогда по алгоритму из [40] выполняются следующие действия. Если двоичное дерево Р - пустое, то сообщается, что искомый узел не найден. Иначе выполняется сравнение К со значением ключа корневого узла X. Если К = Х, то указывается ссылка на данный узел. Если же К X, то рекурсивно выполняется поиск элемента К в правом поддереве двоичного дерева Р. В случае К Х, рекурсивно искать ключ К в левом поддереве Р.

Узлы двоичного дерева, в которых выполняется поиск, образуют нисходящий путь от корня и временная сложность представленной операции определяется количеством элементов обхода: 2 + 21+22 + ...+2riog 1 N. Отсюда т(\) NT = 0(N) , где т - время сравнения двух элементов, N - число элементов дерева [36].

Поиск элемента в двоичном дереве по параллельному алгоритму единичного порядка из п. 3.1 (теорема 3.2) выполняется на основе синхронных и взаимно независимых сравнений всех элементов, используя максимально параллельную сортировку подсчетом по матрице сравнений с временной сложностью

Сравнивая поиск в двоичном дереве по алгоритму из [40] и поиск по параллельному алгоритму из п. 3.1 (теорема 3.1), получим ускорение =0(N) за счет увеличения числа процессорных элементов в =0\N 2, организованных таким образом, что все процессоров исполняют векторные команды, за даваемые общим для всех устройств управлением, причем каждый процессорный элемент работает с отдельным элементом вектора [108].

Операция поиска по алгоритму с логарифмической оценкой из п. 3.1 на основе максимально параллельной сортировки и последовательности параллельных N2 шагов вычисления индексов корней поддеревьев выполняется на — процессорах с логарифмической оценкой временной сложности Т — =0(IOR2N), где N - число входных элементов двоичного дерева. Соответственно, ускорение 7Vln2 = O(N) за log27V v счет увеличения числа процессорных элементов в O(N2).

Оба подхода по алгоритмам из п. 3.1 позволяют достигать абстрактно предельного ускорения операции поиска элемента по сравнению с алгоритмом из 132 [40]. При этом ускорение в системах матричного типа может быть больше, чем в конвейерных за счет отсутствия шагов загрузки [108], однако асимптотические оценки в обоих случаях выравниваются до 0(N) .

Операция добавления элемента в двоичное дерево по алгоритму из [40] выполняется аналогично поиску, только в случае отсутствия у элемента дочернего узла на это (пустое) место вставляется добавляемый элемент.

Пусть необходимо вставить элемент К в двоичное дерево Р. Тогда по алгоритму из [40] выполняются следующие действия. Если двоичное дерево Р - пустое, то оно заменяется на дерево, имеющее один корневой узел с элементом К. Если дерево Р не пустое, тогда выполняется сравнение элемента К с элементом корневого узла X. При этом, если К Х, то вставляемый элемент к добавляется к правому поддереву двоичного дерева Р; если К X, то вставляемый элемент К добавляется к левому поддереву двоичного дерева Р. В случае равенства К = Х, выполняется замена текущего узла новым (вставляемым) элементом К.

При добавлении элемента в двоичное дерево по алгоритму из [40] образуется нисходящий путь от корня и временная сложность представленной операции, по аналогии с операцией поиска [40], определяется количеством элементов обхода: 2 + 21 + 22 +... + 2Гк 2"1-1 N. В этом случае т(\) Nx = 0(N) , где т - время сравнения двух элементов, N - число элементов дерева [36].

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

Для операции вставки можно повторить оценки поиска, и ускорение составит 0(N).

Пусть по алгоритму из [40] необходимо удалить узел с элементом К из двоичного дерева Р, имеющее корень п, содержащий элемент X. Тогда если двоичное дерево Р - пустое, то процесс удаления прекращается. Иначе сравнивается элемент К с элементом X корневого узла п. В случае если К Х, удаляется элемент К из правого поддерева двоичного дерева Р; если К X, удаляется элемент К из левого поддерева двоичного дерева Р. В случае равенства К = Х, то возможны три случая. Если узел не имеет дочерних узлов, то у родительского узла указатель заменяется на нулевой (null), а текущий узел с элементом К - удаляется. Если у узла имеется один дочерний узел, то создается новая связь между родителем удаляемого узла и дочерним узлом, и значение элемента ребенка ставится вместо значения корневого узла. Если узел имеет два дочерних узла, то ищется следующий за ним элемент и перемещается на место удаляемого узла, в этом случае у этого элемента не будет левого потомка.

Операции удаления элемента в двоичном дереве по рассматриваемому алгоритму из [40] выполняются за T(I) NT = O(N), где т - время сравнения двух элементов, N - число элементов дерева [36], поскольку по алгоритму из [40] при удалении выполняется последовательный анализ каждой вершины двоичного дерева, тем самым образуется нисходящий путь от корня и временная сложность представленной операции, определяется количеством элементов обхода:

Нетрудно видеть, что и в этом случае применение обоих параллельных алгоритмов п. 3.1 для идентификации удаляемого элемента путем синхронных сравнений даст ускорение 0(N) ценой увеличения числа процессорных элементов в O(N 2).

По алгоритму из [118] для вставки элемента К в двоичное дерево необходимо сначала выполнить предварительную обработку всех N элементов и затем идентифицировать все вхождения для установки т меток. При каждой вставке элемента выполняется пересчет подмножества т меток. Для элементов, которые не встречаются на этапе вычисления меток с помощью сортировки и удаления избыточности, назначается новый ярлык.

Общая оценка временной сложности вставки элемента в двоичное дерево по алгоритму из [118]: r(i?) = 0(log2iV-log2m), где N - число элементов двоичного де N рева, т - подмножество меток, R = число процессорных элементов.

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

Оценка временной сложности выполнения поиска в двоичном дереве по алгоритму из [118] такая же, как оценка вставки: T(R) = o(iog2N-log2m), где N - ко личество элементов двоичного дерева, т - подмножество меток, R = число процессорных элементов.

Операция удаления в двоичном дереве по алгоритму из [118] не предусматривается.

Оценки ускорения с учетом взаимной независимости разрядных преобразований при выполнении операций сравнения

При использовании поразрядно-параллельного метода сравнения из п. 1.3 и дополнительно п. 1.4 представленные в табл. 3.3 – 3.5 значения ускорений увеличатся в 0{п), где п - число разрядов данных.

Согласно леммам 1.3, 1.4, которые не учитывают время выделения старшего ненулевого разряда слова, каждое сравнение п -разрядных слов при затрате п параллельных компонентов выполняется за время т(п) = 0(і). В то же время последовательное по разрядам сравнение оценивается как г(і) = 0{п).

Число параллельных компонентов устройства сравнения пропорционально О (п) - числу разрядов двоичного представления меньшего по длине из сравниваемых слов.

На этой основе с учетом разрядной обработки алгоритм из [152] работает за время т(і) = о(ш), а метод из п. 3.1 (теорема 3.2) с применением поразрядно параллельного сравнения - за время где п - число разрядов сравни ваемых слов. Отсюда суммарное ускорение составит — =0{ш) ценой затраты o(N2n) параллельных процессорных элементов, включая разрядные компоненты.

Аналогично, алгоритм из [125] работает за время f(l) = O{N2), а с учетом разрядной обработки - за время f (l) = o(N2n). По отношению к этому алгоритму при использовании поразрядно-параллельного сравнения достигается ускорение — ценой той же затраты оборудования - о(ы2п) параллельных компонентов.

Полиномиальный алгоритм [16] работает за время T(\) = O(N3), с учетом разрядной обработки - за время f(l) = о(ыъп). По отношению к этому алгоритму при использовании поразрядно-параллельного сравнения достигается ускорение = о(ыъп) ценой той же затраты оборудования - О (N2n), п - число разрядов слова.

LCRS-алгоритм [24] работает за время т(\) = о(м2), с учетом разрядной обработки - за время Т(\) = о(м2п). По отношению к этому алгоритму при использо вании поразрядно-параллельного сравнения достигается ускорение ценой той же затраты оборудования - o(N2n), п - число разрядов слова.

Алгоритм на основе шаблонов (1991) [118] работает за время f(\)=0{\D\hg2D), с учетом разрядной обработки - за время T(\)=o{n\D\hg2D). По отношению к этому алгоритму при использовании поразрядно-параллельного сравнения достигается ускорение 0(4Dlog2 ) ценой той же затраты обору дования - п - число разрядов слова.

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

Относительно алгоритма из [152], работающего с оценкой f(l) = o(Nn), где учитывается последовательное по разрядам бинарное сравнение слов, метод из п. 3.1 (теорема 3.1) с применением поразрядно-параллельного сравнения будет работать с оценкой T(N2n)=o(log2N), п, по-прежнему, - число разрядов сравнива емых слов, суммарное ускорение составит

Аналогично, для алгоритма [125] ускорение составит - = 0 — = o(nN 2 In 2).

Khg2Nj Для полиномиального алгоритма [161 ускорение — = 0\ = 0\nN 3 In 2).

LCRS-алгоритм [24] работает за время т(\) = о{м2), где учитывается последовательное по разрядам бинарное сравнение слов, метод из п. 3.1 (теорема 3.1) с применением поразрядно-параллельного сравнения будет работать с оценкой T(N 2 n)=o(log2N). Суммарное ускорение составит - = о\ —\ = o(nN 2\п2). Затра v / v 2 ) т i0g2 J v / ты оборудования составят 0(N2n) параллельных процессорных элементов, включая разрядные компоненты.

Алгоритм на основе шаблонов [118] работает за время f(n)=o{n\D\hg2D), где D - мощность словаря шаблонов. В оценке учитывается последовательное, поразрядное сравнение слов. Метод из п. 3.1 (теорема 3.2) будет работать за время T(N 2 n)= o(log 2 N). Тогда суммарное ускорение составит Т- = /"№« д1. v ; v Т { hg2N J

По сравнению с предложенным последовательным алгоритмом построения дерева п. 3.1.2 (теорема 3.3), достигаются следующие оценки ускорения.

Алгоритм из [152], работающего с оценкой f(l) = o(Nn), где учитывается последовательное по разрядам бинарное сравнение слов, метод из п. 3.1.2 (теорема 3.3) с применением поразрядно-параллельного сравнения будет работать с оценкой T(n) = 0(Nlog2N), п - число разрядов сравниваемых слов, суммарное ускорение составит Затраты оборудования составят 0(п) парал yTj \og2N j лельных процессорных элементов, включая разрядные компоненты.

Аналогично, для алгоритма [125] в рассматриваемом случае ускорение со ставит число разрядов сравниваемых слов, при соответственных затратах О (п) процессорных (разрядных) элементов.

Для полиномиального алгоритма [16] ускорение в рассматриваемом случае число разрядов сравниваемых слов, при соответственных составит затратах О (п) процессорных (разрядных) элементов.

LCRS-алгоритм [24] работает за время f(l) = o{nN2), где учитывается последовательное по разрядам бинарное сравнение слов, метод из п. 3.1.2 (теорема 3.3) с применением поразрядно-параллельного сравнения будет работать с оценкой

T(n) = o(hg2N). Суммарное ускорение составит - = оШ. Затраты оборудования со ставят О (п) параллельных процессорных элементов, включая разрядные компоненты. Алгоритм на основе шаблонов [118] работает за время Т(l)=o(/?Z)log2Z)), где D - мощность словаря шаблонов. В оценке учитывается последовательное, поразрядное сравнение слов. Метод из п. 3.1.2 (теорема 3.3) будет работать за время т(п) = 0(loo,7 N).