Моделирование параллельных процессов с учётом схемы обмена и объёма передаваемых сообщений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Аль-Марди Мохаммед Хайдар Авадх

• Аль-Марди Мохаммед Хайдар Авадх
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Аль-Марди Мохаммед Хайдар Авадх

Терминология

ВВЕДЕНИЕ

Глава 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ПРОЕКТИРОВАНИЯ И ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГРАММ

1.1. Классификация архитектур вычислительных систем

1.1.1. Массивно-параллельные вычислительные системы

1.1.2. Модель передачи сообщений (MPI)

1.2. Способы представления алгоритмов

1.3. Графы и способы их представления

1.4. Графы в параллельном программировании

1.5. Методы и инструменты оптимизации параллельных программ

1.5.1. Задача оптимизации алгоритмов

1.5.2. Матричное преобразование алгоритмов и их оптимизация по числу процессоров

1.5.3. Оптимизация алгоритма по ширине с применением списков смежности

1.5.4. Оптимизация алгоритма по ширине с применением списков следования

1.5.5. Оптимизация параллельных алгоритмов по времени выполнения

1.5.6. Оптимизация алгоритма по времени выполнения с применением списков следования

1.5.7. Оптимизация алгоритмов по нескольким параметрам

1.5.8. Временные оценки на информационных графах и расписание выполнения операций алгоритма

1.6. Выводы

Глава 2. МЕТОДЫ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ПО ЧИСЛУ МЕЖПРОЦЕССНЫХ ОБМЕНОВ ДАННЫМИ И ПРИ ОДИНАКОВОМ ВРЕМЕНИ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ АЛГОРИТМА

2.1. Типы параллелизма

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

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

2.3.1. Метод оптимизации параллельного алгоритма в ширину с конца

2.3.2. Метод оптимизации параллельного алгоритма в ширину с начала

2.3.3. Метод оптимизации параллельного алгоритма в глубину с конца

2.3.4. Метод оптимизации параллельного алгоритма в глубину с начала

2.4. Оценка минимального общего времени выполнения алгоритма

2.5. Анализ всех направлений перебора вершин графа в методе оптимизации алгоритма с учетом мепроцессных обменов данными

2.6. Выводы

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

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

3.2. Метод поиска оптимального расписания для отдельной группы вершин

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

3.4. Методы перебора вершин графа с начала в ширину и в глубину с учетом времени выполнения операций

3.5. Методы перебора вершин графа с конца в ширину и в глубину с учетом времени выполнения операций

3.6. Выводы

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

4.1 Дополнение информационного графа новыми параметрами алгоритма

4.2 Распределенные вычисления

4.2.1. Особенности распределённых вычислений, учитываемые в методах оптимизации алгоритмов по числу межпроцессных передач данных

4.2.2. Поярусный метод построения расписания распределенного алгоритма

4.3 Применение разработанных методов к запросам в реляционных базах данных

4.3.1 Обзор существующих баз данных

4.3.2. Специфика построения параллельного плана запроса

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

4.3.4 Тестирование запросов с помощью специально разработанного приложения

4.4. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

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

Приложение А

Приложение В

Терминология

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

Процесс - согласно стандарту ISO 9000:2000 это совокупность взаимосвязанных и взаимодействующих действий, преобразующих входящие данные в исходящие [112]. Каждый вычислительный процесс может быть реализован в виде процесса операционной системы, либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса ОС.

Межпроцессное взаимодействие (Inter-Process Communication, IPC) -это обмен данными между множеством потоков в одном или более процессах. Обмен может осуществляться на одном или более компьютерах, связанных сетью. IPC-способы делят на механизмы обмена сообщениями, разделяемой памяти, синхронизации и удаленных вызовов [113].

Схема межпроцессного взаимодействия - это графическое описание взаимодействия между процессами с учетом таких характеристик взаимодействия, как:

• направление связи: указание на вход какого процесса поступают выходные данные каждого отдельно взятого процесса;

• используемая модель передачи данных - потоковая или модель сообщений;

• объем передаваемой информации;

• время отправления данных;

• время выполнения процесса и др.

Сообщение - это совокупность данных и метаданных (адресат, объем, отправитель, тип данных и др.служебная информация).

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

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

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

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

Элементарная операция - простейшее обозначенное в машинном языке действие, совершаемое вычислительной машиной, то есть такое действие, которое не может быть представлено совокупностью более простых действий. Какие действия и объекты элементарны, а какие — нет, зависит от исполнителя (вычислительной машины). Набор элементарных действий и элементарных объектов для каждого исполнителя чётко зафиксирован. Элементарные действия оперируют с небольшим числом элементарных объектов. Все остальные объекты и действия являются совокупностью элементарных действий [86].

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

Граф - это совокупность о = (V, Е), которая представляет собой множество вершин V, связи между которыми определены множеством ребер Е [111]

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

Вершина графа - операция алгоритма.

Группа вершин - совокупность вершин, принадлежащих одному ярусу информационного графа.

Параллельная форма информационного графа - информационный граф, соответствующий параллельной форме алгоритма [43].

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

Высота информационного графа - число ярусов, т.е. время выполнения операций графа.

Ширина информационного графа - максимальное число операций в

ярусах.

Минимальная высота графа - наибольший путь в графе от начальной вершины до конечной вершины.

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

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

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

Массово-параллельная архитектура (англ. massive parallel processing, MPP, также «массивно-параллельная архитектура») — класс архитектур параллельных вычислительных систем. Главная особенность архитектуры состоит в том, что память разделена физически.

Концептуальная модель — это модель, представленная множеством понятий и связей между ними, определяющих смысловую структуру рассматриваемой предметной области или её конкретного объекта.

Введение диссертации (часть автореферата) на тему «Моделирование параллельных процессов с учётом схемы обмена и объёма передаваемых сообщений»

ВВЕДЕНИЕ

Актуальность темы исследования. Рост математических моделей, объемов данных и необходимость обработки в режиме реального времени; большой выбор СУБД, которые не справляются с обработкой запросов; наличие множества алгоритмов оптимизации, которые плохо адаптированы для параллельной обработки данных и наличие суперЭВМ, которые не могут быть применены непосредственно к задачам обработки данных большого объема, определяют актуальность темы исследования.

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

Под термином «высокопроизводительные вычисления» (highperformance computing — HPC) обычно подразумевают не только выполнение большого объема расчетов, но и обработку больших объемов данных за сравнительно небольшой промежуток времени [17]. Сегодня существует целый ряд разновидностей высокопроизводительных вычислений. Это и параллельные вычисления на компьютерах с различными архитектурными решениями (работа с векторными операциями, организация быстрого обмена

сообщениями между процессорами или организация глобальной памяти в многопроцессорных системах и др.) [19]. Это и распределенные вычисления, включающие технологии одноранговых сетей (peer-to-peer или P2P) и грид-технологии [18]. Это облачные и туманные вычисления и другие. И несмотря на это разнообразие надо отметить, что в области высокопроизводительных вычислений технология разработки параллельных программ играет не просто большую роль, а одну из главных ролей.

Больше всего исследовательских работ проводилось ранее и проводится сегодня в области создания и развития параллельных алгоритмов для решения прикладных задач в разных областях практических приложений. Здесь можно выделить работы, например, связанные c моделированием расчета электромагнитного излучения на основе многоядерных процессоров и кластеров параллельной архитектуры GPU с использованием гибридного параллельного алгоритма MPI-OpenMP и MPI-CUDA [44]. Проводятся исследования в области трансляции больших объемов данных в IoT (Internet of Things) с применением высокопроизводительных технологий [45]. Много исследований параллельных алгоритмов проводится в области дифференциальных уравнений [46] и систем линейных уравнений [47, 48]. С учетом большого объема данных и необходимости решения задач в режиме реального времени сегодня распараллеливают алгоритмы поиска кратчайшего пути для городской дорожной карты [49].

Начало анализа масштабируемости параллельных программ и компьютерных систем относится к 1967 году, когда сотрудник IBM Gene Amdahl (Gene Amdahl) опубликовал статью [50], которая позже стала классикой. Дальнейшая оценка ускорения вычислительных алгоритмов, использования ресурсов и производительности вычислительных систем была получена во многих других исследованиях [52-55]. Анализ эффективности

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

Проблема балансировки загрузки процессоров рассматривается в работах [57, 58].

Новейшие суперкомпьютеры [59] имеют очень большее число вычислительных узлов / ядер, но многие практические приложения не могут достичь максимальной производительности на этих суперкомпьютерах из-за недостаточно хорошо развитого аппарата исследования параллелизма в приложениях. В области формирования общих принципов разработки параллельных алгоритмов можно выделить исследования по планированию выполнения операций алгоритма [60, 61]. Одним из недостатков этих алгоритмов является их КР-полнота.

Проблема построения расписания параллельного алгоритма с оптимальным временем выполнения была освещена в различных исследованиях с 80-х годов. С тех пор были созданы различные алгоритмы построения расписания основанные на методах нахождения максимального потока в транспортной сети, на основе ветвей и границ, динамическом программировании, а также итерационные (например, генетические алгоритмы, алгоритм отжига) [62, 63]. Большинство из этих алгоритмов, в частности, основанные на нахождении максимального потока в транспортной сети, имеют псевдополиномиальную сложность [64, 65].

Вопросам распараллеливания отдельных фрагментов алгоритмов, обычно наиболее сложно распараллеливаемым, посвящены работы [66, 67].

Таким образом, процессы распараллеливания алгоритмов по -прежнему проводятся «вручную» и ложатся на плечи разработчика. Это одна проблема.

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

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

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

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

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

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

2. Рост объемов данных. Развитие веб-технологий, распространение мобильных устройств, возникновение «Интернета вещей» привело к появлению проблем обработки данных и их хранения в традиционных реляционных базах данных. Объём информации стал насколько велик, что обрабатывать её традиционными способами стало нецелесообразно, в не некоторых случаях и вовсе невозможно. Самой основной проблемой данных большого объёма являются затраты на их обработку, поскольку она требует дорогостоящего оборудования и высокой квалификации от специалистов. Обработка больших данных позволяет строить совершенно неожиданные взаимосвязи, что помогает предприятиям принимать важные решения, делать прогнозы, проводить аналитику, анализировать потребности клиентов и другое. Второй проблемой является фильтрация данных, поскольку из большого объёма структурированной, слабоструктурированной и неструктурированной информации необходимо выделить только те данные, которые необходимы для обработки. Третьей проблемой является конфиденциальность данных. Традиционные методы обеспечения конфиденциальности, такие как брандмауэры, антивирусное программное обеспечение и прочее оказалось недостаточно эффективным механизмом для эффективной защиты, поскольку данные механизмы создавались для защиты небольших данных. Четвёртой проблемой является потеря информации. Наличие одного резервного хранилища оказалось недостаточным, поскольку требуется обеспечить высокую отказоустойчивость и надёжное хранение данных. Однако с увеличением объёмов информации растёт и сложность их хранения. Постоянно растущие объёмы информации требуют не только

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

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

4. Быстрое устаревание существующих программ и невозможность их применения на новых вычислительных мощностях. И если 20 лет назад речь шла о модификации только последовательных алгоритмов и их адаптации под параллельные вычислительные системы, то сегодня речь идет о модификации уже самих параллельных программ. За последние десятилетия не только увеличилось число последовательных программ, но и параллельных программ.

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

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

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

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

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

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

4. Адаптировать разработанные методы под применение в распределённой вычислительной среде и в запросах к базам данных.

Объектом диссертационного исследования являются параллельные и распределённые вычисления.

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

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

Основные результаты:

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

2. Методика применения разработанных методов при расширенном наборе параметров исследуемых параллельных алгоритмов, таких как время передачи по сети, объем данных и других.

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

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

5. Методика применения разработанных методов к запросам в реляционных базах данных.

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

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

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

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

4. Методика применения разработанных методов при добавлении нового параметра (например, объёма данных) исследуемого алгоритма.

5. Метод организации распределенных вычислений.

Научная новизна результатов исследования.

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

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

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

4. Предложена методика применения разработанных методов при добавлении нового параметра (например, объёма данных) исследуемых алгоритмов или вычислительной системы.

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

6. Показана возможность применения разработанных методов к запросам в базах данных.

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

Теоретическая значимость результатов исследования заключается в:

1) разработке метода оптимизации параллельных алгоритмов с учетом межпроцессного обмена данными;

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

3) разработке метода оптимизации параллельных алгоритмов на взвешенных графах с учетом времени выполнения операций алгоритма;

4) обосновании возможности добавлении новых параметров для расширения разработанных методов и их улучшения;

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

Практическая значимость результатов исследования заключается в применимости:

1) разработанных методов для параллельных и распределенных вычислений;

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

3) разработанных методов не только к классическим алгоритмам, но и к запросам в базах данных.

Реализация результатов исследования

Теоретические и практические результаты диссертационной работы используются в программах ГК «СТИ», что подтверждено актом о применении. Результаты работы используются в учебном процессе кафедры вычислительной техники ФГАОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» при преподавании курсов «Параллельные алгоритмы и системы», «Распределенные базы данных».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на конференциях различного уровня: 69-я научно-техническая конференция профессорско-преподавательского состава ЛЭТИ, 16th International Conference NEW2AN 2016, 9th Conference ruSMART 2016, 18th International Conference on Computational Science and Its

Applications ICCSA 2018, 18th International Conference on Next Generation Wired/Wireless Advanced Networks and Systems NEW2AN 2018.

Публикации по теме диссертации.

Полученные основные теоретические и практические результаты диссертационного исследования опубликованы в 8 трудах, среди них: 4 научные статьи, опубликованные в журнале, входящем в рекомендуемый перечень ВАК, 2 научные статьи, опубликованные в зарубежных журналах, входящих в базы цитирования Web of Science и Scopus, 2 публикаций в сборниках конференций. Также получено свидетельство о государственной регистрации программы для ЭВМ «Multithreaded execution of SQL-queries» № 2018619271, дата гос. рег. 02.08.18.

Структура и объем работы

Диссертация состоит из введения, 4 глав, заключения, списка литературных источников, состоящего из 124 наименований, 2 приложений. Работа изложена на 180 машинописных страницах, включая 57 рисунков и 7 таблиц.

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

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

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

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

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

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

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

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

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

В заключении обобщаются основные результаты проведённого исследования.

Глава 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ПРОЕКТИРОВАНИЯ И ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГРАММ

1.1. Классификация архитектур вычислительных систем

В настоящее время выделяется четыре класса архитектур вычислительных средств: SISD, MISD, SIMD, М1МО. Только SISD относится к ЭВМ. Архитектуры MISD, SIMD, MIMD относятся к ВС(Вычислительным системам) [87].

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

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

Матричные вычислительные системы - это системы, в основе которых лежит матричный процессор, состоящий из регулярного массива процессорных элементов (ПЭ).

Мультипроцессорные вычислительные системы - это системы, которые включают конвейерные и матричные вычислительные системы. К таким системам относятся системы с МГМО- архитектурой, состоящие из множества процессоров и общей памяти; взаимодействие между процессорами и памятью осуществляется через коммутатор, а между самыми процессорами через память.

Распределенные вычислительные системы - это мультипроцессорные вычислительные системы с МТМБ-архитектурой, их особенность что в них

нет общей памяти. Распределенная ВС основывается на принципе модульности.

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

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

характеризующиеся рекордной эффективностью для фиксированного этапа развития обработки информации [88].

1.1.1. Массивно-параллельные вычислительные системы

MPP (massive parallel processing) - массивно-параллельная архитектура. Основная особенность этой архитектуры в том, что в системе память физически разделена. Система такого типа строится из отдельных модулей, которые содержат: процессор, локальный банк операционной памяти, коммуникационные процессоры или сетевые адаптеры[105]. Эти модули подобны полнофункциональным компьютерам. К банку оперативной памяти из данного модуля имеют доступ только процессоры из самого модуля[106].

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

Из основных недостатков таких систем, следующее:

- скорость межпроцессорного обмена снижается из-за отсутствия общей памяти;

- каждый процессор использует только ограниченный объем локальной

ОП;

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

Примеры таких ВС это суперкомпьютеры IBM RS/6000 SP, МВС-1000, SGI/CRAY T3E, Hitachi SR8000, системы ASCI и другие.

1.1.2. Модель передачи сообщений (MPI)

MPI (Message Passing Interface) - это программный интерфейс (API -интерфейс прикладного программирования) для передачи информации. Интерфейс для обмена сообщениями между процессами. Модель передачи сообщений является основной моделью параллельного выполнения программы на кластере [107]. В такой модели параллельная программа это систему процессов, взаимодействующих между собой посредством передачи сообщений. Модель передачи сообщений является низкоуровневой, непривычной и неудобной моделью для разработчиков вычислительных программ [108].

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

Параллельная программа это множество процессов, каждый из которых имеет своё локальное адресное пространство. Взаимодействие процессов в

модели передачи сообщений - обмен данными и синхронизация -обеспечивается посредством передачи сообщений [109].

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

1.2. Способы представления алгоритмов

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

На практике наиболее распространенными являются следующие формы записи алгоритмов:

1. словесная;

2. графическая (изображения из графических символов);

3. псевдокоды;

4. программная (тексты на языках программирования);

5. табличная;

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

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

Список литературы диссертационного исследования кандидат наук Аль-Марди Мохаммед Хайдар Авадх, 2019 год

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

1. Abramov, O.V., Katueva, Ya Multivariant analysis and stochastic optimization using parallel processing techniques. // Management problems. № 4, 2003. - P. 11 - 15.

2. Akl, S. The Design and Analysis of Parallel Algorithms. Prentice-Hall, Inc. Upper Saddle River, NJ, USA 1989.

3. Arvindam, S., Kumar, V., Rao, V. Floorplan optimization on multiprocessors. In Proc. 1989 Intl Conf. on Computer Design, pages 109--113. IEEE Computer Society, 1989.

4. Aho, A., Hopcroft, J., Ullman, J. The Design and Analysis of Computer Algorithms. // Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Company, Boston, 1974.

5. Andrews, G. R. Concurrent Programming: Principles and Practice. Benjamin/Cummings Publishing Company, Redwood City, CA 1991.

6. Jordan, H. F., Alaghband, F. Fundamentals of Parallel Processing. Pearson Education, Inc., Upper Saddle River, NJ, 2003. — p. 578.

7. Drake, D. E., Hougardy, S. A linear-time approximation algorithm for weighted matchings in graphs // ACM Transactions on Algorithms, 1 (2005), pp. 107-122.

8. Ahmad, I. A Parallel Algorithm for Optimal Task Assignment in Distributed Systems / I. Ahmad, M. Kafil // Proceedings of the 1997 Advances in Parallel and Distributed Computing Conference. Piscataway, NJ, USA - 1997. - P. 284 - 290.

9. Hu, Chen. MPIPP: An Automatic Profileguided Parallel Process Placement Toolset for SMP Clusters and Multiclusters / Hu.Chen // Proceedings of

the 20th annual international conference on Super-computing. New York, NY, USA- 2006. - P. 353 - 360.

10. Rauber, N., Runger, G. Parallel Programming: for Multicore and Cluster Systems. / N. Rauber, G. Runger. Chemnitz, Germany: Springer, 2010. -450p.

11. Boyer, L. L., Pawley, G. S. "Molecular dynamics of clusters of particles interacting with pairwise forces using a massively parallel computer", Journal of Computational Physics, V.78, 1988. P. 405-409.

12. Brunet, J. P., Edelman, A, Mesirov, J. P. "Hypercube algorithms for direct N-body solver for different granularities", SIAM Journal of Scientific and Statistical Computing, V.14, 1993,. P 1143.-1149.

13. Hu, Y.F., Emerson, D.R., Blake, R.J.. The Communication Performance of the Cray T3D and its Effect on Iterative Solvers. // Parallel Computing, V. 22, 1993, P. 829 - 844.

14. Gergel V.P. Lectures of Parallel Programming: Proc. Benefit / Gergel, V.P., Fursov, V.A. - Samara State Aerospace University Publishing House, 2009. -163p.

15. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб., 2002. 608 с.

16. Шичкина, Ю.А. Сокращение высоты информационного графа параллельных программ // Научно-технические ведомости СПбГПУ. - 2009. - № 3 (80) - с.148-152.

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

18. Радченко, Г.И. Распределенные вычислительные системы / Г.И. Радченко. -Челябинск: Фотохудожник, 2012. - 184 с.

19. А.В. Богданов, В.В. Корхов, В.В. Мареев, Е.Н. Станкова. Архитектуры и топологии многопроцессорных вычислительных систем /А.В. Богданов, В.В. Корхов, В.В. Мареев, Е.Н. Станкова/ — М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2004. — 176 с.

20. Борисенко В. В., Основы программирования, Интернет ун-т информ. технологий. — М.: Интернет ун-т информ. технологий, 2005.

21. Karpov V.E. Introduction to the parallelization of algorithms and programs // Computer Research and Modeling, 2010, vol. 2, no. 3, pp. 231-272

22. В.П. Гергель. Теория и практика параллельных вычислений. Интернет-университет информационных технологий - ИНТУИТ.ру, БИНОМ. Лаборатория знаний, 2007 г., 424 с.

23. Jordan H. F., Alaghband F. Fundamentals of Parallel Processing. — Pearson Education, Inc., Upper Saddle River, NJ 07452, 2003. — с. 578.

24. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы. — М.: Бином. Лаборатория знаний, 2006. — с. 406.

25. В. Е. Карпов. Введение в распараллеливание алгоритмов и программ. КОМПЬЮТЕРНЫЕ ИССЛЕДОВАНИЯ И МОДЕЛИРОВАНИЕ 2010 Т. 2 № 3 С. 231-272

26. Ben Shneiderman. A short history of structured flowcharts (Nassi-Shneiderman Diagrams). / Draft, May 27, 2003.

27. Nassi I., Shneiderman B. Flowchart Techniques for Structured Programming. / SIGPLAN Notices 8, 8 (August, 1973).

28. ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации».

29. Вельбицкий, И. В. Визуальная технология программирования нового поколения для широкого применения на базе стандарта ISO/IEC 8631 / Межд. конф. Кипр, 2010 г

30. Бардзинь Я.М., Калкиньш А.А., Стродс Ю.Ф., Сыцко В.А. Язык спецификаций SDL/PLUS и его применения. Рига 1988, 313 с.

31. Карабегов А.В., Тер-Микаэлян Т.М. Введение в язык SDL. Москва, Радио и связь, 1993, 184 с.

32. ITU Recommendation Z.100: Specification and Description Language. 1993. 204 p.

33. Силантьев, А.В. Использование компьютерной визуализации в процессе эволюции сложных программных систем [Электронный ресурс] / Силантьев А.В., Абрамова О.Ф. // Студенческий научный форум 2014 : докл. VI междунар. студ. электрон. науч. конф., 15 февр. - 31 марта 2014 г. Направл.: Технические науки / РАЕ. - М., 2014. - C. 1-7. - Режим доступа : http://www.scienceforum.ru/2014/pdf/3774.pdf.

34. Матрохин, А.Е. Проблемы процесса разработки программных систем [Электронный ресурс] / Матрохин А.Е., Абрамова О.Ф. // Студенческий научный форум 2014 : докл. VI междунар. студ. электрон. науч. конф., 15 февр. - 31 марта 2014 г. Направл.: Технические науки / РАЕ. -М., 2014. - C. 1-6. - Режим доступа : http ://www. scienceforum.ru/2014/pdf/3414.pdf.

35. Абрамова, О.Ф. CASE-технологии: изучать или исключить? / Абрамова О.Ф. // Alma mater (Вестник высшей школы). - 2012. - № 9. - C. 109-110.

36. Питерсон Дж. Теория сетей Петри и моделирование систем. — М: Мир, 1984. - 264 с

37. Franck C., Olivier-H. From Time Petri Nets to Timed Automata. -N.Y., 2004. - IRCCyN/CNRS UMR-11.

38. Лекарев М.Ф. Программная реализация конечных автоматов с использованием L-сети. -СПб.: СПбГТУ, 2000.-32 с., ил.

39. Brooks, Frederick P., Jr. The Mythical Man-Month. Essays on Software Engineering. Anniversary Edition. Addison-Wesley, 1995. Имеется перевод: Брукс Ф. Мифический человеко -месяц, или как создаются программные системы / Пер. с англ. - СПб.: Символ, 2000.- 304 с., ил.

40. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.

41. Карпов, Ю.Г. Теория и технология программирования. Основы построения трансляторов. / Ю.Г. Карпов. - СПб.: БХВ-Петербург. - 2006. -272 с. 1999. 320 с.

42. С.Немнюгин, О.Стесик. Параллельное программирование для многопроцессорных вычислительных систем - СПб 2002

43. Бурова И.Г., Демьянович Ю.К. Алгоритмы параллельных вычислений и программирование: курс лекций. - СПб.: Изд-во С.-Пб. ун-та, 2007. - 206 с.

44. Bing He, Long Tang, Jiang Xie, XiaoWei Wang, and AnPing Song, Parallel Numerical Simulations of Three-Dimensional Electromagnetic Radiation with MPI-CUDA Paradigms, Mathematical Problems in Engineering, Volume 2015 (2015), Article ID 823426, 9 pages

45. Qin Jiancheng, Lu Yiqin, and Zhong Yu, Parallel Algorithm for Wireless Data Compression and Encryption, Journal of Sensors, Volume 2017 (2017), Article ID 4209397, 11 pages

46. Chunye Gong, Weimin Bao, Guojian Tang, Yuewen Jiang, and Jie Liu, A Parallel Algorithm for the Two-Dimensional Time Fractional Diffusion Equation with Implicit Difference Method, The Scientific World Journal, Volume 2014 (2014), Article ID 219580, 8 pages

47. Xinrong Ma, Sanyang Liu, Manyu Xiao, and Gongnan Xie, Parallel Algorithm with Parameters Based on Alternating Direction for Solving Banded

Linear Systems, Mathematical Problems in Engineering, Volume 2014 (2014), Article ID 752651, 8 pages

48. Junxia Hou, Quanyi Lv, and Manyu Xiao, A Parallel Preconditioned Modified Conjugate Gradient Method for Large Sylvester Matrix Equation, Mathematical Problems in Engineering, Volume 2014 (2014), Article ID 598716, 7 pages

49. De-Xin Yu, Zhao-Sheng Yang, Yao Yu, and Xiu-Rong Jiang, Research on Large-Scale Road Network Partition and Route Search Method Combined with Traveler Preferences, Mathematical Problems in Engineering, Volume 2013 (2013), Article ID 950876, 8 pages

50. G.M. Amdahl, Validity of the single processor approach to achieving large scale computing capabilities // Processings AFIPS spring joint computer conference/ Reston. VA: AFIPS Press, 1967. - P. 483-485.

51. W. Ware The ultimate computer // IEEE spectrum. - 1972. -V.9. -P.84-91.

52. A. Grama, A. Gupta, G. Karypis, V. Kumar "Introduction to Parallel Computing, Second Edition"//USA: Addison Wesley, 2003.

53. V.P. Gergel, R.G. Strongin, Parallel computing for multiprocessor computers, Nizhnij Novgorod: NGU Publ., 2003 (in Russian).

54. M. J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill Education, New York, NY, USA, 1st edition, 2003.

55. T. Wittwer, An Introduction to Parallel Programming, VSSD uitgeverij, 2006.

56. A. Tiwari, V. Tabatabaee, and J. K. Hollingsworth, Tuning parallel applications in parallel, Parallel Computing, vol. 35, no. 8-9, pp. 475-492, 2009.

57. Misbah Mubarak, Seegyoung Seol, Qiukai Lu, Mark S. Shephard, A Parallel Ghosting Algorithm for The Flexible Distributed Mesh Database, Scientific Programming, Volume 21 (2013), Issue 1-2, Pages 17-42

58. B. Kruatrachue, T. Lewis, Grain size determination for parallel processing, IEEE Software, vol. 5, no. 1, pp. 23-32, 1988.

59. H. Meuer, E. Strohmaier, J. Dongarra, H. Simon, Top500 supercomputing sites, 2015.

60. T. Yang, A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 9, 1994, pp. 951-967.

61. S. Darbha, D.P. Agrawal, Optimal Scheduling Algorithm for Distributed Memory Machines, IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 1, 1998, pp. 87-95.

62. C.L. Liu, J.W. Layland, Scheduling Algorithms for Multiprogramming in Hard Real-Time Environment// J. ACM. 1973. V.20. № 1. P. 46-61.

63. B. Marte, Preemptive scheduling with release times, deadlines and due times// J. ACM. 1982. V. 29, №3. P. 812-829.

64. A. Burns, Scheduling Hard Real-Time Systems: A Review// Software Engineering J. 1991, V. 6. № 3. P.116-128.

65. J.A. Stankovic, Implications of Classical Scheduling Results for RealTime Systems// IEEE Computer Society Press, 1995.

66. T.H. Tzen; L.M. Ni, Trapezoid self-scheduling: a practical scheduling scheme for parallel compilers, IEEE Transactions on Parallel and Distributed Systems , v. 4, January 1993, p. 87-98

67. O. Sinnen, L. A. Sousa, Communication contention in task scheduling, in IEEE Trans. on Parallel and Distributed Systems, 2005, pp. 503515.

68. M.S. Kupriyanov, Y.A. Shichkina, Applying the list method to the transformation of parallel algorithms into account temporal characteristics of operations. Proceedings of the 19th International Conference on Soft Computing and Measurements, SCM 2016, 7519759, pp. 292-295. ISBN: 978-146738919-8, DOI: 10.1109/SCM.2016.7519759.

69. M.S. Kupriyanov, J.A. Shichkina, Mohammed Al-Mardi Optimization algorithm for an information graph for an amount of communications. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Volume 9870, 2016, pp. 50-62 ISSN: 03029743 ISBN: 978-331946300-1, DOI: 10.1007/978-3-319-46301-8_5.

70. DBMS Database Models [Электронный ресурс] // Studytonight. URL: https://www.studytonight.com/dbms/database-model.php (дата обращения: 26.05.2018).

71. Codd E. F. A Relational Model of Data for Large Shared Data Banks // Commun. ACM. 1970. Т. 13. С. 377-387.

72. Gray J. The Transaction Concept: Virtues and Limitations // Proc. Seventh Int. Conf. Very Large Databases. 1981. С. 144-154.

73. Vaish G. Getting Started with NoSQL. Packt Publishing, 2013. 142 с.

74. Фаулер М., Садаладж П. Д. NoSQL: новая методология разработки нереляционных баз данных. М.: «Вильямс», 2013. 192 с.

75. What is NoSQL? NoSQL databases explained [Электронный ресурс] // InfoWorld. URL: https://www.infoworld.com/article/3240644/nosql/what-is-nosql-nosql-databases-explained.html (дата обращения: 26.05.2018).

76. Системы обработки многопользовательских баз данных [Электронный ресурс] // БГЭУ. URL: http://www.bseu.by/it/tohod/lekcii8_4.htm (дата обращения: 26.05.2018).

77. https ://www. seagate. com/ru/ru/ our-story/data-age-2025/

78. Rupak Biswas, Zhang Jiang, Kostya Kechezhi, Sergey Knysh, Salvatore Mandra, Bryan O'Gorman, Alejandro Perdomo-Ortiz, Andre Petukhov, John Realpe-Gomez, Eleanor Rieffel, Davide Venturelli, Fedir Vasko, Zhihui Wang; A NASA perspective on quantum computing: Opportunities and challenges; Parallel Computing, Volume 64, May 2017, pp 81-98, DOI 10.1016/j.parco.2016.11.002;

79. Weiming Lu, Yaoguang Wang, Jingyuan Juang, Jian Liu, Yapeng Shen, Baogang Wei; Hybrid storage architecture and efficient MapReduce processing for unstructured data; Parallel Computing, Volume 69, November 2017, pp.63-77, DOI 10.1016/j.parco.2017.08.008

80. Peiquan Jin, Puyuan Yang, Lihua Yue; Optimizing B+-tree for hybrid storage systems; Distributed and Parallel Databases, Volume 33, September 2015, Issue 3, pp 449-475, DOI 10.1007/s10619-014-7157-7

81. Qiong Luo, Jens Teubner; Special issue on data management on modern hardware; Distributed and Parallel Databases, 2015, Volume 33, pp.415416, DOI 10.1007/s10619-014-7168-4

82. Daichi Amagata, Takashiro Hara, Shojiro Nishio; Sliding window top-k dominating query processing over distributed data streams; Distributed and Parallel Databases, December 2016, Volume 34, Issue 4, pp 535-566; DOI 10.1007/s10619-015-7187-9;

83. Research in Mobile Database Query Optimization and Processing, Agustinus Borgy Waluyo, Bala Srinivasan, and David Taniar, Mobile Information Systems, Volume 1 (2005), Issue 4, pp. 225-252

84. Spiliopoulou M., Hatzopoulos M., Ttanslation of SQL queries into a graph structure: query transformations and pre-optimization issues in a pipeline multiprocessor environment, Informafion Sysfems 1992, Vol. 17, No. 2, pp. 161170.

85. McQuillan, John M.; David C. Walden (1975). "Some considerations for a high performance message-based interprocess communication system". Proceedings of the 1975 ACM SIGCOMM/SIGOPS workshop on Interprocess communications, ACM Press

86. Larry LIU Xinyu AlgoXY - открытая книга об элементарных алгоритмах и структурах данных. = AAlgoXY is an open book about elementary algorithms and data structures.. — github.com: -, 2017. — 600 с.

87. Евреинов, Э.В. Однородные вычислительные системы / Э.В. Евреинов, В.Г. Хорошевский. - Новосибирск : Наука. Сибирское отд-е, 1978. - 319 с.

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

89. Миренков, Н. Н. Параллельное программирование для многомодульных вычислительных систем / Н. Н. Миренков. - М. : Радио и связь, 1989. -319 с.

90. Хорошевский, В. Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем / B. Г. Хорошевский, М. Г. Курносов // Автометрия. - 2008. - Т. 44, № 2. -C. 56-67.

91. Яненко, Н. Н. Параллельные вычисления в задачах математической физики на вычислительных системах с программируемой структурой / Н. Н. Яненко, В. Г. Хорошевский, А. Д. Рычков // Электронное моделирование. - 1984. - Т. 6, № 1. - 3-8.

92. Agarwal, Т. Topology-aware task mapping for reducing communication contention on large parallel machines / T. Agarwal et al.. // Parallel and Distributed Processing Symposium. - 2006. - P. 10

93. Поспелов, Д. А. Введение в теорию вычислительных систем / Д. А. Поспелов. — М.: Изд-во "Советское радио", 1972. - 280 с.

94. El-Rewini, H. Advanced computer architecture and parallel processing / H. El-Rewini, M. Abd-El-Barr. - New Jersey : John Wiley & Sons, 2005. -272 p.

95. Grama, A. Introduction to parallel computing / A. Grama. - Harlow : Addison Wesley, 2003. - 856 p.

96. Мамойленко С.Н. Параллельные методы организации функционирования распределенных вычислительных систем. // Материалы докладов региональной научной конференции студентов, аспирантов и молодых ученых. Новосибирск, 2002. - С. 10-12.

97. Распределённые управляющие и вычислительные системы: сб. ст. / Лазарев В.Г. М. : Наукова думка, 1987. - 167 с.

98. Таненбаум Э., М. Ван Стеен. Распределенные системы: принципы и парадигмы. СПб.: Питер, 2003. -877 с.

99. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М. : Радио и связь, 1990. - 256 с.

100. Барский А. Б. Планирование параллельных вычислительных процессов. М. : Машиностроение, 1980. -192 с.

101. Мамойленко С.Н. Параллельные методы организации функционирования распределенных вычислительных систем. // Материалы докладов региональной научной конференции студентов, аспирантов и молодых ученых. Новосибирск, 2002. - С. 10-12.

102. Монахов О.Г., Монахова Э.А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями. Новосибирск: ИВМиМГ РСО РАН, 2000. -168 с.

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

2002, - 400 с.

104. Эндрюс Г. Р. Основы многопоточного, параллельного и распределенного программирования. / пер. с англ. М.: Вильяме, 2003. - 512 с.

105. Сайт проекта Национальный открытый университет Электронный ресурс.. - Режим доступа : http://www. intuit.ru, свободный.

106. Доклады МК "Информационные средства и технологии", том 2. М.: Изд-во "Станкин", 2000. - с.106-109.

107. Корнеев В.Д. Параллельное программирование в MPI. - Москва-Ижевск: Ин-ститут компьютерных исследований, 2003. - 304с.

108. Сайт проекта Курс лекций параллельное программирование в MPI Электронный ресурс.. - Режим доступа : http://www. grsu.by, свободный.

109. Сайт проекта OpenMPI Электронный ресурс.. - Режим доступа : http://www.open-mpi.org, свободный.

110. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенно-го программирования. - М.:Издательский дом "Вильямс",

2003. - 512 с.

111. Берж, К. Теория графов и ее применение / К.Берж - М.: Изд-во иностр. лит.1962 - 319с.

112. ISO 9000:2000 «Системы менеджмента качества. Основные поло жения и словарь».

113. Йохан Лиетке. On ц-Kernel Construction, Proc. 15th ACM Symposium on Operating System Principles (SOSP), декабрь 1995.

114. Носов В. И., Бернштейн Т. В., Носкова Н. В., Храмова Т. В. Элементы теории графов. Учебное пособие. Новосибирск: СибГУТИ, 2008. 107 с.

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

116. Shichkina U. A., Al-Mardi M. H., Kupriyanov M. C. Optimization algorithm for an information graph for an amount of communications // Lecture Notes in Computer Science. 2016. Т. 9870 LNCS. P. 50-62.

117. Shichkina, Y., Al-Mardi M.H., Storublevtcev, N., Degtyarev, A. The construction of the parallel algorithm execution schedule taking into account the interprocessor data transfer// Lecture Notes in Computer Science. 2018. Т. 10963 LNCS. P. 61-77.

118. Шичкина Ю. А., Аль-Марди М.Х. Метод оптимизации параллельного алгоритма за счет уменьшения объема межпроцессорной передачи информации // Известия СПбГЭТУ «ЛЭТИ». -2015. - № 10. - С. 1528.

119. Шичкина Ю.А., Аль-Марди М.Х., М.С.Куприянов Оптимизация параллельного алгоритма путем сокращения времени на межпроцессорный обмен данными // Известия СПбГЭТУ «ЛЭТИ». -2017. - № 7. - С. 51-56.

120. Аль-Марди М.Х., Сравнительный анализ методов оптимизации параллельного алгоритма с учётом и без учёта времени выполнения операций // Компьютерные инструменты в образовании. -2018. - № 3 - С. 36-48.

121. Аль-Марди М.Х., Особенности распределённых вычислений, учитываемые в методах оптимизации алгоритмов по объему межпроцессорных передач // Компьютерные инструменты в образовании. -2018. - № 2 - С. 31-38.

122. Аль-Марди М.Х., Шичкина Ю. А. Метод оптимизации параллельного алгоритма по объёму межпроцессорных коммуникаций на взвешенных графах // научный журнал "Chronos". -2016. - С. 46-52.

123. Аль-Марди М.Х., Шичкина Ю. А. Учёт межпроцессорных передач данных при распараллеливании алгоритмов // национальная ассоциация ученых (НАУ). -2016. - № 1(17). - С. 43-45.

124. Шичкина Ю.А., Аль-Марди М.Х.А. Multithreaded execution of SQL-queries. ПрЭВМ, Свидетельство № 2018619271 дата гос. рег. 02.08.18

Приложение А Пример построения графа запроса

Пусть дан запрос

Для него с помощью специальной программы можно построить матрицу смежности:

F:\Projerts\Query\queries.exe

Iquery:' Select a,b,c,(a*2 as r)

I FroM tablE, (select * From t2, t4 uhere (qqqOOO)) where ddd in I (select d, F, (d+2 as r) From t2 where sd='er'> I union

| select r, * FrOm t2; J TR:J select a,b,c,(a*2 as r> From table, uhere ddd in _1 union select r

* From t2; J TH:'_2 union _3 ' TH:'_4 '

[□]='select * From t2, t4 uhere (qqq(3O0>'

[1]=J select d, F, (d+2 as r> From t2 uhere sd='erJJ

[2]=Jselect a,b,c,(a*2 as r> From table, uhere ddd in _1 '

[3]=J select r, * From t2; '

[4]='_2 union _3 ' -10 12 3 4

0 110 10

0 0 0 1 0 0

0 0 0 1 0 0

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 0 =' t2J =J table' =' t4J

0 1 2 3 4 5 e ?

t2table t4 0 1 2 3 4

0 t2: 0 0 0 1 1 0 l 0

1 -table! 0 0 0 0 0 1 0 0

2 t4! 0 0 0 1 0 0 0 0

3 о: 0 0 0 0 0 1 0 0

4 l: 0 0 0 0 0 1 0 0

5 2: 0 0 0 0 0 0 0 1

6 з: 0 0 0 0 0 0 0 1

7 4! 0 0 0 0 0 0 0 0

я продолжения нажмите любую клавишу .

После передачи этой матрицы на вход любой программе по построению графа будет построен информационный граф:

После применения к нему методов оптимизации будет построено расписание:

Р_1: 2, 3, 5, 7 Р_2: 1, 4 Р_3: 0, 6

Приложение В Фрагменты программы по распараллеливанию запросов

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.Threading;

using System.Diagnostics;

using MySql.Data.MySqlClient;

using System.IO;

namespace mysql thread

// Функция запуска программы

private void start(object sender, EventArgs e) {

if (gl.mode == 1) ThreadFunction 1();

if (gl.mode == 2) {

cur it++; toolStripProgressBar1.Value = cur it; //Создаем в цикле n потоков

for (int i = 0; i < n; i++) {

// Thread thread = new Thread(ThreadFunction); // thread.Start(i);

thread[i] = new Thread(ThreadFunction 2); thread[i].Start (i);

}

}

if (gl.mode == 3) {

ind vr=0;

//Создаем в цикле n потоков

for (int i = 0; i < n; i++) {

thread[i] = new Thread(ThreadFunction 3); thread[i].Start(i);

}

}

if (gl.mode == 4) ThreadFunction 4();

if (gl.ex_mode==0) label7.Text = label7.Text +

gl.end.ToString() + ","; }

// Функции запуска потоков

private void ThreadFunction 4() {

cur it++; toolStripProgressBarl.Value = cur it; if (gl.cn[0] == null) gl.cn[0] = new MySqlConnection();

if (gl.mc[0] == null) gl.mc[0] = new MySqlCommand();

if (gl.cn[0].State == ConnectionState.Closed) {

gl.cn[0].ConnectionString = "Database = " + gl.bd name + "; Data Source = localhost; User Id = root ; Password = lll";

gl.cn[0].Open();

}

gl.mc[0].Connection = gl.cn[0]; gl.mc[0].CommandText =dataGridView2.Rows[0].Cells[1].Value.ToString();

string cmd = gl.mc[0].CommandText; Stopwatch sw = new Stopwatch();

if (gl.dg3.Rows[0].Cells[0].Value.ToString().Length >

0)

{

if (gl.dg3.Rows[0].Cells[0].Value.ToString()[0]

== '@')

{

sw.Start(); gl.vr[0] = gl.mc[0].ExecuteScalar().ToString();

sw.Stop();

}

else {

gl.mc[0].CommandText = "drop view if exists " + gl.dg3.Rows[0].Cells[0].Value.ToString()+";";

gl.mc[0].ExecuteNonQuery(); gl.mc[0].CommandText = "create view " + gl.dg3.Rows[0].Cells[0].Value.ToString() +" as "+ cmd;

sw.Start();

gl.mc[0].ExecuteNonQuery(); sw.Stop();

}

long ticks = sw.ElapsedTicks;

double ns = 1000000000.0 * (double)ticks /

Stopwatch.Frequency;

double ms = ns / 1000000.0;

if (gl.ex mode == 0) {

lb2 text("Time: " + ticks + " ticks = " + ms.ToString() + " ms. = " + ns + " ns.");

if

(gl.dg3.Rows[0].Cells[0].Value.ToString()[0] == '@')

{

if (gl.dgl.Columns.Count == 0) dg2_col(gl.dg3.Rows[0].Cells[0].Value.ToString());

dg2 row inc(); dg2 row(gl.dg1.Rows.Count -

1, 0, gl.vr [0]) ;

}

else {

gl.mc[0].CommandText = "select * from " + gl.dg3.Rows[0].Cells[0].Value.ToString() + ";";

gl.rd [0] = gl.mc[0].ExecuteReader();

if (gl.dg1.Columns.Count == 0) {

for (int i = 0; i <

gl.rd_[0].FieldCount; i++) форме

{

}

// Добавление столбца в таблицу на dg2 col(gl.rd [0].GetName(i));

gl.rd_[0].FieldCount; i++) gl.rd_[0].GetString(i));

gl.rd_[0].FieldCount, "0")

}

dg2 col("Process");

}

// Заполнение таблицы значениями

while (gl.rd_[0].Read()) {

dg2 row inc(); Thread.Sleep(50); for (int i = 0; i <

dg2 row(gl.dg1.Rows.Count - 1, i,

dg2 row(gl.dg1.Rows.Count - 1,

}

gl.rd [0].Close(); gl.rd [0].Dispose();

}

if (gl.fs != null) {

// запись в csv

if (cur it == 1) {

gl.fs.WriteLine(@"""" + cmd + @"""");

gl.fs.WriteLine(@"""Number"";""ticks"";""ms"";""ns""");

}

gl.fs.WriteLine(@"""" + cur it.ToString() + + ticks.ToString() + @""";""" + ms.ToString() + @""";""" +

ns .ToString() + @"""");

}

if (gl.iter == cur it) {

gl.mc[0].Dispose()

gl.cn [0] .Close(); gl.cn[0] .Dispose(); MessageBox.Show("Stop");

}

if (gl.iter > cur it) ThreadFunction 4();

}

private void ThreadFunction 2(object k) {

for (int j = 0; j < n; j++) {

if (j == (int)k) {

if (gl.cn[j] == null) gl.cn[j] = new

MySqlConnection() ; MySqlCommand();

if (gl.mc[j] == null) gl.mc[j] = new

if (gl.cn[j].State == ConnectionState.Closed) {

gl.cn[j].ConnectionString = "Database = " + gl.bd name + "; Data Source = localhost; User Id = root ; Password = 111";"

gl.cn[j].Open();

}

//Объявление курсора

// MySqlCommand mc= new MySqlCommand(); gl.mc[j].Connection = gl.cn[j]; gl.mc[j].CommandText = dataGridView2.Rows[j].Cells[gl.m].Value.ToString();

//_

// считаем время

Stopwatch sw = new Stopwatch(); sw.Start();

gl.rd [j] = gl.mc[j].ExecuteReader(); sw.Stop();

long ticks = sw.ElapsedTicks;

double ns = 1000000000.0 * (double)ticks /

Stopwatch.Frequency;

double ms = ns / 1000000.0; if (gl.ex mode == 0)

lb2 text("Time: " + ticks + " ticks = " + ms.ToString() + " ms. = " + ns + " ns.");

//

i++)

форме

if (gl.dgl.Columns.Count == 0 && j == 0) {

for (int i = 0; i < gl.rd [j].FieldCount;

{

}

// Добавление столбца в таблицу на dg2 col(gl.rd [j].GetName(i));

dg2 col("Process");

// Заполнение таблицы значениями

while (gl.rd [j].Read()) {

lock (Locker) {

dg2 row inc(); Thread.Sleep(50); for (int i = 0; i <

dg2 row(gl.dg1.Rows.Count - 1, i,

gl.rd_[j].FieldCount; i++) gl.rd [j].GetString(i));

dg2 row(gl.dg1.Rows.Count - 1,

gl.rd [j].FieldCount, j.ToString()); " }

}

}

gl.rd [j].Close(); gl.rd [j].Dispose();

if (gl.fs != null) {

// запись в csv

if (cur it == 1) {

f write(@"""" + gl.mc[j].CommandText +

@"""" ) ; Thread.Sleep(50);

if (j == 0)

f write(@"""number"";""thread"";""ticks"";""ms"";""ns""");

//gl.fs.WriteLine(@"""number"";""thread"";""ticks"";""ms"";""ns""");

}

lock (Locker) {

f write(@"""" + cur it.ToString() + @""";""" + j,ToString() + @""";""" + ticks.ToString() + @""";""" + ms.ToString( ) + @""";""" + ns.ToString() + @"""");

Thread.Sleep(50);

}

gl .mc[j].Dispose ( );

f (gl.iter == cur it)

gl.cn[j] .Close (); gl.cn[j].Dispose ( );

ock (Locker)

end (j); Thread.Sleep(50);

}

private void ThreadFunction 3(object k) {

// если не последний уровень запроса, то вывода нет

for (int j = 0; j < n; j++) {

if (j == (int)k) {

if (gl.cn[j] == null) gl.cn[j] = new

MySqlConnection( ) ; MySqlCommand();

if (gl.mc[j] == null) gl.mc[j] = new

if (gl.cn[j].State == ConnectionState.Closed) {

gl.cn[j].ConnectionString = "Database = " + gl.bd name + "; Data Source = localhost; User Id = root ; Password = 111";

gl.cn[j].Open();

}

gl.mc[j].Connection = gl.cn[j]; gl.mc[j].CommandText = dataGridView2.Rows[j].Cells[gl.m].Value.ToString();

string cmd = gl.mc[j].CommandText;

if (gl.dg3.Rows[j].Cells[gl.m -

1].Value.ToString().Length > 0)

{

if (gl.dg3.Rows[j].Cells[gl.m -

1].Value.ToString()[0] == '@')

{

if (gl.sw [j] == null) {

gl.sw [j] = new Stopwatch(); gl.sw [j].Start();

}

else gl.sw [j].Restart();

}

}

gl.vr[j] = gl.mc[j].ExecuteScalar().ToString();

gl.sw [j].Stop () ;

}

else {

gl.mc[j].CommandText = "drop view if exists " + gl.dg3.Rows[j].Cells[gl.m - 1].Value.ToString() + ";";

gl.mc[j].ExecuteNonQuery(); gl.mc[j].CommandText = "create view " + gl.dg3.Rows[j].Cells[gl.m - 1].Value.ToString() + " as " + cmd;

if (gl.sw [j] == null) {

gl.sw [j] = new Stopwatch(); gl.sw [j].Start();

}

else gl.sw [j].Restart(); gl.mc[j].ExecuteNonQuery(); gl.sw [j].Stop ();

}

Stopwatch.Frequency;

long ticks = gl.sw [j].ElapsedTicks; double ns = 1000000000.0 * (double)ticks /

double ms = ns / 1000000.0; if (t tics < ticks) t tics = ticks; if (t ns < ns) t ns = ns; if (t ms < ms) t ms = ms;

if (gl.ex mode == 0)

lb2_text("Thread " + j.ToString() + " Time: " + ticks + " ticks = " + ms.ToString() + " ms. = " + ns + " ns.") ;

if (gl.fs != null) {

// 3anMCb b csv

lock (Locker) {

f write(@"""" + cur it.ToString() + @""";""" + j,ToString() + @""";""" + (gl.m-1).ToString() + @""";""" +

ticks.ToString() + @""";""" + ms.ToString() + @""";""" + ns.ToString() + @"""");

Thread.Sleep(50);

}

}

}

gl.cn[j].Close(); gl.cn[j].Close(); gl.cn[j].Dispose(); gl.mc[j].Dispose();

lock (Locker)

end_(j); Thread.Sleep(50);

};

}

}

private void ThreadFunction 3 end(object k) {

// если последний уровень запроса, то вывода нет

for (int j = 0; j < n; j++) {

if (j == (int)k) {

if (gl.cn[j] == null) gl.cn[j] = new

MySqlConnection( ) ; MySqlCommand();

if (gl.mc[j] == null) gl.mc[j] = new

if (gl.cn[j].State == ConnectionState.Closed) {

gl.cn[j].ConnectionString = "Database = " + gl.bd name + "; Data Source = localhost; User Id = root ; Password = 111";

gl.cn[j].Open();

}

gl.mc[j].Connection = gl.cn[j]; gl.mc[j].CommandText = dataGridView2.Rows[j].Cells[gl.m].Value.ToString();