Содержание к диссертации
Введение
Глава 1. Обтекание усеченной сферы 24
Постановка задачи и математическая модель 24
Численная реализация 27
Глава 2. Сжатие сеточных данных 31
Особенности входных и выходных данных 32
Обзор существующих методов сжатия 34
Аппроксимация сеточных данных 42
Общая схема многоэтапного сжатия 48
Глава 3. Визуализация трехмерных скалярных данных 52
Изоповерхности и сечения 52
Сжатие триангулированных поверхностей 56
Однопроцессорное сжатие 56
Параллельное сжатие 93
Интерактивная система распределенной визуализации 98
Сжатие трехмерных скалярных данных 100
Ресурсоемкость алгоритмов 105
Глава 4. Результаты 108
Моделирование обтекания усеченной сферы 108
Сжатие поверхностей 111
Однопроцессорное сжатие 111
Параллельное сжатие 118
Сжатие трехмерных скалярных данных 120
Заключение 123
Основные результаты работы 123
Литература
- Численная реализация
- Аппроксимация сеточных данных
- Сжатие триангулированных поверхностей
- Сжатие трехмерных скалярных данных
Введение к работе
Высокая производительность современных многопроцессорных систем позволяет обрабатывать большие объемы данных, используя для численного решения широкого круга задач механики сплошной среды подробные пространственные сетки. Большой объем описывающих такие сетки данных затрудняет их хранение, передачу по сети и обработку. Одним из наиболее информативных методов анализа результатов моделирования является их визуализация. Однако профессиональные пакеты визуализации ориентированы на последовательную обработку данных и не способны за приемлемое время отображать большие объемы результатов вычислительных экспериментов, проводимых на современных вычислительных системах. Под большим объемом данных здесь и далее понимается такой объем, единовременная обработка которого требует больше оперативной памяти, чем обычно доступно в современном персональном компьютере. В результате многие численные эксперименты сегодня не проводятся или проводятся с вынужденными ограничениями, так как отсутствуют или являются недоступными необходимые средства анализа результатов расчетов.
Визуализация большого объема данных на персональном компьютере невозможна без их предварительной обработки, а именно количественного сокращения элементов данных с сохранением тех свойств, которые нужно исследовать при визуализации. При этом для сжатия результатов современных широкомасштабных экспериментов наиболее эффективно использовать многопроцессорные вычислительные системы (МВС) [1,2].
В диссертации исследуются различные методы сжатия трехмерных сеточных скалярных данных. Основная цель рассматриваемых методов сжатия - обеспечить возможность визуализации научных данных большого объема. В качестве объектов для сжатия могут быть использованы наборы
4 скалярных данных, получаемых при моделировании различных задач гидродинамики.
Таким образом, актуальность темы диссертационной работы определяется необходимостью создания параллельных алгоритмов сжатия, способных выполнять эффективную многопроцессорную обработку больших объемов данных для обеспечения возможности визуального исследования результатов современных вычислительных экспериментов.
Моделирование трехмерных газодинамических течений. В
современной науке широко используется метод математического моделирования [3,4]. Его сущность состоит в замене исходного объекта его «образом» - математической моделью, отражающей его основные свойства, -и дальнейшем исследовании полученной модели. Работа с моделью объекта (явления, процесса) дает возможность относительно быстро и без существенных затрат исследовать его свойства и поведение в различных ситуациях. До появления ЭВМ изучение математических моделей выполнялось в основном аналитическими методами. С появлением компьютеров для исследования математических моделей большое распространение получил вычислительный эксперимент [5]. В современном математическом моделировании используются новейшие численные методы, реализуемые на быстродействующих вычислительных машинах. Вычислительные (компьютерные) эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных методов и технических инструментов, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам. В отличие от аналитических методов, где зачастую для каждой задачи разрабатываются свои самостоятельные приемы решения, численные методы отличаются большой универсальностью и применимы для исследования широкого класса явлений.
Одной из важных проблем, стоящей перед современной наукой и техникой, является исследование движения сплошной сжимаемой среды. В основе построения соответствующей математической модели лежат уравнения газовой динамики. Разработанные на сегодняшний день аналитические методы решения данных уравнений хотя и дают результаты высокой точности, но не охватывают всего спектра важных в инженерной практике задач.
При исследовании течений вязкого газа традиционно используется модель, представляющая собой уравнения Навье-Стокса - систему нелинейных дифференциальных уравнений. Фактически единственным эффективным способом решения подобных уравнений являются численные методы, реализуемые на быстродействующих вычислительных машинах. То есть на основе математической модели при помощи численного решения соответствующих уравнений количественно определяется поведение газодинамических течений в тех или иных условиях.
В работе рассматривается задача вязкого газодинамического обтекания (рисунок 1). Обтекаемая поверхность, выбранная для исследования, представляет собой усеченную сферу. Какое-либо вращение обтекаемого тела не рассматривается. В качестве математической модели для исследования газодинамических течений используется система уравнений Навье-Стокса.
На примере визуализации результатов моделирования данной задачи проводится подробное исследование разработанных методов сжатия.
Численная реализация
Расчет выполнялся с использованием программного комплекса GIMM [31], разрабатываемого в ИММ РАН.
Пространственная дискретизация уравнений Навье-Стокса проводилась на нерегулярной тетраэдральной сетке. Построение сетки N выполнялось разбиением расчетной области Q на тетраэдры Т}\ Q=\jTj. 7=1
При этом тетраэдры могут иметь общие вершины, ребра и грани, но не могут пересекаться по трехмерным областям.
При расчете использовался смешанный метод аппроксимации: члены конвективного переноса аппроксимировались с использованием метода конечных объемов (интегро-интерполяционный метод), а диффузионная часть - методом конечных элементов (с заданием базисной линейной функции на каждом тетраэдре) [42,43].
Для расчетов на основе интегро-интерполяционного метода вокруг каждого /-го узла сетки строится барицентрический контрольный объем (расчетная ячейка С,) [44]. При этом расчетная область Q разбивается на ячейки С,, обладающие теми же свойствами, что и тетраэдры Гу (см. выше). Построение контрольных объемов выполняется по следующему правилу: граница каждой ячейки С7 должна проходить через центры масс всех тетраэдров, содержащих вершину /, и центры масс всех их граней и ребер, содержащих данную вершину.
Численный поток через грани контрольного объема определялся с помощью схемы Роу [45]. Повышение порядка аппроксимации достигалось заменой кусочно-постоянного распределения газодинамических параметров в расчетной ячейке на кусочно-линейное (аппроксимация типа MUSCL) [46]. При определении кусочно-линейного распределения используются узловые градиенты, определенные по контрольному объему, окружающему узел.
Интегрирование по времени осуществлялось явным линейным методом типа Рунге-Кутты второго порядка [47].
Процедура моделирования организуется на основе явного численного интегрирования уравнений Навье-Стокса. На каждом шаге по времени вычисляются конвективные потоки (невязкие) на основе метода конечных объемов и вязкие потоки, рассчитанные по методу конечных элементов. При этом отдельные итерации делятся на следующие основные вычислительные блоки: Вычисление шага по времени. Вычисление узловых градиентов от газодинамических переменных (для расчета конвективного потока с повышенным порядком точности). Вычисление непосредственно конвективных потоков с использованием схемы Роу. Вычисление диссипативных потоков. Обработка граничных элементов. Определение значений газодинамических переменных на новом слое по времени.
Значения всех рассчитываемых газодинамических переменных определяются в вершинах тетраэдров сетки. Вокруг каждой вершины строится барицентрический контрольный объем (расчетная ячейка). При этом два соседних контрольных объема имеют несколько общих граней, число которых соответствует числу тетраэдров сетки, опирающихся на ребро, соединяющее центры соответствующих расчетных ячеек. В общем случае число общих граней может быть достаточно велико, что повышает вычислительную сложность алгоритма.
Для сокращения числа операций использован метод огрубления барицентрического контрольного объема. Посредством суммирования векторов площадей общих граней расчетные ячейки приводятся к такому виду, что между двумя соседними ячейками существует только одна общая грань. Данный подход позволяет существенно снизить затраты времени и ресурсов на вычисление конвективных потоков. Из-за сложности геометрии контрольных объемов нет возможности скорректировать объемы расчетных ячеек с учетом огрубления формы, что является недостатком описанного подхода.
Аппроксимация сеточных данных
Рассмотрим общий план многоэтапного сжатия сеточных данных, в котором используются как методы сжатия с потерями, так и без потерь. Многоэтапное сжатие с последовательным применением различных подходов позволяет добиться наиболее высокой степени сжатия и используется в основном для облегчения хранения и передачи данных.
Рассмотрим наиболее популярный способ хранения триангуляции и тетраэдральных сеток. Компьютерное представление указанных данных обычно разделяется на две основные части:
числовой набор, в котором определяются вещественные координаты точек в пространстве и значения сеточных функций в этих точках;
структурный набор, определяющий связи между точками и задающий треугольники (для поверхностей) или тетраэдры (для трехмерных полей), являющиеся основными структурными единицами обрабатываемых данных. Можно выделить четыре основных этапа при сжатии рассматриваемых данных: 1. удаление количественной избыточности; 2. числовое огрубление; 3. оптимизированное компактное представление структуры данных; 4. кодирование данных без потерь.
Первый этап позволяет уменьшить количество базовых элементов (точек, треугольников, тетраэдров), с помощью которых задаются обрабатываемые данные. Основные методы, относящиеся к данному этапу, описаны в предыдущем параграфе.
На втором этапе все числовые значения сеточных функций и пространственных координат могут быть огрублены путем представления каждого вещественного числа меньшим количеством битов. Например, если исходные числа занимали по 8 байтов (программный тип double), то на них можно выделить по 4 байта (программный ivm float). Таким образом, после огрубления весь набор вещественных чисел будет занимать места в 2 раза меньше, чем до этого. Данный способ огрубления данных вполне обоснован, поскольку четырехбайтовые вещественные числа могут хранить 6-7 значащих цифр мантиссы. Данная точность более чем достаточна, если учесть, что на предыдущем этапе при удалении количественной избыточности точность обычно теряется в гораздо большей степени. Так, например, при сжатии для целей визуализации точность чаще всего варьируется от 0,1 до 1 процента, то есть значимыми являются не более трех первых цифр мантиссы.
Помимо уменьшения количества битов для хранения чисел, можно произвести округление всех вещественных чисел до определенного знака после запятой. При этом нужно учитывать точность, с которой было выполнено сжатие данных на первом этапе. Смысл указанного округления в том, что округленные числа сожмутся в большей степени на последнем этапе кодирования без потерь.
Следует также иметь в виду случай, когда исходные числовые данные , заданы с добавкой некоторого шума постоянного уровня, существенно превышающего по порядку величины значения существенных битов данных. В этом случае целесообразно предварительно вычислить среднее значение f по всему множеству исходных чисел, а операции округления выполнять с числами -
На третьем этапе более компактно может быть представлена запись структуры данных, а именно выполнено сжатие без потерь специализированным методом, основанным на свойствах связей вершин обрабатываемых сеточных данных. Рассмотрим данный метод сжатия на примере триангулированных поверхностей. Подобные поверхности обычно задаются путем указания всех составляющих их треугольников; причем для каждого треугольника указываются три его вершины. Для краткости указываются только номера точек, заданных отдельно в виде списка координат. При этом если каждая вершина (ее номер) занимает S байтов, то для хранения N треугольников поверхности потребуется 3SN байтов.
Однако треугольники поверхности можно хранить еще более компактно. Для этого нужно разбить всю поверхность на как можно меньшее количество «триангулированных лент» [104].
Сжатие триангулированных поверхностей
Практика применения многопроцессорных вычислительных систем показывает их высокую эффективность при обработке больших объемов данных. По этой причине для более эффективного сжатия данных большого объема также целесообразно использовать МВС. Однако, прежде всего, будем рассматривать последовательные (однопроцессорные) алгоритмы сжатия, поскольку, как правило, именно они лежат в основе параллельных алгоритмов.
Рассмотренные до этого последовательные алгоритмы сжатия сеточных данных обладают определенными недостатками, создающими проблемы при их практическом применении. Во-первых, в большинстве случаев авторы разработанных алгоритмов публикуют только основные идеи, на которые опирается алгоритм. При этом полное описание алгоритмов с исходными кодами не доступно для общего доступа. Во-вторых, подобные алгоритмы сжатия, как правило, имеют ограниченную область применения (работают только с узким классом входных данных) или не обладают нужными свойствами, например, выполняют сжатие неэффективно, не гарантируют достижение требуемого объема или не удовлетворяют какому-то иному специальному критерию.
В результате возникает необходимость создания алгоритма сжатия, удовлетворяющего следующим основным требованиям11: 1. представление поверхности на входе и на выходе алгоритма триангуляцией точек в трехмерном пространстве; 2. ориентация алгоритма на визуализацию получаемых результатов; 3. сжатие поверхности с требуемой точностью, определяемой расстоянием Хаусдорфа между двумя поверхностями12; 4. возможность обработки любой триангуляции, которая может поступить на вход алгоритма (с учетом используемого способа генерации данных); 5. обеспечение достаточно высокой степени сжатия (достижение требуемого объема V результирующих данных13 без учета возможного дополнительного сжатия без потерь); 6. сохранение таких особенностей поверхности, как несвязность отдельных фрагментов, форма границ поверхности и линий самопересечения; 7. выполнение сжатия за приемлемое время; 8. возможность распараллеливания алгоритма на основе стандартных методов. Поясним некоторые из перечисленных требований.
Первое требование существует не столько из-за необходимости, сколько из-за удобства. Ранее уже говорилось о том, что представление поверхностей в виде триангуляции точек является наиболее популярным и удобным способом.
Под вторым требованием имеется в виду не достижение объема данных, необходимого для быстрой визуализации, а учет конкретного планируемого способа визуализации. Наиболее распространенным способом визуализации поверхности является классическое отображение ее треугольников в трехмерном пространстве с учетом различных положений камеры. При этом близость точек наблюдатель оценивает по классическому расстоянию между ними, а не вдоль какой-либо определенной оси. По этой причине для определения расстояния между двумя точками в реализации всех разработанных алгоритмов использовалась формула (2.1).
Выполнение четвертого требования обеспечивает робастность алгоритма при обработке всех возможных типов входных данных. Если исходная поверхность представляет собой изоповерхность некоторого трехмерного скалярного параметра, распределенного в трехмерной области, то она вполне может содержать отверстия и участки самопересечения, а также состоять из нескольких несвязных частей. Кроме того, если в некоторой области трехмерный параметр имеет константное значение, то изоповерхность, соответствующая данному значению, будет содержать в данной области множественные треугольники, не образующие «поверхность» в обычном смысле этого слова. Алгоритм сжатия должен быть предусмотрен для обработки даже подобного типа данных.
Тогда как четвертое требование необходимо для возможности обработки триангуляции с различными особенностями, то выполнение шестого требования обеспечивает сохранение всех данных особенностей.
Седьмое требование подразумевает, что в алгоритме сжатия отсутствуют множественные поиски и переборы по всем точкам поверхности, значительно увеличивающие время сжатия для средней вычислительной системы. Желательно, чтобы зависимость времени сжатия от объема исходных данных была линейной или почти линейной. Более того, важным желаемым свойством алгоритма является возможность его использования в системе интерактивной визуализации. При этом сжатие должно выполняться за несколько секунд, чтобы пользователь имел возможность получить результат почти сразу же после своего запроса.
Сжатие трехмерных скалярных данных
Рассмотрим результаты сжатия скалярного параметра, заданного на тетраэдральной сетке. В качестве исходных данных для тестирования однопроцессорного алгоритма брались результаты моделирования рассматриваемой задачи обтекания усеченной сферы.
О качестве сжатия трехмерных полей можно судить, сравнивая изоповерхности исходных и полученных данных, соответствующие одному и тому же значению скалярного параметра. Рассмотрим скалярные данные, исследуемая изоповерхность которых имеет сложную форму с множеством пространственных особенностей.
На рисунке 34 показаны нулевые изоповерхности первого собственного значения тензора S2+fl2. Слева - изоповерхность исходных данных, справа - изоповерхность данных, сжатых с точностью 1%. В таблице 7 приведены численные результаты сжатия с разной степенью точности. Время сжатия сравнивалось на системе с частотой процессора 2,6 ГГц.
По сравнению со сжатием поверхностей алгоритм сжатия трехмерных скалярных данных имеет невысокие коэффициенты сжатия и выполняется за значительно большее время. Относительно низкие коэффициенты сжатия объясняются тем, что преобразование фрагмента тетраэдральной сетки сопровождается большим числом проверок на допустимость, а значит обладает меньшей «свободой», чем преобразование фрагмента триангуляции. Относительно большое количество проверок обусловлено, в первую очередь, значительным числом тетраэдров, затрагиваемых каждым локальным преобразованием. Каждое преобразование участка триангуляции затрагивает в среднем 10 треугольников, тогда как преобразование фрагмента тетраэдральной сетки требует проверить и изменить около 30-50 тетраэдров. Этим же объясняется и более медленное сжатие тетраэдральных сеток. Кроме того, сами по себе операции в четырехмерном пространстве более сложны, а значит требуют большего времени на выполнение.
Другой недостаток данного алгоритма состоит в том, что при сжатии не контролируется пространственное расположение границ изоповерхностей, которые можно бы было извлечь из обрабатываемых данных (в частности сохранение отверстий), а также связность/несвязность их участков. Единственное ограничение, в той или иной степени препятствующее нарушению данных особенностей, - это контроль сохранения требуемой точности.
Наконец, приведем результаты параллельного сжатия трехмерных данных. Для тестирования алгоритма представленные выше данные были проинтерполированы на тетраэдральную сетку, содержащую более 7 миллионов узлов и состоящую из 40 отдельных частей. На рисунке 35 представлены результаты сжатия полученных данных с точностью 1%.
В таблице 8 приведены численные результаты данного сжатия с разной степенью точности. Указано только время общего процесса сжатия в целом, без учета процессов чтения исходных данных и записи результатов в файл. Сжатие выполнялось на МВС с частотой каждого процессора 3 ГГц.
В случаях, когда все описанные недостатки не являются существенными, разработанные алгоритмы сжатия скалярных полей могут успешно применяться. С их помощью можно сжимать тетраэдральные сетки высокой плотности в десятки раз, сохраняя при этом общую картину распределения скалярных полей, определенных на данных сетках.
Очевидно, что сжатия данным алгоритмом может оказаться недостаточным для возможности визуализации полученных результатов. В этих случаях необходимо будет извлекать из полученных или исходных данных нужные изоповерхности или сечения и применять рассмотренный ранее алгоритм для сжатия триангуляции.
Заключение
Основные результаты работы
1. Разработаны алгоритмы сжатия данных, описываемых произвольной триангуляцией точек в трехмерном пространстве, получаемых при моделировании задач трехмерной гидродинамики. Алгоритмы позволяют сжимать данные до заданного объема и обеспечивают возможность визуализации данных большого объема.
2. Разработан алгоритм сжатия с требуемой точностью трехмерных скалярных данных, заданных на тетраэдральных сетках, используемых для описания трехмерных течений. Алгоритм обеспечивает компактное хранение результатов вычислительных экспериментов.
3. Разработаны параллельные версии алгоритмов сжатия триангулированных поверхностей и скалярных функций, определенных на тетраэдральных сетках. Параллельный алгоритм сжатия триангулированных поверхностей интегрирован в состав интерактивной системы распределенной визуализации.
4. На примере обработки результатов моделирования газодинамического обтекания трехмерных тел показана эффективность предложенных алгоритмов сжатия.
