Декомпозиция расчетных сеток для решения задач механики сплошных сред на высокопроизводительных вычислительных системах

• Автор: Головченко, Евдокия Николаевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 165 с. : ил.

Оглавление
Введение
Глава 1. Постановка задачи
1.1 Критерии декомпозиции
1.2 Математические модели
1.3 Моделирование газоплазменных потоков в диверторе токамака
1.4 Моделирование воздушных ударных волн
1.4.1 Моделирование распространения ударной волны от приземного источника энергии взрывного типа
1.4.2 Моделирование распространения ударной волны от взрыва химического взрывчатого вещества в протяженном сооружении с нетривиальной геометрией
1.5 Программный комплекс МАИРЬЕЗО
Глава 2. Алгоритмы декомпозиции
2.1 Модель декомпозиции
2.1.1 Построение графа по сетке
Нодальный граф
Дуальный граф
2.1.2 Модели декомпозиции графов
2.1.3 Модель декомпозиции
2.2 Обзор и анализ существующих алгоритмов
2.2.1 Простые алгоритмы разбиения сеток
2.2.2 Алгоритмы геометрической декомпозиции сеток
2.2.3 Алгоритмы декомпозиции графов
2.2.3.1 Спектральная бисекция
2.2.3.2 Алгоритм локального уточнения
2.2.3.3 Иерархические алгоритмы
Огрубление графа
Разбиение огрубленного графа
Восстановление разбиения
Локальное уточнение разбиения
Параллельные реализации иерархических алгоритмов
2.2.3.4 Диффузионные и генетические алгоритмы
Диффузионные алгоритмы
Генетические алгоритмы
2.2.3.5 Оптимизация характеристических отношений доменов
2.2.3.6 Алгоритмы наращивания доменов
Алгоритм Фархата

Жадный алгоритм с выигрышами
Алгоритм пузырькового роста
2.2.3.7 Инкрементный алгоритм декомпозиции графов
2.3 Параллельный алгоритм геометрической декомпозиции сеточных данных
2.3.1 Параллельная сортировка
2.3.2 Деревья разбиений
2.3.3 Определение количества доменов, формируемых на процессорах.
2.3.4 Рекурсивная координатная бисекция вершин по процессорам
2.3.5 Локальная рекурсивная координатная бисекция вершин по доменам
2.3.6 Принятые решения
2.4 Параллельный инкрементный алгоритм декомпозиции графов
2.4.1 Геометрическая декомпозиция
2.4.2 Присоединение малых блоков вершин
2.4.3 Инициализация доменов и локальное разбиение
Инициализация доменов
Локальное разбиение
2.4.4 Перераспределение плохих групп доменов и повторное локальное разбиение
Перераспределение плохих групп доменов
2.4.5 Принятые решения
Глава 3. Результаты
3.1 Комплекс программ параллельной декомпозиции сеток GRIDSPIDERPAR
3.2 Сравнение параллельного инкрементного алгоритма с последовательным инкрементным алгоритмом
3.3 Масштабируемость алгоритмов
3.4 Разбиения на микродомены
3.5 Разбиения на домены
3.6 Результаты тестирования разбиений на физических задачах
3.7 Результаты тестирования разбиений на микродомены на физических задачах
Заключение
Список литературы

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

Глава 2. Алгоритмы декомпозиции
2.1 Модель декомпозиции
2.1.1 Построение графа по сетке
Для учета коммуникационных нагрузок сетки задача разбиения сетки на домены обобщается на задачу разбиения графа на домены. Для каждой сетки можно построить несколько графов.
Нодальный граф
В нодальном графе (nodal graph) вершины графа соответствуют узлам сетки, а ребра - связям между узлами [38]. В полном нодальном графе (complete nodal graph) между вершинами существует ребро, если соответствующие узлы связаны элементом (Рис. 136). В сокращенном нодальном графе (reduced nodal graph) между вершинами есть ребро, только если соответствующие узлы связаны линией на границе элемента (Рис. 13в).
Рис. 13. Построение нодального графа, а) — исходная сетка, б) - полный нодальный граф, в) - сокращенный нодальный граф
Дуальный граф
В дуальном графе (dual graph) вершины представляют собой элементы сетки. В сокращенном дуальном графе (reduced dual graph) на Рис. 146 вер-