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

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

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

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

Значительный качественный разрыв между производительностью компьютеров рабочего места пользователя и распределенного вычислительного пространства, обуславливающий возникновение многих проблем практического использования многопроцессорных систем, будет продолжать возрастать. Подтверждением тому служит активное развитие GRID технологий и возможностей метакомпьютинга, приводящее к интенсивному росту объединенных вычислительных мощностей при относительно низкой стоимости их объединения. В настоящее время нет доступных пакетов, обеспечивающих использование терафлопных вычислительных систем для решения задач механики сплошной среды. Существующие пакеты ориентированы на использование последовательных систем, например FlowVi-sion [1,2,3], либо кластерных систем с ограниченным числом процессоров, например пакет GDT [4,5], или один из ведущих пакетов численного моделирования двух и трехмерных задач газовой динамики, Fluent [6]. Подобная ситуация складывается и в ряде других областях знаний. Создание пакетов, снимающих с прикладного программиста вопросы, не относящиеся непосредственно к предметной области, является приоритетной задачей, поскольку целесообразность дальнейшего развития самих вычислительных систем непосредственно зависит от наличия инструментария, обеспечивающего возможность их эффективного применения.

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

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

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

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

Эффективным методом построения параллельных вычислительных алгоритмов моделирования задач механики сплошной среды является метод геометрического параллелизма. Основная проблема при его использовании связана с необходимостью решения задачи статической балансировки загрузки — выбора такой декомпозиции расчетной сетки, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные возможным дублированием вычислений и необходимостью передачи данных между процессорами малы. Задача сводится к разбиению вершин некоторого графа на заданное число классов эквивалентности — доменов. Задача рационального разбиения графов, наиболее близкой к которой можно считать задачу о разрезании графов [7], принадлежит классу yVP-полных [8], что обуславливает необходимость использования для ее решения эвристических алгоритмов.

К простым, но малоэффективным алгоритмам относятся методы рекурсивного координатного [10,11] и инерциального [9] разбиения. Заслуживают упоминания алгоритмы рациональной декомпозиции сеток, основанные на методах спектрального разбиения, алгоритмах Kernighan-Lin (KL) и Fiduccia-Mattheyses (FM) [62, 67]. Наиболее эффективны иерархические методы рационального разбиения графов [61,78,79]. Доступен ряд пакетов декомпозиции графов, среди которых выделяются последовательные и параллельные версии пакетов СНАСО [12,17] и PARMETIS [13], пакеты PARTY [14], JOSTLE [15], SCOTCH [16], Zolman [189].

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

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

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

Вторая глава посвящена вопросам динамической балансировки загрузки при моделировании на МВС химически реагирующих многокомпонентных течений. Рассматривается разработанный в соавторстве с М. А. Корнилиной алгоритм серверного параллелизма, обеспечивающий децентрализованное перераспределение элементарных заданий, размещенных на множестве процессорных узлов.

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

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

Согласно методу суммарной аппроксимации [138] поочередно рассматриваются газодинамические процессы, и процессы, описывающие химическую кинетику горения. Газодинамические течения описываются кинетически согласованными разностными схемами, уравнения химической кинетики интегрируются при помощи L-устойчивых методов решения жестких систем обыкновенных дифференциальных уравнений.

Общее время расчета уравнений блока кинетики горения многократно превышает время расчета уравнений блока газовой динамики, причем распределение вычислительной загрузки процессоров на этапе расчета кинетики горения отличается сильной неоднородностью из-за большой разницы времён необходимых для расчета областей интенсивного протекания химические реакции и областей, расположенных на удалении от зоны горения. В связи с этим известных алгоритмов статической (геометрический параллелизм, он же «domain decomposition») и динамической (коллективное решение, он же «processor farm» [143,111], диффузная балансировка.

19]) балансировки загрузки не достаточно для организации эффективного вычислительного процесса. Так же неэффективен для задач с высокой динамикой миграции по сетке вычислительной нагрузки блочный алгоритм.

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

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

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

• сервер визуализации, как правило, выполняемый на многопроцессорной системе, обеспечивает обработку большого объема данных;

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

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

Созданная система визуализации RemoteView обеспечивает изучение трехмерных скалярных данных. Одним из наиболее мощных и наглядных методов представления трехмерных скалярных данных является визуализация изоповерхностей, в связи с чем поддерживается именно этот метод. Среди подходов к визуализации поверхностей, выделяется метод, основанный на использовании мультитриангуляций [173,172,72,169]. Использование относительно простых структур данных — линейных массивов треугольников, позволяет опираться на известные алгоритмы огрубления триангуляций. Кроме того, современные видеоускорители аппаратно поддерживают отображение массивов треугольников, что значительно повышает наглядность визуализации, как за счет высокой скорости вывода данных на экран, так и за счет возможности автоматического формирования стереоизображений.

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

Простейшие алгоритмы сжатия, основанные на уменьшении точности представления вещественных чисел, описывающих сетку и последующей компрессии с помощью стандартных алгоритмов группового кодирования (RLE), кодирования строк [99, 98] и им подобных значительного выигрыша не дают. Информация о связях между узлами сетки практически не сжимается стандартными методами. Существующие специальные методы, среди которых наиболее эффективен метод шелушения [140], существенно ориентированы на планарность графов и не обобщаются непосредственно на случай триангуляций, расположенных в трехмерном пространстве.

В связи с этим основной интерес представляют алгоритмы, формирующие некоторую новую триангулированную поверхность, аппроксимирующую исходную изоповерхность, но содержащую значительно меньшее количество узлов. В этой связи полезен ряд базовых алгоритмов огрубления триангуляций и многоуровневого описания трехмерных объектов поверхностными сетками [168, 169, 170, 171].

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

Разработанная в соавторстве с П. С. Криновым и С. В. Муравьевым система визуализации успешно функционирует не только на кластерах и суперкомпьютерах, но и на метакомпьютерах, поскольку объемы передаваемых в ходе ее работы данных относительно невелики.

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

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

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

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

Моделирование обтекания трехмерных тел сложной формы.

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

Моделирование задач горения. Моделирование процессов горения является одной из наиболее сложных с вычислительной точки зрения проблем и требует больших вычислительных ресурсов. Результаты моделирования горения струи метана на многопроцессорной системе МВС-1000М показывают, что применение алгоритма серверного параллелизма обеспечивает эффективность на уровне 60% при расчете сетки, содержащей 1000×1000 узлов, на 600 процессорах, что подтверждает хорошую масштабируемость метода. Так же высокую эффективность подтвердили расчеты горения метановой струи на объединении двух кластеров. Несмотря на медленный канал связи между системами (30 и 12-процессорной) была получена более, чем 90% эффективность.

Моделирование добычи углеводородов с помощью методов пер-коляции. Актуальность проблемы интенсификации добычи нефти обусловлена истощением месторождений и необходимостью снижения остаточной нефтенасыщенности и обводнённости продукции. Перспективным выглядит использование для этих целей подхода, основанного на методах теории перколяции. Для достоверного описания трехмерного пористого коллектора месторождения с помощью перколяционной модели необходимо использовать решетки содержащие более 107 узлов [174], что стало возможным в последнее время благодаря развитию высокопроизводительных многопроцессорных систем. Изучению методов теории перколяции и свойств, описываемых ими многомерных геометрических структур, посвящены монографии [175, 176]. Перколяционный подход для описания фильтрации флюидов и активного нефтевытеснения рассматривается в работах [103,104,105,106].

Трёхфазная динамическая перколяционная модель (ДПМ) [105] хорошо описывает такие эффекты, как наличие порога протекания, кластеров запертой нефти и рукавов прорыва вытесняющего агента, конечное время распространения волн давления. Использование больших вычислительных мощностей позволило обнаружить важное для практических приложений свойство ДПМ: увеличение фильтрационного потока при использовании импульсного режима внешней накачки.

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

При построении генератора использован подход, основанный на рекуррентных соотношениях [119] и аналогичных им генераторах Фибоначчи [177,179]. Разработаны алгоритмы формирования ПСЧ длины 2″ 5−1, 2ЗП -1, 21 023 — 1 бит, что соответствует 1076, 10ш, Ю307 вещественных чисел.

По теме диссертации опубликовано более 40 работ [21−60], из них 9 статей — в ведущих рецензируемых научных журналах и изданиях, перечень которых определен Высшей аттестационной комиссией [21−29].

Автор глубоко благодарен Б. Н. Четверушкину, оказавшему большое влияние на все этапы выполнения исследований, за неослабевающее внимание к работе и постоянную поддержку. Автор выражает искреннюю благодарность своему учителю Е. И. Леванову за постоянное внимание и поддержку. Автор глубоко благодарен А. Р. Кесселю и С. С. Лапушкину за постановку задачи моделирования динамики заводнения месторождений нефти и газа с помощью перколяционных методов, предложенную математическую модель и плодотворные обсуждения. Автор выражает глубокую благодарность С. В. Полякову, за многочисленные дискуссии по широкому кругу затрагиваемых в диссертации вопросов. Автор благодарен П. С. Кринову, С. А. Сукову, С. В. Муравьёву, М. А. Корнилиной,.

С.В.Болдареву, И. И. Антоновой и Д. В. Петрову за совместную работу над созданием и реализацией ряда рассматриваемых в диссертации алгоритмов, библиотек и программ. Автор благодарен Б. М. Шабанову, О. С. Аладышеву, П. Н. Телегину и другим сотрудникам МСЦ РАН за внимательное отношение и всестороннюю поддержку, позволившую успешно выполнить значительную часть вычислительных экспериментов. Автор выражает свою особую благодарность И. И. Галигузовой за доброжелательную поддержку на протяжении многих лет.

Заключение

.

В заключении сформулируем основные результаты диссертации:

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

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

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

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