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

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

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

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

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

Муравьев Сергей Владимирович

АВТОРЕФЕРАТ

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

Москва - 2006

Работа выполнена в Институте математического моделирования Российской Академии Наук.

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

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

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

доктор физико-математических наук Галкин В.А.

кандидат физико-математических наук Поляков С.В.

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

Научно-исследовательский вычислительный центр МГУ

Защита диссертации состоится «-/3» ОКТЯБРЯ 2006г. на заседании диссертационного совета К 002.058.01 при Институте математического моделирования РАН по адресу: 125047, Москва, Миусская пл. 4а.

С диссертацией можно ознакомиться в библиотеке Института математического моделирования РАН.

Автореферат разослан «•/■?» СЕНТЯБРЯ 2006 г.

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

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

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

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

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

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

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

• ' Рис. I. Структура системы распределенной визуализации.

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

/.Требуемые, параллельные методы сжатия должны не только обеспечивать необходимое уменьшение объема данных, но и делать это за приемлемое ■ ¡время,- с сохранением всех особенностей исходных данных, которые могут являться важными для исследователя.:

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

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

Для достижения указанных целей решаются следующие задачи:

• выбор способа визуализации трехмерных данных;

• обзор и анализ существующих подходов к сжатию сеточных данных и выбор наиболее приемлемого подхода для решения рассматриваемой проблемы;

• выбор метода для оценки ошибки аппроксимации и определение способа контроля требуемой точности при сжатии;

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

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

Основной из разработанных алгоритмов сжатия используется в пакете моделирования задач механики сплошной среды, разрабатываемом в ИММ РАН в рамках государственного контракта отделения математических наук РАИ. ;

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на ряде научно-технических семинаров, в том числе на V-ом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2005 г), на международной выставке CeBIT (Германия, Ганновер, 2003-2005 гг), на научных семинарах в МГУ и в ИММ РАН в 2006 г. Работа поддержана проектами программы президиума РАН, отделения математических наук РАН и грантами РФФИ 02-01-00589-а и 05-01-00750-а.

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

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

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

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

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

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

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

¿0 , 5ВД) | дУ2(д) [ 5Г3((3) _ 5^(0) | 5^(0) | 8( Зх ду дг Эх ду дг

где О = (р, ри, рк>, рхм, Е)Т — вектор консервативных газодинамических переменных; ^(0), Г2(0) и Г3(<3) - конвективные потоки; , ^ -

диффузионные потоки; и = (м,у,— декартовы компоненты скорости; р, р — плотность и давление; Е — р(м2 4- V2 + и,2)/2 + ре — полная энергия; е — удельная внутренняя энергия.

Система уравнений (1) замыкается уравнением состояния идеального газа: р = ре(у — 1), где у - показатель адиабаты.

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

прилипания и = 0 и условия адиабатической стенки [ = О

I дп

Здесь п -

внешний вектор нормали к границе. На входных и выходных границах расчетной области - граничные условия типа Стегера-Уорминга.

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

р = \, и = 1, у = и>=0, р = \/уМ2, у = 1,4, М = 0,8.

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

Расчет выполнялся с использованием программного комплекса С1ММ, разрабатываемого в ИММ РАН. При расчете члены конвективного переноса аппроксимировались с использованием метода конечных объемов (интегро-интерполяционный метод), а диффузионная часть — методом конечных элементов (с заданием базисной линейной функции на каждом тетраэдре).

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

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

Интегрирование по времени осуществлялось явным линейным методом типа Рунге-Кутты второго порядка.

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

Особенности входных данных. В работе рассматриваются методы сжатия поверхностей и трехмерных скалярных данных, заданных на тетраэдральных сетках1. Каждый из указанных типов данных можно разбить на отдельные подтипы, обладающие различными характерными свойствами. Так, например, входные данные, представляющие поверхности, могут характеризоваться следующими свойствами: 1) однозначная проектируемость на некоторую плоскость (например, когда поверхность задается однозначной сеточной функцией г(х,у) на прямоугольной области); 2) наличие или отсутствие граничных ребер, то есть ребер, на которые опирается по одному треугольнику; 3) наличие или отсутствие самопересечений2 поверхности; 4) связность (триангуляция может представлять собой единое целое лйбо состоять из изолированных частей). Кроме того, входные данные могут задаваться либо на регулярных, либо на нерегулярных сетках.

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

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

Обзор существующих методов. Преобразования, определяемые только геометрической формой. Например, можно выполнять слияние в единый многоугольник группы смежных треугольников, лежащих на параллельных (или близких к тому) плоскостях. Недостатком данного метода является то, что он подходит в основном для обработки поверхностей с относительно большой площадью плоских участков. Данный подход был рассмотрен, например, в работах Л. Кальвина и Р. Тейлора из IBM Research.

Детализирующие методы. В методах данной группы изначально строится триангуляция, грубо аппроксимирующая исходную поверхность, после чего каждый из треугольников мельчится до тех пор, пока не будет достигнута требуемая точность, или выполнены какие-то иные условия. Примеры исследований данного подхода можно найти, например, в работах Е. Пуппо и Л. Флориани (University of Genova, Генуя, Италия). Недостатком данного метода является то, что он ориентирован на поверхности, однозначно проектируемые на некоторую плоскость. Однако, например, М. Якобовский (ИММ РАН, Москва) продемонстрировал применение данного подхода для обработки поверхностей более общего типа.

Кластерный подход основан на объединении группы близких точек в одну точку. Данный метод довольно эффективен, но он не предусматривает сохранение таких особенностей поверхности, как связность участков, наличие или отсутствие отверстий и самопересечений. В статьях К. Лоу и Т. Тана (National University of Singapore, Сингапур) рассматривались способы улучшения качества поверхностей, получаемых с помощью данного метода.

Редукиионный подход подразумевает итерационное удаление структурных единиц поверхности (вершин, ребер или треугольников) в соответствии с определенными критериями оптимальности. Подобный метод сжатия может применяться для любых поверхностей без самопересечений, хотя может быть доработан и для сжатия триангуляций более широкого класса. Один из самых эффективных алгоритмов подобного рода был разработан М. Гарландом и П. Хекбертом в Carnegie Mellon University (Питтсбург, США).

Вейвлеты. В данном подходе используется аппроксимация сеточных данных с помощью набора базисных функций. Как правило, вейвлеты применяются для обработки регулярных данных, что является их недостатком. Использование данного подхода для аппроксимации триангулированных поверхностей исследовалось, например, М. Гроссом, О. Штадтом и др. (Swiss Federal Institute of Technology, Цюрих, Швейцария).

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

Ошибка может быть рассчитана в терминах различных норм. После замены одного вектора и (некоторой точки пространства) на вектор V возникшая ошибка равна расстоянию между данными векторами. Расстояние по евклидовой норме определяется следующим образом:

-,1/2

. (3)

Вместо евклидовой нормы может быть использована и следующая:

rfv(u) = rfu(v) = lu-vl =

||u - v|| = max Iut - |. (4)

i=i

В случае трехмерных поверхностей п—3.

Для определения ошибки аппроксимации для двух поверхностей 5, и S2 (далее для определенности Sl - это исходная поверхность, a S2 -результирующая) можно использовать формулу Хаусдорфа, выражающую расстояние между двумя поверхностями:

Z>(51>52) = max] max dy(S2), max ¿v(5,)|, (5)

V^WO ve/»(S2) J

где dv(S)= min dv(yv). (6)

weP(S)

Здесь P(S) - множество точек поверхности S, с помощью триангуляции которых она задана, dv(S) — расстояние между точкой v и поверхностью S, dv(w) — расстояние между точками v и w, которое можно вычислять с помощью формул (3) или (4).

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

dv(S) = rmndv(T), (7)

TcS

где Т— один из треугольников, которыми задана поверхность, a dv(T) -расстояние от точки v до треугольника Т.

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

Если максимально допустимая ошибка задана в виде числового порога Е (абсолютная ошибка аппроксимации), то для контроля выполнения этого требования должно выполняться следующее условие:

£>(ад)<£. (8)

При практическом применении требуемую точность удобнее задавать в процентах: p = (E/L(Sl))x 100%, (9)

где Z(Si) - характерный линейный размер исходной поверхности S^.

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

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

Можно выделить четыре основных этапа при сжатии рассматриваемых данных: 1) удаление количественной избыточности (сжатие данных с потерями); 2) числовое огрубление (уменьшение количества бит, отводимого для хранения чисел, округление вещественных чисел); 3) оптимизированное компактное представление структуры данных (сжатие без потерь специализированным методом, основанным на свойствах связей вершин обрабатываемых сеточных данных); 4) кодирование данных без потерь известными универсальными методами.

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

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

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

Помимо изоповерхностей предлагаемые алгоритмы могут быть использованы для отображения различных сечений трехмерных данных. В работе рассмотрен метод получения сечений произвольной плоскостью Ах + Ву + Сг+ 0 = 0. Правила нахождения треугольников сечения схожи с правилами для поиска треугольников изоповерхности.

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

В результате возникает необходимость создания алгоритма сжатия, удовлетворяющего следующим основным требованиям: 1) представление поверхности на входе и на выходе алгоритма триангуляцией точек в трехмерном пространстве; . 2) ориентация алгоритма на визуализацию получаемых результатов; 3) сжатие поверхности с требуемой точностью, определяемой расстоянием Хаусдорфа между двумя поверхностями; 4) возможность обработки любой исходной триангуляции (с учетом используемого способа генерации данных); 5) сохранение таких особенностей поверхности, как ■ несвязность отдельных фрагментов, форма границ поверхности3 и линий самопересечения; 6) выполнение сжатия за приемлемое время; 7) обеспечение достаточно высокой степени .сжатия (достижение требуемого объема V результирующих данных без учета возможного дополнительного сжатия без потерь); 8) возможность распараллеливания алгоритма на основе стандартных методов.

В работе подробно описываются три алгоритма сжатия.

Первый из них основан на кластерном подходе. Данный подход состоит в том, что каждая группа близких друг к другу точек (кластер точек) заменяется одной точкой.

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

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

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

И

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

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

Алгоритм сжатия состоит из нескольких этапов. Ниже приведено краткое описание основного этапа.

Выполняется циклический перебор всех точек поверхности с учетом всех их меток. Виды меток точек: «запрещенная к удалению» (задается в параметрах алгоритма), «запрещенная к удалению в данной итерации» (устанавливается для точек, добавленных в данной итерации), «запрещенная к удалению до момента удаления смежной точки» (устанавливается при невозможности ее удаления из-за нарушения каких-то ограничений, которые в последствии могут исчезнуть), «внутренняя», «граничная», «точка самопересечения». Часть меток являются постоянными, остальные - временные метки ~ могут изменяться в процессе сжатия. Перебор всех точек (итерация) по завершении может быть повторен необходимое число раз. На практике выполняется в среднем не более десяти итераций.

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

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

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

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

Помимо основного этапа сжатия в алгоритм добавлено предварительное ускоренное сжатие, существенно уменьшающее общее время обработки. Платой за скорость являются возможные превышения допустимой ошибки аппроксимации для отдельных участков поверхности. Однако на практике данные нарушения оказываются несущественными для визуализации. Ускоренное сжатие реализовано в два этапа: на первом этапе может быть выполнено слияние групп близких точек в одну точку (объединяются точки в радиусе £/10, где Е — параметр абсолютной ошибки аппроксимации); на втором этапе выполняется сжатие с упрощенным контролем аппроксимации, причем для удаления проверяются только ребра малой длины, не превосходящей Е.

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

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

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

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

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

Выполнение параллельного алгоритма сжатия состоит из следующих основных этапов: 1) распределение всех частей поверхности по процессорам; 2) сжатие каждой части с сохранением всех общих точек частей (для сжатия на каждом из процессоров используется рассмотренный выше последовательный алгоритм); 3) передача всех частей на один процессор и их объединение в единую поверхность («сшивка» по общим точкам); 4) повторное сжатие уже всей поверхности в целом (обрабатываются только «швы», состоящие из помеченных ранее точек).

Система распределенной визуализации. Разработанная в ИММ РАН интерактивная система распределенной визуализации основана на принципах технологии клиент-сервер. Основная цель данной системы — обеспечение возможности исследования трехмерных: скалярных полей большого объема с использованием многопроцессорной системы (сервера визуализации) и отображение результатов на компьютере рабочего места пользователя (клиентской части).

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

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

разработан алгоритм (последовательная и параллельная версии) для сжатия пространственных данных, заданных на тетраэдральных сетках.

Данный алгоритм в целом аналогичен предыдущему, разработанному для сжатия поверхностей. Основные изменения в нем следующие: 1) перед сжатием выполняется . нормализация значений сеточной функции (перемасштабирование) и выбор ее в качестве четвертой координаты точек; 2) используется представление точек данных одновременно в 3-мерном и в 4-мерном ■ евклидовых пространствах; 3) для контроля аппроксимации используется : более сильное . условие, чем проверка расстояния до гиперплоскостей получаемых тетраэдров.

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

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

есть: Е(д) = £>(д, Т) =

в „V2 ( 4

— 2

. где | + *о = 0

уравнение данной гиперплоскости.

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

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

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

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

И в следе за ее кормовой частью вдоль оси Ох. На рисунке 4 показало сечение расчетной сетки плоскостью у = сопз1. оказало сечение

Рис. 3. Обтекание усеченной сферы газовым потоком.

Рис. 4. Сечение расчетной сетки.

Моделирование обтекания производилось при Ке^Ю5 М = 08 В «Тсф^й. ПОЛУ,еЮ ^ вихр™

На рисунке 5 показаны результаты однопроцессорного сжатия

в^™1ТеСИТеЛЬНО Неб°ЛЬт0ГО ^^ ™ изволило выполни" визуализацию не только результирующих, но и исходных данных Визуализация выполнена в системе Теср1о1. исходных данных.

Р а) Ь)

Рис. 5. Сжатие изопоеерхности с точностью 0,5%.

■ На рисунке 5-а представлена исходная поверхность - изоповерхность давления,, извлеченная из результатов расчета и состоящая из 28 тысячек На рисунке 5-Ь показана полученная поверхность, которая состоит мен^ чемиз тысячи точек. Сжатие данной и схож!« по объему поветей "ГГл™ за несколько секунд даже на однопроцессорной системе с отнГ^ьно невысокой тактовой частотой процессора. относительно

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

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

Кол-во исходных, треуг-в Количество процессоров Кол-во точек Кол-во треуг-в Коэфф-т сжатия Время сжатия, с

20 ООО ООО 4 839 1 579 12 700 28

20 ООО ООО 9 1 013 1 915 10 500 14

20 000 000 16 1 173 2 227 9 000 9

20 000 000 36 1 793 3 434 5 830 6

200 000 000 36 4 589 8 656 23 100 58

Табл. 1. Результаты параллельного сжатия поверхностей.

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

Рис. 6. Результат параллельного сжатия тестовой поверхности.

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

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

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

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

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

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

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

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

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

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

1. Rrinov P.S., Iakobovski M.V., Muravyov S.V. Large Data Volume Visualization on Distributed Multiprocessor Systems. In: Parallel Computational Fluid Dynamics: Advanced numerical methods software and applications. Proc. of the Parallel CFD 2003 Conference. Moscow, Russia (May 13-15, 2003). (Ed. By B.Chetverushkin et al.), Elsevier, Amsterdam. - 2004. p.433-43 8.

2. Кринов П.С., Якобовский M.B., Муравьёв C.B. Визуализация данных большого объёма в распределённых многопроцессорных системах. В кн.: Высокопроизводительные параллельные вычисления на кластерных системах. Материалы 3-го Международного научно-практического семинара. 13-15 ноября 2003. Изд.-во Нижегородск. госуниверситета.. Нижний Новгород. - 2003, с.81-88.

3. Кринов П.С., Якобовский М.В., Муравьев С.В. Сжатие и визуализация триангулированных поверхностей // VI-я научная конференция МГТУ "Станкин" и "Учебно-научного центра математического моделирования МГТУ "Станкин" - ИММ РАН". 28-29 апреля, Москва. Программа, сборник докладов. - М.: Янус-К, ИЦ МГТУ "Станкин", 2003, с. 32-42.

4. Iakobovski M.V., Krinov P.S., Muravyov S.V. Large data volume visualization on distributed multiprocessor systems. // Book of Abstracts. Parallel Computational Fluid Dynamics. «Янус-К». 2003. p.301-304.

5. Marina A. Komilina, Mikhail V. Iakobovski, Peter S. Krinov, Sergey V. Muravyov, Ivan A. Nesterov, Sergey A. Sukov. Parallel visualization of CFD data on distributed systems. Int. Conf. on Parallel CFD'2005. (May 24-27, 2005), Univ. of Maryland, College Park, Maryland, USA. Book of abstracts. 2005, 5 pp.

6. Муравьев C.B. Сжатие научных данных большого объема для обеспечения возможности их визуализации. Материалы 5 международного научно-практического семинара Нижний Новгород, 2005. УДК 681.3.012:51 ББК 32.973.26-018.2:22 стр. 182.

Муравьев Сергей Владимирович

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

Подписано в печать 13.09.2006 г. Формат 60x90, 1/16'. Объем 1,25 п.л. Тираж 100 экз. Заказ № 750

Отпечатано в ООО "Фирма Блок" 107140, г. Москва, ул. Краснопрудная, вл. 13. т. 264-30-73 www.blokO 1 centre.narod.ru Изготовление брошюр, авторефератов, печать и переплет диссертаций.

Введение.

Глава 1. Обтекание усеченной сферы.

Постановка задачи и математическая модель.

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

Глава 2. Сжатие сеточных данных.

Особенности входных и выходных данных.

Обзор существующих методов сжатия.

Аппроксимация сеточных данных.

Общая схема многоэтапного сжатия.

Глава 3. Визуализация трехмерных скалярных данных.

Изоповерхности и сечения.

Сжатие триангулированных поверхностей.

Однопроцессорное сжатие.

Параллельное сжатие.

Интерактивная система распределенной визуализации.

Сжатие трехмерных скалярных данных.

Ресурсоемкость алгоритмов.

Глава 4. Результаты.

Моделирование обтекания усеченной сферы.

Сжатие поверхностей.

Однопроцессорное сжатие.

Параллельное сжатие.

Сжатие трехмерных скалярных данных.

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

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

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

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

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

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

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

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

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

Рис. 1. Обтекание усеченной сферы газовым потоком.

Пространственная дискретизация уравнений Навье-Стокса выполнялась на нерегулярных тетраэдральных сетках [6,7]. Заметим, что аппроксимация на нерегулярных сетках обычно уступает по точности аппроксимации с использованием регулярных сеток [8,9]. Кроме того, нерегулярная сетка требует явного описания всех ее элементов (например, тетраэдров или треугольников), чего можно избежать в случае со структурированными сетками (например, кубическими решетками). Однако подобные недостатки нерегулярных сеток компенсируются их полезными свойствами. Плотность узлов нерегулярной сетки может меняться по пространству в достаточно широких пределах. При этом при генерации сетки можно сосредоточить большинство узлов в подобластях, где необходимо исследовать более детальную картину процесса и получить решение с повышенной точностью. К указанным подобластям могут относиться участки с сильно меняющимся решением, а также любые другие области, • наиболее важные или интересные для исследователя. Кроме того, нерегулярные сетки дают возможность с высокой точностью аппроксимировать поверхности сложной формы, в результате чего можно более точно задать границы геометрической области, внутри которой исследуются физические процессы.

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

В настоящее время существует большое число программных средств визуализации данных на персональном компьютере (ПК). Это такие программные пакеты как Tecplot [10-13], Origin [14], EasyPlot [15], IRIS Explorer [16] и ряд других. Данные пакеты обладают широким набором функциональных возможностей по визуализации и исследованию различного рода научных данных.

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

В течение последних нескольких лет появился ряд профессиональных программных средств параллельной визуализации (например, Visapult [17,18], ParaView [19], OpenDX [20], EnSight [21] и др. [22]) Большинство из них ориентировано на такие условия функционирования, при которых компьютер пользователя находится в непосредственной близости от суперкомпьютера или соединен с ним высокоскоростной сетевой средой. Кроме того, имеющиеся разработки проблематично, а иногда просто невозможно доработать или переделать под конкретные желаемые условия, если это окажется необходимым. По этим причинам необходимо создание специализированного средства для визуализации научных данных большого объема.

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

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

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

Третья задача - реализация выбранного способа просмотра данных с использованием технических средств машинной графики [23-25]. Просмотр может осуществляться в различном виде, например, в форме изображений, цветовых распределений, поверхностей, линий уровня и т.д. Задача просмотра должна быть решена таким образом, чтобы исследователь мог рассмотреть данные, как в целом, так и подробно изучить их произвольный участок. Желательно, чтобы просмотр, будучи наглядным, являлся достаточно простым и быстрым. Корректность визуализации чрезвычайно важна, поскольку от нее зависит правильность интерпретации физических явлений, описываемых данными. Рассматриваемая задача включает в себя несколько подзадач, представленных ниже.

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

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

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

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

• тран сформация, позволяющая осуществлять сдвиг, поворот, перемасштабирование, отражение и т.д.;

• цветов ые преобразования, изменение освещенности и теней;

• до полнительное сжатие и фильтрация в зависимости от текущего положения точки наблюдения;

• ото бражение дополнительных объектов, например, координатной сетки;

• базов ые операции статистического анализа: вычисление среднего, дисперсии, построение аналитических графиков;

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

Обычно результаты трехмерного моделирования задач гидродинамики представляют собой трехмерные скалярные данные. Для визуализации подобных данных можно использовать различные методы [26-30]. Например, можно выделять плоскость (или срез) из исследуемого объема. Полученная таким образом информация является уже двумерной и может быть непосредственно выведена на экран, «отражая» значение исследуемой функции, например - цветом. Рассматривая набор срезов между границами области, можно получить представление о распределении значений исследуемой функции в трехмерном объеме. Недостатком подобного подхода является то, что пользователь одновременно видит лишь небольшую часть данных - их плоский срез.

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

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

Таким образом, в качестве основных типов обрабатываемых данных рассматриваются «поверхности» (изоповерхности некоторого скалярного физического параметра) и трехмерные скалярные данные (непосредственно само распределение исследуемого физического параметра).

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

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

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

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

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

Различают сжатие данных без потерь (lossless compression) и сжатие с потерями (lossy compression).

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

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

В некоторых случаях удается сразу получать данные приемлемого объема уже на этапе их создания (например, при сканировании можно уменьшить параметр разрешающей способности сканера). Однако данный способ огрубляет представление данных везде в одинаковой степени, независимо от того, насколько избыточен тот или иной участок данных. При этом возрастает риск пропуска важных особенностей поведения наблюдаемых параметров в отброшенных данных. Тем же недостатком обладает однородное прореживание данных, в рамках которого вдоль каждого направления выбирается, например, каждый п-ый элемент данных, а все остальные — удаляются. Целесообразно выполнять огрубление и удаление лишних элементов в большей степени в областях с большей избыточностью, то есть удалять данную избыточность в зависимости от участка данных, причем настолько сильно, насколько это возможно в рамках сохранения некоторой заданной точности.

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

К наиболее известным алгоритмам сжатия без потерь можно отнести алгоритм Хаффмана [34], алгоритм RLE (Run Length Encoding) [35], алгоритмы группы KWE (KeyWord Encoding) [36,37], арифметическое кодирование [38] и ряд других.

Примеры форматов сжатия без потери информации:

• GIF, TIFF - для графических данных;

• ZIP, ARJ, RAR, CAB, LH - для произвольного типа данных.

Среди широко используемых методов сжатия с потерями можно особо выделить алгоритм JPEG (Joint Photographie Expert Group) для сжатия растровых изображений [32], семейство алгоритмов MPEG (Moving Picture Experts Group) для сжатия видеоданных [39] и алгоритм МРЗ (MPEG Audio Layer-3) для сжатия аудиоданных [40]. Для сжатия данных иных типов обычно разрабатываются и применяются отдельные специальные методы.

Большинство методов сжатия с потерями включает в себя и сжатие без потерь для дополнительного увеличения степени компрессии.

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

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

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

Основной из разработанных алгоритмов сжатия используется в пакете моделирования задач механики сплошной среды [31], разрабатываемом в ИММ РАН в рамках государственного контракта отделения математических наук РАН.

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

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

Основные результаты работы

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

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

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

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

Заключение

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

2. Корнеев В.В. Параллельные вычислительные системы. М., Нолидж, 1999.-311 с.

3. Самарский А. А., Михайлов А. П. Математическое моделирование. Идеи. Методы. Примеры. 2-е изд., испр. - М.: Физматлит, 2001. - 316 с. -ISBN 5-9221-0120-Х.

4. Введение в математическое моделирование. Учебное пособие. Под ред. Трусова П. В. М.: Логос, 2005. - 439 с. - ISBN 5-98704-037-Х.

5. Самарский А.А. Математическое моделирование и вычислительный эксперимент // Вестник АН СССР. 1979. - №5. - с. 38-49.

6. Самарский А.А., Попов Ю.П. Разностные схемы газовой динамики. -М.: Наука, 1975.-350 с.

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

8. Tecplot ADK User's Manual, by Tecplot, Inc; co-published with On Demand Manuals a division of Trafford Holdings Ltd.

9. Tecplot CFD Analyzer Users Manual, by Tecplot; co-published with On Demand Manuals a division of Trafford Holdings Ltd.

10. Tecplot Reference Manual, by Tecplot , Inc; co-published with OnDemandManuals.com - a division of Trafford Holdings, Ltd.13. www.tecplot.com

11. Origin V75 User's Manual. OriginLab Corporation (www.originlab.corn). 2003.15. www.spiralsoftware.com/ep/eplot.html

12. IRIS Explorer™ Documentation (Windows NT®/2000) 2000 The Numerical Algorithms Group Ltd.17. www-vis.lbl.gov/Research/visapult2/

13. Д. Роджерс, Дж. Адаме. Математические основы машинной графики. М.: из-во "Мир", 2001. 603 с.

14. Блинова Т.А. Компьютерная графика: Учеб. пос./ Т.А. Блинова, В.Н. Порев; Под ред. В.Н. Порева. Киев: Изд-во "ЮНИОР", 2006. - 520с.: ил.+CD-ROM. - ISBN 966-7323-48-Х.

15. М. Ikits, J. Kniss, А. Е. Lefohn, С. Hansen. Volume Rendering Techniques. In GPU Gems: Programming Techniques, Tips and Tricks for RealTime Graphics, chapter 39. Edited by Randima Fernando, Addison Wesley, pp. 667-692, 2004.

16. David Kenwright. Visualization Algorithms for Gigabyte Datasets. Siggraph '97 course notes. ACM Siggraph, August, 1997.

17. T.T. Elvins. A survey of algorithms for volume visualization. Computer Graphics (ACM Siggraph Quarterly), 26(3): 194-201, Aug 1992.

18. W. Schroeder, K. Martin, B. Lorensen. The Visualization Toolkit: An Object Oriented Approach to 3D Graphics 3rd Edition. Kitware, Inc.; Feb, 2003, ISBN: 1 1-930934-07-6.

19. D. Bartz and M. Meiner. Voxels versus Polygons: A Comparative Approach for Volume Graphics. In Proc. of Volume Graphics, pages 33-48, 1999.

20. C.D. Hansen, C.R. Johnson. The Visualization Handbook. Edited by C.D. Hansen and C.R. Johnson, Elsevier, 2005. ISBN: 0-12-387582-X.

21. Четверушкин Б.Н., Гасилов В.А. и др. Пакет прикладных программ GIMM для решения задач гидродинамики на многопроцессорных вычислительных системах. Математическое моделирование, 2005, том 17, номер 6, стр. 58-74.

22. Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003. - 384 с. - ISBN: 5-86404-170-Х.33. www.compression.ru

23. Huffman, D. A., "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.

24. Golomb S.W. Run-length encoding. IEEE Tr. Inf. Theory IT-12, (1966), p. 399-401.

25. Ziv J., and Lempel, A. Compression of individual sequences via variablerate coding. // IEEE Trans. Inf. Theory IT-24, 5 (Sept. 1978), p. 530-536.

26. Welch Т.A. A technique for high-perfomance data compression. // IEEE Comput. 17, 6 (June 1984), p. 8-19.

27. Rubin F. 1976. Experiments in text file compression. Commun. ACM 19, 11,617-623.39. www.armosvstems.ru/system/compression mpeg.ahtm40. www.iis.fraunhofer.de/amrn/techinf/layer3/

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

29. Dervieux A., Desederi J.A. Compressible Flow Solvers using Unstructured Grid, Rapport INRIA, No. 1732, 1992.

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

31. Т. J. Barth and D. CJespersen , The Design and Application of Upwind Schemes on Unstructured Meshes, AIAA paper 89-0366, 1989.

32. Roe L. Approximate Riemann Solvers, Parameter Vectors, and Difference Schemes, J. Сотр. Phys.,1981,43, p.357-372.

33. Van Leer В., Towards the Ultimate Conservative Difference Scheme. V. A Second-Order Sequel to Godunov's Method, J. Сотр. Phys.,1979, 32, p.101-136.

34. 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.

35. Iakobovski M.V., Krinov P.S., Muravyov S.V. Large data volume visualization on distributed multiprocessor systems. // Book of Abstracts. Parallel Computational Fluid Dynamics. «Янус-К». 2003. p.301-304.

36. Муравьев C.B. Сжатие научных данных большого объема для обеспечения возможности их визуализации. Материалы 5 международного научно-практического семинара Нижний Новгород, 2005. УДК 681.3.012:51 ББК 32.973.26-018.2:22 стр. 182.

37. Hirsh С. Numerical computation of internal and external flows. Vol.2, Wiley Interscience, 1990.

38. Carl Erikson. Polygonal simplification: An overview. Technical Report TR96-016, Department of Computer Science, University of North Carolina -Chapel Hill, February 16, 1996.

39. J. Rossignac, editor. Geometric Simplification (ACM SIGGRAPH Course Notes No.35). ACM Press, 1996.

40. P. Heckbert and M. Garland. Survey of surface simplification algorithms. Technical report, Carnegie Mellon University Dept. of Computer Science, 1997.

41. P. Cignoni, C. Montani and R. Scopigno. "A comparison of mesh simplification algorithms". Computers and Graphics 22 (1998), pp.37-54.

42. E. Puppo and R. Scopigno. Simplification, LOD, and Multiresolution-Principles and Applications. Technical Report C97-12, CNUCE, C.N.R., Pisa (Italy), June 1997. (also in: EUROGRAPHICS'97 Tutorial Notes, Eurographics Association, Aire-la-Ville (CH)).

43. Josie Wernecke. The Inventor mentor: programming Object-oriented 3D graphics with Open Inventor. Addison Wesley, 1994.

44. The Virtual Reality Modeling Language Specification Version 2.0, August 1996.

45. Hoppe, H., DeRose, Т., Duchamp, Т., McDonald, J., Stuetzle, W. Surface Reconstruction from Unorganized Points. Proceedings of the 19th annual conference on Computer graphics, Pages 71-78, 1992.

46. Amenta, N., Bern, M., Kamvysselis, M. A new Voronoi-based surface reconstruction algorithm. Proceedings of the 25th annual conference on Computer graphics and interactive techniques. July 1998.

47. Bernardini, F.; Mittleman, J.; Rushmeier, H.; Silva, C.; Taubin, G. The ball-pivoting algorithm for surface reconstruction. Visualization and Computer Graphics, IEEE Transactions on, Volume: 5 Issue: 4, Oct.-Dec. 1999. Page(s): 349 -359.

48. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999.

49. Owen, Steven J. "A Survey of Unstructured Mesh Generation Technology", Proceedings, 7th International Meshing Roundtable, Sandia National Lab, pp.239-267, October 1998.

50. Borouchaki, H. and S.H. Lo. "Fast Delaunay triangulation in three dimensions", Computer methods in applied mechanics and engineering, Elsevier, Vol 128, pp.153-167, 1995.

51. Pav, Steven E. and Noel J. Walkington. "Robust Three Dimensional Delaunay Refinement", Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories, SAND #2004-3765C, pp.145156, September 19-22 2004.

52. M.J. De Haemer and M.J. Zyda. Simplification of objects rendered by polygonal approximations. Computers & Graphics, 15(2): 175-184,1991.

53. P. Hinker and C. Hansen. Geometric optimization. In IEEE Visualization '93 Proc., pages 189-195, October 1993.

54. A.D. Kalvin and R.H. Taylor. Superfaces: Poligonal mesh simplification with bounded error. IEEE C.G.&A., 16(3):64-77, 1996.

55. William J. Schroeder, Jonathan A. Zarge, and William E. Lorensen. Decimation of triangle meshes. In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 65-70, July 1992.

56. R. Ronfard and J. Rossignac. Full-range approximation of triangulated polyhedra. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):67-76, 1996.

57. M.E. Algorri and F. Schmitt. Mesh simplification. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):78-86,1996.

58. P. Lindstrom and G. Turk. Fast and memory efficient polygonal simplification. In IEEE Visualization, pages 279-286, 1998.

59. B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design, 11 (2): 197-214, 1994.

60. Garland, M. and Heckbert, P. S. Surface Simplification using Quadric Error Metrics. Proceedings of SIGGRAPH 97. In Computer Graphics Proceedings, Annual Conference Series, 1997, ACM SIGGRAPH, pp. 209-216.

61. J. Cohen, A. Varshney, D. Manocha, G. Turk, H.Weber, P. Agarwal, F. Brooks, andW. Wright. Simplification envelopes. In Computer Graphics Proc., Annual Conf. Series (Siggraph '96), ACM Press, pages 119-128, Aug. 6-8 1996.

62. Marc Soucy and Denis Laurendeau. Multiresolution surface modeling based on hierarchical triangulation. Computer Vision and Image Understanding, 63(1):1—14, 1996.

63. A. Ciampalini, P. Cignoni, C. Montani, and R. Scopigno. Multiresolution decimation based on global error. The Visual Computer, 13(5):228-246, June 1997.

64. C. L. Bajaj and D.R. Schikore. Error bounded reduction of triangle meshes with multivariate data. SPIE, 2656:34-45,1996.

65. R. Klein, G. Liebich, and W. Strafler. Mesh reduction with error control. In R. Yagel and G. Nielson, editors, Proceedings of Visualization '96, pages 311318, 1996.

66. Greg Turk. Re-tiling polygonal surfaces. In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 5564, July 1992.

67. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Mesh optimization. In ACM Computer Graphics Proc., Annual Conference Series, (Siggraph '93), pages 19-26, 1993.

68. H. Hoppe. Progressive meshes. In ACM Computer Graphics Proc., Annual Conference Series, (Siggraph '96), pages 99-108, 1996.

69. M. Reddy. Scrooge: Perceptually-driven polygon reduction. Computer Graphics Forum, 15(4): 191-203, 1996.

70. K.L. Low and T.S Tan. Model simplification using vertex clustering. In 1997 ACM Symposium on Interactive 3D Graphics, pages 75-82, 1997.

71. M. Garland, "Multiresolution Modeling: Survey & Future Opportunities", State of the Art, Eurographics, pp.111-131,1999.

72. Lori Scarlatos and Theo Pavlidis. Hierarchical triangulation using cartographic coherence. CVGIP: Graphical Models and Image Processing, 54(2):147-161, March 1992.

73. C. Andujar, D. Ayala, P. Brunet, R. Joan-Arinyo, and J. Sole'. Automatic generation of multiresolution boundary representations. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):87-96,1996.

74. David Luebke and Carl Erikson. View-dependent simplification of arbitrary polygonal environments. In SIGGRAPH 97 Proc., August 1997.

75. Enrico Puppo, Larry Davis, Daniel DeMenthon, and Y. Ansel Teng. Parallel terrain triangulation. Intl. J. of Geographical Information Systems, 8(2): 105-128,1994.

76. Michael Garland and Paul S. Heckbert. Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS-95-181, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, September 1995.

77. Delingette H. Simplex Meshes: a General Representation for 3D Shape Reconstruction. INRIA research report no. 2214. March 1994.

78. Якобовский M.B. Обработка сеточных данных на распределенных вычислительных системах. // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2004. Вып.2. с. 4053.

79. Добеши И. Десять лекций по вейвлетам. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004,464 стр.

80. М.Н. Gross, O.G. Staadt, and R. Gatti. Efficient triangular surface approximations using wavelets and quadtree data structures. IEEE Trans, on Visual, and Сотр. Graph., 2(2): 130-144, June 1996.

81. D.J. Hebert and H.-J. Kim. Image encoding with triangulation wavelets. Proceedings SPIE, (2569(l)):381-392,1995.

82. A. Certain, J. Popovic, Т. DeRose, Т. Duchamp, D. Salesin, and W. Stuetzle. Interactive multiresolution surface viewing. In Сотр. Graph. Proc., Annual Conf. Series (Siggraph '96), ACM Press, pages 91-98, Aug. 6-8 1996.

83. Lounsbery, M., DeRose, T.D., Warren, J. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics (TOG). January 1997. Volume 16, Issue 1.

84. Natarajan V., Edelsbrunner H.: Simplification of three-dimensional density maps. IEEE Transactions on Visualization and Computer Graphics 10, 5 (2004), 587-597.

85. Chiang, Y.-J., and Lu, X. Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Computer Graphics Forum (Special Issue for Eurographics *03) 22, 3 (2003), 493-504.

86. Келли Дж. JI. Общая топология. М.: Наука, 1968. - 384 с.

87. Francine Evans, Steven S. Skiena, and Amitabh Varshney. Optimizing triangle strips for fast rendering. In IEEE Visualization '96. IEEE, October 1996. ISBN 0-89791-864-9.

88. W.E. Lorensen and H.E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphics, 21(4):163-169, July 1987.

89. Han-Wei Shen and Christopher Johnson. Sweeping simplices: A fast iso-surface extraction algorithm for unstructured grids. In IEEE Visualization '95, pages 143-150. IEEE CS Press, 1995.

90. P. Cignoni, C. Montani, E. Puppo, and R. Scopigno. Optimal isosurface extraction from irregular volume data. In Proceedings of IEEE/ACM 1996 Symposium on Volume Visualization, pp.31-38. ACM Press, October 28-29 1996.

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

92. 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.

93. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998.112. http://glaros.dtc.umn.edu/gkhome/views/metis

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

95. 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.