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

• Автор: Якобовский, Михаил Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 225 с. : ил.

Введение

Глава 1. Статическая балансировка загрузки.

Постановка задачи

Критерии декомпозиции графов.

Иерархический алгоритм декомпозиции графа

Огрубление графа.

Первичное разбиение графа

Спектральная бисекция

Восстановление графа.

Дополнительные критерии декомпозиции.

Инкрементный алгоритм декомпозиции графа.

Иерархическое хранение больших сеток.
Измельчение пирамидальных сеток
Глава 2. Динамическая балансировка загрузки
Постановка задачи
Алгоритм серверного параллелизма.
Структура параллельной программы
Управляющий алгоритм балансировки загрузки.
Основной цикл взаимодействия управляющих процессов.
Двухуровневый алгоритм серверного параллелизма.
Глава 3. Распределенная визуализация.
Постановка задачи
Архитектура системы визуализации.
Этапы визуализации.
Серверная и клиентская части системы визуализации
Визуализация трехмерных скалярных данных.
Методы преобразования решеток в пирамидальные сетки.
Разбиение ячейки на пирамиды
Разбиение 8ми ячеек на пирамиды
Разбиение ячейки на 5 пирамид
Симметричное разбиение смежных ячеек.
Разбиение ячейки на 6 пирамид
Аппроксимация изоповерхности.
Виды данных описывающих триангуляцию.
Точность аппроксимации.
Вычисление абсолютной ошибки.
Сохранение топологических особенностей.
Методы построения аппроксимирующей триангуляции
Метод кластеризации
Метод детализации.
Метод синтеза.
Метод редукции
Параллельные алгоритмы построения аппроксимирующих триангуляций
Результаты тестирования.
Зависимость времени обработки и коэффициента сжатия методом редукции от
точности аппроксимации
Зависимость времени и коэффициента сжатия от гладкости изоповерхности 9 Соотношение времени чтения данных и времени их обработки
Сравнение метода синтеза и метода редукции
Зависимость времени расчета и коэффициента сжатия от числа используемых
процессоров
I технологий визуализации данных.
Интерфейс системы визуализации
Глава 4 Среда моделирования сеточных задач на распределенных вычислительных
системах
Управление вычислительным экспериментом.
Моделирование обтекания трехмерных тел сложной формы
Моделирование обтекания ступеньки.
Моделирование обтекания сферы.
Моделирование обтекания летательных аппаратов.
Распределенное хранение сеточных данных.
Моделирование задач горения.
Моделирование распространения горячей газовой струи.
Моделирование добычи углеводородов с помощью методов перколяции
Параллельный алгоритм генерации последовательностей псевдослучайных чисел
Заключение
Список литературы


Н.Четверушкину, оказавшему большое влияние на все этапы выполнения исследований, за неослабевающее внимание к работе и постоянную поддержку. Автор выражает искреннюю благодарность своему учителю Е. И.Леванову за постоянное внимание и поддержку. Автор глубоко благодарен А. Р.Кесселю и С. С.Лапушкину за постановку задачи моделирования динамики заводнения месторождений нефти и газа с помощью перколяционных методов, предложенную математическую модель и плодотворные обсуждения. Автор выражает глубокую благодарность С. В.Полякову, за многочисленные дискуссии по широкому кругу затрагиваемых в диссертации вопросов. Автор благодарен П. С.Кринову, С. А.Сукову, С. В.Муравьеву, М. С.В. Болдареву, И. И.Антоновой и Д. В.Петрову за совместную работу над созданием и реализацией ряда рассматриваемых в диссертации алгоритмов, библиотек и программ. Автор благодарен Б. М.Шабанову, О. С.Аладышеву, П. Н.Телегину и другим сотрудникам МСЦ РАН за внимательное отношение и всестороннюю поддержку, позволившую успешно выполнить значительную часть вычислительных экспериментов. Автор выражает свою особую благодарность И. И.Галигузовой за доброжелательную поддержку на протяжении многих лет. Глава 1. Широко используемый при численном решении с помощью конечных разностей или конечных элементов задач механики сплошной среды метод геометрического параллелизма предполагает деление сетки, покрывающей геометрическую расчетную область, на множество доменов, каждый из которых обрабатывается отдельным процессором системы. Общая вычислительная нагрузка каждого из процессоров определяется суммарным временем обработки входящих в домен элементов сетки. Объем передаваемых между процессорами данных определяется общим количеством элементов сетки, инцидентных рёбрам, соединяющим вершины, принадлежащие разным доменам. Основная проблема при использовании метода геометрического параллелизма связана с необходимостью решения задачи статической балансировки загрузки - выбора такой декомпозиции расчетной сетки, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные дублированием вычислений и необходимостью передачи данных между процессорами, малы. Современные коммуникационные среды обеспечивают одновременную передачу данных между независимыми парами процессоров без снижения скорости передачи относительно случая монопольного использования коммуникационного оборудования парой процессоров. Таким образом, следует минимизировать не общий объем передаваемых в ходе расчета данных, а максимальный объем данных, передаваемых каждым из процессоров. При использовании регулярных сеток, топологически эквивалентных индексному параллелепипеду, задача декомпозиции сетки, как правило, решается просто. Достаточно разбить сетку гиперплоскостями перпендикулярными к её индексным осям, на заданное число доменов, в каждом из которых содержится примерно одинаковое количество узлов. Задача рационального распределения по процессорам нерегулярных сеток может быть сведена к разбиению на компактные домены вершин графа, веса узлов которого отражают объемы вычислений в соответствующих элементах сетки, а веса ребер - объемы данных, передача которых необходима для выполнения согласованного расчета элементов сетки, обрабатываемых на разных процессорах. Требуется найти такое разбиение я(г)=(р, у. Множитель а обеспечивает согласование единиц измерения весов вершин и ребер, что позволяет одновременно учитывать требования выравнивания вычислительной и снижения коммуникационной нагрузки на процессоры, сводя задачу декомпозиции к минимизации У. Задача рационального разбиения графов (1)-(2), наиболее близкой к которой можно считать задачу о разрезании графов [7] является ЫР-полной [8]. В общем случае найти ее точное решение за обозримое время не представляется возможным, что приводит к необходимости использования эвристических алгоритмов []. При моделировании задач механики сплошной среды с помощью сеточных методов, как правило, значения сеточных функций последовательно вычисляются для множества моментов модельного времени.