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

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

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

V

I Кринов Пётр Сергеевич

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

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

АВТОРЕФЕРАТ

' диссертации на соискание ученой степени

4 кандидата физико-математических наук

Москва - 2005

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

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

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

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

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

кандидат физико-математических наук Карташова Е.Л.

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

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

Защита диссертации состоится «_» марта 2005г.

на заседании диссертационного совета К 002.058.01 при Институте математического моделирования РАН по адресу: 125047, Москва, Миусская пл. 4.

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

Автореферат разослан «_»_февраля_2005 г.

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

Похилко В.И.

¿<00оЬ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РОС. НМ ¡"Oil ■ ПЫ!АЯ

'и,-Г 'i--.it:'- V

"••-St vpi

290 РК

щихся на множестве файловых серверов или вычислительных модулей вычислительной системы.

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

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

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

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

- на IV-ой Международной конференции по математическому моделированию. Москва. 2001;

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

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

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

- на международной выставке CeBIT Германия, Ганновер в 2001, 2002 и 2003 годах;

- неоднократно на научных семинарах ИММ РАН;

- на третьей Всероссийской молодёжной школе «Суперкомпьютерные вычислительно-информационные технологии в физических и химических исследованиях». Черноголовка. 2001.

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

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

Реализация результатов. Результаты диссертации получены в ходе выполнения ряда работ, поддерживаемых РФФИ, в которых автор принимал участие в качестве основного исполнителя (гранты 99-01-01036-а, 99-07-90388-ск, 02-01-00589-а, 02-01-00700-а, 02-07-90168-в, 04-01-03011-6, 04-01-08034-офи а) и руководителя (грант 02-01-06250-мас). Разработанный комплекс параллельных программ является составной частью пакета моделирования задач механики сплошной среды, разрабатываемого в ИММ РАН в рамках го-

сударственного контракта № 10002-251ЮМН-03/026-023/240603-806 от 30 апреля 2003 г.

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

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

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

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

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

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

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

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

Для численного моделирования изучаемой задачи используются кинетически-согласованные разностные схемы. Одна из конкретных реализаций разностных схем этого семейства, обладающая первым порядком аппроксимации по времени и пространству, в трёхмерной декартовой системе координат выглядит следующим образом: р,+(ри) +(ру) +(р\м).=

х у г

= (т'(ри- + р\ \ + (ту(ру2 + р)у)г + + р)7):,

(ри)( + (ри2 +/?)>+ (риу), + (рим). =

X у г

= (т'(риг +3ри)х)х +(т>(риу-)у)у+(г'{риу<%)1 +

1 4

+ — (- (МЩ), + {циу )у + (рщ),), К.С 3

(ру), + (руи) + {р\г + р), + (рууу). =

X У 2

(1)

(2)

(3)

(рм>), +(р\т) +(р\т), + (ру^+р). + /,,/> =

л у г

Е,+(и(Е + р)),+(и(Е + р)) +(и(Е + р)) =

+(-

г' Г 5 ч! + ту + т' и'-(Е + ^-р)

- 2 з. 2 У _ У - 2 г .

р(р~ 1)

р{р- О

СР2)у)у+(

ПР-ТУ ^

Ф

+—+

Яе ЯеРг(/-]) р Р Р

(4)

Ф = 0.5[(| М(и\ +

Нм(и-)-у +мЫ),), +(А»2% +

Здесь р - плотность, «,у,и>- компоненты скорости вдоль продольной, поперечной и вертикальной координатных осей соответственно, р - давление, Т- температура, е- внутренняя энергия, Е = р(и2 + н^)/2 + ре - полная энергия, Ие- число Рейнольдса, ¡л- коэффициент динамической вязкости, Г = ср1с„- показатель адиабаты, с = ^у(у-\)£ - скорость звука, А',Л',/!1 - шаги

сетки, т, = й*/2с,г, =А'/2с,гг=й!/2с., /г, = ^ф-.

Рис 1 Геометрия расчетной области

На нижней границе расчётной области (кроме самого сопла) использованы граничные условия прилипания для скоростей и условие др/дп = 0 для давления. На свободных границах использовано «мягкое» условие сноса #7Эл = 0. На входной границе (срезе сопла) задан профиль струи.

Схема обладает устойчивостью курантовского вида: Д/ = аЛПШ1/шах(|Г/| + с)

Здесь Л/ - шаг по времени, /¡тп- минимальный шаг пространственной сетки, и = + у2 + нг), а - параметр, выбираемый экспериментально.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый класс алгоритмов обеспечивает сохранение симметрии и разбивает исходную ячейку на 24 тетраэдра (рис. 2). Отрицательной стороной этого подхода является необходимость построения дополнительных опорных точек и значительное увеличение объема информации, описывающей используемой при построении изоповерхности сетку. Одна кубическая ячейка, состоявшая из 6-ти четырёхугольников и 12-ти рёбер, заменяется 24-мя пирамидами, содержащими 32 треугольника и 50 рёбер.

Рис. 2. Симметричное разбиение ячейки на пирамиды

Рис. 3. Опорные точки (не отмеченные) симметричного разбиения группы из 8-ми ячеек

Симметрия и относительная свобода в выборе 7-ми опорных точек, позволяет применить данный алгоритм для 8-ми кубических ячеек одновременно, что позволяет уменьшить объём построенной тетраэдрической сетки в 8 раз (рис. 3). При таком подходе происходит заметная потеря данных, поскольку игнорируются значения поля в узлах, отмеченных на рис. 3 квадратами - из 27-ми узлов не учитываются 12.

Второй класс алгоритмов не обеспечивает сохранение симметрии, но и не требует построения дополнительных опорных точек. В соответствии с ним, на каждой грани исходной ячейки проводится одно дополнительное диагональное ребро (рис. 4). Полученная декомпозиция «куба» содержит 5 пирамид и 18 рёбер, что даёт почти трехкратный выигрыш в объёме данных, описывающих сетку, исходя из которой, строится изоповерхность, причем без игнорирования значений исследуемой функции в каких бы то ни было точках.

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

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

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

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

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

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

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

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

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

• объём передаваемых по сети данных не должен превышать заданного значения.

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

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

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

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

Система визуализации (рис. 5) разработана на основе модели клиент/сервер. Разработан алгоритм и сценарий взаимодействия компонент системы, что, в совокупности с описанными в главе 2 методами, обеспечивает решение поставленной задачи визуализации:

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

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

СуперЭВМ

Удаленное рабочее место

Локальная или глобальная сеть

Рис. 5. Структура системы визуализации

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

1. клиентская часть системы визуализации выполняется на персональном компьютере;

2. коммуникационная часть сервера визуализации выполняется на управляющем узле многопроцессорной системы;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Трехмерная визуализация предполагает отображение сложных пространственных структур, что требует обеспечения возможности хорошей ориентация в трех измерениях. Человеку легко извлечь пространственную информацию из двухмерного изображения при условии, что на нем присутствуют вспомогательные «уровни глубины». Многие уровни глубины связаны с объектами и поверхностями, однако данные скалярного поля по своей природе не содержат объектов или поверхностей, и соответственно уровней глубины. Чтобы передать положение в пространстве, приходиться вводить специальные трёхмерные объекты и поверхности, связанные с изображаемым полем, или использовать геометрию окружения. В диссертационной работе рассмотрены различные уровни, передающие форму, глубину и движение. Предоставленная в рамках системы визуализации возможность интерактивного вращения трехмерного образа изоповерхностей значительно повышает наглядность восприятия. Использование при разработке системы визуализации технологий OpenGL и DirectX позволяет получать объёмное изображение исследуемых объектов, при наличии в составе оборудования клиент-

ской части таких средств виртуальной реальности, как шлемы и стерео очки. Кроме возможности использования стерео устройств, реализована поддержка 3-х мерного манипулятора, называемого трекер. Это устройство, подключаемое к компьютеру, способно сообщать клиентскому приложению свои углы поворота в 3-х мерном пространстве (т.н. 3DOF - degrees of freedom). При помощи трекера, можно вращать и рассматривать исследуемый 3-х мерный объект на экране компьютера, вращая в нужную сторону устройство находящееся в руках пользователя.

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

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

Исследованы возможности работы системы распределённой визуализации в рамках технологии GRID, на нескольких многопроцессорных машинах, территориально удалённых и связанных медленными каналами связи. В работе приводятся результаты тестирования системы распределённой визуализации при обработки данных одновременно на многопроцессорных машинах, содержащих различное количество вычислительных модулей и обладающих существенно отличающимися характеристиками производительности. Тестирование на двух кластерах (12 Celeron-850Mhz и 12 2xPentiumIII-600Mhz). связанных lOMbit-ной сетью подтверждает высокую эффективность разработанных программ и показывает достоверность полученных результатов.

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

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

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

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

3. На основе модели клиент-сервер создан программный комплекс интерактивной удаленной визуализации результатов вычислительных экспериментов.

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

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

1. П.С.Кринов. Моделирование на многопроцессорных системах затопленной тепловой струи. Материалы пятого всероссийского семинара «сеточные методы для краевых задач и приложения». Казань. 2004 Издательства «Казанский государственный университет имени В.И.Ульянова-Ленина». С. 129-132.

2. П.С.Кринов, М.В.Якобовский. Визуализация в распределённых вычислительных системах результатов численных экспериментов. Материалы Четвёртого Всероссийского семинара. Издательство Казанского математического общества. 2002. с. 69-74.

3. П.С.Кринов, С.В.Поляков, М.В.Якобовский. Визуализация в распределённых системах результатов трёхмерных расчётов. Труды четвёртой международной конференции по математическому моделированию. Под ред. Л.А. Уваровой. Издательство «Станкин». 2001. Том 2. с.126-133.

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

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

6. Кринов П.С., Якобовский М.В., Муравьев C.B. Сжатие и визуализация триангулированных поверхностей. Vl-я научная конференция МГТУ «СТАНКИН» и «Учебно-методического центра математического моделиро-

вания МГТУ «СТАНКИН» - ИММ РАН». Издательство «Янус-К». 2003. с.32-42.

7. M.V. lakobovski, D.E.Karasev, P.S. Krinov, S.V. Polyakov, Visualisation of Grand Challenge Data on Distribyted Systems, Mathematical Modeling. Problems, methods, applications, Proc. of the Fourth International Mathematical Modeling Conference, June 27 - July 1 2000, Moscow, Russia (Ed. by L.A. Uvarova, A.V. Latyshev), Kluwer Academic, Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. ISBN 0-306-46664-3, 2001, pp. 71-78.

8. Peter S. Krinov, Mikhail V. lakobovski, Sergey V. Muravyov, Large Data Volume Visualization on Distributed Multiprocessor Systems , Parallel Computational Fluid Dynamics (Moscow, Russia, May 13-15, 2003), Edited by B. Chetverushkin, A. Ecer, J. Periaux and N. Satofiika - Assistant Editor: Pat Fox, Elsevier Science BV, Amsterdam, 2004, pp. 433-438.

9. P.S.Krinov. Modeling the therml jet. VI International congress on mathematical modeling. Book of abstracts. University of Nizhny Novgorod. 2004. p.499.

10. lakobovski 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.

Формат 60x90/16 Бумага 80 гр/м2 Гарнитура "Times"

Объем 1,4 уч.-изд. л. Тираж 50 экз. Заказ №

СТАНКИН 103055, Москва, Вадковский пер., д. За

Of. (2- 0S,ß

РНБ Русский фонд

2005-4 40004

у*

Г' .

•а ц.

f #*, *<- *

( !.. \ ч» » э

- 1121

Введение.

Доступные пакеты визуализация.

Базовые стратегии универсальных методов.

Канонический алгоритм Хаффмана.

Словарные методы сжатия.

Сжатие с потерями.

Сжатие для визуализации научных данных.

Краткое содержание диссертации.

Глава 1. Моделирование трехмерной тепловой струи.

Постановка задачи.

Математическая модель.

Разностная схема.

Граничные условия.

Описание расчётного алгоритма.

Параллельная реализация алгоритма.

Работа с большими сетками.

Глава 2. Визуализация скалярных полей.

Конвейер визуализации.

Методы отображения.

Методы построения изоповерхностей.

Интерполяция.I.

- расчёт 7-ми опорных точек.

- поиск точек пересечения искомой изоповерхности и 50-ти рёбер каждой ячейки

- восстановление топологии.

Сжатие данных.

Сжатие массивов чисел с плавающей запятой.

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

Алгоритмическое сжатие.

Сжатие редукцией.

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

Библиотека распределенного ввода/вывода. . Декомпозиция сеток большого размера.

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

Параллельный алгоритм построения изоповерхности.

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

Расчёт струи.

Визуализация.

Сжатие сеточных данных.

Распределённая визуализация.

Интерфейс пользователя.

GRID-технологии.

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

Сложность решаемых методами математического моделирования научных и технологических задач, увеличение требований к точности их решения приводит к неуклонному росту объемов обрабатываемых в ходе вычислительных экспериментов данных. Проведение математических расчётов [1] позволяет сэкономить значительное время и материальные средства при выполнении натурных экспериментов, предваряя и существенно облегчая, а иногда и заменяя их полностью. Решение целого ряда задач газовой динамики, в особенности задач с химическими процессами, например, моделирование процессов горения [2, 3, 4, 5], требует больших вычислительных ресурсов, обеспечиваемых в настоящее время только высокопроизводительной вычислительной техникой, представленной многопроцессорными системами. Основная вычислительная нагрузка в подобных задачах приходится на моделирование химических процессов, причем потребности в вычислительных мощностях растут с ростом числа компонент. Нелинейная природа исследуемых задач приводит к возникновению особенностей решения даже при гладких начальных данных. Усложнение формы изучаемых областей требует проведения расчетов на подробных как по пространству, так и по времени сетках [6], что и определяет высокие требования к используемым ресурсам.

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

Развитие суперкомпьютерных центров и появление большого количества многопроцессорных систем, объединяющих сотни и тысячи процессоров, предоставляющих свои ресурсы через каналы internet, значительно расширило круг научных и прикладных задач решаемых при помощи численного эксперимента [7]. При этом возникли новые проблемы, не обнаруживающие себя, при моделировании на однопроцессорной технике. В первую очередь это вопросы переноса последовательного программного обеспечения на многопроцессорные системы, разработка и реализация параллельных численных алгоритмов [8,9,10,11,12,13]. К числу не возникающих ранее задач относятся вопросы генерации и хранения сеточных данных большого объёма, ввода-вывода результатов вычислений, вопросы обработки и визуализации больших объёмов данных, в том числе при использовании для расчётов территориально удалённых или распределённых (GRID) систем [24,25,26].

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

Системы с общей памятью [28,27], на сегодняшний день обладают небольшим числом процессоров и в первую очередь именно по этой причине далее не рассматриваются, поскольку не обеспечивают требуемую вычислительную мощность.

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

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

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

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

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

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

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

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

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

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

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

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

Моделирование задач механики сплошной среды. При проведении математического моделирования широкого круга задач механики сплошной среды согласно предложенной А.А.Самарским триаде «модель-алгоритм-программа» [1], можно выделить следующие основные этапы: о формирование математической модели изучаемого явления (газодинамической задачи, в данном случае); о выбор разностной схемы, допускающей построение эффективного параллельного алгоритма; о построение параллельной программы и выполнение расчёта.

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

Кинетически-согласованные разностные схемы (КСРС) были предложены в Институте математического моделирования РАН в первой половине 80-х годов Б.Н. Четверушкиным. Практика их успешного применения в численном решении различных задач газовой динамики, включая моделирование неустановившихся течений, турбулентных потоков, задач аэроакустики и аэроупругости, течений химически реагирующих газов, насчитывает таким образом более пятнадцати лет [14]. С конца 80-х - начала 90-х годов значительное число практических расчетов проводилось с использованием многопроцессорных вычислительных систем.

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

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

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

Главное физическое предположение, заложенное в основу получения КСРС, состоит в следующем: функция распределения постоянна в момент времени tk) на ячейке расчетной сетки и равна локально-максвелловской функции распределения: а

2RT*)1 (2RT,*)3 т-т а к+1 к

При этом предполагается, что в течение времени ш = t —t имеет место бесстолкновительный разлет молекул, а в момент tk+{ происходит их мгновенная максвеллизация.

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

1 гк 1 fk . гк fk+l гк

J i Ji„ М

At V. ■ J v J' 2 2V.

Суммирование здесь происходит по всем j-м ячейкам, соседним с i-й, а интегрирование - по общей грани /- й и j- й ячеек (V.— объем /- й ячейки). Интегрируя полученные соотношения с сумматорными инвариантами 1, по скоростям молекул, получим систему разностных уравнений для газодинамических параметров, полный вид которой будет приведен ниже. При этом образуются диффузионные члены, играющие роль искусственной диссипации. Однако, в отличие от классической искусственной вязкости фон Неймана, их вид согласован с диссипативными членами в разностном аналоге кинетического уравнения. Это и послужило поводом дать схемам название кинетически-согласованных. С вычислительной точки зрения дополнительные диссипативные члены можно трактовать как эффективные регуляризаторы, позволяющие развиваться естественным неустойчивостям и сглаживающие неустойчивости чисто счетного характера.

Кинетически-согласованный подход обеспечивает естественное обобщение разностной схемы для линейного уравнения переноса на систему нелинейных газодинамических уравнений. Аппроксимацию уравнения переноса схемой с направленными разностями можно интерпретировать как физическую модель переноса кусочно-постоянной функции распределения. Получающиеся после осреднения разностные макроуравнения в дифференциальном приближении можно рассматривать как обобщение уравнений Эйлера и Навье-Стокса. Подробное исследование свойств КСРС и их обоснование с физической точки зрения можно найти, например, в работах [18,19,20]. Всего же этой теме посвящено более ста публикаций.

Выделим теперь те свойства КСРС, которые наиболее важны для проведения параллельных вычислений.

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

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

Стоит отметить и логическую простоту алгоритмов, построенных на основе кинетически-согласованных схем. Начиная с 1988 года они используются для проведения расчетов на различных многопроцессорных системах, при этом соответствующие программы легко адаптируются и используются на новых типах вычислительных систем [21,6,22,23].

Распределенные вычислительные системы. Сегодня в разных организациях сосредоточено много вычислительных ресурсов, которые далеко не всегда используются полноценно. Эти компьютеры могут находиться в разных местах, выполнять разные приложения, использовать разные средства хранения информации и системы доступа. С другой стороны, есть ряд актуальных задач глобального масштаба, для решения которых требуются разнообразные компьютерные ресурсы и большие вычислительные мощности, причём алгоритмы решения этих задач допускает эффективное распараллеливание. Во многом именно по этой причине появилась технология Grid Computing [24,25,26] - технология распределённой работы в сетях вычислительных ресурсов.

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

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

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

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

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

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

Инструментарий с открытым кодом Globus Toolkit, разработанный совместно Калифорнийским университетом и Аргоннской национальной лабораторией, стал фактическим стандартом платформы Grid-сетей, получившим поддержку ведущих компаний США и Японии. Компании Hewlett-Packard, Cray, SGI, Sun Microsystems, Veridian, Fujitsu, Hitachi, NEC, IBM и Microsoft создают оптимизированные варианты Globus Toolkit для своих платформ. Компания Platform Computing планирует совместно с разработчиками инструментария создать его коммерческую версию. Работа над Globus Toolkit шла в течение шести лет и ее результатом стало появление набора протоколов, служб и приложений, обладающих открытой архитектурой и реализующих основную концепцию Grid, как надежной масштабируемой среды координированного совместного использования ресурсов в динамичных многоячеечных "виртуальных организациях".

Sun эксплуатирует собственную Grid-сеть, объединяющую более 6000 процессоров и 210 Тбайт данных. Каждый день эта система обрабатывает десятки тысяч задач электронного проектирования, при этом средняя загрузка процессоров составляет около 98%.

Рисунок 1 Категории Grid-сетей.

Sun Microsystems различает три основные категории Grid-сетей

Рисунок 1):

• относительно простая вычислительная сеть, предоставляющая ресурсы пользователям одной рабочей группы, одного департамента, одного проекта (Cluster Grid);

• вычислительная сеть корпоративного уровня, охватывающая несколько групп, работающих над различными проектами (Enterprise Grid);

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

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

Доступные пакеты визуализация

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

Существует значительное число средств визуализации научных данных, обладающих широкими функциональными возможностями. Это такие программные пакеты как TecPlot [32,33,34], Origin, IRIS Explorer [35], EasyPlot и ряд других. Эти продукты активно используются при анализе и обработке результатов численных экспериментов большим количеством учёных по всему миру. К сожалению, объём визуализируемых с их помощью данных естественным образом ограничен ресурсами персонального компьютера. Размеры сеток, на которых производится моделирование на многопроцессорных системах, а также исходные и результирующие данные, всё чаще превышают по объёму размер оперативной памяти одного персонального компьютера. Это делает невозможным анализ и визуализацию при помощи используемых обычно для этих целей инструментов без предварительной обработки данных. Объемы данных, измеряемые десятками и сотнями гигабайт, не только не помещаются в оперативной памяти персонального компьютера, но и не могут разместиться даже на одном жестком диске. Работа с суперкомпьютерными центрами возможна и в основном происходит с уделённых мест - через каналы internet, в то время как только передача по сети, к примеру, результатов расчётов размером в несколько гигабайт, займет значительное время. Таким образом, перед визуализацией, необходимо из всего объёма выделить небольшую часть, которую уже можно будет передать на персональный компьютер и обработать стандартными средствами. Так как для выборки данных для визуализации не существует доступного инструментария, экспериментаторы, в основном, прореживают данные, уменьшая, таким образом, их объём. При такой процедуре теряется значительная часть информации.

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

Базовые стратегии универсальных методов

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

Существует три базовые стратегии сжатия [36]:

1. Преобразование потока

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

2. Статическая стратегия

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

• Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика.

3. Преобразование блока

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

Таким образом, метод сжатия может быть или статическим, или трансформирующим и обрабатывать данные либо потоком, либо блоками, причём исследования [37-87] показывают, что:

• Чем больше и однороднее данные и память1, тем эффективнее блочные методы;

• Чем меньше и неоднороднее данные и память, тем эффективнее поточные методы;

• Чем сложнее источник, тем сложнее улучшит сжатие оптимальное преобразование;

• Чем проще источник, тем эффективнее прямолинейное статистическое решение.

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

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

1 Однородная память - память, выделенная одним блоком: никаких особенностей при обращении к ней нет. Если память не однородна, доступ по произвольному адресу (random access) замедляется, как правило, в несколько раз неявным образом. Но всегда сжатие достигается за счёт устранения статистической избыточности в представлении информации.

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

Существует 2" различных файлов длины п бит, где п=0, 1, 2, . . Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2" исходным файлам будет соответствовать самое большое 2Л| различных сжатых файлов. Тогда, по крайней мере, одному архивному файлу будет соответствовать несколько различающихся исходных и, следовательно, его декодирование без потерь информации будет невозможно в принципе.

Таким образом, невозможен «вечный» архиватор, который способен бесконечное число раз сжимать свои же архивы. С этой точки зрения [36]. «наилучшим» архиватором является программа копирования, при её применении мы можем всегда быть уверены в том, что объём данных в результате обработки не увеличится.

Канонический алгоритм Хаффмана

Один из классических алгоритмов, известных с 50-х годов канонический алгоритм Хаффмана [46], использует только частоту появления одинаковых байтов во входном блоке данных, ставя в соответствие символам входного потока, которые встречаются чаще, цепочку битов меньшей длины, и напротив, встречающимся редко -цепочку большей длины. Для сборки статистики требует двух проходов по входному блоку (также существуют однопроходные адаптивные варианты алгоритма). Алгоритм Хаффмана требует помещения в файл со сжатыми данными таблицы соответствия кодируемых символов и кодирующих цепочек. На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить её адаптивно, т.е. в процессе архивации/разархивации. Эти приёмы избавляют нас от двух проходов по входному блоку и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется, в частности, в качестве последнего этапа архивации в JPEG.

Словарные методы сжатия

Особое внимание следует уделить словарным методам сжатия данных [39,40,40394042,43]. Основная идея здесь такова. Входную последовательность символов можно рассматривать как последовательность строк, содержащих произвольное количество символов. Идея словарных методов состоит в замене строк символов на такие коды, что их можно трактовать как индексы строк некоторого словаря. Образующие словарь строки будем дальше называть фразами. При декодировании осуществляется обратная замена индекса на соответствующую ему фразу словаря.

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

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

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

Алгоритмы словарного сжатия Зива-Лемпела [41,48] появились во второй половине 70-х годов. Это были так называемые алгоритмы LZ77 и LZ78, разработанные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем первоначальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчётное количество модификаций.

LZ77 и LZ78 являются универсальными алгоритмами сжатия, словарь которых формируется на основании уже обработанной части входного потока, т.е. адаптивно. Иногда также говорят о словарных методах LZ1 и LZ2.

Сжатие с потерями

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

Поскольку алгоритмы сжатия без потерь обладают принципиальными ограничениями по коэффициентам сжатия, для многократного увеличения компрессии необходимо прибегать к методам сжатия с потерями [67-87]. В случае, если речь идёт об исходных или промежуточных данных при проведении крупномасштабного численного эксперимента, то какие бы то ни было потери недопустимы, в то время как, при подготовке данных для визуализации они вполне приемлемы.

В общем случае, сжатие с потерями (lossy compression) распадается на два последовательных этапа:

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

2. сжатие без потерь выделенных данных.

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

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

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

Оценка потерь качества изображения

Одна из серьёзных проблем машинной графики заключается в том, что до сих под не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати и, что для нас особенно важно, при сжатии с потерями. Можно привести пример [36] простого критерия -среднеквадратичное отклонение значений пикселов (Ь2 мера, или root mean square - RMS): d(x,y) = n2

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

Свои неприятные стороны есть и у других критериев. Рассмотрим, например, максимальное отклонение: d(x,y) - maxlx^. -yJ.

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

Мера, которую сейчас используют на практике, называется мерой отношения сигнала у шуму (peak-to-peaksignal-to-noise ratio - PSNR):

2552-п2 d (дг, = 10* log

10

ТМи-Уу? i-l.v-l

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

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

Алгоритм JPEG

Алгоритм JPEG - один из новых и достаточно мощных алгоритмов сжатия. Он практически является стандартом де-факто для полноцветных изображений. Оперирует алгоритм областями 8x8 растровых точек, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой области в двойной ряд по косинусам, значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счёт плавности изменения цветов в изображении.

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG - Joint Photographic Expert Group - подразделение в рамках ISO - Международной организации по стандартизации. В целом алгоритм основан на дискретном косинусоидальном преобразовании (ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов.

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

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

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

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьёзных потерь.

Фрактальное сжатие

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

Сжатие на основе вейвлет-преобразования

И наконец скажем о рекурсивном (волновом) алгоритме.

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

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

Так, два числа a2i и a2l41 всегда можно представить в виде Ь\=(а21+а2М)/2 и b2i=(a2i-a2M)/2. Вся последовательность может быть попарно переведена в последовательность bh2r Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

Заметим, что мы применяли наше преобразование по цепочке только 2 раза. Реально мы можем позволить себе применить wavelet-преобразование 4-6 раз. Более того, дополнительное сжатие можно получать, используя таблицы Хаффмана с неравномерным шагом, т.е. нам придётся сохранять код Хаффмана для ближайшего в таблице значения.

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

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

26 способности устройств вывода: дисплеев и принтеров. Тем не менее, непосредственно применение описанных выше методов сжатия с потерями может (и на самом деле именно это и произойдёт при около-предельном сжатии) затереть или сгладить области с резким изменением интересующего нас параметра, что в результате приведёт к тому, что экспериментатор не увидит самого главного или увидит какие-либо «новые» образования, получившиеся в результате сжатия и не имеющие отношения к данным эксперимента. С другой стороны, сжатие в сотни раз может оказаться недостаточным для гигантских данных, полученных в результате крупномасштабного эксперимента.

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

Сжатие для визуализации научных данных

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

Краткое содержание диссертации

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

Заключение

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

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

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

3. На основе модели клиент-сервер создан программный комплекс интерактивной удаленной визуализации результатов вычислительных экспериментов.

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

1. Самарский А.А., Михайлов А.П. Математическое моделирование. -М.: ФИЗМАТЛИТ, 2001.

2. Chetverushkin B.N., Iakobovski M.V., Kornilina М.А., Malikov K.Yu.,

3. Romanukha N.Yu. Ecological after-effects numerical modelling under methane combustion. In: Mathematical Models of Non-Linear Excitations,t Transfer, Dynamics, and Control in Condensed Systems and Other Media.

4. Proc. of a Symp., June 29 July 3 1998, Tver, Russia (Ed. by L.A Uvarova,

5. A.E. Arinstein, and A.V. Latyshev), Kluwer Academic // Plenum Publishers. New York, Boston, Dordrecht, London, Moscow. ISBN 0-306-46133-1. -1999.-pp. 147-152.

6. Корнилина М.А., Леванов Е.И., Романюха Н.Ю., Четверушкин Б.Н., Якобовский М.В. Моделирование газового течения с химическими реакциями на многопроцессорной системе. В кн.: Применение математического моделирования для решения задач в науке и технике.

7. Сб. трудов междунар. конф. «Математическое моделирование в науке и технике» (ММНТ'98). Отв. ред. М.Ю.Альес. Изд-во ИПМ УрО РАН. Ижевск. 1999. - С.34 - 48.

8. Болдырев С.Н. Решение некоторых задач газовой динамики с применением нерегулярных сеток на параллельных вычислительных системах. // Некоторые проблемы фундаментальной и прикладной математики: Междувед. сб. / МФТИ. М., 1998. С. 159-167.,

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

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

11. Лацис А. Как построить и использовать суперкомпьютер. -М.:Бестселлер, 2004.г 10. Савин Г.И., Шабанов Б.М., Забродин А.В., Левин В.К., Каратанов

12. B.В., Корнеев В.В., Елизаров Г.С. Структура многопроцессорнойвычислительной системы МВС-1000М // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их пригожения», г. Черноголовка, 2000, с.3-8. изд. МГУ.

13. Андреев А., Воеводин В., Жуматий С. Кластеры и суперкомпьютеры близнецы или братья? // Открытые системы, №5-6, 2000.

14. Joseph D. Sloan. High Performance Linux Clusters with OSCAR, Rocks, OpenMosix, and MPI. O'Reilly & Associates, 2004.

15. C. Bookman. Linux Clustering: Building and Maintaining Linux Clusters. New Riders Publishing. 2002.

16. D. Spector. Building Linux Clusters. O'Reilly & Associates, 2000.

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

18. S.M. Deshpande. Kinetic Flux Splitting Schemes. // Сотр. Dynamic Review. John Wiley & Sons, Chichester, 1995, pp. 161-181.

19. Власов А.А. Статистические функции распределения. M.: Наука, 1966.

20. Т.Г. Елизарова, Б.Н. Черверушкин. Кинетически-согласованные разностные схемы для моделирования течений вязкого теплопроводного газа. // Журнал вычмслительной математики и математической физики, 1988, т.28, №11, с.695-710.

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

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

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

24. Абалакин И.В., Бабакулов А.Б., Музафаров X.A., Якобовский М.В. Моделирование течений умеренно-разреженного газа на транспьютерных системах. // Математическое моделирование, 1992. Т.4. №11. С.3-18.

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

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

27. Fran Berman, Geoffrey Fox, Anthony J.G. Hey. Grid Computing: Making The Global Infrastructure a Reality. John Wiley & Sons (April 8, 2003)

28. Ian Foster, Carl Kesselman. The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann; 2 edition (November 18, 2003)

29. Jarek Nabrzyski, Jennifer M. Schopf, Jan Weglarz. Grid Resource Management: State of the Art and Future Trends (International Series in Operations Research and Management Science). Springer; 1 edition (September, 2003)

30. Jelica Proti, Milo Tomasevi, Veljko Milutinovi. Distributed Shared Memory : Concepts and Systems. Wiley-IEEE Computer Society Pr; 1 st edition (July 27,1997)

31. Daniel E. Lenoski, Wolf-Dietrich Weber. Scalable Shared-Memory Multiprocessing. Morgan Kaufmann Publishers (March 1, 1995)

32. Arndt Bode. Distributed Memory Computing: 2nd European Conference, Edmcc2, Munich, Frg, April 22-24, 1991 (Lecture Notes in Computer Science, Vol 487). Germany European Distributed Memory Computing Conference 1991 Munich. Springer-Verlag (May 1, 1991)

33. Eva Kuhn. Virtual Shared Memory for Distributed Architectures. Nova Science Publishers (January 1, 2002)

34. М.В.Якобовский. Распределённые системы и сети. Издательство «Станкин». Москва. 2000.

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

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

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

38. IRIS Explorer™ Documentation (Windows NT®/2000) 2000 The Numerical Algorithms Group Ltd.

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

40. Bender Р.Е., Wolf J.K. New asymptotic bounds and improvements on the Lempel-Ziv data compression algorithm // IEEE Transactions on Information Theory. May 1991. Vol. 37(3). P.721-727.

41. Deutsch L.P. (1996) DEFLATE Compressed Data Format Specofocation v.1.3 (RFC 1951)

42. Fiala E.R., Greene D.H. Data compression with finite windows. Commun //ACM. Apr. 1989. Vol. 32(4). P. 490-505.

43. Hoang D.T., Long P.M., Vitter J.S. Multi-dictionary compression using partial matching//Proceedings of Data Compression Conference. March 1995. p.272-281, Snowbird, Utah.

44. Langdon G.G. A note on the Ziv-Lempel model dor compressing individual sequences // IEEE Transaction on Information Theory. March 1983. Vol. 29(2). P.284-287.

45. Larsson J., Moffat A. Offline dictionary-based compression // Proceedings IEEE. Nov. 2000. Vol. 88(11). P.1722-1732.

46. Matias Y., Rajpoot N., Sahinalp S.C. Implementation and experimental evaluation of flexible parsing for dynamic dictionary based compression //Proceedings WAE'98. 1998.

47. Rissanen J.J., Langdon G.G. Universal modeling and coding // IEEE Transactions on Information Theory. Jan. 1981. Vol. 27(1). P. 12-23.

48. Storer J.A., Szymanski T.G. Data compression via textual substitution // Journal of ACM. Oct. 1982. Vol 29(4). P.928-951.

49. Welch T.A. A technique for high-perfomance data compression // IEEE Computer. June 1984. Vol. 17(6). P.8-19.

50. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. May 1977. Vol. 23(3). P.337-343.

51. Ziv J. and Lempel A. Compression of individual sequences via variable-rate coding // IEEE Transactions on Information Theory. Sept. 1978. Vol. 24(5). P.530-536.

52. Шкарин Д. Повышение эффекривности алгоритма PPM // Проблемы передачи информации. 2001. Т.34(3). С. 44-54.

53. Bell Т.С., Witten I.H., Cleary J.G. Modelin for text compression // ACM Computer survey. 1989. Vol 24(4). P.555-591.

54. Blomm C. Solving the problem of comtext modeling // California Institute of Technology. 1996.

55. Buntom S. On-Line Stochastic Processes in Data Compression // PhD thesis, University of Washingtom. 1996.

56. Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching // IEEE Transaction on Communications April 1984. Vol. 32(4). P.396-402.

57. Cleary J.G., Teahan W.J. Unbounded length context for PPM // The computer Journal. 1997. Vol. 40(2/3).P.67-75.

58. Cormack G.V., Horspool R.N. Data compression using dynamic Markov modelling // The Computer Journal. Dec. 1987. Vol 30(6). P.541-550.

59. Howard P.G. The design and analysis of efficient lossless data compression systems //PhD thesis, Brown Universuty, Providence, Rhode Island. 1993.

60. Lelewer D.A., Hirschberg D.S. Streamlining Context Model for Data Compression. //Proceedings of Data Compression Conference, Snowbird, Utah. 1991. P.313-322.

61. Moffat A. Implementing the PPM data compression scheme // IEEE Transactions on Communications. Nov. 1990. Vol. 38(11). P.1917-1921.

62. Nevill-Manning C.G., Witten I.H. Linear-tiem, incremental hierarchy inference for compression // Proceedings of Data Compression Conference /By ed. J.A.Storer and M.Cohn. Los Alamitos, CA: IEEEPress. 1997. P.3-11.

63. Shannon C.E. A mathematical theory of communication // The Bell System Technical Journal. July, October, 1948. Vol.27. P.379-423. 623-656.

64. Schmidhuber J. Sequential neural text compression // IEEE Transactions on Neural Networks. 1996. Vol. 7(1). P.142-146.

65. Teahan W.J. Probability estimation for PPM // Proceedings of the New Zealand Computer Science Research Students Conference, 1995. University of Waikato, Hamilton, New Zealand.

66. Willems F.M.J., Shtarkov Y.M., Tjalkens T.J. The context-tree weighting methodA Basic properties // IEEE Transaction on Information Theory. May 1995. Vol. 41(3). P. 653-664.

67. Witten I.H., Bell T.C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression // IEEE Transactions on Information Theory. July 1991. Vol. 37(4). P.1085-1094.

68. Wittem I.H., Bray Z., Mahoui M., Teahan B. Text mining: a new frontier for lossless compression // University of Waikato, New Zealand. 1999.

69. Ryabko B.Ya. Twice Universal Coding // Problims of Information Transmition. Vol. 20(3). 1984. P.173-177.

70. Le Gall D.J. The MPEG Video Compression Algorithm // Sognal Processing: Image Communication. 1992. Vol.4, №2.P. 129-140.

71. Wallach D.S., Kunapalli S., Cohen M.F. Accelerated MPEG compression of Dynamic poligonal scenes // ACM. Jun 1994.

72. Liou Ming. Overview of the px64 kbit/s video coding standart // Communication of ACM. April 1991. Vol.34. №4.

73. Coding of moving pictures and associated audio // Committee Draft of Standart ISOl 1172: ISO/MPEG 90/176 Dec. 1990.

74. JPEG digital compression and codig of continuous-tone stil images.1.010918.1991.

75. Video codec for audio visual services px64 Kbit/s. CCITT k recommendation H.261. 1990.

76. MPEG proposal package description. Document ISO/WG8/MPEG 89/128. July 1989.

77. International Telecommunication Union. Video Coding for Low Bitrate Communication, ITU-T recommendation H.263. 1996.

78. RTP Payload Format for H.263 Video Streams, Intel Corp. Sept. 1997. RFC2190.

79. Mitchell J.L., Pennebaker W.B., Fogg C.E. and Le Gall D.J, "MPEG

80. Video Compression Standard" //Digital Multimedia Standards Series. New Yourk, NY: Chapman & Hall, 1997.

81. Haskell B.G., Puri A. and Netravali A.N. Digital Video: An Introduction to MPEG-2 // ISBN: 0-412-08411-2. New York, NY: Chapman & Hall, 1997.

82. Image and Video Compression Standards Algorithms and Architectures, Second Edition by Vasudev Bhaskaran. Boston Hardbound: Kluwer Academic Publishers, 472p.

83. Sikora Т., MPEG-4 Very Low Bit Rate Video // Proc. IEEE ISCAS f* Conference, Hongkong, June 1997.

84. Rao K.R. and Yip P. Discrete Cosine Transform Algorithms, 'ч Advantages, Applications // London: Academic Press, 1990.

85. ISO/IEC JTC1/SC29/WG1 IN MPEG-4 Video Frequently Asked Questions // March 2000.

86. ITU. Chairman of Study Group 11. The new approaches to quality assessment and measurement in digital broadcasting. Doc. 10-1 lQ/9,6. October 1998.

87. Kuhn Peter, Algorithms, Complexity Analysis and Vlsi Architectures for MPEG-4 Motion Estimation // Boston Harbound: Kluwer Academic

88. Publishers, June 1999. ISBN 0792385160, 248p.

89. Цифровое телевиденье // Под ред. М.И. Кривошеева. М.:Связь, 1980.t 87. Кривошеев М.И. Основы телевизионных измерений. 3-еизд.М.:радио и связь, 1989.

90. П.С.Кринов, М.В.Якобовский. Визуализация в распределённых вычислительных системах результатов численных экспериментов. Материалы Четвёртого Всероссийского семинара. Издательство Казанского математического общества. 2002. с. 69-74.

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

92. V 98. Кринов П.С., Поляков C.B., Якобовский M.B. «Визуализация враспределённых вычислительных системах результатов трёхмерных » расчётов»// Тезисы четвёртой международной конференции

93. Математическое моделирование нелинейных возбуждений, переноса, динамики, управления в конденсированных системах и других средах» М.: Издательство «Станкин», 2000. С. 65.

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

95. OO.Hendrickson B. and Leland R. A Multi-Level Algorithm for Partitioning Graphs, Tech. Rep. SAND93-1301, Sandia National Laboratories, Albuquerce, October 1993.

96. Hendrickson B. and Leland R. An Improved Spectral Graph Partitioning Algorithm For Mapping Parallel Computations — SIAM J. Sci. Comput.,f 1995, vol.16. №2.

97. Валерий Качуров «Современные распределенные файловые системы для Linux: Основные сведения.» Журнал «Компьютерра». 2002, Издательский дом «КОМПЬЮТЕРРА» 16.9.2002

98. Юрий Тихомиров. Программирование трёхмерной графики -СПб.:БХВ Санкт-етербург, 1999. - 256 е., iui.ISBN 5-8206-0068-1

99. Чарльз Петзолд. Программирование для Windows 95; в двух томах.; пер. с англ. CTI6.:BHV - Санкт-Петербург, 1997. - 752 е., 368с., iui.ISBN 1-55615-676-6 ISBN 5-7791-0022-9

100. Александр Цимбал. Технология CORBA (+CD). СПб: Питер, 2001.-624 е.: ил.ISBN 5-272-00396-9

101. Джо Вебер. Технология Java в подлиннике: пер. с англ.-СПб.:ВНУ-Санкт-Петербург, 1997.-1104 е., mi.ISBN 0-7897-0936-8 (англ.) ISBN 5-7791-0051-9

102. Barrett, Daniel and Richard Silverman. SSH, the Secure Shell:v

103. The Definitive Guide. Sebastopol, CA: O'Reilly & Associates, Inc., 2001.

104. Bookman, Charles. Linux Clustering: Building and Maintaining ^ Linux Clusters. Indianapolis, IN: New Riders Publishing, 2002.

105. Callaghan, Brent. NFS Illustrated. Reading, MA: Addison Wesley Professional, 1999.

106. Culler, David, Jaswinder Pal Singh, with Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1998.

107. Dowd, Kevin and Charles Severance. High Performance Computing. Second Edition. Sebastopol, CA: O'Reilly & Associates, Inc., 1998.

108. Dongarra, Jack et al., eds. Sourcebook of Parallel Computing. San Francisco, CA: Morgan Kaufmann Publishers, Inc., 2003.

109. Geist, Al et al. PVM: Parallel Virtual Machine: A User's Guide and Tutorial for Networked Parallel Computing. Cambridge, MA: MIT Press, 1994.

110. Gropp, William, Ewing Lusk, and Anthony Skjellum. Using MPI: Portable Parallel Programming with the Message-Passing Interface. Second Edition. Cambridge, MA: MIT Press, 1999.

111. Message Passing Interface Forum. MPI-2: Extensions to the Message-Passing Interface. Knoxville, TN: University of Tennessee, 1997.

112. Pacheco, Peter. Parallel Programming with MPI. San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1997.

113. Snir, Marc et al. MPI: The Complete Reference. 2 vols. Cambridge, MA: MIT Press, 1998.

114. Tanenbaum, Andrew. Computer Networks. Fourth Edition. Saddle River, NJ: Pearson Education, 2002.

115. Thompson, Robert and Barbra Thompson. Building the Perfect PC. Sebastopol, С A: O'Reilly & Associates, Inc., 2004.

116. Wilkinson, Barry and Michael Allen. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Upper Saddle River, NJ: Prentice-Hall, Inc., 1999.

117. Абрамович Г.Н. Теория Турбулентных Струй. ФизМатГиз. Москва. 1960г.

118. Абрамович Г.Н. Прикладная газовая динамика. ФизМатГиз. Москва 1976г.

119. S. Park, С. Bajaj, I. Ihm. Visualization of Very Large Oceanography Time-Varying Volume Datasets. Lecture Notes in Computer Science (LNCS), ed. by M. Bubak et. al., ICCS 2004, Volume 3037, 2004 , pages 419 426, Springer-Verlag Heidelberg

120. Z. Yu, С. Bajaj. Visualization of Icosahedral Virus Structures from Reconstructed Volumetric Maps. Technical Report, Department of Computer Sciences, The University of Texas at Austin, April 9, 2004.