Сложность решаемых методами математического моделирования научных и технологических задач, увеличение требований к точности их решения приводит к неуклонному росту объемов обрабатываемых в ходе вычислительных экспериментов данных. Проведение математических расчётов [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,40 394 042,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.
ТМи-Уу? i-l.v-l.
Данная мера, по сути, аналогична среднеквадратичному отклонению, однако пользоваться её несколько удобнее за счёт логарифмического масштаба шкалы. Ей присущи те же недостатки, что и среднеквадратичному отклонению.
Лучше всего потери качества изображений оценивают наши глаза. Отличным считается сжатие, при котором невозможно на глаз различить первоначальное и распакованное изображения. Хорошим — когда сказать, какое из изображений подверглось сжатию, можно только сравнивая две находящиеся рядом картинки. При дальнейшем увеличении степени сжатия, как правило, становятся заметны побочные эффекты, характерные для данного алгоритма. На практике, даже при отличном сохранении качества, в изображение могут быть внесены регулярные специфические изменения. Поэтому алгоритмы сжатия с потерями не рекомендуется использовать при сжатии изображений, которые в дальнейшем предполагается либо печатать с высоким качеством, либо обрабатывать программами распознавания образов. Неприятные эффекты с такими изображениями могут возникать даже при простом масштабировании изображения.
Алгоритм JPEG.
Алгоритм JPEG — один из новых и достаточно мощных алгоритмов сжатия. Он практически является стандартом де-факто для полноцветных изображений. Оперирует алгоритм областями 8×8 растровых точек, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой области в двойной ряд по косинусам, значимыми оказываются только первые коэффициенты. Таким образом, сжатие в 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. Выполнено моделирование ряда режимов распространения горячей затопленной струи. На примере изучения полученных результатов показано, что разработанный комплекс визуализации позволяет эффективно выполнять интерактивный анализ результатов вычислительных экспериментов в режиме удаленного доступа к многопроцессорным вычислительным системам центров коллективного пользования и метакомпьютерам.
