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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

«СТАНКИН»

На правахрукописи

Суков Сергей Александрович

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МОДЕЛИРОВАНИЯ

ГАЗОДИНАМИЧЕСКОГО ОБТЕКАНИЯ ТЕЛ НА НЕРЕГУЛЯРНЫХ ТЕТРАЭДРАЛЬНЫХ СЕТКАХ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2004

Работа выполнена в Московском Государственном Технологическом Университете «СТАНКИН»

Научный руководитель:

Официальные оппоненты:

кандидат физико-математических наук Якобовский М.В.

доктор физико-математических наук Луцкий А.Е.

кандидат физико-математических наук Шильников Е.В.

Ведущая организация:

Межведомственный Суперкомпьютерный Центр РАН

Защита диссертации состоится « ОеШорЯ/ 2004г. на заседании диссертационного совета Д 212.142.03 при Московском Государственном Технологическом Университете «СТАНКИН» по адресу: 103055, Москва, Вадковский пер., За.

С диссертацией можно ознакомиться в библиотеке МГТУ «СТАНКИН».

Автореферат разослан

2004 г.

Ученый секретарь диссертационного совета, кандидат технических наук

Семячкова Е.Г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Широкий круг проблем, стоящих перед современной наукой и техникой, связан с решением задач газовой динамики. Возросли требования, предъявляемые к летательным аппаратам, в области экологии и экономичности. В связи с этим актуальны задачи проектирования и конструирования многокомпонентного сложного профиля крыла, оптимизации аэродинамических форм, уменьшения шума струи реактивного двигателя. Для изучения этих проблем необходимо полное решение уравнений Навье-Стокса для вязкого сжимаемого теплопроводного газа (иногда с учетом химически реагирующих сред). Фактически единственным эффективным способом решения сложных систем нелинейных дифференциальных уравнений, каковыми являются газодинамические уравнения Эйлера и Навье-Стокса, являются численные методы.

Алгоритм построения численного метода существенно зависит от способа дискретизации расчетной области (разностной сетки). На сегодняшний день все более широкое распространение получают методы генерации сеток, основанные на поверхностной и пространственной триангуляции. Тетраэдральная сетка может обладать нерегулярной структурой (иметь переменную плотность узлов по пространству), что позволяет сосредоточить большинство узлов расчетной сетки в тех подобластях, где необходимо получить решение с повышенной точностью, и с высокой точностью аппроксимировать поверхности сложной формы.

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

Одно из наиболее интересных направлений развития современной вычислительной техники на сегодняшний день представляют многопроцессорные вычислительные системы. Основным параметром их классификации является наличие общей (SMP) или распределенной (МРР) памяти. Использование многопроцессорной техники сопряжено с рядом проблем, не связанных непосредственно с проблематикой решаемых задач, но значительно затрудняющих использование параллельных систем. Это сложность адаптации последовательных алгоритмов к параллельным системам вообще и к системам с распределенной памятью, в особенности, и проблема обеспечения равномерной загрузки процессоров в ходе решения задачи. Кроме того, существенные трудности по применению многопроцессорных систем для решения задач математической физики связаны с обработкой нерегулярных сеток большого размера.

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

Цели диссертационной работы. Основной целью данной диссертационной работы является разработка эффективных параллельных алгоритмов моделирования пространственных газодинамических течений для многопроцессорных систем с общей и распределенной памятью с использованием нерегулярных тетраэдральных сеток большого размера. Для ее достижения решаются следующие задачи:

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

• Разработка параллельных алгоритмов моделирования обтекания тел сложной формы на тетраэдральных сетках для многопроцессорных систем с общей и распределенной памятью.

• Исследование особенностей обработки нерегулярных сеток при решении задач математической физики и создание алгоритмов распределенного хранения и обработки нерегулярных сеток большого размера.

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

Научная новизна и практическая ценность работы. В диссертации предложены оригинальные параллельные алгоритмы моделирования задач газовой динамики для многопроцессорных систем с общей и распределенной памятью на основе методов конечных объемов и конечных элементов с использованием нерегулярных сеток. Разработаны алгоритмы двухуровневого распределенного хранения и обработки тетраэдральных сеток большого размера. С учетом особенностей расчетов на основе методов конечных объемов и конечных элементов сформулированы критерии оценки качества балансировки загрузки.

На основе разработанных алгоритмов создан комплекс параллельных программ по решению задач газовой динамики. Выполнено тестирование программ комплекса на различных многопроцессорных вычислительных системах для различного числа процессоров и объема исходных данных.

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

На примере задачи моделирования невязкого обтекания летательного аппарата показана возможность использования разработанного комплекса программ при выполнении научных исследований и производственных расчетов.

Апробация работы.

Основные результаты диссертационной работы докладывались и обсуждались на многих научно-технических конференциях и семинарах, в частности:

- на IV-ой Научной конференции МГТУ «СТАНКИН» и «Учебно-научного центра математического моделирования МГТУ «СТАНКИН» и ИММ РАН», Москва, 2001 г.

- на 2-ой Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки", Самара, 2001 г.

- на V-ом Международном конгрессе по математическому моделированию, Дубна, 2003 г.

- на конференции Parallel Computational Fluid Dynamics (ParCFD), Москва, 2003.

-на VI-ом Международном конгрессе по математическому моделированию, Нижний Новгород, 2004.

- неоднократно на семинарах ИММ РАН.

Публикации. Основные результаты диссертации опубликованы в пяти работах, список которых приведен в конце данного автореферата.

Достоверность результатов. Достоверность результатов, полученных в работе, подтверждается тем, что для выполненных в работе численных расчетов наблюдается качественное совпадение полученных результатов с точным решением соответствующих задач, экспериментальными данными и результатами других авторов. Эффективность предложенных параллельных алгоритмов подтверждается результатами тестирования разработанных на их основе программ.

Реализация результатов. Результаты диссертации получены в ходе выполнения ряда работ, поддерживаемых РФФИ, в которых автор при-

нимал участие в качестве основного исполнителя (гранты 02-01-00589,0401-00310, 02-07-90168, 02-01-00700) и руководителя (гранты 02-01-06203, 03-01-06108). Разработанный комплекс параллельных программ является составной частью пакета моделирования задач механики сплошной среды, разрабатываемого в ИММ РАН в рамках государственного контракта № 10002-251/0МН-03/026-023/240603-806 от 30 апреля 2003 г.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем составляет 128 машинописных страниц, текст содержит 35 рисунков и 8 таблиц

СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из введения, четырех глав, заключения и списка используемой литературы.

Во введении обоснована актуальность рассматриваемых в работе проблем, сформулированы основные цели диссертации и дано ее краткое содержание по главам.

В первой главе содержится постановка рассматриваемых в работе задач газовой динамики, приводится описание используемой математической модели, ее численной реализации и построенного на их основе расчетного алгоритма.

Рассматриваются задачи нестационарного вязкого и невязкого газодинамического обтекания. В качестве математической модели взята система безразмерных уравнений Навье-Стокса, описывающая течения вязкого теплопроводного совершенного газа, записанных в дивергентной форме, и уравнения Эйлера. Пространственная дискретизация выполнена на тетраэдральных сетках с использованием методов конечных объемов (конвективный перенос) и конечных элементов (диффузионная часть). Для расчетов на основе интегро-интерполяционного метода вокруг каждого узла сетки строится барицентрический контрольный объем. Численный поток

через грани контрольного объема определяется с помощью схем Роу и кинетически согласованной разностной схемы (КСРС) Четверушкина. Схема Роу, в основу которой положено приближенное решение задачи Римана о распаде произвольного разрыва, дает хорошие результаты при расчете течений с разрывами (ударные волны, волны разрежения). Оригинальная методика КСРС, базирующаяся на кинетическом расщеплении вектора потока, дает возможность проводить расчеты течений с разрывами и моделировать слабосжимаемые течения при малых числах Маха. Повышение порядка аппроксимации достигается заменой кусочно-постоянного распределения газодинамических параметров в расчетной ячейке на кусочно-линейное. При определении кусочно-линейного распределения используются узловые градиенты, определенные по окружающему узел контрольному объему. Для устранения нефизических осцилляции разностного решения в окрестностях разрывов и больших градиентов делается локальное переключение на схему первого порядка в зависимости от знака соседних узловых градиентов. Дискретизация членов со вторыми производными осуществляется методом конечных элементов с использованием линейных базисных функций, определенных на каждом тетраэдре (Р1-метод Галер-кина). Интегрирование по времени выполняется явным линейным методом типа Рунге-Купы второго порядка точности или с использованием схемы Эйлера первого порядка.

Предложенный на основе выбранной дискретной модели расчетный алгоритм согласно теоретическим оценкам содержит минимальное число действий, т.е. имеет минимальную вычислительную сложность. Для сокращения числа операций разработан метод огрубления барицентрического контрольного объема. Предложенный подход позволяет изменить форму расчетных ячеек таким образом, чтобы между двумя соседними контрольными объемами существовала только одна плоская грань, что суще-

ственно снижает затраты времени и ресурсов на вычисление конвективных потоков.

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

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

Обработка нерегулярных сеток, даже в последовательном режиме, сопряжена с существенными трудностями. Нерегулярная сетка в пространстве любой размерности имеет только одномерную нумерацию узлов, что в свою очередь требует явного описания всех ее элементов. Следствием этого является тот факт, что на практике производительность реализации какого-либо алгоритма, связанного с обработкой элементов нерегулярной сетки, зависит от нумерации узлов сетки и последовательности обработки ее элементов.

Для исключения подобных эффектов предлагается использовать оригинальный алгоритм обработки нерегулярных сеток. Суть алгоритма состоит в предварительном разбиении сетки на связные подобласти, локализации подобластей путем выделения элементов (тетраэдров), находящихся целиком внутри подобластей (внутренние подобласти) и на границах между ними (граничная подобласть), с одновременной перенумерацией узлов с учетом полученного разбиения. Далее для вычисления значений искомых переменных на новом слое по времени выполняется последова-

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

В третьей главе приводится описание разработанных параллельных алгоритмов моделирования для многопроцессорных систем с общей и распределенной памятью. Рассматриваются проблемы балансировки загрузки и организации распределенного хранения и обработки нерегулярных сеток большого размера.

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

В качестве модели выполнения параллельного алгоритма для SMP систем взята модель общей памяти. В модели общей памяти параллельная программа представляет собой систему легковесных вычислительных процессов (нитей), взаимодействующих посредством общих переменных и

примитивов синхронизации. Программа начинает свое выполнение как один процесс (главная нить). При входе в параллельную область главная нить порождает некоторое число подчиненных ей нитей. При выходе из параллельной области алгоритма порожденные нити сливаются с главной, которая продолжает дальнейшее выполнение. Основной сложностью при разработке параллельных алгоритмов и программ для мультипроцессоров является решение проблем одновременного доступа к данным (когерентности кэш-памяти) и обработки критических секций. Критическими секциями являются те места алгоритма, где возможна одновременная модификация несколькими нитями одной разделяемой переменной.

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

Многопроцессорные системы с распределенной памятью и вычислительные кластеры на сегодняшний день являются самыми распространенными платформами для высокопроизводительных вычислений. Они хорошо масштабируются путем добавления новых вычислительных модулей, что для решения задач газовой динамики дает возможность увеличивать число узлов расчетной сетки. Основной на сегодняшний день моделью параллельного программирования на вычислительных кластерах и МРР системах является модель передачи сообщений. Чаще всего для ее реализации стандартный язык последовательного программирования рас-

ширяется специальными библиотечными функциями (например, С + MPI). В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Взаимодействие процессов - обмен данными и синхронизация - осуществляется посредством передачи сообщений. Основные трудности при разработке параллельных алгоритмов в рамках такого подхода связаны с необходимостью локализации данных для обработки каждым процессором и инициализации массивов межпроцессорного обмена данными.

Обработка сеток большого размера (миллионы узлов) сопряжена с трудностями, связанными с нерегулярностью их структуры и непосредственно с обработкой больших объемов данных. Описание геометрии такой сетки, как и таблица распределения узлов по процессорам, не могут целиком храниться в оперативной памяти одного вычислительного узла, и, следовательно, все действия, связанные с ее обработкой, должны выполняться в распределенном режиме.

Распределенная обработка топологии сеток выполняется с использованием специально разработанного алгоритма двухуровневого распределенного хранения и обработки топологии нерегулярных сеток. Перед началом серии расчетов сетка делится на множество подобластей (микродоменов). Затем в соответствии с полученным разбиением производится перенумерация (изменение идентификаторов) узлов сетки и выделяется описание геометрии каждого микродомена. Далее топология сетки записывается в распределенном виде: описание общей структуры (граф микродоменов и их связей) и множество отдельных описаний микродоменов. Формат записи описаний отдельных подобластей определяется требованиями используемой для расчетов численной методики. В соответствии с выбранным алгоритмом численного моделирования микродомен задается набором данных, которых достаточно для автономного определения геометриче-

ских параметров контрольных объемов с центрами в узлах рассматриваемой подобласти.

Процедура подготовки расчета (подготовки данных для параллельного выполнения вычислительных итераций) делится на несколько этапов. На этапе балансировки загрузки выполняется разбиение графа микродоменов на подобласти, в результате чего каждый процессор получает список обрабатываемых микродоменов. Разбиение графа микродоменов требует намного меньших затрат времени по сравнению с разбиением исходной сетки и, учитывая его малый размер, может быть выполнено на одном процессоре. Далее происходит объединение микродоменов процессора: составляется список обрабатываемых элементов геометрической модели его расчетной области. Следующий этап заключается в локализации полученной расчетной области с учетом передаваемых и принимаемых данных (соответствующая перенумерация узлов) и одновременной инициализации буферов приема и передачи данных.

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

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

В заключение описания параллельного алгоритма для вычислительных кластеров рассматриваются возможные варианты организации межпроцессорного обмена данными (периодичности обменов и объемов передаваемой информации) во время выполнения вычислительных итераций, и дается теоретическая оценка их эффективности с точки зрения производительности соответствующих параллельных программ.

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

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

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

Оценка эффективности предложенных в работе последовательного и параллельных алгоритмов моделирования задач газовой динамики выполнялась путем тестирования производительности разработанного на их основе комплекса программ. Модельные расчеты выполнялись с использованием нерегулярных тетраэдральных сеток, содержащих от 500000 до 2 000 000 узлов. Для расчета в последовательном режиме приведен наглядный пример возможной зависимости времени выполнения программы от порядка обработки элементов и нумерации узлов сетки. Запуск параллельных программ производился на различных многопроцессорных вычислительных системах с общей и распределенной памятью. Приведены результаты сравнения производительности параллельных программ для систем с общей и распределенной памятью по отношению к производительности последовательной программы, а также сравнительный анализ эффективности программы для систем с распределенной памятью при расчетах на большом числе процессоров (до 100) для различных вычислительных кластеров. На основании полученных в ходе тестирования производительности результатов сделана оценка эффективности разработанных алгоритмов и программ.

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

В заключении диссертационной работы сформулированы основные выводы и приведены выносимые на защиту результаты.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработаны алгоритмы распределенного двухуровневого хранения и эффективной параллельной обработки нерегулярных сеток, содержащих миллионы узлов.

3. Разработаны параллельные алгоритмы моделирования газодинамических течений для систем с общей и распределенной памятью. Разработан и успешно опробован на ряде расчетов вязкого и невязкого обтекания трехмерных тел комплекс последовательных и параллельных программ решения задач газовой динамики.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Болдырев С.Н., Леванов Е.И., Суков СА, Якобовский М.В., Обработка и хранение нерегулярных сеток большого размера на многопроцессорных системах. Материалы 3 Всероссийского семинара. Казань. Изд-во Казанск. мат. об-ва, 2002, с. 33-39.

2. Chetverushkin B.N., Kornilim MA, Sukov SA, Iakobovski M.V., Methane combustion simulation on multiprocessor computer systems, Mathematical Modeling. Problems, methods, applications, Proc. ofthe Fourth International Mathematical Modeling Conference, June 27 - July 1 2000, Moscow, Russia (Ed. by LA Uvarova, A.V. Latyshev), Kluwer Academic, Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. ISBN 0-306-46664-3, 2001, pp. 53-59.

3. Суков С.А., Якобовский М.В., Обработка трехмерных неструктурированных сеток на многопроцессорных системах с распределенной памятью. В сб. "Фундаментальные физико-математические проблемы и мо-

делирование технико-технологических систем", вып. 6, под ред. Л.А. Уваровой. М, Изд-во "Janus-K", 2003, с. 233-239.

4. Mikhail V. Iakobovski, Sergey N. Boldyrev, and Sergey A. Sukov, Big Unstractured Mesh Processing on Multiprocessor Computer Systems, Parallel Computational Fluid Dynamics (Moscow, Russia, May 13-15,2003), Edited by B. Chetverushkin, A. Ecer, J. Periaux and N. Satomka - Assistant Editor. Pat Fox, Elsevier Science BV, Amsterdam, 2004, pp. 71-77.

5. Абалакин И.В., Суков СА, Моделирование внешнего обтекания тел на многопроцессорных системах с использованием тетраэдрических сеток. В сб. "Фундаментальные физико-математические проблемы и моделирование технико-технологических систем", вып. 7, под ред. Л.А. Уваровой. М., Изд-во "Janus-K", 2004, с. 52-57.

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Суков Сергей Александрович

Параллельные алгоритмы моделирования газодинамического обтекания тел на нерегулярных тетраэдральных сетках

Лицензия на издательскуюдеятельностьЛР №01741 от 11.05.2000 Подписано в печать 15.11.2004. Формат 60x90 1/16 Уч.изд. л. 1. Тираж50 экз. Заказ № 213

Отпечатано в Издательском Центре МНУ «СТАНКИН» 103055, Москва, Ваковский пер., д.3а

1123 5 o?

Содержание.

А Введение.

Глава 1. Постановка задачи, математическая модель и численная реализация.

Описание рассматриваемых задач.

Математическая модель. Безразмерные уравнения Навье-Стокса и граничные условия.

Численная реализация.

Пространственная аппроксимация.

Определение конвективного численного потока.

Схема Роу.

Кинетически-согласованная разностная схема Четверушкина.

Поток повышенного порядка точности (МШСЬ аппроксимация).

Определение диффузионного численного потока.

1 Определение потоков на границе области.

4 Аппроксимация по времени.

Расчетный алгоритм.

Глава 2. Последовательный алгоритм.

Последовательный алгоритм.

Обработка нерегулярных сеток.

Глава 3. Параллельные алгоритмы.

Балансировка загрузки.

Параллельный алгоритм для систем с общей памятью.

Параллельный алгоритм для многопроцессорных систем с распределенной памятью.

Распределенная обработка нерегулярных сеток.

Параллельный алгоритм.

Глава 4. Результаты расчетов.

Расчет газодинамических течений.

Эффективность параллельных алгоритмов.

В диссертации рассматриваются вопросы эффективного использования многопроцессорных вычислительных систем (МВС) для моделирования пространственных газодинамических течений с использованием нерегулярных расчетных сеток.

В современной науке широко используется методология математического моделирования [35]. Ее сущность состоит в замене исходного объекта его «образом» - математической моделью - и дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов. Этот метод сочетает в себе многие достоинства как теории, так и эксперимента. Работа с моделью объекта (явления, процесса) дает возможность безболезненно, относительно быстро и без существенных затрат исследовать его свойства и поведение в любых мыслимых ситуациях (преимущества теории). В то же время вычислительные (компьютерные, симуляционные, имитационные) эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных методов и технических инструментов информатики, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам (преимущества эксперимента).

Широкий круг проблем, стоящих перед современной наукой и техникой, связан с решением уравнений газовой динамики. Уравнения газовой динамики описывают движение сплошной сжимаемой среды. В последнее время практика все чаще выдвигает задачи, где на газодинамические течения воздействуют различные дополнительные факторы такие, как электромагнитные и гравитационные поля, процессы тепло- и электропроводности, химические реакции и т.д. Учет подобных явлений усложняет математическую постановку задач и порождает самостоятельные проблемы при их решении. Однако и в этом случае основу задачи по-прежнему составляют классические уравнения газовой динамики.

Разработанные на сегодняшний день аналитические методы решения уравнений газовой динамики, хотя и дают результаты высокой точности, но не охватывают всего спектра нужных в инженерной практике задач. Наибольших успехов развитие аналитических методов достигло только в исследовании уравнений Навье-Стокса для несжимаемой жидкости. Однако современное развитие аэрокосмической индустрии ставит перед исследователями в этой области несколько иные задачи, чем те которые были 20-30 лет назад. Возросли требования, предъявляемые к летальным аппаратам, в областях экологии и экономичности. В связи с этим актуальны задачи проектирования и конструирования сложного многокомпонентного профиля крыла (называемых в зарубежной литературе — high lift system), оптимизации аэродинамических форм, уменьшения шума струи реактивного двигателя. Для изучения этих проблем необходимо решение полных уравнений Навье-Стокса для сжимаемого теплопроводного газа (иногда и с учетом химически реагирующих сред). Фактически единственным эффективным способом решения сложных систем нелинейных дифференциальных уравнений, каковыми являются газодинамические уравнения Эйлера и Навье-Стокса, являются численные методы, реализуемые на быстродействующих вычислительных машинах. То есть, на основе математической модели при помощи непосредственного численного решения соответствующих уравнений количественно определяется поведение газодинамических течений в тех или иных условиях. В отличие от аналитических методов, где зачастую для каждой задачи разрабатываются свои самостоятельные приемы решения, численные методы отличаются большой универсальностью и применимы для исследования широкого класса явлений.

Нелинейность уравнений газодинамики требует аккуратного подхода в выборе численного метода. Во-первых, он должен отражать свойства решения дифференциальной задачи. Прежде всего, это выполнение разностных законов сохранения — свойство консервативности, особенно важное для моделирования течений с ударными волнами. Другое важное свойство дифференциальной задачи, которое должно переноситься и на численный метод — это «принцип максимума». Выполнение этого принципа численной методикой приводит к локально монотонным решениям, без дополнительных экстремумов, не присутствующих в решениях дифференциальной задачи. В теории численных методов для уравнений Эйлера существует различные способы реализации разностного «принципа максимума»: TVD (Total Variation Diminishing) схемы [69], «квазимонотонные» схемы [16, 17], ENO (Essentially Non-Oscillatory) схемы [70]. Во-вторых, алгоритм построения численного метода существенно зависит от способа дискретизации расчетной области (выбора разностной сетки). Так если используется структурированная прямоугольная сетка, то чаще всего численный метод выбирается на основе конечных разностей [31]. Для неструктурированных сеток (например, треугольных или тетраэдральных) построение численного алгоритма проводится с использованием метода конечных объемов (интегро-интерполяционный метод) или метода конечных элементов. В случае расчетов с использованием сильно анизотропной (неравномерной) сетки по методу конечных объемов немаловажным фактом является и способ построения контрольной ячейки, и выбор метода аппроксимации первой или второй производных. Помимо вышеназванных требований весьма важным является свойство однородности вычислительного алгоритма [35]. Оно заключается в том, что формулы, по которым ведется расчет, должны записываться единообразно во всех узлах сетки, без явного выделения возможных «нерегулярностей» решения, например, точек разрыва. Свойство однородности существенно упрощает организацию программы для реализации алгоритма на вычислительных системах.

В диссертации рассматриваются задачи нестационарного вязкого и невязкого газодинамического обтекания. В качестве математической модели газодинамических течений используется система уравнений Навье-Стокса, описывающая течения вязкого теплопроводного совершенного газа, и уравнения Эйлера. Пространственная дискретизация уравнений Навье-Стокса, проводится на тетраэдральных сетках с использованием метода конечного объёма (конвективный перенос) и метода конечных элементов (диффузионная часть) [57]. Такого типа смешанная (совместное использованием метода конечных объемов и метода конечных элементов) аппроксимация является эффективной методикой для решения уравнений Навье-Стокса, обладающих свойствами, как гиперболической, так и параболической систем уравнений. Метод конечного объема, примененный к аппроксимации невязкой (гиперболической) части системы уравнений, делает систему получающихся разностных уравнений консервативной в независимости от задания формы потока через грань контрольной ячейки. Метод конечных элементов, с заданием линейной функции на каждом тетраэдре, имеет порядок точности не ниже второго для задания вторых производных. Базовая аппроксимация первого порядка конвективных членов уравнения Навье-Стокса или численный поток через грани контрольного объема строится на основе решения задачи Римана по направлению внешней нормали к грани с использованием двух различных методов. Первый метод базируется на приближенном решении задачи Римана — схема Роу [81]. Второй метод — это метод расщепления вектора потока (рассматривается его частный случай, так называемая кинетически согласованная разностная схема или кинетическое расщепление) [4, 8, 21, 39, 49, 50, 87]. Повышения порядка аппроксимации достигается заменой кусочно-постоянного распределения газодинамических параметров в расчетной ячейке на кусочно-линейное распределение (аппроксимация типа МШСЬ) [85]. При определении кусочно-линейного распределения используются узловые градиенты, определенные по контрольному объему окружающему узел. Для устранения нефизических осцилляций разностного решения в окрестностях разрывов и больших градиентов делается локальное переключение на схему первого порядка в зависимости от знака соседних узловых градиентов.

Дискретизация членов со вторыми производными осуществляется методом конечных элементов с использованием линейных базисных функций, определенных на каждом тетраэдре (Р1-метод Галеркина). Интегрирование по времени выполняется явным линейным методом типа Рунге-Кутты второго порядка [75].

Моделирование газодинамических течений, на основе прямого численного расчета уравнений Навье-Стокса, достаточно дорогостоящая в вычислительном плане процедура. Во-первых, это связано с большим числом узлов разностных сеток, применяемых в реальных инженерных расчетах. Например, если надо детально описать течение с помощью численного моделирования на равномерной трехмерной кубической решетке, минимальное количество ее узлов пропорционально Яе9/4 [39], где Яе — число Рейнольдса. В этом случае даже в расчетах при умеренных (до 1500) числах Рейнольдса число узлов может достигать 107. В процессе моделирования сверхзвуковых течений для более детального описания взаимодействий разрывов между собой или с окружающим их течением возникает необходимость использовать подробную сетку в окрестности течения с большими градиентами. Помимо этого в некоторых случаях необходимо увеличивать плотность узлов сетки в области пограничного слоя. Так как толщина пограничного слоя имеет порядок Ке"1/2 [27], то количество узлов будет возрастать с увеличением числа Рейнольдса. Вторым значимым аспектом, приводящим к повышению вычислительной сложности алгоритма, является использование в численных методах аппроксимаций выше первого порядка точности. Численные алгоритмы повышенного порядка точности позволяют избежать нежелательной численной диссипации, характерной для разностных схем первого порядка.

Таким образом, одной из основных трудностей по применению численных методов для решения задач газовой динамики является большой объем вычислений. С течением времени возможности вычислительной техники увеличиваются, что позволяет повышать точность получаемых количественных характеристик и степень детализации картины физических явлений. Одновременно с этим появляется возможность изменить постановку задачи и усовершенствовать применяемый для ее решения математический аппарат. В результате процессы развития вычислительной техники и применяемого для решения задач математического аппарата становятся взаимосвязанными: рост возможностей электронной техники позволяет повышать сложность математических моделей, а усовершенствованные модели требуют для своей реализации технику все большей производительности [3, 7, 42, 51, 55, 74].

Одно из наиболее интересных направлений развития современной вычислительной техники на сегодняшний день представляют многопроцессорные вычислительные системы [25,30,72]. Основным параметром их классификации является наличие общей (SMP) или распределенной памяти (МРР). Нечто среднее между SMP и МРР представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кроме того, в последнее время во всем мире происходит бурное внедрение вычислительных кластеров, которые, по сути, являются более дешевым вариантом МРР.

Массивно-параллельные системы (МРР) состоят из однородных вычислительных узлов, которые включают в себя один или несколько центральных процессоров, локальную память (прямой доступ к памяти других узлов невозможен), коммуникационный процессор или сетевой адаптер, жесткие диски и/или другие устройства ввода-вывода. Узлы системы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.). При этом общее число процессоров в реальных МРР системах может достигать нескольких тысяч (например, ASCI Red и Blue Mountain). Для таких вычислительных комплексов возможно два варианта построения операционной системы (ОС): полноценная ОС работает только на управляющей машине, на каждом узле работает сильно урезанный вариант ОС, обеспечивающий только работу расположенной в нем ветви параллельного приложения; на каждом узле работает полноценная UNIX-подобная ОС (близкий к кластерному подходу вариант). Разработка параллельных алгоритмов и программирование для МРР систем выполняется в рамках модели передачи сообщений (MPI).

Симметричные мультипроцессорные системы (SMP) состоят из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью и подключены к ней либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора. Когерентность кэшей процессоров поддерживается на аппаратном уровне. Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel-платформ поддерживается Windows NT), которая в большинстве случаев автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling). Наличие общей памяти существенно упрощает взаимодействие процессоров между собой, но накладывает большие ограничения на их число. Для построения масштабируемых систем на базе SMP обычно используется кластерная архитектура. Разработка параллельных алгоритмов и программирование для SMP систем выполняется в рамках модели общей памяти (POSIX threads, OpenMP). Помимо этого существуют сравнительно эффективные средства автоматического распараллеливания.

Вычислительные кластеры представляют собой мультикомпьютеры, состоящие из множества отдельных компьютеров или рабочих станций общего назначения (узлов), связанных между собой единой коммуникационной системой. Каждый узел имеет свою локальную оперативную память (общей физической оперативной памяти для узлов не существует). Если в качестве узлов используются симметричные мультипроцессорные системы, то такой кластер называется SMP-кластером. Для вычислительных кластеров используются стандартные для рабочих станций операционные системы, чаще всего, свободно распространяемые

Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки. Программирование, как и в случае МРР систем, выполняется на основе модели передачи сообщений (MPI).

Системы с распределенной памятью, по-видимому, всегда будут лидировать по показателю пиковой производительности, поскольку любые новые однопроцессорные (или многопроцессорные на основе общей памяти) системы могут быть легко объединены сетью и использованы в качестве многопроцессорных вычислительных систем с распределенной памятью. Кроме того, массивно-параллельные системы и вычислительные кластеры, почти всегда выигрывают у систем с общей памятью по показателю соотношения цены и производительности.

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

На первом месте традиционно стоит сложность адаптации последовательных алгоритмов к параллельным системам вообще и к системам с распределенной памятью, в особенности [10, 12, 13, 14, 28, 38]. Практически неизвестны априорные способы установления правильности параллельного алгоритма, не говоря об установлении корректности конкретной реализации алгоритма в виде программы на том или ином алгоритмическом языке. Если для последовательной программы существует возможность создания системы тестов, выполнение которых в некоторой мере гарантирует работоспособность программы на некотором подмножестве исходных данных, то для параллельной программы нет даже такой возможности. Одна и та же программа, на одних и тех же данных может неограниченно долго давать верные (ожидаемые от нее) результаты, но дать совершенно непредсказуемый результат при очередном запуске с теми же данными. Причина такого неадекватного поведения параллельных программ кроется в наличии неопределенности в порядке выполнения действий, необходимых для получения результата. Например, ожидая ввода двух величин с двух каналов, нельзя заранее предсказать, с какого канала данные придут раньше. Основными на сегодняшний день методами построения параллельных программ и алгоритмов являются алгоритмический параллелизм, геометрический параллелизм, конвейерный параллелизм и параллелизм типа «коллективное решение» [43].

В качестве следующего препятствия на пути эффективного использования параллельной техники справедливо называют проблему обеспечения равномерной загрузки процессоров в ходе решения задачи. Задача балансировки загрузки [26,41] является одной из основных задач, решаемых при проведении параллельных вычислений, и одной из самых сложных и трудоемких при работе с нерегулярными сетками [53,68]. Необходимо таким образом распределить вычислительную и иную нагрузку между процессорами системы, чтобы по возможности исключить простои отдельных процессоров и наиболее эффективно использовать доступные ресурсы. Традиционно используемый при численном решении задач математической физики и применяемый в данной работе метод геометрического параллелизма предполагает деление общей расчетной области на множество подобластей, относимых к различным процессорам системы, путем соответствующего распределения сеточных узлов. При этом в случае использования систем с распределенной памятью, необходимо с одной стороны как можно более равномерно распределить между процессорами суммарный объем вычислений, а с другой стороны минимизировать межпроцессорные обмены данными, чтобы таким образом сократить общее время работы каждого из процессоров. На сегодняшний день известен широкий спектр алгоритмов статической и динамической балансировки загрузки [43], позволяющих сравнительно быстро и эффективно решать подобные задачи. Как правило, критериями разбиения являются примерно равное число узлов по подобластям и минимизация числа разрезанных в результате разбиения ребер сетки. В данной работе для расчетов с применением методов конечных объемов и конечных элементов сформулированы собственные, несколько отличные от традиционных, критерии оценки качества балансировки загрузки процессоров.

Многие требования к параллельным алгоритмам и пакетам параллельных программ формируются, исходя из существующих правил коллективного использования многопроцессорных вычислительных систем. Современные крупномасштабные вычислительные комплексы, как правило, доступны большому числу пользователей. Разделение вычислительной мощности системы между ними выполняется с помощью системы очередей заданий. Наивысший приоритет при выборе задачи на выполенение в большинстве случаев имеют программы, запускаемые на небольшом числе процессоров на достаточно короткое время. Расчеты с использованием всех процессоров системы на практике выполняются крайне редко и сильно ограничены по времени. Крупные многопроцессорные системы с общей памятью (SMP системы на 16 и более процессоров) в силу своей дороговизны и редкости, как правило, доступны ограниченному числу пользователей. В результате реальные масштабные численные эксперименты проводятся на МВС с распределенной памятью или вычислительных кластерах с использованием небольшого (в рамках данной системы) числа процессоров за множество коротких вычислительных сеансов.

Пространственная дискретизация рассматриваемой в работе системы уравнений выполняется с использованием тетраэдральных сеток. Такая сетка может обладать неоднородной структурой, то есть плотность ее узлов по пространству может меняться в достаточно широких пределах, что позволяет сосредоточить большинство узлов сетки в тех подобластях, где необходимо получить решение с повышенной точностью. Кроме того, нерегулярные сетки дают возможность с высокой точностью аппроксимировать поверхности сложной формы, например, поверхности обтекаемых газовым потоком летательных аппаратов. Приведенные свойства способны помимо прочего компенсировать тот факт, что аппроксимация на нерегулярных сетках обычно уступает по точности аппроксимации с использованием регулярных сеток [32,34]. При этом переменная плотность узлов и нерегулярная структура тетраэдральной сетки приводит к определенным трудностям при ее хранении и обработке, характерным для нерегулярных сеток вообще. В силу отсутствия глобальной упорядоченности в топологии для них в общем случае невозможно построить систему целочисленных координат той же размерности, что и у пространства задачи, имеющих простую функциональную связь со структурой взаимного расположения узлов и ребер. Поэтому нерегулярная сетка в пространстве любой размерности имеет только одномерную нумерацию узлов, что в свою очередь требует явного описания всех ее элементов (для тетраэдральной сетки — тетраэдров и треугольников, лежащих на границах расчетной области), которое не всегда нужно при работе со структурированными сетками (например, кубическими решетками).

Существенные трудности по применению многопроцессорных систем для решения задач математической физики связаны с обработкой нерегулярных сеток большого размера [9, 37, 78]. Увеличение числа узлов сетки влечет резкий рост затрат времени на балансировку загрузки процессоров, чтение и запись данных о сетке и значений сеточных функций, локализацию и вычисление необходимых для численного моделирования геометрических параметров сетки и определение информации для межпроцессорного обмена. Эти затраты становятся сопоставимыми со временем отдельного сеанса моделирования. Кроме того, возможна ситуация, когда информация о сетке, даже в сжатом виде, не сможет быть записана в один файл по причине превышения ограничений, накладываемых файловой системой. В результате моделирование с использованием достаточно крупных сеток «в традиционной постановке» становится невозможным или малоэффективным и требует разработки специальных алгоритмов распределенной обработки, хранения, чтения и записи данных, один из которых предложен в рамках данной диссертации.

Учитывая все выше сказанное, большое значение при разработке параллельных алгоритмов и программ моделирования физических процессов начинает играть снижение затрат времени на вспомогательные операции, не имеющие отношения непосредственно к процессу вычисления искомых параметров. Это чтение данных, балансировка загрузки процессоров, запись промежуточных и окончательных результатов расчетов (контрольных точек). Время выполнения этих действий должно быть по возможности минимизировано, и не должно сильно зависеть от числа используемых процессоров. В противном случае короткие вычислительные сеансы становятся неэффективными. Кроме того, из-за ограниченности дискового пространства, выделяемого пользователям, и сравнительно низкой производительности каналов связи между ними и МВС необходимо разумно минимизировать объемы данных, используемые для описания геометрии расчетной области (топологии расчетной сетки), и задания контрольных точек.

В данной работе, с учетом приведенных выше требований к параллельным алгоритмам и проблем, связанных с обработкой нерегулярных сеток большого размера, на основе выбранной дискретной модели разработаны параллельные алгоритмы моделирования газодинамических течений для многопроцессорных систем с общей и распределенной памятью.

Отдельно стоит упомянуть проблему непосредственно генерации нерегулярных сеток [1, 20, 29]. Генерация тетраэдральной сетки представляет собой достаточно нетривиальную задачу с множеством критериев особенно в случаях, когда речь идет о сетках с переменной плотностью узлов по пространству. Необходимо увязать воедино размеры элементов поверхностной сетки, желательное число ее узлов и тетраэдров и при этом добиться того, чтобы все ее элементы строго удовлетворяли критериям, накладываемым используемым математическим аппаратом. К сожалению, это удается далеко не всегда. Понятно, что при моделировании обтекания тел точность получаемых результатов напрямую зависит от качества аппроксимации обтекаемых поверхностей: чем детальнее будет задана поверхность летательного аппарата, тем точнее могут быть определены его аэродинамические характеристики. Теоретически после получения равномерной поверхностной триангуляции требуемого качества для границ расчетной области можно построить пространственную сетку, состоящую из приблизительно равных тетраэдров, размер которых будет обусловлен площадью поверхностных треугольников. Но в этом случае малый размер поверхностных элементов порождает сетки, содержащие большое число узлов, что повышает требования к производительности необходимых для расчетов вычислительных систем и увеличивает время проведения эксперимента. Но и при таком подходе возможности большинства свободно доступных генераторов тетраэдральных сеток ограничиваются вполне конкретным числом узлов (максимально это 1 ООО ООО узлов). Кроме того, нет никакого смысла сильно детализировать картину в тех подобластях, где заранее известно, что исследуемые параметры будут меняться в малых пределах. Поэтому чаще всего при решении задач газовой динамики целью ставится построить сетку, узлы которой сгущаются вблизи поверхностей обтекаемых тел и в подобластях, где требуется получить более детальную картину процесса (например, в зонах отрывов и ударных волн). Как правило, в этом случае плотность узлов задается некоторой пространственной функцией. Основная проблема при генерации сеток таким способом -избежать появления вырожденных элементов (например, тетраэдров с большим отношением длин максимальной и минимальной высот), так как это негативно сказывается на точности получаемых результатов. Второй способ получения сеток требуемой структуры - построение исходной равномерной сетки с достаточно крупными элементами и ее последующее измельчение или адаптация по ходу вычислительно эксперимента. В случае адаптации разностной сетки в процессе моделирования нестационарных процессов определенные трудности заключаются в выборе критерия адаптации и периодичности ее выполнения.

Для расчетов рассматриваемых в данной работе задач использовались тетраэдральные сетки с прямоугольными элементами, полученные путем разбиения на тетраэдры элементов пространственных прямоугольных решеток, а также квазиравномерные и сгущающиеся тетраэдральные сетки. Квазиравномерные и сгущающиеся сетки были взяты с сервера 1ЫЯ1А (задача моделирования невязкого обтекания летательного аппарата) и построены с помощью генератора [52, 54, 60, 66, 88, 89], предоставленного Ю. Василевским (Институт Вычислительной математики РАН).

В данной диссертационной работе ставятся следующие основные цели:

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

• Разработка параллельных алгоритмов моделирования обтекания тел сложной формы на тетраэдральных сетках для многопроцессорных систем с общей и распределенной памятью.

• Исследование особенностей обработки нерегулярных сеток при решении задач математической физики и разработать алгоритмы распределенного хранения и обработки нерегулярных сеток большого размера.

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

Научная новизна и практическая ценность работы. В диссертации предложены оригинальные параллельные алгоритмы моделирования задач газовой динамики для многопроцессорных систем с общей и распределенной памятью на основе методов конечных объемов и конечных элементов с использованием нерегулярных сеток. Разработаны алгоритмы двухуровневого распределенного хранения и обработки тетраэдральных сеток большого размера. С учетом особенностей расчетов на основе методов конечных объемов и конечных элементов сформулированы критерии оценки качества балансировки загрузки.

На основе разработанных алгоритмов создан комплекс параллельных программ по решению задач газовой динамики. Выполнено тестирование программ комплекса на различных многопроцессорных вычислительных системах для различного числа процессоров и объема исходных данных.

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

На примере задачи моделирования невязкого обтекания летательного аппарата показана возможность использования разработанного комплекса программ при выполнении научных исследований и производственных расчетов.

Достоверность результатов, полученных в работе, подтверждается тем, что для выполненных в работе численных расчетов наблюдается качественное совпадение полученных результатов с точным решением соответствующих задач, экспериментальными данными и результатами других авторов. Эффективность предложенных параллельных алгоритмов подтверждается результатами тестирования разработанных на их основе программ.

На защиту выносятся следующие результаты:

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

2. Разработаны алгоритмы распределенного двухуровневого хранения и эффективной параллельной обработки нерегулярных сеток, содержащих миллионы узлов.

3. Разработаны параллельные алгоритмы моделирования газодинамических течений для систем с общей и распределенной памятью. Разработан и успешно опробован на ряде расчетов вязкого и невязкого обтекания трехмерных тел комплекс последовательных и параллельных программ решения задач газовой динамики.

Апробация работы и публикации. Основные результаты диссертационной работы докладывались и обсуждались на многих научно-технических конференциях и семинарах, в частности: на IV-ой Научной конференции МГТУ «СТАНКИН» и «Учебно-научного центра математического моделирования МГТУ «СТАНКИН» и ИММ РАН», Москва, 2001 г. на 2-ой Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки", Самара, 2001 г. на V-ом Международном конгрессе по математическому моделированию, Дубна, 2003 г. на конференции Parallel Computational Fluid Dynamics (ParCFD), Москва, 2003. на VI-ом Международном конгрессе по математическому моделированию, Нижний Новгород, 2004. неоднократно на семинарах ИММ РАН. Основные материалы диссертационной работы опубликованы в следующих изданиях:

1. Болдырев С.Н., Леванов Е.И., Суков С.А., Якобовский М.В., Обработка и хранение нерегулярных сеток большого размера на многопроцессорных системах. Материалы 3 Всероссийского семинара. Казань. Изд-во Казанск. мат. об-ва, 2002, с. 33-39.

2. Chetverushkin B.N., Kornilina M.A., Sukov S.A., Iakobovski M.V., Methane combustion simulation on multiprocessor computer systems, Mathematical Modeling. Problems, methods, applications, Proc. of the Fourth International Mathematical Modeling Conference, June 27 - July 1 2000, Moscow, Russia (Ed. by L.A. Uvarova, A.V. Latyshev), Kluwer Academic, Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. ISBN 0-306-466643,2001, pp. 53-59.

3. Суков C.A., Якобовский M.B., Обработка трехмерных неструктурированных сеток на многопроцессорных системах с распределенной памятью. В сб. "Фундаментальные физико-математические проблемы и моделирование технико-технологических систем", вып. 6, под ред. Л.А. Уваровой. М., Изд-во "Janus-K", 2003, с. 233-239.

4. Mikhail V. Iakobovski, Sergey N. Boldyrev, and Sergey A. Sukov, Big Unstructured Mesh Processing on Multiprocessor Computer Systems, Parallel Computational Fluid Dynamics (Moscow, Russia, May 13-15, 2003), Edited by B. Chetverushkin, A. Ecer, J. Periaux and N. Satofuka - Assistant Editor: Pat Fox, Elsevier Science BV, Amsterdam, 2004, pp. 71-77.

5. Абалакин И.В., Суков C.A., Моделирование внешнего обтекания тел на многопроцессорных системах с использованием тетраэдрических сеток. В сб. "Фундаментальные физико-математические проблемы и моделирование технико-технологических систем", вып. 7, под ред. Л.А. Уваровой. М., Изд-во "Janus-K", 2004, с. 52-57.

Диссертация состоит из введения, четырех глав, заключения и списка используемой литературы.

Заключение.

Сформулируем основные результаты диссертационной работы:

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

2. Разработаны алгоритмы распределенного двухуровневого хранения и эффективной параллельной обработки нерегулярных сеток, содержащих миллионы узлов.

3. Разработаны параллельные алгоритмы моделирования газодинамических течений для систем с общей и распределенной памятью. Разработан и успешно опробован на ряде расчетов вязкого и невязкого обтекания трехмерных тел комплекс последовательных и параллельных программ решения задач газовой динамики.

1. A.B. Скворцов. Триангуляция Делоне и её применение. Изд-во Томского университета. 2002.

2. Абалакин И.В., Жохова A.B., Четверушкин Б.Н. Кинетически-согласованные разностные схемы на нерегулярных сетках. // Математическое моделирование, 1997. Т.9. №7. С.44-53.

3. Абалакин И.В., Жохова A.B., Четверушкин Б.Н. Разностные схемы на основе кинетического расщеплении вектора потока, Математическое моделирование, 2000, 13, № 4, с.73-82.

4. Абалакин И.В., Жохова A.B., Четверушкин Б.Н., 2001, Кинетически -согласованные схемы повышенного порядка точности, Математическое моделирование, 13, No. 5, 53.

5. Абалакин И.В., Четверушкин Б.Н. Кинетически-согласованные разностные схемы как модель для описания газодинамических течений. // Математическое моделирование, 1996. Т.8. №8. С.17-36.

6. Болдырев С.Н., Леванов Е.И., Суков С.А., Якобовский М.В., Обработка и хранение нерегулярных сеток большого размера на многопроцессорных системах. Материалы 3 Всероссийского семинара. Казань. Изд-во Казанск. мат. об-ва, 2002, с. 33-39.

7. Валях Е. Последовательно-параллельные вычисления. Пер. с англ. — М.: Мир, 1985. 456 е., ил.

8. Ван-Дайк М., 1986, Альбом течения жидкости и газа, М. «Мир», с.34.

9. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, Главная редакция физико-математической литературы, 1986.

10. Воеводин В.В. Математические основы параллельных вычислений. М.: Издательство МГУ, 1991.

11. Воеводин В.В. Параллелизм в алгоритмах и программах. // Вычислительные процессы и системы. Выпуск 10. / Под ред. Г.И. Марчука. М.: Физматлит., 1993.

12. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ - Петербург, 2002. - 608 е.: ил.

13. Вязников К.В., Тишкин В.Ф., Фаворский А.П. Квазимонотонные разностные схемы для уравнений газовой динамики, М., 1987, Препринт ИПМ им. М.В. Келдыша АН СССР, 175.

14. Вязников К.В., Тишкин В.Ф., Фаворский А.П. Построение монотонных разностных схем повышенного порядка точности аппроксимации для систем линейных дифференциальных уравнений с постоянными коэффициентами, Математическое моделирование, 1989,1, с.95-120.

15. Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео, Изд-во Диалог-МИФИ, 2002.

16. Дородницын JI.B., Четверушкин Б.Н., Чурбанова Н.Г. Кинетически согласованные разностные схемы и квазигазодинамическая система для моделирования течений плотных газов и жидкостей. Математическое моделирование, 2001, 13, № 4, с. 56-79.

17. Е.А. Никулин Компьютерная геометрия и алгоритмы машинной графики. Санк-Петербург. Изд-во «БХВ-Перербург». 2003.

18. Елизарова Т.Г., Четверушкин Б.Н. Кинетически-согласованные разностные схемы для моделирования течений вязкого теплопроводного газа. // ЖВМ и МФ, 1988. Т.28. №11. С.1695-1710.

19. Жмакин А.И., Фурсенко A.A., 1980, Об одной монотонной разностной схеме сквозного счета, Ж. вычисл. матем и матем. физ., 20, 1021.

20. К.Флетчер, Численные методы на основе метода Галеркина, Мир, 1988

21. Кнут, Дональд, Эрвин, Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ.: Уч. Пое. М.: Издательский дом «Вильяме», 2000. - 832 е.: ил. - Парал. тит. англ.

22. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999.

23. Лойцянский Л.Г. Механика жидкости и газа: Учеб. Для вузов 7-е изд., испр. - М.: Дрофа, 2003 - 840 с.

24. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989.

25. H.H. Голованов. Геометрическое моделирование. Москва, Изд-во «Физматлит», 2002.

26. Р. Хокни, К. Джессхоуп. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986.

27. Разностные схемы (введение в теорию). С.К. Годунов, B.C. Рябенький, учебное пособие, Главная редакция физико-математической литературы узд-ва «Наука», М., 1973.

28. A.A. Самарский, Ю.П. Попов Разностные схемы газовой динамики. Главная редакция физико-математической литературы изд-ва «Наука», М., 1975.

29. Рождественский Б.Л., Яненко H.H. Системы квазилинейных уравнений и их приложения к газовой динамике. М.: Наука, 1978.

30. Самарский A.A., Колдоба A.B., Повещенко Ю.А., Тишкин В.Ф., Фаворский А.П. Разностные схемы на нерегулярных сетках. Минск, 1996.

31. Самарский A.A., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. М.: Наука. Физматлит, 1997. - 320 с. - ISBN 5-02015186-6.

32. Стивене У. UNIX: взаимодействие процессов. СПб.: Питер, 2002. -576 е.: ил.

33. Т. Акселрод, М. Беккерман и др. Программирование на параллельных вычислительных системах: Пер. с англ. / Под ред. Р. Бэбба II. М.: Мир, 1991.

34. Фриш У. Турбулентность. Наследие А.Н. Колмогорова. М.: ФАЗИС, 1998.

35. Четверушкин Б.Н. Кинетически-согласованные схемы в газовой динамике. М.: Издательство МГУ, 1999.

36. Четверушкин Б.Н. Проблемы эффективного использования многопроцессорных вычислительных систем. // Информационные технологии и вычислительные системы, 2000. №2. С.22-34.

37. Шильников Е.В., Шумков М.А. Моделирование трехмерных нестационарных течений газа на МВС с распределенной памятью. // Математическое моделирование, 2001. Т. 13. №4. С.35-46.

38. Якобовский М.В. Распределенные системы и сети. Учебное пособие. -М.: МГТУ «Станкин», 2000. 118 е., ил.

39. A. George and J. W.-H. Liu. Computer Solution of Large Sparse Positive Define Systems. Prentice-Hall, Englewood Cliffs, NJ, 1981.

40. B. Hendrickson, R. Leland. A Multilevel Algorithm for Partitioning Graphs. // Supercomputing '95 Proceedings. San Diego, CA, 1995.

41. B. Hendrickson, R. Leland. An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations. // SIAM Journal on Scientific Computing, 1995. Vol.16. No.2. pp.452-469.

42. B. Hendrickson, R. Leland. An Improved Spectral Load Balancing Method. // Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics, 1993, pp.953-961.

43. B. Hendrickson, R. Leland. Multidimensional Spectral Load Balancing. Technical report SAND 93-0074, Sandia National Laboratories, Albuquerque, NM, 1993.

44. B.N. Chetverushkin, E.V. Shilnikov. Kinetic-consistent finite difference schemes and quasigasdynamic equations as the physical models for gasdynamic flow description. // Proceedings of the III Asian CFD Conference. Bangabore, India, 1998. pp.243-248.

45. B.N. Chetverushkin. On improvement of gas flow description via kinetically-consistent difference schemes. // Experimentation, Modelling and Computation in Flow, Turbulence and Combustion, Vol.2. John Wiley & Sons, Chichester, 1997. pp.27-38.

46. B.N. Chetverushkin. Solution of gasdynamic problems on massively parallel computer systems // Proceedings of the II European Computational Fluid Dynamic Conference. Stuttgart, Wiley-Addison, 1994. pp.397-401.

47. Buscaglia G.C., Dari E.A. Anisotropic mesh optimization and its application in adaptivity // Internat. J. Numer. Neth. Eng. 1998.

48. Castro Diaz M.J., Hecht F. Mohammadi B. New progress in anisotropic grid adaptation for inviscid and viscous flows simulations: Rapp. Rech. 2671, Inst. Nat. Rech. Informat. Automat. France, 1995. P. 1-22.

49. Dervieux A., 1985, Steady Euler simulation Using Unstructured Meshes, Von Karman Institute for Fluid Dynamics, Lecture Series 1985-94.

50. Dervieux A., Désedéri J.A. Compressible Flow Solvers using Unstructured Grid, Rapport INRIA, No. 1732, 1992

51. Deshpande S.M. Kinetic theory based new upwind methods for inviscid compressible flow. AIAA Paper 86-0275, 1986.

52. Donley H.E. The Drag Force on a Sphere, UMAP Journal, Spring 1991, 12, no. 1, pp. 47-80.

53. Fortin. M., Vallet M.-G., Dompierre G., Bourgault Y., Habashi W.G. Anisotropic mesh adaptation: theory, validation and application // Comput. Fluid. Dynamic. Chichester etc.: John Wiley and Sons Ltd. 1996 P. 174-180.

54. G. Karypis and V. Kumar. Multilevel algorithms for multi-containt graph partitioning. Technical Report TR 98-019, Department of Computer Science, University of Minnesota, 1998.

55. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998.

56. G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. Siam Review, 41(2):278-300, 1999.

57. G. Karypis, V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. Technical report CORR 95-035, University of Minnesota, Dept. Computer Science, Minneapolis, MN, 1995.

58. G. Karypis, V. Kumar. Analysis of Multilevel Graph Partitioning. Proceedings of the 7th Supercomputing Conference, 1995.

59. George P.L. Automatic mesh generation. Chichester: John Wiley & Sons Ltd., 1991.

60. Gushin V. A., Matyushin P. V. et al., 2003, Parallel Computing of 3D Separated Homogeneous and Stratified Fluid Flows around Bluff Bodies, Parallel Computational Fluid Dynamics, May 13-15, Abstracts, p.100.

61. H.D. Simon. Partitioning of Unstructured Problems for Parallel Processing. // Computing Systems in Engineering, 1991. Vol.2. No.2/3. pp.135-148.

62. Harten A. High Resolution Schemes for Hyperbolic Conservation Laws, J. Сотр. Phys.,1983, 49, p.357-393.

63. Harten A., Engquist В., Osher S., Chakravarthy S. R. Uniformly High Order Accurate Essentially Non-oscillatory Schemes, III, J. Сотр. Phys.,1987, 71, p.231-303.

64. I.V. Abalakin, S.N. Boldyrev, B.N. Chetverushkin, M.V. Iakobovski, A.V. Zhokhova. Parallel Algorithm for Solving Flow Problems on Unstructured Meshes. // 16th IMACS World Congress 2000 Proceedings. Lausanne, Switzerland, 2000.

65. Jameson A. Numerical Solution of the Euler Equations for Compressible inviscid Fluids, Numerical. Methods for the Euler Equations of Fluid Dynamics, 1985, SIAM,Philadelphia, p. 199.

66. Jeong J., Hussain F, 1995, On the identification of a vortex, J. Fluid Mech., 285, 69.

67. Lallemand M.-H., 1988, Schémas decentrés Multigrilles pour la Résolution des Equations D'Euler en Eléments Finis, Thesis, L'Universite de Provence Saint Charles.

68. Osher S., Solomon F. Upwind difference schemes for hyperbolic systems of conservation laws, Math. Comp., 1982, 38, p.339-374.

69. P. Colella and P.R. Woodward, 1984, The Piecewise Parabolic Method for Gasdynamical Simulation, J. Comp. Phys, 54, 174.

70. Roe L. Approximate Riemann Solvers, Parameter Vectors, and Difference Schemes, J. Comp. Phys., 1981, 43, p.357-372.

71. T. J. Barth and D. C.Jespersen , The Design and Application of Upwind Schemes on Unstructured Meshes, AIAA paper 89-0366, 1989.

72. Van Leer B., Towards the Ultimate Conservative Difference Scheme. V. A Second-Order Sequel to Godunov's Method, J. Comp. Phys.,1979, 32, p.101-136.

73. W. Donath, A. Hoffman. Algorithms for Partitioning of Graphs and Computer Logic Based on Eigenvectors of Connection Matrices. IBM Technical Disclosure Bulletin, 1972. Vol.15.

74. W. Gropp, E. Lusk, N. Doss, A. Skjellum. A High-performance, Portable Implementation of the MPI Message Passing Interface Standard. // Parallel Computing, 1996. No.22. pp.789-828.

75. Yu.Vassilevski and K. Lipnikov, An adaptive algorithm for quasioptimal mesh generation, Computational Mathematics and Mathematical Physics, 39, № 9, p.1468-1486.

76. Zavattieri P.D., Dari E.A., Buscaglia G.C. Optimization strategies in unstructured mesh generation // Internat. J. Numer. Meth. In Engng. 1996. V.39.P. 2055-2071.