Алгоритмы анализа и синтеза управляющих графов в задачах организации параллельных вычислений

• Автор: Попова-Коварцева, Дарья Александровна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Самара
• Количество страниц: 174 с. : ил.

Содержание
Введение
1. СОВРЕМЕННОЕ СОСТОЯНИЕ МЕТОДОВ СИСТЕМНОГО АНАЛИЗА МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

1.1. Методы анализа моделей параллельных алгоритмов

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

1.3. Современные методы глобальной оптимизации

Выводы и основные результаты

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

2.1. Концептуальная модель технологии ГСП

2.2. Управление вычислительными процессами. Граф-машина

2.2.1. Представление графа управления агрегатов

2.2.2. Граф-машина
2.3. Концептуальная модель организации параллельных вычислений в ГСП
2.3.1. Синхронный параллелизм
2.3.2. Правила построения модели организации параллельных вычислений
2.3.3. Межмодульный интерфейс параллельного обмена данными
2.3.4. Десуперпозиция Р-графа
2.3.5. Сложность алгоритма Р-нумерации вершин Р-графа
2.4. Алгоритм Б-нумерации вершин Р-графа
2.4.1. Головная программа алгоритма Р-нумерации Р-графа
2.4.2. Агрегат «Разметка вершин преемников для дуг типа 1»
2.4.3. Агрегат «Разметка вершин преемников для дуг типа 2»
2.4.4. Агрегат «Разметка вершин преемников для дуг типа 3»
2.5. Алгоритм десуперпозиции Р-графа
2.5.1. Агрегат «Построение графа, содержащего подграфы»
2.5.2. Агрегат «Вершина ветвления графа, содержащего подграфы».
2.5.3. Агрегат «Параллельный граф без вложений»
2.6. Преобразование графа управления модели параллельного алгоритма к стандартному виду
2.7. Алгоритм суперпозиции иерархической граф-модели параллельных вычислений
2.7.1. Дерево вложенности агрегатов
2.7.2. Алгоритм операции суперпозиции двух агрегатов
Выводы и основные результаты
3. ОПТИМИЗИРУЮЩИЕ ПРЕОБРАЗОВАНИЯ ПРОГРАММ. АЛГОРИТМ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

3.1. Введение
3.2. Методы глобальной оптимизации функций многих переменных
3.3. Постановка задачи глобальной оптимизации. Метод половинных делений
3.4. Оценка сложности алгоритмов глобальной оптимизации
3.4.1. Полный перебор метода половинных делений
3.4.2. Метод половинных делений с учётом отбраковки параллелепипедов
3.4.3. Метод редукции
3.4.4. Алгоритмы глобальной оптимизации, использующие локальную технику
3.5. Модифицированный метод половинных делений глобальной оптимизации функции многих переменных
3.6. Алгоритм построения множества точек начальных приближений для алгоритма локальной оптимизации
3.7. Двухфазный алгоритм метода половинных делений (ДАМПД)
3.8. Параллельная версия двухфазного алгоритма метода половинных делений
3.9. Исследование сходимости двухфазного алгоритма метода половинных делений
3.10. Схема «менеджер-исполнитель» ДАМПД
3.11. Генератор тестовых многоэкстремальных функций многих переменных
3.12. Исследование эффективности алгоритма ДАМПД
Выводы и основные результаты
4. СТРУКТУРНАЯ ОПТИМИЗАЦИЯ АГРЕГАТОВ ТЕХНОЛОГИИ ГСП.
4.1. Введение
4.2. Структурное тестирование агрегатов технологии ГСП
4.3. Схемы маршрутов в технологии ГСП
4.4. Метрики оценки структурной сложности программы
4.5. Алгоритм структурного преобразования программы
4.6. Алгоритм топологической сортировки
4.6.1. Топологическая сортировка
4.6.2. Алгоритм Р-нумерации
Выводы и основные результаты
Заключение
Список литературы
Приложение
П1.1 Агрегат "Десуперпозиция параллельного графа па составляющие"
П1.2 Текст модуля "Проверка вложенности параллельных ветвей"
Приложение 2 Акты внедрения

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

агрегата проектировщик освобождается от необходимости установления информационных связей, которые устанавливаются автоматически.
Агрегат терногазодинамического расчета ТРДД
Агрегация
Библиотека моду лей термогазодпнямнческого расчета ГТД
- ВЕНТ. ТГ- КВД
1 кип СА
У КС
4 ТОО
Модель териогазодинаиического расчета ТРДД.
Канал 2 контура

Расчет СА невязок
КНЦ КВД КС твд тнд Первый контур
Метод Ньютона
і5 Список греднкатов 1. Истина

Выходные параметры двигателя
12. | Е і < 0.000
Рисунок 2.
2.2. Управление вычислительными процессами. Граф-машина
В технологии ГСП для объектов - агрегатов используется мониторная схема организации вычислений. Фактически вычислительным процессом управляет универсальная программа: граф-машина, общая для всех
агрегатов. Исходной информацией для граф-машины служит, описанная выше, модель графа управления вычислительным процессом.
Синтез агрегата происходит на основе его графического изображения, представленного соответствующими структурами данных, которые хранятся в информационном фонде технологии ГСП.
В ГСП агрегат фактически состоит из двух компонент:
• универсальной управляющей программы граф-машины (ГМ), которая, в соответствии со структурой графа управления каждого из агрегатов, управляет развитием вычислительного процесса;