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

• Автор: Шичкина, Юлия Александровна
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 330 с. : 29 ил.

СОДЕРЖАНИЕ
Введение
Г лава 1. Обзор способов представления распределенных структур и методов их обработки

1.1. Ориентированные, взвешенные графы и деревья

1.2. Матричные алгоритмы на графах

1.3. Технологии обработки разреженных матриц

1.4. Методы определения трудоемкости алгоритмов 51 ] .5. Оптимизация вычислений за счет распараллеливания
алгоритмов
Выводы
Глава 2. Методы преобразования разреженных прямоугольных матриц с сохранением первоначальных значений

2.1. Примеры задач, сводимых к разреженным матрицам

2.2. Приведение разреженной матрицы к односторонне
окаймляющей блочной диагональной форме
2.3. Приведение разреженной матрицы к треугольной форме
2.3.1. Метод ненулевой диагонали
2.3.2. Метод уплотнения вниз
Выводы
Глава 3. Организация последовательных и параллельных вычислений
3.1. Матричный метод перебора путей в графе
3.2. Построение параллельного алгоритма на основе его
последовательного аналога с последующей оптимизацией по числу процессоров
3.2.1. Матричное преобразование алгоритмов и их
оптимизация по числу процессоров
3.2.2. Оптимизация алгоритмов по ширине с применением
списков смежности

3.2.3. Оптимизация алгоритмов по ширине с применением
списков следования
3.3. Оптимизация параллельных алгоритмов по времени выполнения
3.3.1. Матричное преобразование алгоритма с целью
оптимизации по времени выполнения
3.3.2. Оптимизация алгоритма по времени выполнения с
применением списков следования
3.4. Оптимизация алгоритмов по нескольким параметрам
Выводы
Глава 4. Методы конструирования реляционных схем на основе метаданных функциональных зависимостей
4.1. Проблемы аномалии избыточности в различных моделях
данных
4.2. Функциональные зависимости реляционных отношений
4.2.1. Представление функциональных зависимостей с
помощью графов
4.2.2. Преобразование орграфа функциональных
зависимостей в дерево
4.3. Построение реляционной модели на основе орграфа
функциональных зависимостей
4.4. Декомпозиция отношения на основе орграфа простых функциональных зависимостей
4.5. Метод получения новых функциональных зависимостей на основе декларированных
4.6. Определение ключей по орграфу функциональных зависимостей
4.7. Декомпозиция отношения на основе орграфа составных функциональных зависимостей
Выводы
Глава 5. Применение разработанных методов на различных прикладных задачах
5.1. Задача 1. Распараллеливание алгоритма конструирования реляционных схем
5.1.1. Построение информационного графа алгоритма
5.1.2. Оптимизация информационного графа алгоритма нормализации реляционных отношений
Выводы
5.2. Задача 2. Организация преобразований в системах, основанных на расписании
5.2.1. Выполнение параллельных процессов в системе
5.2.2. Графовый метод распределения задач на кластере
5.2.3. Матричный метод распределение задач
5.2.4. Применение онтологий при организации процесса распределения задач на кластере
Выводы
5.3. Задача 3. Тестирование разработанных методов на модели управления процессом электролиза алюминия
5.3.1. Структурная идентификация процесса получения алюминия
5.3.2. Выбор метода решения системы линейных уравнений
5.3.3. Применение методов распараллеливания к алгоритму по приведению разреженной матрицы к форме ВПЕ на модели управления процессом электролиза алюминия
Выводы
5.4. Задача 4. Применение матричных методов в теории принятия решений
5.4.1. Особенности алгоритмов построения дерева решений
5.4.2. Применение методов распараллеливания к

Деревья
Еще одной разновидностью графа являются деревья - иерархические структуры некой совокупности элементов. С точки зрения классической теории графов, деревья — малопривлекательный объект, в монографиях по теории графов им редко отводится больше одной главы. Иное отношение к деревьям в прикладной теории графов: они играют важную роль в программировании, теории информационных систем, электротехнике, химии и пр.
Деревом называется неориентированный связный граф без циклов [59]. Вершины при этом называются узлами.
Формально дерево можно рекуррентно определить следующим образом:
1. Один узел является деревом. Этот же узел также является корнем этого дерева.
2. Пусть п - это узел, а 7], Т2,Тк - деревья с корнями пип2,.:.,пк соответственно. Можно построить новое дерево, сделав п родителем узлов п[,п2
Обычно при работе с деревом выделяют конкретную вершину, которую определяют как корень дерева, и рассматривают ее особо: в нее не заходит не одно ребро. В этом случае дерево становится ориентированным.
Ориентированным деревом (ордеревом, или корневым деревом) называется орграф со следующими свойствами:
1. существует единственный узел, полустепень захода которого равна нулю, т.е. в нее не заходит ни одно ребро. Он называется корнем ордерева;
2. полустепень захода всех остальных узлов равна единице, т.е. в них заходит только одно ребро, а исходит произвольное количество ребер;
3. каждый узел достижим из корня.
Подграф, определяемый множеством узлов, достижимых из узла у, является ордеревом с корнем у (это ордерево называется поддеревом узла у).