Параллельные алгоритмы моделирования газодинамического обтекания тел на нерегулярных тетраэдральных сетках тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Суков, Сергей Александрович

• Суков, Сергей Александрович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Суков, Сергей Александрович

Содержание.

А Введение.

Глава 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. Разработаны параллельные алгоритмы моделирования газодинамических течений для систем с общей и распределенной памятью. Разработан и успешно опробован на ряде расчетов вязкого и невязкого обтекания трехмерных тел комплекс последовательных и параллельных программ решения задач газовой динамики.

Список литературы диссертационного исследования кандидат физико-математических наук Суков, Сергей Александрович, 2004 год

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.