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

• Чабанюк, Денис Андреевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Чабанюк, Денис Андреевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ИСПОЛЬЗОВАНИЕ ВЗАИМНО НЕЗАВИСИМЫХ РАЗРЯДНЫХ ПРЕОБРАЗОВАНИЙ НА ОСНОВЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ДАННЫХ ПРИ ВЫПОЛНЕНИИ ОПЕРАЦИЙ СРАВНЕНИЯ ДЛЯ ИНФОРМАЦИОННОГО ПОИСКА

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

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

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

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

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

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

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

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

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

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

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

1.8. Выводы

ГЛАВА 2. ДЕТЕРМИНИРОВАННОЕ ПОСТРОЕНИЕ ДЕКАРТОВА ДЕРЕВА С ЛОГАРИФМИЧЕСКОЙ ВРЕМЕННОЙ СЛОЖНОСТЬЮ ДЛЯ УСКОРЕНИЯ ОБРАБОТКИ ДАННЫХ

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

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

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

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

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

2.6. Выводы

ГЛАВА 3. МЕТОДЫ МИНИМИЗАЦИИ ВРЕМЕННОЙ СЛОЖНОСТИ ПОСТРОЕНИЯ ДВОИЧНОГО ДЕРЕВА НА ОСНОВЕ УСТОЙЧИВОЙ АДРЕСНОЙ СОРТИРОВКИ

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

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

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

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

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

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

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

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

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

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

3.6. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

173

Приложение 1. Последовательное моделирование процесса построения

декартова дерева

Приложение 2. Акты об использовании результатов диссертационной работы

Введение диссертации (часть автореферата) на тему «Преобразование информационных данных и двоичных структур с минимизацией временной сложности на основе алгоритмов сортировки»

ВВЕДЕНИЕ

Актуальность проблемы. Стремительное развитие компьютерных технологий [5, 102] и создание высокопроизводительных микропроцессоров [25, 106] привело к тому, что доминирующими тенденциями разработок многопроцессорных вычислительных систем на данный момент являются системы, обладающие массовым параллелизмом, которые содержат тысячи параллельно функционирующих процессоров, соединенных между собой соответствующей коммутационной системой. Современные высокопроизводительные вычислительные системы являются мультиархитектурными, в которых характерно введение дополнительных специализированных ресурсов, а также им свойственна иерархическая организация данных.

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

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

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

В пределах этой идеи современными авторами предложены и реализованы [32, 52, 68, 161] различные способы обработки информации, в частности - параллельные, реализуемые под конкретные задачи. Однако наличие множества исследований не снижает актуальность создания эффективных, обладающих достаточной простотой программной реализации алгоритмов для организации и функционирования параллельных структур данных. В связи с этим, актуализируются исследования, связанные с разработкой новых теоретических основ и методов построения высокопроизводительных многопроцессорных параллельных вычислительных систем, в частности параллельных структур данных.

Параллельные вычислительные системы - физические компьютерные, либо программные системы, которые реализуют любым способом параллельную обработку структур данных на множестве вычислительных узлов [120, 141].

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

Современная научно-техническая революция немыслима без широкого применения различных автоматизированных структур данных [39, 40, 47]. Целью современных структур данных является устранение недостатков классических структур [12, 37]: избыточности, ухудшения оценок временной сложности, снижения производительности и т.д. Современные структуры данных [32, 69, 139] являются многозадачными и многопользовательскими, при этом они, как правило, имитируют параллельное исполнение задач посредством механизма прерываний на основе программно-аппаратных средств параллельной обработки запросов [9].

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

повышению эффективности работы со структурами данных тесно связаны с особенностями задач, решаемых в системах [54].

Реальные пути повышения эффективности ЭВМ для структур данных известны [39]: повышение быстродействия элементов, усовершенствование программного обеспечения, развитие логической структуры, архитектуры машин.

По оценкам специалистов [46], за счет увеличения быстродействия электронных элементов можно повысить эффективность ЭВМ для структур данных всего на один-два порядка. Усовершенствование программного обеспечения направлено в основном на ускорение подготовки задач, таких как автоматизация программирования, применение проблемно-ориентированных языков, а не их решения.

Логическая структура современных баз данных описывает практическое применение компонентов логической архитектуры для реализации работоспособной системы. Ее развитие, с одной стороны, способствует более полному использованию ресурсов вычислительного комплекса и вследствие этого увеличению эффективности. С другой стороны, сложное программное обеспечение для системы баз данных, требует для своих собственных целей значительного расхода памяти и времени, что снижает общую эффективность [105].

Наиболее важным резервом повышения эффективности вычислительных систем для работы со структурами данных является развитие архитектуры ЭВМ [57, 106, 110]. Это обусловлено тем, что большинство задач, решаемых в структурах баз данных, носят узконаправленный характер, а также тем, что исходная информация в базах данных организована в определенные структуры (массивы, таблицы и т.д.). При решении таких задач на универсальных машинах классической архитектуры со стандартным набором основных команд, оперирующих последовательно со скалярными величинами, невозможно использовать специфический характер информации и видов обработки в структурах данных.

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

гии интегральных схем создает реальные предпосылки для проектирования и производства машин новой архитектуры. Например [66], степень интеграции сверхбольшой интегральной схемы (СБИС) каждые 1-2 года увеличивается вдвое, а ее стоимость уменьшается ежегодно примерно на 30%, что позволяет выполнять весьма сложную аппаратуру малых габаритов и с низкой стоимостью. В среднем внедрение лидерами индустрии новых техпроцессов по Международному плану по развитию полупроводниковой технологии (International Technology Roadmap for Semiconductors, ITRS) [168] происходит каждые 2 года, при этом обеспечивается удвоение количества транзисторов на единицу площади: 45 нм (2007), 32 нм (2009), 22 нм (2011), 14 нм (2014), освоение 10 нм процессоров планируется к концу 2018 года [174].

В идейном, структурном отношении все выпускаемые в настоящее время микропроцессорные наборы остаются машинами классической архитектуры последовательного действия. Большинство их - сравнительно простые устройства, в лучшем случае приближаются по характеристикам к мини-машинам третьего поколения. При этом структурные решения, которые используются в машинах, практически реализуемых на современных элементах, не позволяют достичь больших возможностей, которые заложены в новой технологии [25]. Потенциал для улучшения архитектуры ЭВМ за счет увеличения аппаратного уровня, специализации отдельных устройств, применения массовой, групповой, параллельной обработки становится реальным [43]. Например [15], массово-параллельная система с КАИС-структурой (корпоративная автоматизированная информационная система) состоит из отдельных 10б узлов (ядер, процессорных элементов, элементарных машин и т.д.), имеет хорошую масштабируемость, в которой отсутствует необходимость в потактовой синхронизации процессоров.

Развитие архитектуры ЭВМ обеспечивает новые возможности построения алгоритмов, стимулирует разработку более совершенных математических подходов к решению задач [106]. Основное место среди новых решений в архитектуре компьютеров занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

Разновидности параллельной и конвейерной обработки информации.

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

Существуют различные способы реализации параллельных вычислений [120]: параллелизм на уровне битов, параллелизм на уровне инструкций, параллелизм данных и параллелизм задач.

Параллелизм на уровне битов основан на увеличении размера машинного слова, в результате чего уменьшается количество операций процессора для обработки действий над переменными, размер которых превышает длину машинного слова. Например [159], если на 8-битном процессоре необходимо сложить два 16-битных целых числа, то для этого вначале нужно сложить нижние 8 бит чисел, затем сложить верхние 8 бит и к результату их сложения прибавить значение флага переноса. В результате 8-битному процессору необходимо обработать три инструкции, а 16-битному процессору - одну инструкцию. На современном этапе для этих целей используются 64-битные процессоры [110].

Развитие архитектуры и технологии построения процессов также ориентировано на увеличение числа операций за один такт процессора, т.е. на распараллеливание операций. Главными вершинами развития архитектуры процессоров стали гиперконвейеризация (технология NetBurst [57, 59]), суперскалярность (архитектуры x86, x64 [101], MIPS [137], ARM [140]), неупорядоченная модель обработки (архитектура VLIW [123]), векторное процессирование (технология SIMD [129, 149]). Все ступени развития технологий построения процессоров ориентированы на повышение степени параллелизма исполнения операций.

В настоящее время мощные серверы систем баз данных представляют собой мультипроцессорные системы, а в процессорах активно используется параллелизм уровня потоков [50].

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

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

Развитие параллелизма на уровне инструкций в архитектуре компьютеров происходило в 80-90-е гг. прошлого века [7]. Современные методики повышения данного параллелизма основаны на использовании процессоров класса SIMD, векторного процессирования, матричных процессоров, архитектуры УЬГ^

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

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

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

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

При параллелизме задач, подразумевается, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач, и каждый процессор загружается своей собственной подзадачей. Такой параллелизм применяется в процессорах класса М1МО [175].

В последнее время, из-за физических ограничений на рост тактовой частоты процессоров, параллельные вычисления стали доминирующей парадигмой в архитектуре компьютеров, в основном в форме многоядерных процессоров [5, 6, 35].

Для совершенствования однопроцессорных систем и обеспечения одновременного выполнения потока разнородных задач выделяют следующие разновидности параллельной обработки информации [4, 56, 99]: многозадачность, параллелизм независимых ветвей, параллелизм объектов.

Существует несколько вариантов обеспечения многозадачности [14]. При однопроцессорной работе схемы обработки потока разного рода задач отличаются в зависимости от потока задач и возможных решений по организации операций ввода-вывода. В этом случае [106] каждая задача получает конкретный ресурс процессора на определенное время (квант), и после прерывания по интервальному таймеру операционная система передает управление следующей задаче (рис. 1). Такой подход не приводит к значительному сокращению общего времени обработки.

Рис. 1. Многозадачность в режиме квантования времени.

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

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

В многопроцессорной обработке присутствует несколько обрабатывающих устройств (арифметико-логических устройств или процессоров), позволяющих реализовать параллельную обработку заданий. Существует несколько вариантов реализации [9, 30]. Например [106], многомашинная система (рис. 2), использующая раздельную оперативную память, т.е. несколько ЭВМ (процессор и оперативная память) находятся под общим управлением диспетчера задач, который распределяет поток заданий.

Рис. 2. Многомашинная система с параллельной обработкой заданий.

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

Изучение проблемы параллелизма ветвей [9] показывает, что для параллельной реализации этапов необходимо выполнение следующих условий: отсутствие связи данных, т.е. результаты одного этапа не являются входом другого; отсутствие связей по управлению - один этап не передает управление другому (выполняется принцип единственности присваивания); отсутствие общих ячеек памяти по записи - этапы не производят запись по одному и тому же адресу памяти.

Следующим способом распараллеливания в многопроцессорной обработке является параллелизм объектов [2], при котором различные по значениям, но однородные по структуре данные подвергаются одинаковой обработке на многопроцессорной системе. Такая обработка реализуется как в глубину, так и в ширину.

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

Рис. 3. Параллелизм объектов с реализацией в ширину.

Потребность в решении крупных вычислительных задач с более высокой скоростью привела в 60-е годы прошлого века к необходимости разработки ЭВМ с высокоскоростной параллельной обработкой данных, которая реализуется в глубину.

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

1 этап обработки

iэтап обработки

N этап обработки

N-часть данных

^ v J

1-я часть данных _

Процессор 1

Процессор N

время

Рис. 4. Параллелизм объектов с реализацией в глубину.

Первыми машинами с конвейерной обработкой потока данных являются UNIVAC LARC и IBM 7030 [106, 145]. В области конвейерных суперкомпьютеров первой была фирма Control Dada Corporation, которая создала ЭВМ CDC-6600 (1964) и CDC-7600 (1969), впоследствии объединившихся в семейство кибер-физических систем (CPS) [110]. Конвейерные принципы были использованы также в машинах CDC STAR-100 (1971) и Texas Instruments ASC (1973). Наиболее полно принципы конвейерной обработки нашли свое отражение в архитектуре CRAY процессора [160].

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

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

блока. В результате все блоки конвейера работают одновременно и выполняют N разных ступеней обработки потока данных для любых п пар операндов.

Если конвейер обработки потока данных сконструирован таким образом, что время прохождения одной пары операндов в арифметико-логическом устройстве и конвейере одинаково и равно Т, а количество п пар операндов, последовательно проходящих через конвейер достаточно велико. В этом случае в исходном блоке арифметико-логического устройства на исполнение одной операции потребуется время Т. На N -звенном конвейере на обработку множества операций, состоящих из п пар операндов, потребуется время (п + NТ^, где N - количество сегментов конвейера, п - число пар операндов [98]. При этом на одну операцию затратится

Т (п + т ^ N Т

время —-. При соотношении — время стремится к —, т.е. возникает ускорение

nN п п

вычислений приблизительно в N раз, где N - количество сегментов конвейера.

Такая оценка вызвана тем, что в конвейерных процессорах выбор (п + N) блока, к которому производилось последнее обращение, осуществляется путем последовательного перебора ячеек с адресами (п +1), (п + 2),..., (п + ^ -1)). При этом время доступа к ячейке Т = ^ - 1)т , где т - время обращения к одному сегменту конвейера [103].

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

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

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

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

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

Конвейер в ширину [12] имеет аппаратную реализацию определенной операции в качестве набора конвейерных сегментов (рис. 5). Ввиду того, что некоторые ступени машинных команд совпадают, то подобная реализация является ап-паратно избыточной. Однако конвейер в ширину позволяет достичь ускорения процессора для ряда определенных задач.

Рис. 5. Структура конвейера в ширину.

Конвейер в глубину [12] предполагает последовательное объединение конвейерных блоков в единый сегмент (рис. 6). Вместе с операндами команды устройство управления передает конвейеру значение регистра маски, содержащего единицы в тех позициях, которые соответствуют необходимым для данной операции конвейерным блокам.

Сложение или вычитание порядков Выравнивание -^ Умножение Деление Нормализация

мантисс мантисс мантисс

Рис. 6. Структура конвейера в глубину.

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

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

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

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

Существуют другие модели параллельного программирования с применением разных средств распараллеливания (OpenMP, MPI, POSIX Threads, Windows API), которые отличаются гибкостью, механизмами взаимодействия между задачами, уровнем параллелизма, зернистостью, масштабируемостью, поддержкой модульности и т.д. [55, 107].

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

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

Исследования показали [55, 104, 107], что потенциальный параллелизм в научных и технических прикладных программах достигает сотен и тысяч команд за один такт, однако реально достижимый параллелизм значительно меньше и составляет 10-20 команд за один такт. Такое ограничение вызвано временем ожидания результатов операции последующей операцией, использующей эти результаты в качестве операндов, либо ожиданием прихода данных из памяти.

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

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

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

Список литературы диссертационного исследования кандидат наук Чабанюк, Денис Андреевич, 2018 год

СПИСОК ЛИТЕРАТУРЫ

1. Абалакин И.В., Бахвалов П.А., Горобец А.В. Параллельный программный комплекс NOISETTE для крупномасштабных расчетов задач аэродинамики и аэроакустики // Вычислительные методы и программирование. - 2012. - Т. 13. -№ 3. - C. 110-125.

2. Аладьев В.З. Классические однородные структуры. Клеточные автоматы. -Гродно: ГрГУ, 2009. - 535 с.

3. Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений. Гриф УМО университетов РФ. - М.: ИНТУИТ, 2014. - 320 с.

4. Алексеев П.С. Многопоточное программирование. Учебное пособие. - СПб: ИТМО, 2010. - 123 с.

5. Аноприенко А.Я. Модели эволюции компьютерных систем и средств компьютерного моделирования // Материалы пятой международной научно-технической конференции «Моделирование и компьютерная графика» 24-27 сентября 2013 года. Донецк. - 2013. - C. 403-423.

6. Антонов А.С., Воеводин В.В., Одинцов И.О. Методика сертификации учебных курсов и программ в области «Суперкомпьютеры и параллельные вычисления» // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2014. -№ 2-1. - C. 13-18.

7. Ахо А., Джон Э., Хопкрофт Д. Структуры данных и алгоритмы. - М.: Виль-ямс, 2016. - 400 с.

8. Ахо А., Ульман Д., Хопкрофт Д. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

9. Бас А.А., Горохов М.М., Корепанов А.В. Технология распараллеливания вычислений при моделировании трехмерных течений // Вестник Ижевского государственного технического университета. - 2007. - № 2. - C. 3-7.

10. Берлин В.Г. Параллельно-рандомизированные стратегии поиска // Автоматика и телемеханика. - 1972. - Т. 33. - № 3. - C. 398-403.

11. Васильев П.В., Михелев В.М. Параллельные алгоритмы оптимизации границ карьеров по методу псевдопотока на модели данных со структурой октодере-ва // Научные ведомости БелГУ. Сер. Экономика. Информатика. - 2016. -Т. 9(230). - № 38. - С. 123-128.

12. Вирт Н. Алгоритмы и структуры данных. - М.: ДМК Пресс, 2010. - 272 с.

13. Воеводин В.В., Воеводин В.В. Параллельные вычисления. - СПб: БХВ-Петербург, 2002. - 608 с.

14. Воеводин В.В. Некоторые машинные аспекты распараллеливания вычислений / М., 1981. - 10 с. - Деп. в ВИНИТИ 16.10.1981, № 10 - В81-10/21.

15. Воробьев В.А., Юфрякова О.А. Мелкозернистые локально-параллельные алгоритмы // Вестник Северного (Арктического) федерального университета. Серия: Естественные науки. - 2013. - № 1. - С. 110-115.

16. Гавриков А.В. Т-неприводимые расширения для ориентированных бинарных деревьев // Компьютерные науки и информационные технологии. - 2016. -№ 6. - С. 123-125.

17. Гасанов Э.Э. Теория хранения и поиска информации // Фундаментальная и прикладная математика. - 2009. - Т. 15. - № 3. - С. 47-73.

18. Герасимов М.А. Реализация алгоритма Хаффмана с заданной длиной разбиений входного потока на машинах Тьюринга с почти линейным временем // Вестник Санкт-Петербургского университета. - 2010. - Т. 10. - № 3. - С. 100-105.

19. Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем. - Нижний Новгород: ННГУ им. Н.И. Лобачевского, 2010. - 421 с.

20. Гергель В.П. Теория и практика параллельных вычислений: учеб. пособие. -М.: Бином, 2007. - 423 с.

21. Головченко Е.Н. Параллельный пакет декомпозиции больших сеток // Математическое моделирование. - 2011. - Т. 23. - № 10. - С. 3-18.

22. Горобец А.В. Параллельная технология численного моделирования задач газовой динамики алгоритмами повышенной точности // Журнал вычислительной математики и математической физики. - 2015. - Т. 55. - № 4. - С. 641-652.

23. Горяинов С.И. Перестройка бинарных деревьев в алгоритме Хаффмана // Программные системы и вычислительные методы. - 2014. - Т. 4. - № 4. - C. 464-471.

24. Гриценко Н.С., Белов Ю.С. Построение двоичного дерева на основе модифицированной схемы хранения деревьев общего вида «left child»-«right sibling» (LCRS) // Инженерный журнал: наука и инновации. - 2014. - № 3. - C. 75-84.

25. Гук И.А. Мультиядерные процессоры компании Texas Instruments семейства 66AK2X // Вестник Электроники. - 2015. - № 4. - C. 18-23.

26. Дейт С.Д. Введение в системы баз данных. - М.: Вильямс, 2005. - 1328 с.

27. Дейт С.Д. Руководство по реляционной СУБД DB2. - М.: Финансы и статистика, 1988. - 320 с.

28. Жабицкая Е.И., Земляная Е.В., Киселев М.А. Исследование структуры однослойных везикул DMPC с использованием параллельного алгоритма асинхронной дифференциальной эволюции // Вестник Российского университета дружбы народов. Серия: Математика, информатика, физика. - 2014. - Т. 2. - C. 253-258.

29. Иванова А.С. Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску: Дисс. ... канд. техн. наук. - Таганрог: ФГБОУ ВПО «Таганрогский государственный педагогический институт имени А.П. Чехова», 2013. - 158 с.

30. Ильин В.П. О вопросах распараллеливания крыловских итерационных методов // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. - 2013. - Т. 2. - № 3. - C. 48-62.

31. Илюшечкин В.М. Основы использования и проектирования баз данных: учебник для академического бакалавриата. - М.: МИЭТ, 2014. - 213 с.

32. Кайт Т., Дарл К. Oracle для профессионалов. Технологии и решения для достижения высокой производительности и эффективности. - Москва: Вильямс, 2015. - 960 с.

33. Карцев М.А. Арифметика цифровых машин: учеб. пособие. - М.: Наука, 1969. - 576 с.

34. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. - М.: Радио и связь, 1981. - 358 с.

35. Киселев В.К., Оболенский С.В., Пузанов А.С. Параллельные вычисления в задачах физико-топологического моделирования физических процессов в перспективных полупроводниковых приборах с учетом радиационного воздействия // Журнал радиоэлектроники. - 2014. - № 2. - C. 172-203.

36. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. - М.: Виль-ямс, 2014. - 824 с.

37. Кнут Д. Искусство программирования. Т. 1. Основные алгоритмы. - М.: Виль-ямс, 2015. - 720 с.

38. Козик А.А., Побегайло А.П. Ускорение параллельного поиска в ширину в графах при вычислениях на GPU // Вестник БГУ. Серия 1, Физика. Математика. Информатика. - 2015. - № 2. - C. 102-107.

39. Колдаев В.Д. Структуры и алгоритмы обработки данных. Учебное пособие. Гриф УМО МО РФ. - М.: РИОР, 2014. - 296 с.

40. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: Вильямс, 2013. - 1328 с.

41. Котов В.Е. О связи алгебраических и архитектурных аспектов параллельных вычислений. // Вычислительные процессы и системы: сборник статей. под ред. Г.И. Марчука. - М.: Наука, 1983. - C. 54-80.

42. Кудин А.В., Линев А.В. Архитектура и операционные системы параллельных вычислительных систем. - Нижний Новгород: ННГУ им. Н.И. Лобачевского, 2007. - 73 с.

43. Кулагин В.П. Проблемы параллельных вычислений // Перспективы науки и образования. - 2016. - Т. 19. - № 1. - C. 7-11.

44. Кун С., Госселин К. Структурный синтез параллельных механизмов. - М.: ФИЗМАТЛИТ, 2012. - 276 с.

45. Курносова С.Г. Т-неприводимые расширения полных бинарных деревьев // Вестник Томского гос. ун-та. - 2005. - № 14. - C. 158-160.

46. Лафоре Р. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. - СПб: Питер, 2015. - 704 с.

47. Левитин А. Алгоритмы: введение в разработку и анализ. - М.: Вильямс, 2006. - 576 с.

48. Лиходед Н.А. Методы распараллеливания гнезд циклов. - Минск: БГУ, 2008. - 100 с.

49. Луни К. Oracle Database 10g. Полное справочное руководство. В 2-х томах. -СПб: Питер, 2006. - 1500 с.

50. Льюис Д. Ядро Oracle. Внутреннее устройство для администраторов и разработчиков баз данных. - М.: ДМК Пресс, 2015. - 372 с.

51. Маннинг Х., Рагхаван П., Шютце Х. Введение в информационный поиск. -М.: Вильямс, 2011. - 520 с.

52. Миллсап К., Хольт Д. Oracle. Оптимизаци производительности. - СПб: Символ-Плюс, 2006. - 464 с.

53. Михайлов Б.М., Халабия Р.Ф. Классификация и организация вычислительных систем: учебное пособие. - М.: МГУПИ, 2010. - 144 с.

54. Могилко А.А. Параллельный алгоритм поиска ближайшей точки в радиусе // Наука и образование. - 2013. - Т. 13. - № 11. - C. 363-382.

55. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. - СПб: БХВ-Петербург, 2002. - 400 с.

56. Нужнов Е.В. Операционные системы: Учебное пособие. Часть 1. Основы операционных систем. - Таганрог: ЮФУ, 2013. - 144 с.

57. Озеров С.Н. Архитектура CPU [Электронный ресурс]. - URL: http://old.computerra.ru/2005/609/233266/ (дата обращения: 11.01.2017).

58. Оппель Э. Изучаем SQL. - М.: НТ Пресс, 2007. - 320 с.

59. Орлов С.А., Цилькер Б.Я. Организация ЭВМ и систем: Учебник для вузов. -СПб: Питер, 2014. - 688 с.

60. «Огас1е СНГ»: начало пути [Электронный ресурс]. - URL: http://www.pcweek.ru/themes/detai1.php?ID=68340 (дата обращения: 02.07.2016).

61. Плетнев А.А. Динамическая база данных, допускающая параллельную обработку произвольных потоков запросов // Интеллектуальные системы. Теория и приложения. - 2015. - Т. 19. - № 1. - C. 117-142.

62. Плетнев А.А. Логарифмическая по сложности параллельная обработка автоматами произвольных потоков запросов к динамической базе данных // Интеллектуальные системы. Теория и приложения. - 2015. - Т. 19. - № 1. - C. 171-212.

63. Повышение доступности Oracle Database 12c [Электронный ресурс]. - URL: http://www.oracle.com/technetwork/ru/database/maximum-availability-wp-12c-1896116-ru.pdf.

64. Подольский В.Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. - 2015. - Т. 4. - C. 189-214.

65. Постников А.И., Вейсов Е.А. Теория автоматов и машинная арифметика: учебное пособие. - М.: ИПЦ КГТУ, 2006. - 326 с.

66. Рабаи Ж.М., Чандракасан А., Николич Б. Цифровые интегральные схемы. Методология проектирования. - М.: Вильямс, 2007. - 912 с.

67. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. -М.: Мир, 1978. - 848 с.

68. Редмонд Э., Уилсон Д. Семь баз данных за семь недель. Введение в современные базы данных и идеологию NoSQL. - М.: ДМК Пресс, 2015. - 384 с.

69. Ржеуцкая С.Ю. Базы данных. Язык SQL. - Вологда: ВоГТУ, 2010. - 159 с.

70. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки: Дис. ... д-ра техн. наук. / ВНТИ Центр, № 05.990.001006. -Таганрог: ТРТУ, 1998. - 546 с.

71. Ромм Я.Е. Вертикальная организация поразрядно-параллельных вычислений в ЭВМ / ТРТИ - Таганрог, 1990. - 57 с. - Деп. в ВИНИТИ 16.07.90, № 3970 - В 90.

72. Ромм Я.Е., Виноградский В.В. Параллельное видоизменение сортировки Хоара // Вестник Таганрогского государственного педагогического института. -2006. - № 1. - C. 55-64.

73. Ромм Я.Е., Заика И.В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ. - 2011. - Т. 47. - № 2. - C. 165-180.

74. Ромм Я.Е., Иванова А.С. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску / ТГПИ -Таганрог, 2012. - 44 с. - Деп. в ВИНИТИ 03.09.2012, № 362-В2012.

75. Ромм Я.Е., Иванова А.С. Метод расширения числового диапазона при вертикальной арифметической обработке // Известия ЮФУ. Технические науки. -2012. - № 2 (127). - С. 35-43.

76. Ромм Я.Е., Иванова А.С. Оценка роста числового диапазона промежуточных слагаемых в методе вертикального группового суммирования без вычисления переноса / ТГПИ - Таганрог, 2010. - 29 с. - Деп. в ВИНИТИ 19.11.10, № 644 - В 2010.

77. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный анализ. - 1998. - № 3. - С. 123-151.

78. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным операциям // Кибернетика и системный анализ. - 1998. - № 6. - С. 146-162.

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

80. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. - 1995. - № 4. - С. 13-37.

81. Ромм Я.Е. Параллельные итерационные методы решения систем линейных алгебраических уравнений с логарифмическим числом итераций. - Таганрог: ТГПИ, 2000. - 537 с.

82. Ромм Я.Е., Чабанюк Д.А. Выделение старшего ненулевого разряда при поразрядно-параллельном способе сравнения слов // Вопросы образования и науки: теоретический и методический аспекты. - 2015. - Т. 5. - С. 124-125.

83. Ромм Я.Е., Чабанюк Д.А. Параллельное построение двоичного дерева на основе сортировки // Материалы Всероссийской научно-практической конференции с международным участием «Аспекты развития науки, образования и модернизации промышленности». - 2017. - Т. 1. - С. 77-84.

84. Ромм Я.Е., Чабанюк Д.А. Параллельное построение двоичного дерева на основе сортировки с логарифмической и единичной временной сложностью // Актуальные вопросы науки: Материалы XXXII Международной научно-практической конференции (10.07.2017). - 2017. - Т. 3. - С. 118-123.

85. Ромм Я.Е., Чабанюк Д.А. Параллельное построение декартова дерева с логарифмической оценкой временной сложности // Современные проблемы науки и образования. - 2015. - № 1.

86. Ромм Я.Е., Чабанюк Д.А. Параллельные алгоритмы обработки структур данных и последовательное моделирование построения декартова дерева / Таганрог. ин-т им. А.П. Чехова (филиал) ФГБОУ ВПО «РГЭУ (РИНХ)». - Таганрог, 2015. - 53 с. - Деп. в ВИНИТИ 16.01.15, № 9 - В2015.

87. Ромм Я.Е., Чабанюк Д.А. Поразрядно-параллельное сравнение ключей в некоторых древовидных структурах данных / Таганрог. ин-т им. А.П. Чехова (филиал) ФГБОУ ВПО «РГЭУ (РИНХ)». - Таганрог, 2014. - 41 с. - Деп. в ВИНИТИ 04.09.14, № 244 - В2014.

88. Ромм Я.Е., Чабанюк Д.А. Построение двоичного дерева на основе параллельной сортировки // Фундаментальные исследования. - 2015. - Т. 8. - № 3. -С. 509-513.

89. Ромм Я.Е., Чабанюк Д.А. Применение метода вертикальной обработки информации к операциям сравнения и поиска / ТГПИ - Таганрог, 2013. - 32 с. - Деп. в ВИНИТИ 20.05.13, № 141 - В2013.

90. Ромм Я.Е., Чабанюк Д.А. Сопоставление оценок временной сложности параллельного построения декартова дерева // II Международные научные чтения (памяти С.Ф. Ковалевской). Сборник статей Международной научно-практической конференции (Москва, 19.09.2016 г.). - 2016. - С. 18-21.

91. Ромм Я.Е., Чабанюк Д.А. Сравнение слов с единичной временной сложностью / ТГПИ - Таганрог, 2013. - 30 с. - Деп. в ВИНИТИ 30.10.13, № 306 - В2013.

92. Ромм Я.Е., Чабанюк Д.А. Сравнение слов с единичной временной сложностью // Известия ЮФУ. Технические науки. - 2014. - № 7 (156). - С. 230-238.

93. Сигалаев Г.В. Сравнение материализованных представлений и аналитических рабочих областей в Oracle Database 11g [Электронный ресурс]. - URL: http://www.mterface.ru/home.asp?art[d=20806 (дата обращения: 26.07.2016).

94. Смирнов А.Д. Архитектура вычислительных систем. - М.: Наука, 1990. - 320 с.

95. Снова о тестах TPC [Электронный ресурс]. - URL: http://www.osp.ru/os/2000/11/178309/ (дата обращения: 01.07.2016).

96. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // Записки научных семинаров Ленинградского. - 1982. - Т. 118. -C. 159-187.

97. Стадник М.В. Иерархические структуры данных и Doctrine [Электронный ресурс]. - URL: http://mikhailstadnik.com/hierarchical-data-structures-and-doctrine (дата обращения: 07.11.2016).

98. Стефен Т. Прошлое, настоящее и будущее распараллеливания .NET-приложений // MSDN Magazine. - 2011. - Т. 10. - № 10. - C. 10-23.

99. Столлингс В. Структурная организация и архитектура компьютерных систем. - М.: Вильямс, 2002. - 896 с.

100. СУБД: проблема выбора [Электронный ресурс]. - URL: http://www.osp.ru/os/2015/01/13045322/ (дата обращения: 01.07.2016).

101. Таненбаум Э., Остин Т. Архитектура компьютера. - СПб: Питер, 2007. - 848 с.

102. Тимченко Л.И. Концептуальная модель многоуровневой параллельно-иерархической сети // Оптико-электронные информационно-энергетические технологии. - 2014. - № 2. - C. 22-28.

103. Угрюмов Е.П. Цифровая схемотехника: учеб. пособие для вузов. - СПб: БХВ-Петербург, 2010. - 816 с.

104. Уильямс Э. Параллельное программирование на C++ в действии. Практика разработки многопоточных программ. - М.: ДМК Пресс, 2012. - 672 с.

105. Ульман Д., Хопкрофт Д., Мотвани Р. Введение в теорию автоматов, языков и вычислений. Руководство. - М.: Вильямс, 2015. - 528 с.

106. Ульянов М.В. Архитектуры процессоров. - М.: МГАПИ, 2002. - 68 с.

107. Федотов И.Е. Модели параллельного программирования. - М.: Солон-Пресс, 2012. - 384 с.

108. Фернбах С. СуперЭВМ. Аппаратная и программная организация. - М.: Радио и связь, 1991. - 320 с.

109. Харченко С.А., Ющенко А.А. Параллельная реализация алгоритма разреженного QR разложения для прямоугольных верхних квазитреугольных матриц со структурой разреженности типа вложенных сечений // Вестник Южно -Уральского государственного университета. Серия: Вычислительная математика и информатика. - 2016. - Т. 5. - № 2. - C. 316-323.

110. Хорошевский В.Г. Архитектура вычислительных систем: Учеб. пособие. -М.: МГТУ им. Н.Э. Баумана, 2008. - 520 с.

111. Храпченко В.М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. - 1967. - № 19. - C. 107-123.

112. Храпченко В.М. Об одном способе преобразования многорядного кода в однорядный // ДАН СССР. - 1963. - Т. 148. - № 2. - C. 296-299.

113. Чернов А.Ф. Ускорение поиска в индексах на основе R-деревьев // Программные продукты и системы. - 2012. - № 2. - C. 46-50.

114. Черноскутов М.А. Параллельная высокопроизводительная обработка графов // Параллельные вычислительные системы. - 2016. - № 1. - C. 736-742.

115. Эйзенберг Э., Мелтон Д. Стандартизация SQL. Следующие шаги // Открытые системы. - 1999. - Т. 1. - № 29. - C. 34-42.

116. Abramson I., Abbey M., Corey M.J. Oracle Database 10g: a beginner's guide. Oracle Database 10g. - New York: London: McGraw-Hill/Osborne; McGraw-Hill, 2004. - 392 p.

117. Aho A.V., Corasick M.J. Efficient string matching: an aid to bibliographic search // Communications of the ACM. - 1975. - Vol. 18. - Efficient string matching. -№ 6. - P. 333-340.

118. Amir A., Farach M. Adaptive dictionary matching // Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. - IEEE, 1991. - P. 760-766.

119. Aragon C.R., Seidel R.G. Randomized search trees. - Algorithmica, 1996. -P. 464-497.

120. Asanovic K., Bodik R. The landscape of parallel computing research: A view from berkeley // Electrical Engineering and Computer Sciences. - 2006. - № 183. -P. 12-66.

121. Badkobeh G., Lehre P., Sudholt D. Unbiased Black-Box Complexity of Parallel Search // Parallel Problem Solving from Nature - PPSN XIII: Lecture Notes in Computer Science. - Springer International Publishing, 2014. - Vol. 8672. - P. 892-901.

122. Badkobeh G., Lehre P.K., Sudholt D. Black-box Complexity of Parallel Search with Distributed Populations // Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII: FOGA'15. - New York, NY, USA: ACM, 2015. -P. 3-15.

123. Bahtat M., Belkouch S. Instruction scheduling heuristic for an efficient FFT in VLIW processors with balanced resource usage // EURASIP Journal on Advances in Signal Processing. - 2016. - Vol. 2016. - № 1. - P. 1-21.

124. Boyer R.S., Moore J.S. A fast string searching algorithm // Communications of the ACM. - 1977. - Vol. 20. - № 10. - P. 762-772.

125. Chalermsook P., Goswami M. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015): Berkeley, California, USA, 17 - 20 October 2015. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015). - Piscataway, NJ: IEEE, 2015. - 410-423 p.

126. Chamberlin D.D. A complete guide to DB2 universal database. - San Francisco, Calif: Morgan Kaufmann Publishers, 1998. - 795 p.

127. Colussi L. Correctness and efficiency of pattern matching algorithms // Information and Computation. - 1991. - Vol. 95. - № 2. - P. 225-251.

128. Cook J., Harbus R., Snow D. The universal guide to DB2 for Windows NT: IBM DB2 certification guide series. - Upper Saddle River, N.J: Prentice Hall, 1999. - 498 p.

129. Darlington J., Ghanem M., Guo Y. Guided Resource Organisation in Heterogeneous Parallel Computing // Journal of High Performance Computing. - 1996. - Vol. 4. -№ 1. - P. 13-23.

130. Demaine E.D., Landau G.M., Weimann O. On Cartesian Trees and Range Minimum Queries // Automata, Languages and Programming. - Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. - Vol. 5555. - P. 341-353.

131. Ferreira A., Rolim J. Parallel Algorithms for Irregularly Structured Problems: Second International Workshop. - Lyon: Springer, 1995. - 409 p.

132. Feuerstein S., Pribyl B. Oracle PL/SQL programming. - Beijing: O'Reilly, 2014. - 1340 p.

133. Fischer J., Heun V. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE // Combinatorial Pattern Matching. - Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. - Vol. 4009. - P. 36-48.

134. Flynn M.J. Very high-speed computing systems // Proceedings of the IEEE. -1966. - Vol. 54. - № 12. - P. 1901-1909.

135. Garbow H.N. Scaling algorithms for network problems // Journal of Computer and System Sciences. - 1985. - Vol. 31. - № 2. - P. 148-168.

136. Greenwald R., Stackowiak R., Stern J. Oracle essentials: Oracle database 11g. Oracle essentials. - Beijing; Sebastopol, [CA]: O'Reilly, 2008. - 386 p.

137. Gross T.R., Jouppi N.P., Hennessy J.L. A Retrospective on "MIPS: A Microprocessor Architecture" // IEEE Computer Society. - 2016. - Vol. 36. - №2 4. - P. 73-76.

138. Gupta S.B., Mittal A. Introduction to database management system. - New Delhi: University Science Press, 2009. - 298 p.

139. Haderle D.J., Saracco C.M. The History and Growth of IBM's DB2 // IEEE Annals of the History of Computing. - 2013. - Vol. 35. - № 2. - P. 54-66.

140. Hennessy J.L., Patterson D.A., Asanovic K. Computer architecture: a quantitative approach. Computer architecture. - Waltham, MA: Morgan Kaufmann/Elsevier, 2012. - 493 p.

141. Hennessy J.L., Patterson D.A. Computer organization and design: the hardware/software interface. Computer organization and design. - San Francisco, Calif: Morgan Kaufmann Publishers, 1998. - 793 p.

142. Horspool R.N. Practical fast searching in strings // Software: Practice and Experience. - 1980. - Vol. 10. - № 6. - P. 501-506.

143. Hume A., Sunday D. Fast string searching // Software: Practice and Experience. -1991. - Vol. 21. - № 11. - P. 1221-1248.

144. Jian L., Wang C., Liu Y. Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA) // The Journal of Supercomputing. - 2013. - Vol. 64. - № 3. - P. 942-967.

145. Karp R.M., Rabin M.O. Efficient randomized pattern-matching algorithms // IBM Journal of Research and Development. - 1987. - Vol. 31. - № 2. - P. 249-260.

146. Karp R.M., Zhang Y. Randomized Parallel Algorithms for Backtrack Search and Branch-and-bound Computation // J. ACM. - 1993. - Vol. 40. - № 3. - P. 765-789.

147. Knuth D.E., Morris, Jr. J.H., Pratt V.R. Fast Pattern Matching in Strings // SI-AM Journal on Computing. - 1977. - Vol. 6. - № 2. - P. 323-350.

148. Kumar S., Saraswatipura M. IBM DB2 9.7 advanced application developer cookbook: over 70 practical recipes for advanced application development techniques with DB2: Quick answers to common problems. IBM DB2 9.7 advanced application developer cookbook. - Birmingham: Packt Publ, 2012. - 426 p.

149. Kunzman D.M., Kale L.V. Programming Heterogeneous Systems // IEEE International Symposium on Parallel and Distributed Processing. - 2011. - № 1. - P. 2061-2064.

150. Kyte T. Expert one-on-one Oracle. - Birmingham: WROX Press, 2001. - 1297 p.

151. Kyte T. Expert Oracle Database architecture: Oracle Database 9i, 10g, and 11g programming techniques and solutions: The expert's voice in Oracle. Expert Oracle Database architecture. - Berkeley: Apress, 2010. - 780 p.

152. Lagana A., Kumar V., Tan C. Computational Science and Its Applications: Lecture Notes in Computer Science. - Assisi: Springer Science & Business Media, 2004. - 1044 p.

153. Land A.H., Doig A.G. An Automatic Method of Solving Discrete Programming Problems // Econometrica. - 1960. - Vol. 28. - № 3. - P. 497.

154. Loh W.Y. Classification and regression trees // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. - 2011. - № 12. - P. 14-23.

155. Main M., Savitch W.J. Data structures & other objects using C++. - Boston, MA: Addison Wesley Longman, 2001. - 783 p.

156. Manber U., Myers G. Suffix Arrays: A New Method for On-Line String Searches // SIAM Journal on Computing. - 1993. - Vol. 22. - Suffix Arrays. - № 5. - P. 935-948.

157. Manning C.D., Raghavan P., Schütze H. Introduction to Information Retrieval. -New York: Cambridge University Press, 2008. - 482 p.

158. Mishra S., Beaulieu A. Mastering Oracle SQL: [putting Oracle SQL to work; covers Oracle9i]. Mastering Oracle SQL. - Beijing: O'Reilly, 2002. - 321 p.

159. Moralee D. Microprocessor architectures: ten years of development // Electronics and Power. - 1981. - Vol. 27. - Microprocessor architectures. - № 3. - P. 214.

160. Murray C.J. The supermen: the story of Seymour Cray and the technical wizards behind the supercomputer. The supermen. - New York: John Wiley, 1997. - 232 p.

161. Neagu A., Pelletier R. IBM DB2 9.7 advanced administration cookbook: over 100 recipes focused on advanced administration tasks to build and configure powerful databases with IBM DB2. IBM DB2 9.7 advanced administration cookbook. - Birmingham: Packt Publ, 2012. - 464 p.

162. O'Hearn S. OCA Oracle database: SQL certified expert exam guide: (exam 1Z0-047). OCA Oracle database. - New York: McGraw-Hill, 2010. - 753 p.

163. Okasaki C. Purely functional data structures. - Cambridge: Cambridge Univ. Press, 2003. - 220 p.

164. Pavkovic P., Divjak S. Primerjava casovne zahtevnosti zahtev SQL pri podat-kovni bazi IBM DB2 na operacijskem sistemu Z/OS: diplomsko delo. - Ljubljana: Univ. v Ljubljani, 2011. - 70 p.

165. Poon C., Yuan H. A Faster CREW PRAM Algorithm for Computing Cartesian Trees // Algorithms and Complexity: Lecture Notes in Computer Science. - Berlin: Springer Berlin Heidelberg, 2013. - Vol. 7878. - P. 336-344.

166. Price J. Java programming with Oracle SQLJ. - Sebastopol, CA: O'Reilly, 2001. - 381 p.

167. Rajani N., McArdle K., Dhillon I.S. Parallel k nearest neighbor graph construction using Tree-based data structures // 1st High Performance Graph Mining workshop. -2015. - Vol. 1. - P. 3-11.

168. Schmoldt A., Benthe H.F., Haberland G. Digitoxin metabolism by rat liver microsomes // Biochemical Pharmacology. - 1975. - Vol. 24. - № 17. - P. 1639-1641.

169. Shoham Y., Toledo S. Parallel Randomized Best-First Minimax Search // Artificial Intelligence. - 2002. - Vol. 137. - № 1-2. - P. 165-196.

170. Shojaei A., Asadi A. Presenting a Parallel Algorithm for Constructing Cartesian Trees and its Application in Generating Separate and Free Trees // Journal of American Science. - 2012. - Vol. 8. - № 6. - P. 811-813.

171. Shun J., Blelloch G.E. A Simple Parallel Cartesian Tree Algorithm and Its Application to Parallel Suffix Tree Construction // ACM Transactions on Parallel Computing. - 2014. - Vol. 12. - P. 32-52.

172. Stallings W. Computer organization and architecture: designing for performance. Computer organization and architecture. - Upper Saddle River, NJ: Prentice Hall, 2010. - 774 p.

173. Swartzlander E.E. Parallel Counters // IEEE Transactions on Computers. - 1973. -Vol. 22. - № 11. - P. 1021-1024.

174. Tan X., Chen B.G., Zhang B.J. An advanced rack server system design For Rotational Vibration (RV) performance // Thermal and Thermomechanical Phenomena in Electronic Systems (ITherm), 2016 15th IEEE Intersociety Conference on. - 2016. -P. 1320-1325.

175. Tanenbaum A.S., Goodman J.R. Structured computer organization. - Upper Saddle River, N.J: Prentice Hall, 1999. - 669 p.

176. Ukkonen E. On-line construction of suffix trees // Algorithmica. - 1995. -Vol. 14. - № 3. - P. 249-260.

177. Visser S.M., Wong B. Sams teach yourself DB2 Universal Database in 21 days. -Indianapolis, Ind: Sams, 2004. - 601 p.

178. Weiss M.A. Linear-time construction of treaps and Cartesian trees // Information Processing Letters. - 1994. - Vol. 52. - № 5. - P. 253-257.

179. Yannakoudakis E.J. The Architectural Logic of Database Systems // Springer Science & Business Media. - 2012. - P. 87-90.