Содержание к диссертации
Введение
Глава 1. Статическая балансировка загрузки 19
Постановка задачи 20
Критерии декомпозиции графов 22
Иерархический алгоритм декомпозиции графа 24
Огрубление графа 24
Первичное разбиение графа 26
Спектральная бисекция 27
Восстановление графа 29
Дополнительные критерии декомпозиции 34
Инкрементный алгоритм декомпозиции графа 37
Иерархическое хранение больших сеток 42
Измельчение пирамидальных сеток 43
Глава 2. Динамическая балансировка загрузки 46
Постановка задачи 54
Алгоритм серверного параллелизма 55
Структура параллельной программы 57
Управляющий алгоритм балансировки загрузки 58
Основной цикл взаимодействия управляющих процессов 63
Двухуровневый алгоритм серверного параллелизма 65
Глава 3. Распределенная визуализация 72
Постановка задачи 72
Архитектура системы визуализации 75
Этапы визуализации 77
Серверная и клиентская части системы визуализации 78
Визуализация трехмерных скалярных данных 80
Методы преобразования решеток в пирамидальные сетки 83
Разбиение ячейки на 24 пирамиды 83
Разбиение 8-ми ячеек на 24 пирамиды 85
Разбиение ячейки на 5 пирамид 86
Симметричное разбиение смежных ячеек 87
Разбиение ячейки на 6 пирамид 87
Аппроксимация изоповерхности 88
Виды данных описывающих триангуляцию 92
Точность аппроксимации 95
Вычисление абсолютной ошибки 98
Сохранение топологических особенностей 99
Методы построения аппроксимирующей триангуляции 99
Метод кластеризации 99
Метод детализации 103
Метод синтеза 107
Метод редукции 113
Параллельные алгоритмы построения аппроксимирующих триангуляции 116
Результаты тестирования 117
Зависимость времени обработки и коэффициента сжатия методом редукции от точности аппроксимации 117
Зависимость времени и коэффициента сжатия от гладкости изоповерхности 119
Соотношение времени чтения данных и времени их обработки 123
Сравнение метода синтеза и метода редукции 124
Зависимость времени расчета и коэффициента сжатия от числа используемых процессоров 125
GRID технологий визуализации данных 127
Интерфейс системы визуализации 129
Глава 4 Среда моделирования сеточных задач на распределенных вычислительных системах 135
Управление вычислительным экспериментом 135
Моделирование обтекания трехмерных тел сложной формы 139
Моделирование обтекания ступеньки 141
Моделирование обтекания сферы 144
Моделирование обтекания летательных аппаратов 147
Распределенное хранение сеточных данных 154
Моделирование задач горения 157
Моделирование распространения горячей газовой струи 173
Моделирование добычи углеводородов с помощью методов перколяции 174
Параллельный алгоритм генерации последовательностей псевдослучайных чисел
191
Заключение 201
Список литературы
- Иерархический алгоритм декомпозиции графа
- Структура параллельной программы
- Серверная и клиентская части системы визуализации
- Моделирование обтекания трехмерных тел сложной формы
Введение к работе
Многопроцессорные системы терафлопной производительности, объединяющие в настоящее время от сотен до сотен тысяч процессоров, позволяют выполнять за короткое время большие объемы вычислений. Их использование допускает проведение вычислительных экспериментов, направленных на решение с высокой точностью естественнонаучных и технологических задач. Большая часть современных суперкомпьютеров востребована не в полной мере. Косвенным свидетельством тому служит статистика использования 500 крупнейших многопроцессорных систем мира, согласно которой область применения более половины из них не конкретизирована.
Накопленный опыт применения многопроцессорных систем ориентирован, в первую очередь, на параллельные системы средней производительности, содержащие относительно небольшое число процессоров. При переходе к вычислительным системам, количество процессоров в которых исчисляется сотнями и более, требуется создание адекватных средств обработки больших объемов данных. Необходимы параллельные алгоритмы и средства, поддерживающие всю цепочку действий, требуемых для численного моделирования задач на подробных сетках. В том числе: методы формирования геометрических моделей высокого качества, генераторы поверхностных и пространственных сеток, средства декомпозиции сеток, библиотеки распределенного ввода-вывода, алгоритмы и библиотеки балансировки загрузки процессоров, средства визуализации результатов крупномасштабных экспериментов и многое другое. Разработка методов, обеспечивающих поддержку любого из перечисленных этапов, представляет собой серьёзную научную и технологическую проблему. Не менее актуальной и сложной является проблема согласования и объединения методов в рамках единой системы, позволяющей специалисту прикладной области воспользоваться ими для выполнения вычислительного эксперимента.
Полноценная вычислительная среда может быть создана только в условиях тесного взаимодействия специалистов в области разработки параллельных приложений и специалистов в области решения прикладных задач, поскольку создание адекватных средств невозможно без глубокого понимания проблем, присущих основным этапам вычислительного эксперимента, выполняемого на системах массового параллелизма.
Значительный качественный разрыв между производительностью компьютеров рабочего места пользователя и распределенного вычислительного пространства, обуславливающий возникновение многих проблем практического использования многопроцессорных систем, будет продолжать возрастать. Подтверждением тому служит активное развитие GRID технологий и возможностей метакомпьютинга, приводящее к интенсивному росту объединенных вычислительных мощностей при относительно низкой стоимости их объединения. В настоящее время нет доступных пакетов, обеспечивающих использование терафлопных вычислительных систем для решения задач механики сплошной среды. Существующие пакеты ориентированы на использование последовательных систем, например FlowVi-sion [1,2,3], либо кластерных систем с ограниченным числом процессоров, например пакет GDT [4,5], или один из ведущих пакетов численного моделирования двух и трехмерных задач газовой динамики, Fluent [6]. Подобная ситуация складывается и в ряде других областях знаний. Создание пакетов, снимающих с прикладного программиста вопросы, не относящиеся непосредственно к предметной области, является приоритетной задачей, поскольку целесообразность дальнейшего развития самих вычислительных систем непосредственно зависит от наличия инструментария, обеспечивающего возможность их эффективного применения.
Актуальность диссертационной работы определяется необходимостью создания средств, обеспечивающих эффективное решение задач механики сплошной среды методами математического моделирования на вычислительных системах терафлопного диапазона.
Цель работы состоит в создании алгоритмов и компонентов вычислительной среды, обеспечивающих возможность эффективного решения задач механики сплошной среды методами математического моделирования на многопроцессорных вычислительных системах терафлопного диапазона.
В диссертации представлены новые параллельные алгоритмы рациональной декомпозиции многомерных регулярных и неструктурированных сеток, динамической балансировки загрузки, сжатия триангулированных поверхностей и согласованного формирования на множестве процессоров фрагментов последовательностей псевдослучайных чисел большой длины. Предложена модель и создана система распределенной визуализации трехмерных результатов вычислительных экспериментов. Система визуализации предназначена для изучения данных, объем которых не оставляет возможности их анализа с помощью последовательных программ, и может быть использована для интерактивного изучения сеточных данных различной природы. Создана вычислительная среда, обеспечивающая согласованное применение разработанных методов при проведении вычислительных экспериментов с использованием сеток содержащих 10 и более узлов на системах терафлопного диапазона и метакомпьютерах. С ее помощью выполнено моделирование задач обтекания тел сложной формы, горения и добычи углеводородов на вычислительных системах с большим числом процессоров.
В первой главе рассматриваются методы рациональной декомпозиции графов, описывающих регулярные и нерегулярные сетки. Обсуждается ряд критериев декомпозиции, рассматривается метод иерархической обработки и хранения больших сеток.
Эффективным методом построения параллельных вычислительных алгоритмов моделирования задач механики сплошной среды является метод геометрического параллелизма. Основная проблема при его использовании связана с необходимостью решения задачи статической балансировки загрузки - выбора такой декомпозиции расчетной сетки, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные возможным дублированием вычислений и необходимостью передачи данных между процессорами малы. Задача сводится к разбиению вершин некоторого графа на заданное число классов эквивалентности - доменов. Задача рационального разбиения графов, наиболее близкой к которой можно считать задачу о разрезании графов [7], принадлежит классу yVP-полных [8], что обуславливает необходимость использования для ее решения эвристических алгоритмов.
К простым, но малоэффективным алгоритмам относятся методы рекурсивного координатного [10,11] и инерциального [9] разбиения. Заслуживают упоминания алгоритмы рациональной декомпозиции сеток, основанные на методах спектрального разбиения, алгоритмах Kernighan-Lin (KL) и Fiduccia-Mattheyses (FM) [62, 67]. Наиболее эффективны иерархические методы рационального разбиения графов [61,78,79]. Доступен ряд пакетов декомпозиции графов, среди которых выделяются последовательные и параллельные версии пакетов СНАСО [12,17] и PARMETIS [13], пакеты PARTY [14], JOSTLE [15], SCOTCH [16], Zolman [189].
Для ряда задач актуальны дополнительные критерии декомпозиции. Минимизация максимальной степени домена [22] позволяет снизить число актов обмена данными на каждом шагу по времени, тем самым увеличить эффективность расчетов. Обеспечение связности каждого из подграфов, соответствующих доменам позволяет в ряде случаев упростить вычислительные алгоритмы [21], повысить коэффициенты сжатия сеточных данных.
Иерархические алгоритмы, положенные в основу перечисленных выше пакетов декомпозиции графов, не контролируют связность и максимальную степень доменов. В связи с этим, актуальна разработка алгоритмов декомпозиции, отвечающих этим критериям. В качестве альтернативы разработан инкрементный метод рационального разбиения графов, наиболее близким аналогом которого, является пузырьковый алгоритм [18].
В заключении главы рассмотрен метод иерархической обработки и хранения больших сеток. Его применение позволяет значительно снизить время выполнения декомпозиции и ввода-вывода сеток, содержащих 108 и более узлов на этапах численного моделирования и анализа результатов, за счет переноса основных операций по декомпозиции сетки на выполняемый однократно подготовительный этап.
Вторая глава посвящена вопросам динамической балансировки загрузки при моделировании на МВС химически реагирующих многокомпонентных течений. Рассматривается разработанный в соавторстве с М.А.Корнилиной алгоритм серверного параллелизма, обеспечивающий децентрализованное перераспределение элементарных заданий, размещенных на множестве процессорных узлов.
Одной из глобальных экологических проблем современности является рост концентрации метана в атмосфере, значительным источником эмиссии которого являются добыча, переработка и транспортировка природного газа и нефти. При прорыве газа из скважин месторождений для уменьшения экологических последствий газовый фонтан поджигают. Однако горение метана само по себе наносит значительный вред, поскольку среди продуктов горения присутствуют высокотоксичные оксиды азота.
Используемая для оценки экологических последствий модель химически реагирующих течений предполагает совместное решение уравнений газовой динамики и химической кинетики, описывающих реакции с участием 19 веществ.
Согласно методу суммарной аппроксимации [138] поочередно рассматриваются газодинамические процессы, и процессы, описывающие химическую кинетику горения. Газодинамические течения описываются кинетически согласованными разностными схемами, уравнения химической кинетики интегрируются при помощи L-устойчивых методов решения жестких систем обыкновенных дифференциальных уравнений.
Общее время расчета уравнений блока кинетики горения многократно превышает время расчета уравнений блока газовой динамики, причем распределение вычислительной загрузки процессоров на этапе расчета кинетики горения отличается сильной неоднородностью из-за большой разницы времён необходимых для расчета областей интенсивного протекания химические реакции и областей, расположенных на удалении от зоны горения. В связи с этим известных алгоритмов статической (геометрический параллелизм, он же «domain decomposition») и динамической (коллективное решение, он же «processor farm» [143,111], диффузная балансировка [19]) балансировки загрузки не достаточно для организации эффективного вычислительного процесса. Так же неэффективен для задач с высокой динамикой миграции по сетке вычислительной нагрузки блочный алгоритм [20], ориентированный на задачи с медленным дрейфом «горячих» областей. В связи с этим разработан алгоритм серверного параллелизма. Он основан на принципах коллективного решения, но в значительной мере свободен от его недостатков благодаря наделению каждого из процессоров управляющими функциями. Разработан кластерный алгоритм серверного параллелизма, позволяющий, за счет введения процессов-шлюзов, обеспе- чить высокую эффективность выполнения расчетов на объединении нескольких кластерных систем, соединенных относительно слабыми каналами передачи данных.
В третьей главе рассматривается проблема распределенной визуализации результатов крупномасштабных вычислительных экспериментов.
Проблема визуализации больших объемов научных данных отмечается в публикациях с конца 1980х годов. В это время было сформировано новое научное направление - научная визуализация, в основе которой лежит комбинированный подход, предполагающий интерактивное отображение научных данных в среде виртуального окружения и предоставляющий исследователю возможность непосредственного манипулирования изучаемыми объектами, в рамках которого проблеме анализа больших объемов данных уделяется значительное внимание. С ростом числа процессоров, используемых для проведения вычислительных экспериментов, сложность задачи преобразования больших объемов вычисленных данных к виду, пригодному для наглядного отображения качественно возрастает, поскольку графические станции и компьютеры рабочих мест пользователей уже не обеспечивают её решение. Наиболее естественным путем решения проблемы является использование технологии клиент-сервер. В его рамках: сервер визуализации, как правило, выполняемый на многопроцессорной системе, обеспечивает обработку большого объема данных; клиент визуализации, выполняясь на компьютере рабочего места пользователя, обеспечивает интерфейс взаимодействия с пользователем и непосредственное отображение данных подготовленных сервером, используя при этом аппаратные и программные мультимедийные возможности персонального компьютера, как для построения наглядных визуальных образов (с помощью графических ускорителей, стерео устройств), так и для управления ими (с помощью многомерных манипуляторов).
На серверной компоненте системы визуализации готовятся данные, обеспечивающие формирование на клиентской компоненте именно трехмерного образа объекта, манипулирование которым с целью осмотра с различных точек зрения возможно уже без дополнительных обращений к серверу. В этом одно из существенных отличий предлагаемого подхода от методов используемых в большинстве доступных систем визуализации (например, VISIT, EnSight, ParaView), выполняющих на стороне сервера «рендеринг» - формирование двумерного растрового образа изучаемого объекта.
Созданная система визуализации RemoteView обеспечивает изучение трехмерных скалярных данных. Одним из наиболее мощных и наглядных методов представления трехмерных скалярных данных является визуализация изоповерхностеи, в связи с чем поддерживается именно этот метод. Среди подходов к визуализации поверхностей, выделяется метод, основанный на использовании мультитриангуляций [173,172,72,169]. Использование относительно простых структур данных - линейных массивов треугольников, позволяет опираться на известные алгоритмы огрубления триангуляции. Кроме того, современные видеоускорители аппаратно поддерживают отображение массивов треугольников, что значительно повышает наглядность визуализации, как за счет высокой скорости вывода данных на экран, так и за счет возможности автоматического формирования стереоизображений.
Ядро системы визуализации представлено рядом алгоритмов фильтрации и сжатия первичных данных, позволяющих аппроксимировать результаты вычислений ограниченным объемом данных, достаточным, одна- ко, для восстановления изучаемого образа с заданным уровнем качества. При сжатии преследуются две основные цели: сжатие непосредственно в процессе визуализации - сжатие данных до заданного объема за короткое время, определяемое требованиями, накладываемыми интерактивным режимом. Основным минимизируемым параметром в этом случае является объем данных, описывающих изучаемый объект - он лимитирован временем, отведенным на передачу данных на компьютер рабочего места пользователя; сжатие данных с целью их долговременного хранения для выполнения визуализации впоследствии - формирование сжатого образа, описывающего исходные данные с заданной точностью. Время сжатия не является в данном случае лимитирующим фактором, основное внимание уделяется увеличению степени сжатия.
Простейшие алгоритмы сжатия, основанные на уменьшении точности представления вещественных чисел, описывающих сетку и последующей компрессии с помощью стандартных алгоритмов группового кодирования (RLE), кодирования строк [99, 98] и им подобных значительного выигрыша не дают. Информация о связях между узлами сетки практически не сжимается стандартными методами. Существующие специальные методы, среди которых наиболее эффективен метод шелушения [140], существенно ориентированы на планарность графов и не обобщаются непосредственно на случай триангуляции, расположенных в трехмерном пространстве.
В связи с этим основной интерес представляют алгоритмы, формирующие некоторую новую триангулированную поверхность, аппроксимирующую исходную изоповерхность, но содержащую значительно меньшее количество узлов. В этой связи полезен ряд базовых алгоритмов огрубления триангуляции и многоуровневого описания трехмерных объектов поверхностными сетками [168, 169, 170, 171].
Для системы визуализации разработаны алгоритмы сжатия триангулированных поверхностей на основе методов синтеза и, созданные в соавторстве с С.В.Муравьевым, методы сжатия редукцией.
Разработанная в соавторстве с П.С.Криновым и С.В.Муравьевым система визуализации успешно функционирует не только на кластерах и суперкомпьютерах, но и на метакомпьютерах, поскольку объемы передаваемых в ходе ее работы данных относительно невелики.
В четвертой главе рассматриваются вопросы построения среды моделирования сеточных задач на распределенных вычислительных системах. Создание единой среды моделирования, даже при условии, что для каждого ее блока имеются в наличии алгоритмы и программные модули, представляет собой серьезную проблему, поскольку требует поиска решений, обеспечивающих согласованное выполнение модулей и взаимную стыковку их интерфейсов. В свою очередь, наличие прототипа вычислительной среды и решение с его помощью актуальных прикладных задач позволяет лучше обозначить проблемы использования многопроцессорных систем и стимулирует поиск путей их преодоления. Именно такой подход, основанный на тесной интеграции методов решения прикладных задач и методов создания параллельного математического обеспечения, позволяет разработать вычислительную среду, обеспечивающую решение с помощью МВС и метакомпьютеров сложных задач, требующих больших вычислительных мощностей.
Возможности среды демонстрируются на примере моделирования задач обтекания трехмерных тел (в соавторстве с С.А.Суковым и И.В.Абалакиным), горения в атмосфере метана (в соавторстве с М.А.Корнилиной) и добычи углеводородов с помощью методов перколя-ции (в соавторстве с И.И.Антоновой). Предлагается параллельный алго- ритм генерации последовательностей псевдослучайных чисел большой длины.
Система управление пакетом. Основная цель разработки системы управления пакетом - упрощение процедуры выполнения вычислительного эксперимента на распределенной вычислительной системе. В качестве действий, инициируемых с помощью системы управления, могут выступать вызовы модулей построения геометрической модели, формирования поверхностной и пространственной сетки, подготовки параметров запуска, выполнения расчета, запуск сервера визуализации, клиента визуализации, и так далее.
Основой сеанса работы с вычислительной средой служит проект -набор данных, включающий описание множества действий, модулей, промежуточных файлов и параметров, относящихся к циклу вычислительных экспериментов, направленных на решение прикладной задачи. Формирование проекта и изменение состава действий, выполняемых в его рамках, обеспечивается средствами системы управления, что предоставляет возможность моделирования широкого круга задач. Предусмотренные при настройке проекта операции могут быть инициированы пользователем непосредственно с помощью динамически формируемых элементов интерфейса системы управления. С помощью интерфейса вычислительной среды можно инициировать выполнение локальных заданий - на компьютере пользователя, и заданий, требующих параллельной обработки - на многопроцессорных серверах и удаленных системах. С точки зрения пользователя авторизация, позволяющая использовать распределенные вычислительные ресурсы выполняется только один раз - в начале сеанса. Как правило, между модулями данные передаются с помощью файлов, что упрощает согласование интерфейсов модулей подготовленных разрозненными командами разработчиков. Перечисленные свойства системы управления значительно уп- рощают работу пользователя с множеством модулей, поддерживающих различные этапы вычислительного эксперимента, в том числе при их выполнении на распределенных вычислительных мощностях.
Моделирование обтекания трехмерных тел сложной формы.
Приведены примеры моделирования обтекания ряда трёхмерных тел. В качестве математической модели газодинамического обтекания трехмерных объектов использовалась система записанных в дивергентной форме безразмерных уравнений Навье-Стокса, описывающая течения вязкого теплопроводного совершенного газа. Пространственная дискретизация выполнялась на тетраэдральных сетках с использованием методов конечных объемов (конвективный перенос) и конечных элементов (диффузионная часть). Численный поток через грани барицентрических контрольных объемов определялись с помощью схемы Роу и кинетически согласованной разностной схемы (Б.Н.Четверушкин).
Моделирование задач горения. Моделирование процессов горения является одной из наиболее сложных с вычислительной точки зрения проблем и требует больших вычислительных ресурсов. Результаты моделирования горения струи метана на многопроцессорной системе МВС-1000М показывают, что применение алгоритма серверного параллелизма обеспечивает эффективность на уровне 60% при расчете сетки, содержащей 1000x1000 узлов, на 600 процессорах, что подтверждает хорошую масштабируемость метода. Так же высокую эффективность подтвердили расчеты горения метановой струи на объединении двух кластеров. Несмотря на медленный канал связи между системами (30 и 12-процессорной) была получена более, чем 90% эффективность.
Моделирование добычи углеводородов с помощью методов перколяции. Актуальность проблемы интенсификации добычи нефти обусловлена истощением месторождений и необходимостью снижения остаточной нефтенасыщенности и обводнённости продукции. Перспективным выглядит использование для этих целей подхода, основанного на методах теории перколяции. Для достоверного описания трехмерного пористого коллектора месторождения с помощью перколяционной модели необходимо использовать решетки содержащие более 107 узлов [174], что стало возможным в последнее время благодаря развитию высокопроизводительных многопроцессорных систем. Изучению методов теории перколяции и свойств, описываемых ими многомерных геометрических структур, посвящены монографии [175, 176]. Перколяционный подход для описания фильтрации флюидов и активного нефтевытеснения рассматривается в работах [103,104,105,106].
Трёхфазная динамическая перколяционная модель (ДПМ) [105] хорошо описывает такие эффекты, как наличие порога протекания, кластеров запертой нефти и рукавов прорыва вытесняющего агента, конечное время распространения волн давления. Использование больших вычислительных мощностей позволило обнаружить важное для практических приложений свойство ДПМ: увеличение фильтрационного потока при использовании импульсного режима внешней накачки.
Параллельный алгоритм генерации последовательностей псевдослучайных чисел. Для формирования на многопроцессорных системах перколяционных решеток, содержащих 109 и более узлов, требуются последовательности псевдослучайных чисел (ПСЧ) большой длины. Кроме того, необходима возможность определения любого члена ПСЧ без вычисления всех предыдущих, что позволяет параллельно формировать размещенные на процессорных узлах части решетки и избежать хранения перко- ляционных решеток, сохраняя вместо них параметры соответствующих фрагментов последовательности. При моделировании стохастических процессов каждый эксперимент должен быть воспроизведен многократно с различными выборками используемых случайных величин, поэтому возможность непосредственного определения произвольного элемента ПСЧ значительно повышает эффективность расчетов. Выигрыш достигается за счет возможности использования в разных экспериментах разных независимых фрагментов достаточно длинной последовательности ПСЧ.
При построении генератора использован подход, основанный на рекуррентных соотношениях [119] и аналогичных им генераторах Фибоначчи [177,179]. Разработаны алгоритмы формирования ПСЧ длины 2255-1, 25П_15 2|023-1 бит, что соответствует 1076, 10ш, 10307 вещественных чисел.
По теме диссертации опубликовано более 40 работ [21-60], из них 9 статей - в ведущих рецензируемых научных журналах и изданиях, перечень которых определен Высшей аттестационной комиссией [21-29].
Автор глубоко благодарен Б.Н.Четверушкину, оказавшему большое влияние на все этапы выполнения исследований, за неослабевающее внимание к работе и постоянную поддержку. Автор выражает искреннюю благодарность своему учителю Е.И.Леванову за постоянное внимание и поддержку. Автор глубоко благодарен А.Р.Кесселю и С.С.Лапушкину за постановку задачи моделирования динамики заводнения месторождений нефти и газа с помощью перколяционных методов, предложенную математическую модель и плодотворные обсуждения. Автор выражает глубокую благодарность С.В.Полякову, за многочисленные дискуссии по широкому кругу затрагиваемых в диссертации вопросов. Автор благодарен П.С.Кринову, С.А.Сукову, С.В.Муравьёву, М.А.Корнилиной,
С.В.Болдареву, И.И.Антоновой и Д.В.Петрову за совместную работу над созданием и реализацией ряда рассматриваемых в диссертации алгоритмов, библиотек и программ. Автор благодарен Б.М.Шабанову, О.С.Аладышеву, П.Н.Телегину и другим сотрудникам МСЦ РАН за внимательное отношение и всестороннюю поддержку, позволившую успешно выполнить значительную часть вычислительных экспериментов. Автор выражает свою особую благодарность И.И.Галигузовой за доброжелательную поддержку на протяжении многих лет.
Иерархический алгоритм декомпозиции графа
Основой иерархических методов является следующая последовательность действий: огрубление графа: построение последовательности уменьшающихся в размере вложенных графов; начальная декомпозиция: вершины огрубленных графов распределяются по заданному числу доменов; восстановление графа и локальное уточнение: вершины всех графов сформированной последовательности, начиная с имеющих наименьший размер, распределяются по доменам.
Огрубление графа
Алгоритм огрубления графа (Рис. 2) основан на идее многократного стягивании ребер. Из всего множества ребер графа G выбирается подмножество ребер покрытия таким образом, что бы никакая из вершин не была инцидентна более чем одному из них. Далее каждая пара вершин (v ,v ), соединяемых ребром покрытия е , стягивается в одну агрегированную вершину v +1. Будем в дальнейшем называть вершины v ,v порождающими для вершины v,t+1 и записывать этот факт следующим образом: v +l=/v v \. Некоторые из вершин Gk могут не иметь инцидентных им ребер покрытия, такие вершины, тем не менее, порождают вершины графа Gw: v, +1=(v ). Пусть v / ev),) и v 2+1=(v, @v 2), тогда веса вершин и ребер графа GM определяются следующим образом: 4л# )=4 . vfa)+4 , 2)+4 )+4) Аналогично, если v, +I = (v, Ф v ,) и v 2+1 =(v 2) то: а 4 )=4,0+4,4.) / - ч// 4 )=4, ) 4 о=4 2)+4 )
Однократное выполнение описанной процедуры позволяет примерно вдвое уменьшить число вершин: \Vk+l\»\Vk\/2.
В результате многократного огрубления формируется цепочка графов Gk =(к , ):к " к , к = \,...,т. Разбиение на домены начинается с последнего из них (Gm). При выборе множества ребер покрытия графа G следует отдавать предпочтение ребрам, инцидентным вершинам, имеющим наименьшие веса, что позволяет уменьшить разброс весов вершин графа Gi+I и, не только улучшить качество итогового разбиения, но и сократить время его построения. Первичное разбиение графа
После огрубления графа возникает задача его рациональной декомпозиции на к частей. Традиционно эта задача решается одним из двух способов: разбиением сразу на требуемое число доменов (многопутевая декомпозиция [185]), или рекурсивно, разбиением на каждом шаге рекурсии на меньшее число (обычно 2, 4или 8) доменов. Учитывая, что разбиению подвергается огрублённый граф, и в дальнейшем будет выполнен ряд шагов восстановления графа и уточненния границ доменов, на этапе первичного разбиения можно использовать любой алгоритм. При достаточно сильном огрублении исходного графа можно использовать алгоритм полного перебора, дающий точное решение. Тем не менее, чем большего размера граф подвергается первичному разбиению, и чем выше качество этого разбиения, тем выше качество окончательного результата. В следующем параграфе рассматриваются одни из наиболее привлекательных методов декомпозиции - спектральные [79,74], но, эти методы являются и наиболее требовательными с точки зрения вычислительных затрат. Их использование сопряжено с необходимостью поиска с высокой точностью ряда собственных векторов спектральной матрицы графа [65]. Среди менее затратных методов можно указать методы координатной и инерциальной бисекции, а так же, ориентированный на декомпозицию регулярных сеток метод заполняющих кривых [189,190].
Для разбиения графа содержащего п вершин на произвольное число домено к может быть использована эффективная процедура рекурсивной бисекции (Рис. 3). На Рис. 4 представлен результат разбиения 100 вершин графа на 7 частей приблизительно равного размера. В каждом из корней дерева разрезов указано число вершин соответствующего подграфа, два числа, разделенные знаком косой черты указывают пропорцию, в которой вершины подграфа разбиваются на две части.
Структура параллельной программы
Изложим положения, послужившие основой для создания алгоритма серверного параллелизма для решения подобных задач на многопроцессорных системах с распределенной памятью. Метод является развитием метода коллективного решения, но не требует наличия управляющего процессора, избегая, таким образом, потерь времени на пересылку всех данных управляющему процессору и обратно. За счет этого предлагаемый алгоритм дает возможность получить значительный выигрыш во времени вычислений.
Исходные предпосылки:
1. Перед началом работы алгоритма все точки распределены по всем процессорам. При этом "горячие" точки распределены неравномерно и на некоторых процессорах могут отсутствовать.
2. По завершению выполнения алгоритма результаты обработки каждой из точек должны быть размещены на том процессоре, на котором эти точки были размещены перед началом работы.
Дополнительные требования к алгоритму: Следует осуществлять преимущественную обработку каждым из процессоров локальных горячих точек (точек, хранящихся на данном процессоре). Точки с других процессоров запрашиваются, только ес ли все локальные обработаны или переданы на обработку другим процессорам;
При наличии на процессоре необработанных горячих точек, не следует инициировать поиск свободных процессоров, хотя бы потому, что таких процессоров может не оказаться. Опрашивать процессоры в поисках необработанных точек следует только в том случае, Если на процессоре нет готовых к обработке точек.
Поиск и передача необработанных точек и прием обработанных точек должны выполнятся одновременно с их обработкой. Эти два процесса, по возможности не должны мешать друг другу.
Должна быть реализована возможность вторичного перераспределения точек, полученных для обработки одним процессором от другого, что позволит передавать точки большими группами, не опасаясь, что точки, требующие большого времени обработки, окажутся сконцентрированы только на небольшом числе процессоров, в то время как остальные процессоры будут простаивать.
Поскольку допускается вторичное перераспределение точек, потребуем, что бы точки возвращались не тому процессору, который непосредственно предоставил точки для обработки, а тому, где они должны быть размещены по окончании шага вычислений - процессору "владельцу" точек. В частности, если 6 из 8-ми точек были переданы с первого процессора на третий (рис. 24), а затем 4 из них с 3-го процессора на 5-ый, то все точки должны быть после обработки переданы непосредственно с 3-го на 1-ый и с 5-го на 1-ый, минуя 3-ий процессор.
Структура параллельной программы
Структура программы при использовании 5-ти процессоров приведена на рис. 25. На каждом из процессоров одновременно выполняются два параллельных процесса - управляющий и обрабатывающий.
Пусть на процессоре с номером і запущен управляющий процесс М, и обрабатывающий процесс S,. Основной цикл действий, выполняемых обрабатывающим процессом St, выглядит следующим образом.
Ожидание сообщения от управляющего процесса М,.
Если сообщение содержит указание о необходимости завершить работу, то обрабатывающий процесс завершает работу.
Если сообщение содержит данные, описывающие очередное задание на решение системы ОДУ, то обрабатывающий процесс выполняет численное интегрирование соответствующей системы ОДУ и направляет управляющему процессу М, сообщение, содержащее результат расчёта.
Таким образом, обрабатывающий процесс не взаимодействует с остальными процессорами сети.
Управляющий процесс обработку точек не производит. Он связан с каждым из управляющих процессов, расположенных на других процессорах. Перераспределение точек по процессорам выполняется именно на уровне управляющих процессов. Между собой управляющие процессы полностью эквивалентны и выполняют один и тот же алгоритм. Рассмотрим его подробнее.
Управляющий алгоритм балансировки загрузки Далее удобно использовать следующую терминологию: точка - набор данных, описывающих одну горячую точку. необработанная точка - точка, которая в данный момент не передана обрабатывающему процессу для обработки и не передана никакому другому процессору. Обратим внимание, что согласно этой терминологии точка перестает быть необработанной с момента ее предоставления обрабатывающему процессу. Реальные вычисления по решению системы ОДУ могут быть завершены значительно позже. обрабатываемая точка - точка, переданная обрабатывающему процессу. Точка перестает быть обрабатываемой и становится обработанной после того, как решение системы ОДУ уже завершено и управляющий процесс получил от обрабатывающего процесса результат вычислений.
Серверная и клиентская части системы визуализации
Следует определить круг действий выполняемых серверной и клиентской частями системы визуализации. На серверной стороне должно выполнятся чтение данных. На клиентской части системы должен выполняться вывод визуального образа. Рассмотрим три подхода к решению вопроса о разграничении полномочий по обработке данных: предобработка, отображение и экранизация на стороне сервера, передача изображения на сторону клиента, вывод на стороне клиента; предобработка и отображение на стороне сервера, передача данных описывающих трёхмерную сцену на сторону клиента, экранизация и вывод на стороне клиента; предобработка, заключающаяся в сокращение объёма исходных трёхмерных данных (за счёт фильтрации, сжатия или огрубления) на стороне сервера, передача подготовленных данных на сторону клиента, отображение, экранизация и вывод на стороне клиента.
Первый подход, в соответствии с которым на стороне сервера выполняется практически вся работа по формированию изображения, вплоть до экранизации, используется достаточно широко. В его рамках клиентская компонента системы визуализации может быть сведена практически к нулю, за счёт использования стандартных X-терминалов UNIX, поддерживающих вывод графических окон на мониторы удалённых рабочих станций. Однако, при любом изменении направления обзора визуализируемого трёхмерного образа изображение будет передаваться через относительно медленный канал связи /, что значительно ограничивает наглядность и удобство работы, не позволяя в полной мере использовать возможности современных графических ускорителей рабочих станций.
Второй подход принят за основу при разработке описываемой системы визуализации (RemoteView) и подробно рассматривается в настоящей главе.
Третий подход не целесообразно использовать при работе в интерактивном режиме. Связано это, во-первых, с высокой трудоёмкостью алгоритмов сокращения объема данных, обеспечивающих описание исходных трёхмерные данных с приемлемой точностью и, во-вторых, с большим объёмом данных, формируемых в результате их работы. Простейшие алгоритмы прореживания применимы при обработке регулярных решёток, но их использование может приводить к значительной потери информации. Ценность третьего подхода резко возрастает, если есть необходимость визуализации динамики развития моделируемого процесса. При необходимости сохранить на диске результаты последовательность шагов соответствующих различным моментам модельного времени, возможность сокраще ния объёма каждого из записываемых наборов данных в г раз позволит сохранить в г больше наборов и, впоследствии, выполнить на их основе более детальную визуализацию. Данный подход, применительно к обработке тетраэдральных сеток рассматривается в конце настоящей главы. Поскольку в его рамках визуализация не выполняется, а фактически выполняется сжатие описания трёхмерных сеточных данных и запись результата сжатия на диск, то не возникает противоречия, связанного с интерактивным режимом работы и пакетным режимом вычислений. В моделирующую программу добавляются вызовы библиотечных функций, обеспечивающих сжатие и запись данных, что является вполне естественным для программ моделирования, выполняемых в пакетном режиме.
Визуализация трёхмерных скалярных данных
Система визуализации RemoteView обеспечивает изучение трехмерных скалярных сеточных данных.
Относительно простым и широко распространённым способом визуализации 3-х мерных данных является выделение срезов исследуемого объёма. Широко используются плоские срезы (tecplot, netgen), но могут использоваться срезы выполненные с помощью сферических, цилиндрических и иных поверхностей или их комбинаций.
Полученные в результате такой фильтрации данные определены уже на некотором множестве двумерных областей, значение функций на которых может быть представлено с помощью цветовой палитры, изолиний или (при сечении плоскостью) трёхмерных поверхностей. Экранизация может быть выполнена непосредственно (если образы двумерны, например изолинии на плоскости), либо с помощью известных алгоритмов экранирования невидимых линий, таких, как Z-буфер или метод плавающего горизонта. Рассматривая набор срезов можно получить представление о распределении значений исследуемой функции в 3-х мерном объёме. Существенным недостатком подобных подходов является то, что отображается не 3-х мерный объект, а набор его срезов, что затрудняет восприятие и сопряжено с большими потерями информации - значений функции между срезами.
Другим возможным подходом является использование методов объёмной экранизации. Скалярное поле данных представляется трёхмерным массивом кубических элементов (вокселов). Сегментация (отбор) проводится путём выбора только тех вокселов, которые удовлетворяют определённому критерию, например, заданному пороговому значению функции или координат. Затем выбранные вокселы экранизируются.
Моделирование обтекания трехмерных тел сложной формы
Запись сетки в распределенном формате выполнялась в сжатом виде с использованием стандартных алгоритмов сжатия (GZIP). При этом для повышения эффективности сжатия данных выполнялась предварительная перегруппировка байт в массивах (рис. 100), задающих некоторые из полей в описании микродоменов, что с учетом специфики алгоритма предварительного разбиения и обработки сетки позволило несколько улучшить получаемый в итоге коэффициент сжатия данных.
В общем случае, коэффициент сжатия без потери точности массивов чисел с плавающей запятой низок. Поэтому, перед сжатием алгоритмом LZW выполнялась перекомпоновка байт обрабатываемых чисел. Двоичное представление каждого вещественного числа представимо последовательностью байт, что позволяет рассматривать одномерный массив чисел, как двумерный массив байт. Массивы перекомпоновываются по старшинству байт (рис. 100). Младшие байты помещаются в первый массив, следующие по старшинству во второй и так далее. Полученные массивы могут быть сжаты с более высоким коэффициентом, поскольку во многих случаях близко расположенные в исходном массиве вещественные числа имеют одинаковый или близкий по величине порядок и значения старших цифр мантиссы. Массивы, содержащие соответствующие байты, сжимаются стандартными методами с высокой степенью. Как правило, степень сжатия остальных массивов ниже.
В таблице 13 приведены сравнительные характеристики объёмов описания топологии расчетной сетки в исходном виде, и в распределенном формате. Под описанием расчётной сетки следует понимать совокупность данных необходимых для задания полной информации о расположении и взаимосвязях элементов сетки. В исходном виде описание геометрии сетки состоит из четырех файлов, которые могут записываться в текстовом или двоичном формате: файлы с общими параметрами сетки (число узлов и элементов), координатами узлов, описанием тетраэдров (четверки идентификаторов узлов) и описанием треугольников поверхностной сетки (тройки вершин и метки поверхностей). Описание топологии расчетной сетки в текстовом и двоичном формате занимает, соответственно, 514 МБ и 269 МБ. При упаковывании описания сетки в двоичном формате с помощью стан стандартных средств UNIX (GZIP) размер описания снижается до 124 МБ (коэффициент сжатия 2.17). В таблице 13 для разбиения на различное число микродоменов приводится итоговый размер описания расчетной области в распределенном формате (с учетом файлов с таблицей расположения данных и графом микродоменов). Во всех случаях, за исключением первого столбца, описания микродоменов равномерно распределялись по 25 файлам данных.
По приведенным в таблице 13 результатам можно сказать, что запись распределенного файла приводит, за счет дублирования информации, к увеличению размера примерно в полтора раза по отношению к упакованному двоичному описанию, оставаясь на приемлемом уровне, поскольку позволяет значительно сократить время ввода-вывода данных за счёт их выполнения этих операций одновременно множеством процессоров.
При проведении расчетов на ряде вычислительных система оценивались затраты времени на выполнение вспомогательных операций (балансировка загрузки процессоров, чтение данных в параллельном режиме, создание расчетных областей процессоров, инициализация массивов межпроцессорного обмена данными). Благодаря использованию распределённого формата хранения файлов максимальное время выполнения вспомогательных операций составляет порядка 15 секунд при расчете на 4 процессорах. Эта величина сопоставима со временем выполнения 2 вычислительных итераций, и снижается с ростом числа процессоров.
Приведенные результаты подтверждают высокую эффективность предложенных алгоритмов распределенной обработки нерегулярных сеток и созданных на их основе библиотек подпрограмм.
