Содержание к диссертации
Введение
Глава 1. Моделирование трехмерной тепловой струи 38
Постановка задачи 38
Математическая модель 39
Разностная схема 39
Граничные условия 41
Описание расчётного алгоритма 41
Параллельная реализация алгоритма 42
Работа с большими сетками 47
Глава 2. Визуализация скалярных полей 49
Конвейер визуализации 50
Методы отображения 52
Методы построения изоповерхностей 53
Интерполяция . 53
- расчёт 7-ми опорных точек 56
- поиск точек пересечения искомой изоповерхности и 50-ти рёбер каждой ячейки57
- восстановление топологии 57
Сжатие данных 67
Сжатие массивов чисел с плавающей запятой 68
Сжатие триангулированных поверхностей
Алгоритмическое сжатие
Сжатие редукцией 71
Глава 3. Параллельные алгоритмы визуализации 76
Библиотека распределенного ввода/вывода 76
Декомпозиция сеток большого размера 78
Структура системы распределенной визуализации 79
Параллельный алгоритм построения изоповерхности 82
Глава 4. Результаты расчётов 89
Расчёт струи 89
Визуализация 92
Сжатие сеточных данных 92
Распределённая визуализация 99
Интерфейс пользователя 99
GRID-технологии 109
Использованные технические и программные ресурсы 113
Заключение 116
Литература 117
- Параллельная реализация алгоритма
- Сжатие массивов чисел с плавающей запятой
- Структура системы распределенной визуализации
- Использованные технические и программные ресурсы
Введение к работе
Сложность решаемых методами математического моделирования
научных и технологических задач, увеличение требований к точности их
решения приводит к неуклонному росту объемов обрабатываемых в ходе
вычислительных экспериментов данных. Проведение математических
расчётов [1] позволяет сэкономить значительное время и материальные
средства при выполнении натурных экспериментов, предваряя и
существенно облегчая, а иногда и заменяя их полностью. Решение целого
ряда задач газовой динамики, в особенности задач с химическими
процессами, например, моделирование процессов горения [2, 3, 4, 5],
требует больших вычислительных ресурсов, обеспечиваемых в настоящее
время только высокопроизводительной вычислительной техникой,
представленной многопроцессорными системами. Основная
вычислительная нагрузка в подобных задачах приходится на моделирование химических процессов, причем потребности в вычислительных мощностях растут с ростом числа компонент. Нелинейная природа исследуемых задач приводит к возникновению особенностей решения даже при гладких начальных данных. Усложнение формы изучаемых областей требует проведения расчетов на подробных как по пространству, так и по времени сетках [6], что и определяет высокие требования к используемым ресурсам.
Широко используемые подробные регулярные сетки с фиксированным по пространству вычислительным шаблоном обладают существенным недостатком, выражающимся в необходимости обработки неоправданно большого числа узлов сетки в областях гладкого изменения параметров течения. Альтернативой им выступают нерегулярные сгущающиеся сетки: они имеют большее число узлов в тех областях, где наиболее активно идут моделируемые процессы, наиболее динамично изменяются исследуемые величины, либо располагаются сложные границы
изучаемой геометрической области. В тоже время, в отличие от
регулярных сеток, число расчётных узлов в областях с медленным изменением основных параметров может быть относительно невелико. Следует отметить, что использование сгущающихся сеток, позволяя
значительно лучше описать особенности течения, не позволяет
»
принципиально уменьшить требования к вычислительным ресурсам. В
« связи с этим, использование для расчетов многопроцессорных систем
представляется единственно реальной возможностью.
Развитие суперкомпьютерных центров и появление большого количества многопроцессорных систем, объединяющих сотни и тысячи процессоров, предоставляющих свои ресурсы через каналы internet, значительно расширило круг научных и прикладных задач решаемых при
* помощи численного эксперимента [7]. При этом возникли новые
проблемы, не обнаруживающие себя, при моделировании на
однопроцессорной технике. В первую очередь это вопросы переноса
последовательного программного обеспечения на многопроцессорные
системы, разработка и реализация параллельных численных алгоритмов
[8,9,10,11,12,13]. К числу не возникающих ранее задач относятся вопросы
генерации и хранения сеточных данных большого объёма, ввода-вывода
результатов вычислений, вопросы обработки и визуализации больших
і объёмов данных, в том числе при использовании для расчётов
территориально удалённых или распределённых (GRID) систем [24,25,26].
Многопроцессорные вычислительные системы доступные для проведения широкомасштабных вычислительных экспериментов можно разделить на системы с общей памятью и системы с распределённой (разделённой) памятью.
* Системы с общей памятью [28,27], на сегодняшний день обладают
небольшим числом процессоров и в первую очередь именно по этой
причине далее не рассматриваются, поскольку не обеспечивают требуемую
*
вычислительную мощность.
распределенной памятью, обладающих значительной
производительностью, требует создания методов и подходов эффективного использования их ресурсов, в том числе в режиме удалённого доступа. В первую очередь это проблемы подготовки и загрузки на вычислительный комплекс больших объемов сеточных данных, проблемы балансировки
*' загрузки узлов многопроцессорных систем в ходе проведения расчетов и,
наконец, проблемы дистанционного интерактивного анализа результатов -больших объемов полученных в результате расчетов сеточных функций.
Актуальность темы диссертационной работы определяется необходимостью создания параллельных алгоритмов, обеспечивающих эффективную обработку больших объемов данных на всех этапах
' вычислительного эксперимента, выполняемого на большом числе
процессоров, в том числе, в режиме удаленного доступа.
Цели диссертационной работы. Основной целью диссертационной работы является разработка эффективных параллельных алгоритмов, обеспечивающих возможность проведения вычислительных экспериментов в области моделирования задач газовой динамики на большом числе процессоров с использованием подробных регулярных и нерегулярных трехмерных сеток большого размера. Требования к алгоритмическому и
ъ программному обеспечению, обеспечивающему достижение указанной
цели, могут быть определены только в ходе проведения самих вычислительных экспериментов на большом числе процессоров с использованием подробных сеток. То же относится к установлению соответствия разработанных средств поставленной цели.
В качестве проблемы, эффективное решение которой на
« многопроцессорных системах, без создания специальных средств
обработки больших объемов данных, невозможно, рассматривается задача моделирования истечения в атмосферу затопленной горячей струи. Ее особенность, несмотря на простую геометрию расчетной области,
*,
* заключается в наличии значительной разницы в геометрических масштабах
- общий размер расчетной области составляет километры, при диаметре
трубы из которой поступает струя, измеряемом сантиметрами. Эта разница
приводит к необходимости использования сеток большого размера.
Основное внимание уделено созданию методов визуализации результатов крупномасштабных вычислительных экспериментов
* проводимых на суперкомпьютерах, предоставляемых центрами
коллективного пользования, доступных пользователю через относительно
медленные каналы internet.
Для достижения указанной цели решаются следующие задачи:
выбор подхода к численному решению систем газодинамических
уравнений и выбор эффективных численных методов,
* адаптированных к параллельным вычислениям;
вопросы построения эффективных вычислительных алгоритмов рассматриваются на примере разработки параллельного алгоритма моделирования истечения в атмосферу затопленной горячей струи;
исследование особенностей и алгоритмов визуализации трехмерных скалярных сеточных данных;
создание эффективных параллельных алгоритмов и программ
распределенной визуализации больших объемов данных, в том числе
v хранящихся на множестве файловых серверов или вычислительных
модулей вычислительной системы.
Научная новизна и практическая ценность работы. В
диссертации предложены оригинальные параллельные алгоритмы
обработки результатов моделирования задач газовой динамики на
многопроцессорных системах с распределенной памятью. Предложена
" основанная на модели клиент-сервер структура системы распределенной
визуализации, обеспечивающая возможность интерактивного изучения
сеточных данных, определенных на регулярных и нерегулярных сетках
большого размера.
* На основе разработанных алгоритмов создан комплекс
параллельных программ визуализации трёхмерных скалярных данных
большого объёма, обеспечивающий возможность интерактивного анализа
данных в распределенных системах и на метакомпьютерах. Эффективность
предложенных алгоритмов обработки больших объемов сеточных данных
демонстрируется на примере визуализации результатов задачи о
* распространении в атмосфере горячей затопленной струи.
Моделирование задач механики сплошной среды. При
проведении математического моделирования широкого круга задач
механики сплошной среды согласно предложенной А.А.Самарским триаде
«модель-алгоритм-программа» [1], можно выделить следующие основные
этапы:
4 о формирование математической модели изучаемого
явления (газодинамической задачи, в данном случае); о выбор разностной схемы, допускающей построение
эффективного параллельного алгоритма; о построение параллельной программы и выполнение расчёта.
Среди наиболее подходящих для проведения вычислительных «
экспериментов на многопроцессорных системах выделяются кинетически-согласованные разностные схемы.
Кинетически-согласованные разностные схемы (КСРС) были предложены в Институте математического моделирования РАН в первой половине 80-х годов Б.Н. Четверушкиным. Практика их успешного применения в численном решении различных задач газовой динамики, включая моделирование неустановившихся течений, турбулентных
* потоков, задач аэроакустики и аэроупругости, течений химически
реагирующих газов, насчитывает таким образом более пятнадцати лет [14].
С конца 80-х - начала 90-х годов значительное число практических
»,
* расчетов проводилось с использованием многопроцессорных
вычислительных систем.
В основе построения КСРС лежит нетрадиционный подход в вычислительной газовой динамике, опирающийся на использование тесной связи между кинетическим и макроскопическим описанием сплошной
>
среды. Отметим, что аналогичные схемы, примерно в то же время,
рассматривались и за рубежом, где их часто еще называют
Больцмановскими. Эти схемы подробно рассмотрены в обзоре [15].
Теоретической основой для описания течений реального газа являются уравнения Навье-Стокса. Первоначально эти уравнения были получены феноменологическим путем, опираясь на известный экспериментальный закон о пропорциональности силы трения между движущимися слоями газа производной скорости. Впоследствии они были получены при помощи асимптотического разложения Чепмена-Энскога
решения кинетического уравнения Больцмана для одно-частичной функции распределения. Однако обычно органическая связь между кинетическим и макроскопическим описанием среды не используется при построении вычислительных алгоритмов газовой динамики.
В отличие от других расчетных схем, которые являются теми или иными способами дискретизации систем дифференциальных уравнений
u Эйлера или Навье-Стокса, кинетически-согласованные схемы при своем
выводе непосредственно опираются на дискретную кинетическую модель, описывающую поведение одно-частичной функции распределения. Такой моделью является ступенчато-постоянная (по пространству) функция распределения, плодотворность использования которой была показана в монографии А.А. Власова [16]. Таким образом, уже на алгоритмическом
*/ уровне происходит согласование кинетического и газодинамического
описания сплошной среды.
Главное физическое предположение, заложенное в основу получения КСРС, состоит в следующем: функция распределения постоянна
(в момент времени tk) на ячейке расчетной сетки и равна локально-максвелловской функции распределения:
(2RT,ty (2RT')'
тт а к+\ к
При этом предполагается, что в течение времени At = t -t имеет место бесстолкновительный разлет молекул, а в момент tk+l происходит их мгновенная максвеллизация.
Основное балансное соотношение для функции распределения на произвольной пространственной сетке может быть получено интегро-интерполяционным методом в форме, аналогичной схемам с направленными разностями:
4+1 fk і х-к , rk
/'K+l _ rk і
і JIM , A
I J^n^^k^.J.^ ^lfU _ fiMya
At V,rC " 2 2V,yS)
Суммирование здесь происходит по всему-м ячейкам, соседним с /-
й, а интегрирование - по общей грани /-й и/-й ячеек (Vs— объем /-й ячейки).
Интегрируя полученные соотношения с сумматорными
инвариантами 1, , — по скоростям молекул, получим систему
разностных уравнений для газодинамических параметров, полный вид которой будет приведен ниже. При этом образуются диффузионные члены, играющие роль искусственной диссипации. Однако, в отличие от классической искусственной вязкости фон Неймана, их вид согласован с диссипативными членами в разностном аналоге кинетического уравнения. Это и послужило поводом дать схемам название кинетически-согласованных. С вычислительной точки зрения дополнительные диссипативные члены можно трактовать как эффективные регуляризаторы, позволяющие развиваться естественным неустойчивостям и сглаживающие неустойчивости чисто счетного характера.
+ Кинетически-согласованный подход обеспечивает естественное
обобщение разностной схемы для линейного уравнения переноса на систему нелинейных газодинамических уравнений. Аппроксимацию уравнения переноса схемой с направленными разностями можно интерпретировать как физическую модель переноса кусочно-постоянной функции распределения. Получающиеся после осреднения разностные
макроуравнения в дифференциальном приближении можно рассматривать
как обобщение уравнений Эйлера и Навье-Стокса. Подробное исследование свойств КСРС и их обоснование с физической точки зрения можно найти, например, в работах [18,19,20]. Всего же этой теме посвящено более ста публикаций.
Выделим теперь те свойства КСРС, которые наиболее важны для проведения параллельных вычислений.
1. Одними из наиболее сложных для моделирования являются
течения, характеризующиеся взаимодействием вязкой и невязкой частей
потока. Нередко расчет в каждой из этих частей ведется по своим
собственным алгоритмам. Однако с помощью КСРС расчет в обеих частях
можно вести по единой схеме. В невязкой - идеальной - части потока
диссипативные члены играют роль искусственной вязкости при решении »
уравнений Эйлера, в вязкой части потока эти члены оказываются малыми
и по сравнению с членами естественной диссипации. Однородность
расчетного алгоритма чрезвычайно удобна при его распараллеливании.
2. Наиболее простыми в реализации с точки зрения минимизации
обменов данными между процессорами являются явные схемы. В них
значения функции на новом слое по времени целиком определяются через
ее значения на предыдущем слое, с помощью простой вычислительной
* процедуры, использующей малое число узлов сетки. Серьезным
препятствием, сводящим на нет указанное достоинство, является, как правило, сильное ограничение сверху на допустимый шаг по времени, вытекающее из условия устойчивости расчета. В КСРС структура
+ дополнительных диссипативных членов такова, что при моделировании
многих типов вязких течений позволяет вести счет с условием устойчивости типа Куранта т < h, тогда как обычно явные схемы для задач данного класса требуют гораздо более жесткого ограничения z
* Стоит отметить и логическую простоту алгоритмов, построенных на
основе кинетически-согласованных схем. Начиная с 1988 года они используются для проведения расчетов на различных многопроцессорных системах, при этом соответствующие программы легко адаптируются и используются на новых типах вычислительных систем [21,6,22,23].
Распределенные вычислительные системы. Сегодня в разных организациях сосредоточено много вычислительных ресурсов, которые далеко не всегда используются полноценно. Эти компьютеры могут находиться в разных местах, выполнять разные приложения, использовать разные средства хранения информации и системы доступа. С другой стороны, есть ряд актуальных задач глобального масштаба, для решения которых требуются разнообразные компьютерные ресурсы и большие вычислительные мощности, причём алгоритмы решения этих задач допускает эффективное распараллеливание. Во многом именно по этой
t* причине появилась технология 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%.
Интернет
Global Grid
Рисунок 1 Категории Grid-сетей.
Sun Microsystems различает три основные категории Grid-сетей
(Рисунок 1):
относительно простая вычислительная сеть, предоставляющая ресурсы пользователям одной рабочей группы, одного департамента, одного проекта (Cluster Grid);
вычислительная сеть корпоративного уровня, охватывающая несколько групп, работающих над различными проектами (Enterprise Grid);
сеть, в которой участвуют несколько независимых организаций, предоставляющих друг другу свои ресурсы. Эти организации установили определенные правила обмена ресурсами, определенные протоколы взаимодействия (Global Grid).
Как отмечалось ранее, время взаимодействия между узлами системы Grid Computing измеряется миллисекундами и секундами. Такие системы не предназначены для решения параллельных задач и проведение эффективного численного эксперимента моделирования задач газовой динамики в рамках технологии Grid представляется проблематичным. Тем
не менее, привлечение распределенных и территориально удаленных систем для анализа и обработки результатов расчётов может оказаться вполне выполнимым. Ситуации, когда необходимо прибегать к помощи Grid систем возникают тогда, когда многопроцессорная система на которой производился численный расчёт не доступна, а ресурсов каждой из имеющихся многопроцессорных машин в отдельности не достаточно для обработки данных.
Параллельная реализация алгоритма
Сейчас сетевые файловые системы называют «распределенными». Этот термин отражает тот факт, что многие из этих файловых систем имеют гораздо больше возможностей, чем простая передача данных по сети. Носители данных, связанные с этими файловыми системами, не обязательно могут быть расположены на одном компьютере - они могут быть распределены между многими компьютерами.
Распределенные файловые системы OpenAFS и Coda имеют собственные механизмы управления разделами, которые упрощают возможности хранения общедоступной информации. Они так же поддерживают дублирование - способность делать копии разделов и сохранять их на других файловых серверах. Если один файловый сервер становится недоступным, то все равно к данным, хранящимся на его ра:делах, можно получить доступ с помощью имеющихся резервных копий этих разделов.
Распределенные системы способны упростить многие из стандартных административных задач. В сетевой среде пользователи должны иметь возможность входа в сеть под своим именем с любого компьютера. Это значит, что механизм входа в сеть (или аутентификации) тоже должен быть сетевым. Поэтому в среде распределенной файловой системы файлы групп и паролей, расположенные на индивидуальных компьютерах, вторичны по отношению к сетевым механизмам аутентификации (таким, как Kerberos или NIS, которые предоставляют пользователям возможность работать на любом компьютере). Но стандартные локальные механизмы проверки пароля все же должны существовать, чтобы администраторы могли выполнять на локальных компьютерах необходимые задачи.
Сохранение общих данных на централизованных файловых серверах (а не на индивидуальных компьютерах) упрощает такие административные задачи, как резервирование и восстановление файлов и каталогов. Это так же централизует такие стандартные административные задачи, как контроль за использованием файловой системы, и представляет новые возможности управления хранением данных - например, балансирование загрузки. Распределенные файловые системы типа OpenAFS и Coda обеспечивают встроенные логические системы управления разделами, которые дают администраторам возможность переместить интенсивно используемые данные на более мощные или менее используемые компьютеры. Если распределенная файловая система поддерживает дублирование, копии интенсивно используемых данных могут распределяться между многими файловыми серверами. Это может уменьшить нагрузку на сеть, и облегчить работу серверов. Распределенные файловые системы используют логические разделы вместо физических дисковых разделов, и это позволяет легко добавить в сеть новую свободную память прямо во время работы. (Для добавления нового диска в локальный компьютер пришлось бы потратить некоторое время).
Использование распределенных файловых систем дает системным администраторам не только новые возможности, но и новые проблемы, в частности увеличивает зависимость компьютерных систем от сети. Эта зависимость от данных, к которым люди могут обращаться только по сети, вызывает некоторые интересные проблемы для компьютеров, которые нуждаются в доступе к данным даже тогда, когда доступ к сети невозможен. Это называется «автономная работа» - система должна функционировать, если ресурсы, которые обычно присутствуют в сети (например, пользовательские данные), по каким-то причинам не доступны. В первую очередь это относится к модифицируемым данным, которые должны быть сохранены. Распределенные файловые системы Coda и InterMezzo, доступные в настоящее время для Linux, обеспечивают интегрированную поддержку автономной работы. Так же сейчас ведется работа над обеспечением этой возможности для файловых систем NFS. Coda и InterMezzo уже поддерживаются ядром Linux - поддержка Intermezzo встроена в ядро, начиная с версии 2.4.5, a Coda вообще была интегрирована в ядро 2.4 с самого начала.
Таким образом, пользователь не может быть полностью уверен, что действующая на данном кластере файловая система сохранит свои свойства, и такими же свойствами будут файловые системы других суперкомпьютеров. Использование распределённой файловой системы наиболее простой и, при использовании современного сетевого оборудования, достаточно эффективный способ параллельной работы с одним блоком данных на большом числе вычислительных модулей, но такие системы не всегда доступны и эффективность таких систем не всегда соответствует тем запросам, которые предъявляет экспериментатор к расчёту.
Работа с большими сетками В случае проведения численного эксперимента с использованием нерегулярных сеток на многопроцессорных вычислительных системах, возникает необходимость компактного разбиения сеточных данных по вычислительным модулям. Для обеспечения рациональной декомпозиции нерегулярных сеток, определяющей распределение данных по процессорам, и для организации эффективного чтения данных при проведении расчётов и визуализации, используется разработанный в ИММ РАН алгоритм двухуровневой обработки больших сеток [6,31,99,100,101]. Этот алгоритм предполагает предварительное разбиение всей сетки на большое число микродоменов - компактных фрагментов, содержащих малое, относительно общего количество узлов сетки, число узлов. Кроме того, в представлении сетки, при таком подходе, участвует макрограф, каждая вершина которого соответствует одному микродемену, а ребра наличию ребер, соединяющих вершины, принадлежащие соответствующим микродоменам.
Сжатие массивов чисел с плавающей запятой
Интерактивность разработанного пакета предполагаетминимизацию времени визуализации, что, к сожалению, не достигается само собой в силу большого объёма данных, а требует дополнительных усилий.
С одной стороны, компрессия данных при записи может существенно сократить хранимый объём и таким образом уменьшить объём передаваемых данных. С другой стороны, на компрессию и декомпрессию требуется определённое машинное время, которое в некоторых ситуациях может превышать выигрыш во времени, связанный с уменьшением объема данных.
В разработанной программе широко применялось сжатие данных по алгоритму LZW перед записью на жёсткий диск. Алгоритм LZW [41,48] представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку "Объект TsortedCollection порожден от TCollection.". Анализируя эту строку мы можем видеть, что слово "Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничиться длинной кодируемой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80 бит заменяется на 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле , то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана ( Huffman ) , которому требуется два прохода.
Для сжатия по алгоритму LZW использовалась библиотека zlib, входящая в состав большинства Unix систем и портированна на значительное число платформ.
Поскольку, числа с плавающей запятой сжимаются вообще очень плохо, поэтому, перед сжатием по алгоритму LZW необходимо выполнить некоторые предварительные действия. Здесь был применён следующий подход: массивы чисел float пересортировываются по старшинству байт (Рисунок 18), т.е. младшие байты помещаются в один массив, следующие по старшинству в другой и так далее. Полученные таким образом массивы уже поддаются сжатию с большим коэффициентом.
Однако, сжатие без потерь не решает полностью проблему большого объёма данных, так как в результате сжатия результат имеет размер пропорциональный размеру исходных данных. Такое положение вещей, даже при хорошем коэффициенте сжатия, является не очень удобным, поскольку персональный компьютер пользователя может непосредственно визуализировать очень ограниченный объём данных.
Для решения этой проблемы применялись алгоритмы сжатия с потерями, мало влияющими на субъективное восприятие результирующего изображения. Основные критерии, по которым выбирались алгоритмы, были следующими: новая изоповерхность, полученная в результате применения алгоритма сжатия, должна аппроксимировать исходную изоповерхность с заранее заданной точностью и объём данных, описывающих результирующую изоповерхность, не должен превышать заранее заданного значения. Сжатие триангулированных поверхностей Применяемые алгоритмы сжатия триангулированных поверхностей разделяются на методы алгоритмического сжатия, алгоритмы сжатия редукцией поверхности и алгоритмы сжатия синтезом. Алгоритмическое сжатие Алгоритмические методы сжатия не позволяют аппроксимировать обрабатываемую изоповерхность с гарантированной точностью. Основное преимущество заключается в том, что они обеспечивают сжатие до заданного размера. Объём результирующих данных удовлетворяет критерию по объёму, что жизненно необходимо при работе системы распределённой визуализации в интерактивном режиме, где критичны объёмы передаваемых по сети данных в силу ограниченно пропускной способности коммуникационных сетей. Суть алгоритмов алгоритмического сжатия состоит в разделении точек изоповерхности на внутренние (соседниние к которым образует простой цикл) и внешние. Удаляя все внутренние точки и часть внешних точек получим ряд опорных точек аппроксимирующей поверхности. Далее строим триангуляцию внутренней области, последовательно добавляя вершины внутрь области. Помимо этого, небольшая модификация в реализации алгоритма, позволяет значительно сократить объём передаваемой между клиентской и серверной частями системы визуализации за счёт отсутствия необходимости передачи информации о топологии аппроксимирующей поверхности, если при определении координат очередной вершины использовать только информацию о координатах (x,y,z) опорных точек и уже добавленных вершин, где г- координата пересечения нормали к плоскости (х,у) с исходной изоповерхностью. Для восстановления поверхности необходимо передать на клиентскую часть только информацию (x,y,z) об опорных точках и значения z в добавленных точках. Нет необходимости передавать координаты (х,у) добавленных точек и топологию связей между ними, поскольку эту информацию можно полностью определить при восстановлении поверхности, просто повторив действия, выполненные при ее сжатии.
Структура системы распределенной визуализации
Разделение системы на серверную и клиентскую компоненты предоставляет ряд существенных преимуществ. Во-первых, при таком подходе нет необходимости передавать все изучаемые данные с хранящего результаты расчетов файлового сервера на выполняющий визуализацию компьютер рабочего места пользователя. Во-вторых, подход позволяет использовать для обработки данных тот же многопроцессорный комплекс (или аналогичный ему по мощности), на котором выполнялось моделирование, что гарантирует наличие требуемого количества оперативной памяти и вычислительных ресурсов. В-третьих, так как клиентская часть выполняется на персональном компьютере пользователя, для улучшения наглядности изображения становятся доступными все те средства мультимедиа, которыми сегодня оснащено большинство ПК.
Фактически система визуализации (рис. 21) состоит из трех компонент: - клиентская часть - компонента, выполняющаяся на персональном компьютере пользователя, обеспечивающая отображение данных на мониторе пользователя и предоставляющая пользователю интерфейс управления; - серверная коммуникационная часть - компонента, выполняющая роль посредника между клиентской и серверной обрабатывающей частями, выполняется на управляющем узле МВС (Многопроцессорная Вычислительная Система); - серверная обрабатывающая часть - компонента, выполняющая непосредственную обработку трехмерных полей данных, выполняется на рабочих узлах многопроцессорной системы.
В общем случае, персональный компьютер территориально удален от суперкомпьютера, и не имеет непосредственного доступа к файловой системе, хранящей результаты моделирования. В связи с этим возникает проблема указания имени файла, или группы файлов содержащих интересующие трехмерные данные. Стандартные диалоговые средства ориентированны на обработку локальных файловых систем и в данном случае неприменимы, а разработка специализированных средств связана с рядом обсуждаемых далее ограничений.
Предполагается, что пользователю известно положение файлов на этапе проведения расчетов. Тем не менее, на этапе выполнения визуализации, требуемые файлы могут и не присутствовать по известному пути, могут быть доступным не на всех вычислительных узлах, участвующих в визуализации. Связано такое положение с тем, что, во-первых, для визуализации может использоваться иной, нежели для расчетов, многопроцессорный комплекс, имеющий, тем не менее, доступ к тому же, хранящему данные расчетов, файловому серверу. Во-вторых, для визуализации может быть выделен иной набор процессоров, нежели для расчета. Так как система оперирует в том числе и распределёнными файлами, возможна ситуация когда доступны не все части распределённого файла. Учет указанных ситуаций требует разработки достаточно развитой компоненты диалогового управления распределенными файлами. В рамках настоящей работы, реализовано упрощенное управление: пользователь имеет возможность вводить имена файлов, при этом предполагается, что файлы доступны по указанным пользователем путям со всех узлов, серверной части системы визуализации. Таким образом, пользователь вводит с помощью интерфейса клиентской части имя интересующего его файла, затем клиентский процесс, выполняющийся локально, устанавливает соединение с коммуникационной частью сервера визуализации, выполняющимся именно там, где расположены файлы данные. Поскольку серверная и клиентская части выполняются на существенно разных компьютерах, под управлением различных операционных систем, для передачи информации между ними выбран универсальный протокол на основе tcp/ip. Далее сервер визуализации считывает параметры запрошенного файла, и передает их назад, на клиентскую часть. Среди этих параметров отметим количество и имена хранящихся в файле функций, диапазоны изменения их значении, размеры расчётного поля. Далее пользователь указывает имя интересующей функции, одну или несколько величин значения функции, для которых будут сформированы изоповерхности и указывает геометрические границы интересующей области пространства. Указанные данные передаются на коммуникационную часть для формирования изоповерхностей. Последовательный алгоритм формирования изоповерхностей рассмотрен ранее, а параллельные алгоритмы, подробно обсуждаются в следующем разделе. Результат сжатия сформированных изоповерхностей передается и отображается на клиентской части с помощью современных мультимедийных средств.
Следует подчеркнуть, что отображается именно трехмерный объект, который можно, вращая, изучать с произвольной пространственной точки зрения, без обращения к серверу визуализации, что значительно повышает наглядность представления данных и облегчает их восприятие.
Параллельный алгоритм построения изоповерхности Запрос на визуализацию интересующей функции поступает с клиентской части на коммуникационную и далее на обрабатывающую. Коммуникационный сервер, в соответствии с принципом геометрического параллелизма, определяет декомпозицию трехмерной сетки, на которой задана функция, на части по числу обрабатывающих процессоров, после чего последние считывают каждый свой фрагмент данных. Далее на обрабатывающих процессорах формируется запрошенная пользователем изоповерхность и выполняется ее сжатие.
Серверная часть является параллельной программой, написанной при помощи библиотеки MPI. В рамках приятого подхода, распараллеливание производиться достаточно эффективно на основе метода геометрического параллелизма, так как в процессе построения фрагментов изоповерхности в пределах каждой ячейки не нужна дополнительная информация о соседних или каких-то других ячейках. Этап сжатия изоповерхности так же носит локальный характер, и, при обработке некоторой части поверхности не требует информации о геометрически удаленных фрагментах той же поверхности, при условии, что вся изоповерхность предварительно разбита на компактные части. Таким образом, при многопроцессорной обработке нет необходимости передавать данные между процессорами, обрабатывающими разные части сетки.
Передача рабочим узлам изучаемых трехмерных полей сводится только к передаче информации о местонахождении файла, так как непосредственное чтение выполняется каждым из обрабатывающих узлов сервера визуализации самостоятельно. Данный подход правомерен, как при обработке распределенных файлов, хранящихся на обрабатывающих узлах, так и при чтении файлов, хранящихся на файловых серверах.
Использованные технические и программные ресурсы
На сегодняшний день, использование определённых стандартных технологий, в первую очередь таких как OpenGL и DirectX позволяет при наличии соответствующего мультимедийного оборудования получать стерео изображение практически любой (созданной с помощью данной технологии ) трёхмерной сцены.
В данной работе, на начальном этапе разработки для непосредственной визуализации широко применялся java инструмент WireFrame (позднее переписанный на Win32 API), позволяющий просматривать файлы определённого формата с конструкциями 3-х мерных объектов. Позднее в клиентскую часть была интегрирована поддержка технологий OpenGL и DirectX.
Использование DirectX позволило уже на этапе разработки, не вникая в методы построения стерео изображения, получать объёмное изображение исследуемых объектов.
Кроме поддержки стерео устройств реализована поддержка 3-х мерного манипулятора, называемого трекер. Это устройство, подключаемое к последовательному порту компьютера, способно сообщать клиентскому приложению свои углы поворота в 3-х мерном пространстве (т.н. 3DOF - degrees of freedom). При помощи трекера можно вращать и рассматривать исследуемый 3-х мерный объект на экране компьютера, вращая в нужную сторону устройство находящееся в руках пользователя.
Интерфейс позволяет обрабатывать несколько файлов с данными, заданными по маске. Значения остальных параметров остаются одинаковыми для всех файлов удовлетворяющих маске. Обработка происходит последовательно, с подстановкой в маску параметров, начиная с «First Index» и заканчивая «Last Index» с шагом «D Index», и используется для анимированного показа динамики изменения соответствующих функций.
Например, следующий запрос: Filemask= iter_main_%d.bjn , FirstIndex=T, Lastlndex= 10 , Dindex= 2 , приведет к последовательному отображению данных, хранящихся в пяти файлах с именами iter_main_l.bjn, iter_main_3.bjn, iter_main_5.bjn, iter_main_7.bjn, iter_main_9.bjn.
Следующая группа параметров отображает диапазон изменения значений выбранной функции ( «Value:» ) и позволяет выбирать число исследуемых изоповерхностей и значения исследуемой функции на них.
Нижняя группа основного окна предназначена для подробного изучения выбранных пользователем областей. Изначально (а так же при выборе нового файла) поля заполнены значениями, определяющими всю расчётную область. Далее пользователь может вводить произвольные значения для исследования только интересующего его фрагмента области.
Альтернативой такому просмотру является создание некого 3-х мерного курсора. Однако возникает вопрос: как его перемещать и как фиксировать его положение? Другой способ - последовательно отмечать на каждой из трёх осей интересующие нас интервалы, одновременно выделяя части изоповерхности, попавшие в выделение (например, другим цветом).
Клиентская часть системы распределённой визуализации разработана таким образом, чтобы обращение к функциям работы с графикой, происходило через унифицированный, API-независимый интерфейс. Все функции работы с графикой вынесены в отдельную библиотеку. Выделение графического модуля выполнено таким образом, что замена этой библиотеки подпрограмм на другую, поддерживающую требуемый интерфейс взаимодействия, возможна без перекомпиляции всей программы. Использование технологии DirectX позволяет максимально эффективно использовать при визуализации имеющееся на данном персональном компьютере мультимедийное оборудование и значительно повышает качество результирующего изображения.
Разработанная система обрабатывает трёхмерные скалярные данные заданные как на структурированных кубических сетках, так и на неструктурированных тетраэдрических сетках. Пакет визуализации успешно обрабатывает как тестовые данные, так и результаты реальных численных экспериментов, позволяя анализировать данных в тех случаях, когда никакие другие средства визуализации уже не работают. Проведено сравнение комплекса распределённой визуализации (IMM RemoteView) с системой TecPlot, которая фактически является стандартом для визуализации научных данных на персональном компьютере. Она обладает широкими функциональными возможностями, но объём визуализируемых с её помощью данных ограничен. Далее, все результаты сравнения приводятся для расчёта на сетке 148 257 узлов (51x51x57). Число Маха на срезе сопла Ма=1.15, число Рейнольдса, рассчитанное по параметрам на срезе сопла, Rerf =33000, степень нерасчётности п = pjp = 1.3.
