Аль-Марди Мохаммед Хайдар Авадх Моделирование параллельных процессов с учётом схемы обмена и объёма передаваемых сообщений : Аль-Марді Мохаммед Хайдар Авадх Моделювання паралельних процесів з урахуванням схеми обміну та обсягу повідомлень, що передаються

Краткое описание

Аль-Марди Мохаммед Хайдар Авадх Моделирование параллельных процессов с учётом схемы обмена и объёма передаваемых сообщений
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Аль-Марди Мохаммед Хайдар Авадх
Терминология

ВВЕДЕНИЕ

Глава 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. Выводы

ЗАКЛЮЧЕНИЕ

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

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

Приложение А

Приложение В