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

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

Головченко Евдокия Николаевна

ДЕКОМПОЗИЦИЯ РАСЧЕТНЫХ СЕТОК ДЛЯ РЕШЕНИЯ ЗАДАЧ МЕХАНИКИ СПЛОШНЫХ СРЕД НА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

АВТОРЕФЕРАТ

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

О з ДПР 2014

Москва-2014

005546680

005546680

Работа выполнена в Институте Российской академии наук.

прикладной математики имени М.В.Кеддыша

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

Якобовский Михаил Владимирович

Петров Игорь Борисович доктор физико-математических наук, профессор,

член-корреспондент РАН, МФТИ, зав. кафедрой информатики

Валько Виктор Васильевич доктор технических наук, ФБУН «12 Центральный научно-исследовательский институт Министерства обороны РФ»,

ведущий научный сотрудник

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится «_»_2014 г. в час. мин. на заседании диссертационного совета Д 002.024.03 при Институте прикладной математики имени М.В.Келдыша РАН по адресу: 125047, г. Москва, Миусская пл., д. 4.

С диссертацией можно ознакомиться в библиотеке ИПМ имени М.В.Келдыша РАН.

Автореферат разослан « 27» МП2014 г.

Учёный секретарь

диссертационного совета Д 002.024.03 доктор физико-математических наук

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

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

Общая характеристика работы

Актуальность.

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

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

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

Задача сбалансированного разбиения сетки на домены сводится к более общей задаче разбиения графа на домены. В этом случае выполняется разбиение графа, аппроксимирующего вычислительные и коммуникационные нагрузки сетки. Существует несколько моделей декомпозиции графов, отличающиеся видом графа и критериями сбалансированного разбиения. В случае разбиения сеток хорошо себя зарекомендовал наиболее распространенный подход, использующий стандартную модель графа. В нем сетка аппроксимируется неориентированным графом С = {У,Е), где V — множество вершин, Е - множество ребер. И вершины, и ребра, имеют вес. Оптимальным считается разбиение на домены, при котором выровнен суммарный вес вершин в доменах и минимизирован суммарный вес разрезанных ребер (разрезанное ребро — ребро, соединяющее вершины из разных доменов). В данной модели суммарный вес вершин в доменах отвечает за равномерность распределения вычислительной нагрузки по процессорам, которые будут обрабатывать эти домены, а суммарный вес разрезанных ребер - за коммуникационную нагрузку между процессорами. Как

известно, поставленная задача декомпозиции графа является NP-полной, поэтому для ее решения используются различные эвристические методы. К геометрическим методам относятся алгоритмы рекурсивных координатной и инерциальной бисекций и декомпозиция с использованием кривой Гильберта. К методам разбиения графов относятся алгоритм спектральной бисекции, алгоритм Kernighan-Lin (KL) и Fiduccia-Mattheyses (FM), иерархические алгоритмы, диффузионные и генетические алгоритмы, используемые в рамках иерархического подхода, алгоритмы, оптимизирующие характеристические отношения доменов, жадные алгоритмы (greedy methods), или алгоритмы наращивания доменов, и инкрементный алгоритм декомпозиции графов. Эти алгоритмы, за исключением инкрементного, реализованы в следующих последовательных пакетах декомпозиции графов: METIS, JOSTLE, SCOTCH, CHACO и PARTY. К параллельным пакетам относятся PARMETIS (параллельная версия пакета METIS), JOSTLE, PT-SCOTCH (параллельная версия пакета SCOTCH) и ZOLTAN.

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

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

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

Областью данного исследования являются нерегулярные сетки, содержащие 10д и более вершин. В настоящее время такие сетки невозможно разместить в памяти одного процессора (на гексаэдральную сетку, состоящую из 1.2-108 ячеек, требуется порядка 200 ГБ), поэтому для декомпозиции нужен параллельный алгоритм. Методы разбиения графов параллельных пакетов PARMETIS, JOSTLE, PT-SCOTCH и ZOLTAN основываются на иерархических алгоритмах, состоящих из следующих частей: поэтапное огрубление графа, декомпозиция самого маленького из полученных графов и отображение разбиения на предыдущие графы с периодическим локальным уточнением границ доменов. Недостатком таких алгоритмов является образование доменов, границы которых состоят из неоптимальных наборов сегментов. В частности, домены могут оказаться несвязными. Такое ухудшение качества доменов для некоторых задач является критичным. На доменах с длинными границами или сложной конфигурацией алгоритмы решения систем линейных уравнений сходятся за большее

' Barry Smith, Petter Bjorstad, William Gropp. Domain decomposition: parallel multilevel methods for elliptic partial differential equations // Cambridge University Press, 1996.225 pp.

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

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

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

Цели работы.

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

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

• Разработка программного комплекса декомпозиции больших сеток.

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

2 А. И. Илюшин, А. А. Колмаков, И. С. Меньшов. Построение параллельной вычислительной модели путем композиции вычислительных объектов//Математическое моделирование. 2011. Т. 23. № 7. 97113.

3 А. А. Воропинов. Декомпозиция данных для распараллеливания методики ТИМ-20 и критерии

оценки ее качества // Вестник ЮУрГУ. Серия «Математическое моделирование и программирова-

ние:», вып. 4. 2009. №37(170). 40-50.

Научная новизна.

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

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

Теоретическая и практическая значимость.

В диссертационной работе были разработаны два алгоритма: параллельный алгоритм геометрической декомпозиции сеточных данных и параллельный ин-крементный алгоритм декомпозиции графов, на основе которых был создан комплекс программ ОЯШЗРШЕЯРАК декомпозиции больших сеток. Разработанные алгоритмы поддерживают два основных этапа декомпозиции больших сеток: предварительную декомпозицию сетки по процессорам и параллельную декомпозицию сетки высокого качества.

Параллельный алгоритм геометрической декомпозиции сеточных данных основан на методе рекурсивной координатной бисекции. На каждом этапе рекурсивной координатной бисекции окаймляющий сетку параллелепипед разбивается на две части. Выбирается координатная ось, вдоль которой параллелепипед имеет наибольшую протяженность. Параллелепипед разрезается перпендикулярно выбранной оси. Достоинством данного метода является то, что при разбиении на равные домены числа вершин в получаемых доменах отличаются не больше, чем на единицу. Другими достоинствами являются экономичное использование памяти и относительная быстрота работы. Подобный алгоритм реализован в пакете 20ЬТАЫ. Отличие рекурсивной координатной бисекции созданного алгоритма от аналогичного алгоритма в пакете 20ЬТАК состоит в том, что в нем секущая плоскость (медиана) при необходимости разрезается по нескольким координатам, что позволяет обрабатывать ситуации наличия на одной плоскости множества узлов с одинаковым значением координаты. В пакете 20ЬТАЫ вершины из медианы распределяются по областям произвольным образом, что увеличивает число разрезанных ребер.

Параллельный инкрементный алгоритм декомпозиции графов комплекса программ GR.IDSPIDER.PAR. основан на последовательном инкрементном алгоритме декомпозиции графов (ИПМ им. М.В.Келдыша РАН). Достоинством ин-крементного алгоритма является формирование преимущественно связных доменов. Инкрементный алгоритм не основывается на иерархическом подходе. Наиболее близкими к нему являются алгоритмы пузырькового роста и диффузионные. Однако алгоритм пузырькового роста, в отличие от инкрементного алгоритма, не гарантирует получение сбалансированного разбиения. А существенным отличием инкрементного алгоритма от диффузионных алгоритмов

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

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

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

Основные результаты диссертационной работы докладывались на следующих конференциях:

• 8-ая Международная Конференция «Высокопроизводительные параллельные вычисления на кластерных системах (НРС-2008)», 17-21 ноября 2008, Казань.

• Международная конференция «Современные проблемы вычислительной математики и математической физики», 16 - 18 июня 2009, Москва, ВМК МГУ имени М.В. Ломоносова.

• Международная суперкомпьютерная конференция "Научный сервис в сети ИНТЕРНЕТ: суперкомпьютерные центры и задачи", 20 - 25 сентября 2010, Новороссийск.

• XI Всероссийская конференция «Высокопроизводительные параллельные вычисления на кластерных системах», 1-3 ноября 2011, Нижний Новгород, ННГУ.

• Международная суперкомпьютерная конференция "Научный сервис в сети ИНТЕРНЕТ: поиск новых решений", 17-22 сентября 2012, Новороссийск.

• International Conference on Parallel Computing - ParCo2013, 10 - 13 сентября 2013, Мюнхен, Германия.

• Международная суперкомпьютерная конференция "Научный сервис в сети Интернет: все грани параллелизма", 23 — 28 сентября 2013, Новороссийск.

Публикации.

Основные результаты диссертации опубликованы в одиннадцати работах, первые четыре из которых в изданиях, рекомендованных ВАК [1-11].

Структура и объем диссертации.

Диссертация состоит из введения, трех глав, заключения и списка литературы. Полный объем диссертации составляет 165 страниц, включая 53 иллюстрации и 8 таблиц. Список литературы содержит 107 наименований.

Содержание работы

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

• Критерий сбалансированности получаемых разбиений.

• Критерий минимизации суммарного веса разрезанных ребер.

• Критерий связности формируемых микродоменов.

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

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

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

Представлены следующие физические задачи и результаты их моделирования:

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

(Рис. 1). Он расположен вдоль нижней части вакуумной камеры и служит для приема потоков примесей и излучений из плазмы.

Рис. 1. Дивертор токамака ITER: общий вид (слева) и кассета (справа)

Расчетная область аппроксимировалась тетраэдральной сеткой, содержащей порядка 2.8-106 ячеек (Рис.2).

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

—p+V(pw) = О

at

—H-Vx(w хН) = О

8t v '

vP = [w WW)

Здесь и далее: p - плотность среды, v *' -1" '' - вектор скорости среды, е-удельная внутренняя энергия, Р - давление, Ч - вектор плотности потока энергии, Н - вектор напряженности магнитного поля.

Задача считалась с учетом радиационного и кондуктивного теплопереноса:

| (PB) = -V(i gradT)+Q,ltlJ

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

Qroj = - VIP

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

-V —^-¡rgradU + KPcU = KPcJ 3 к

Здесь кр означает осреднение коэффициента поглощения по Планку, а кя — по Росселанду. Граничное условие на выходе для нормального потока: Wn = - с

U/2.

Учитывалось влияние турбулентной вязкости на скорость потока:

8 д — wt = — dt dxt

" ' дх,

дх, дх.

Здесь <" — коэффициент динамической вязкости (сдвиговая вязкость), — дополнительная "турбулентная вязкость".

На Рис. 2 представлены результаты моделирования газоплазменных течений в диверторе токамака ITER на суперкомпьютере Helios на 256 ядрах.

' ч -Ч^Ч. V

йаяй - г.

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

Моделирование распространения ударной волны от приземного источника энергии взрывного типа. Для моделирования приземного взрыва была выбрана кубическая область, которая аппроксимировалась гексаэдральными сетками, содержащими порядка 6.1-107 и 1.2Т08 ячеек со сгущением в области взрыва.

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

—p+V(pw) = 0

dt

at t ox.

d( l 2 — OE+ — OV> dt\ 2

П,,. = pw,wt + PSlk q = [ps + ^рмг +P

Задача считалась с учетом диссипативных процессов: (ре) = -Ч{к ЯгааТ) + Оы

от

Турбулентные потоки не учитывались.

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

Расчет процесса формирования и распространения ударной волны от приземного взрыва производился на суперкомпьютере «Ломоносов» на 4096 и 10080 ядрах. На Рис. 3 представлены результаты моделирования.

Рис. 3. Апроксимация изоповерхностей давления на расчетную сетку Р[10" Па| в момент времени 1=1000 мс с шагом <1Р=691 Па (слева) и <1Р=518 Па (справа)

Моделирование распространения ударной волны от взрыва химического взрывчатого вещества в протяженном сооружении с нетривиальной геометрией. Для рассмотрения процесса обтекания воздушной ударной волной препятствий в трубу был помещен объект сложной формы, который рассматривался как твердое тело (Рис. 4). Расчетная область аппроксимировалась тетраэдральной сеткой, содержащей порядка 2.6-107 ячеек со сгущением вблизи области взрыва, в районе инженерной секции и вокруг объекта.

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

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

а

—р+'Ч(рм>) = О ЭГ

В расчете учитывалась турбулентная вязкость:

5

q = [pe+ — рм>2 + Р | »>

д

— V/.

51 '

дх.

, N1 ии>, дн>к 2 дн>.

дх.

Радиационный теплоперенос не учитывался.

Расчет процесса формирования и распространения ударной волны в протяженном сооружении производился на суперкомпьютере «Ломоносов» на 4096 ядрах. На Рис. 5 представлены результаты моделирования.

Рис. 5. Распространение ударной волны (вверху) и потоки газа в ударной трубе на поле температуры (внизу)

Приведены краткие сведения о пакете МАИРЬЕЗО, с помощью которого проводилось тестирование разбиений на физических задачах. Параллельный программный комплекс МАЯРЬЕЗБ создан в ИПМ им. М.В.Келдыша РАН, и его предметной областью являются задачи двухтемпературной радиационной

магнитной гидродинамики. Тестирование выполнялось совместно с Дорофеевой Е.Ю. (ИПМ им. М.В.Келдыша РАН). Автор диссертации занималась разработкой алгоритмов и программ выполнения рационального разбиения графов расчетных сеток, а также оценкой качества разбиений, Дорофеева Е.Ю. - постановкой физических задач и проведением вычислительных экспериментов. Эффективность параллельного счета физических задач оценивалась совместно.

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

Пусть С = (У,Е) - неориентированный граф, где К = |уг| — множество вершин, Е = |егу | - множество ребер. И вершины, и ребра, имеют целочисленные

веса |уг| и |егу|, соответственно. Декомпозиция является отображением множества вершин V на заданное число р доменов таким, что каждая вершина V. принадлежит некоторому домену , и пересечение любых двух доменов пусто: =0, и^ = У. Суммарный вес вершин в домене 5 . равен сумме ве-т . ] ]

сов вершин, принадлежащих этому домену: = е . Суммарный вес

г

разрезанных ребер между доменами равен сумме весов ребер, соединяющих

вершины из разных доменов: | Ес\ = ЩеЛ\.е . вЯ^к <т ■ Каждый домен

у 1 т

5. является некоторым подграфом С?-' = (у] графа в = (У,Е), где

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

вес вершин в доменах ф'у1~|к|Д>) и минимизирован суммарный вес разрезанных ребер (гшп|£с|).

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

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

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

Рис. 6. Разбиение сетки на семь доменов параллельным алгоритмом геометрической декомпозиции: первые два этапа разбиения (слева и в середине) и результат (справа)

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

Рис. 7. Разрезание секущей плоскости Рис. 8. Геометрическое распределение вершин по

процессорам (слева) и перераспределение малых блоков вершин (справа)

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

Параллельный инкрементный алгоритм декомпозгщии графов основан на последовательном инкрементном алгоритме декомпозиции графов4. Достоинством инкрементного алгоритма является формирование связных доменов. Параллельный инкрементный алгоритм предполагает выполнение следующих этапов:

4 М. В. Якобовский. Инкрементный алгоритм декомпозиции графов. Вестник Нижегородского университета им. Н.И.Лобачевского. Серия «Математическое моделирование и оптимальное управление», Вып. 1(28). Нижний Новгород: Издательство ННГУ, 2005, с. 243-250.

Рис. 9. Локальное разбиение (слева), сбор плохих групп доменов и их повторное разбиение (справа)

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

• Инкрементный рост доменов и диффузное перераспределение вершин между доменами (Рис. 10,,11)- __________

Рис. 10. Инкрементный рост доменов

• Локальное уточнение доменов алгоритмом KL/FM (Рис. 11). На рисунке справа видно, что желтый домен состоит из двух частей.

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

Перераспределение малых блоков вершин (Рис. 8). Локальное разбиение вершин на каждом из процессоров на домены последовательным инкрементным алгоритмом декомпозиции графов. Перераспределение плохих групп доменов. Сбор каждой группы плохих доменов на одном процессоре.

Локальное повторное разбиение плохих групп доменов инкремент-

Рис. П. Диффузное перераспределение вершин между доменами (слева) и локальное уточнение (справа)

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

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

■^Йг

ррр

Рис. 12. Освобождение части вершин плохих доменов (слева) и результирующее разбиение (справа)

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

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

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

Рис. 13. Оболочки домена

В третьей главе представлены следующие результаты.

На основе разработанных алгоритмов был создан комплекс программ GRIDSPIDERPAR декомпозиции больших сеток (до 109 вершин) на большое число микродоменов.

Вычисления производились на кластерах МВС-100К (228 TFlop/s), "Ломоносов" (1700 TFlops) и Helios (1524 TFlop/s).

Выполнено сравнение разбиений небольшой треугольной сетки, состоящей из 7.6-104 вершин, 2.3-105 ребер, полученных параллельным и последовательным инкрементными алгоритмами декомпозиции графов. Сетка разбивалась на 20 доменов на одном процессоре. Параллельному инкрементному алгоритму при выполнении на одном процессоре потребовалось в два раза меньше итераций и в сто раз меньшее время для нахождения разбиения. Но число разрезанных ребер в разбиении, полученном параллельным инкрементным алгоритмом, немного больше, чем в разбиении, полученном последовательным методом (3873 против 3762).

Проведены тесты по оценке масштабируемости (сильное масштабирование) параллельного инкрементного алгоритма декомпозиции графов и параллельного алгоритма геометрической декомпозиции сеточных данных созданного комплекса программ GRIDSPIDERPAR. Оценивался рост ускорения получения разбиений гексаэдральной сетки, содержащей 14.7-Ю6 ячеек, на 1024 домена с увеличением числа процессоров (до 1024 для инкрементного алгоритма и до 512 для геометрического алгоритма). Результаты представлены на Рис. 14.

раллельного алгоритма геометрической декомпозиции (справа)

16

В параллельном инкрементном алгоритме для каждого общего числа процессоров N число процессоров Ng, на которых запускалась геометрическая пре-декомпозиция вершин по процессорам, варьировалось в пределах от 4 до N. Для каждого N были найдены минимальное и максимальное времена работы алгоритма при изменении Ng. Ускорение speedupmax на левой диаграмме является отношением максимального времени, полученного на наименьшем N, к минимальному времени, полученному на текущем N. Ускорение speedup rnin является отношением минимального времени, полученного на наименьшем N, к максимальному времени, полученному на текущем N.

Были получены практически линейные графики увеличения ускорений обоих алгоритмов. Большая разница между speedup_max и speedup_min на левой диаграмме объясняется изменением времени геометрической предекомпозиции при увеличении числа процессоров Ng с четырех до 512. Поэтому при больших N геометрическую предекомпозицию выгоднее выполнять на числе процессоров Ng = N/2.

Проведены вычислительные эксперименты по сравнению разбиений на микродомены четырех тетраэдральных сеток (108 •*■ 2.7-108 вершин, 7-Ю8 -ь 1.6-109 тетраэдров, 8-Ю8 1.9-109 ребер), полученных методами PartKway (на графиках обозначен РК) и PartGeomKway (на графиках PGK) пакета PARMET1S, методами GeomDecomp (параллельный алгоритм геометрической декомпозиции, на графиках G) и IncrDecomp (параллельный инкрементный алгоритм, на графиках I) разработанного комплекса программ GRIDSP1DERPAR, иерархическим диффузионным алгоритмом пакета PT-SCOTCH и методами RCB, RIB и HSFC пакета ZOLTAN (Рис. 15, 16).

Рис. 15. Процентное отношение макс, модуля отклонения от ср. арифметического числа вершин в микродомене в разбиениях тетраэдральных сеток на 25600 микродоменов

Макс. откл. 4

□ Макс. откл. 1

□ Макс. откл. 2

□ Макс. откл. 3

□ Макс. откл. 4

о.

Число несв. микродоменов 4

Число несв. микро доменов 1

А

^

® ^ Ö © © © <32. <5=. © LJ

dr.

\

1800 1200 600

О

CL

СЭ

ш о сс

Э et

сп

X

□ Число несв. микро-доменов 1

□ Число несв. микро-доменов 3

□ Число несв. микро-доменов 2

□ Число несв. микро-доменов 4

Рис. 16. Число несвязных микродоменов в разбиениях тетраэдральных сеток на 25600 микродоменов

Результаты показали, что наиболее качественные разбиения получены методами GeomDecomp (параллельный алгоритм геометрической декомпозиции) и IncrDecomp (параллельный инкрементный алгоритм) созданного комплекса программ GRIDSPIDERPAR, RCB пакета ZOLTAN и пакетом PT-SCOTCH. Качество разбиений проверялось по дисбалансу числа вершин в микродоменах, числу несвязных микродоменов и числу разрезанных ребер.

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

□ Макс. откл. 1

□ Макс. откл. 2

□ Макс. откл. 3

□ Макс. откл. 4

Макс. откл. 4

Макс. откл.

60%

-40%

-20%

CL

О

Рис. 17. Процентное отношение максимального модуля отклонения от среднего арифметического числа вершин в домене в разбиениях тетраэдральных сеток на 512 доменов (слева приведены разбиения сразу на домены, справа - разбиения графов микродоменов, методы разбиения на микродомены и разбиения графов на домены объединены знаком '+')

Результаты показали, что дисбаланс числа вершин в доменах, сформированных из микродоменов, не зависит от дисбаланса числа вершин в микродоменах. Лучшие разбиения графов микродоменов на домены получены пакетом METIS. Наиболее качественные разбиения на домены получены методами Ge-omDecomp (параллельный алгоритм геометрической декомпозиции) созданного комплекса программ GRIDSPIDERPAR, RCB пакета ZOLTAN и пакетом РТ-SCOTCH.

На описанных выше физических задачах проведено тестирование разбиений, полученных методами созданного комплекса программ GRIDSPIDERPAR, пакета PARMETIS, пакета ZOLTAN и пакета PT-SCOTCH. Сравнивалась эффективность параллельного счета физических задач пакетом MARPLE3D при распределении сеток по ядрам в соответствии с различными разбиениями.

Для всех расчетных сеток были построены дуальные графы, учитывающие связи между ячейками через ребро. Число вершин в графах 2.8-106 1.2-108, число ребер 2.3-107 1.0-109. Далее в тексте приводятся краткие обозначения для физических задач и соответствующих им графов: divertor - моделирование газоплазменных потоков в диверторе токамака, tube - моделирование распространения ударной волны от взрыва химического взрывчатого вещества в протяженном сооружении (ударная труба) с нетривиальной геометрией, boom и boomL — моделирование распространения ударной волны от приземного взрыва (boomL — сетка с 1.2-108 вершинами).

На Рис. 18-20 приведены результаты разбиений графов на домены различными методами.

76,08%

0,01% 0,01% 0,01% 0,01%

о m m о и 7? £ ^ и I

Рис. 18. Процентное отношение макс, модуля отклонения от ср. арифметического числа вершин в домене в разбиениях графа boom на 4096 доменов

6,5Е+07 5.5Е+07 4.5Е+07 3.5Е+07

lllll II

1.5Е+07

5.0Е+06

х.

Q-

*

О CL

О х

CL

m о ее

ffl ОС

р о.

Рис. 19. Число разрезанных ребер в разбиениях графа tube на 4096 доменов

1.1Е+08

106207852

1.0Е+08

Э.0Е+07

82096962

81373389

78279853

8.0Е+07

7.0Е+07

79739465

■ III

97931486 92740019 jffil ! 88852852 Щ :

111

m

о ос

Рис. 20. Число разрезанных ребер в разбиениях графа ЬоотЬ на 10080 доменов

В соответствии с разбиениями дуальных графов были получены разбиения вершин сеток. Для расчета каждой физической задачи на всех разбиениях выделялось одинаковое машинное время. Были получены числа шагов по времени и модельные времена, до которых досчитали задачи. Распределения разбиений по числу шагов по времени и модельным временам оказались аналогичными, поэтому ниже приводятся только распределения по числу шагов по времени. Распределения представлены на Рис. 21, 22.

8236

8189

8068

5893

5874

5764

4000

И о

I

CL

m

m m о

U 7? U-2 (Л

X

4289

Рис. 21. Число шагов по времени для divertor 1600 — 1401 1465 1433

1228

1130

Рис. 22. Число шагов по времени для tube

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

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

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

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

2. На основе разработанных алгоритмов создан комплекс программ GRIDSPIDERPAR параллельной декомпозиции больших сеток на большое число микродоменов. Проведены вычислительные эксперименты по сравнению разбиений на микродомены и домены четырех тетраэдральных сеток (порядка 108 вершин, 109 тетраэдров), полученных методами созданного комплекса программ GRIDSPIDERPAR, пакета PARMETIS, пакета ZOLTAN и пакетом РТ-SCOTCH, показавшие преимущества алгоритмов декомпозиции созданного комплекса программ GRIDSPIDERPAR в качестве получаемых разбиений.

3. Поставлен ряд вычислительных экспериментов со следующими задачами газовой динамики: моделирование газоплазменных потоков в диверторе тока-мака, моделирование ударной волны в протяженном сооружении и моделирование приземного взрыва. На их основе проведено тестирование различных разбиений расчетных сеток (106 - 108 ячеек), подтвердившее сокращение времени счета на разбиениях, полученных алгоритмами созданного комплекса программ GRIDSPIDERPAR.

Публикации автора по теме диссертации

1. Головченко E.H. Комплекс программ параллельной декомпозиции сеток // Вычислительные методы и программирование. 2010. Т. 11. 360-365.

2. E.H. Головченко. Параллельный пакет декомпозиции больших сеток // Математическое моделирование. 2011. Т. 23. № 10.3-18.

3. Бухановский А. В., Марьин С. В., Князьков К. В., Сиднев А. А., Жабин С. Н„ Баглий А. П., Штейнберг Р. Б., Шамакина А. В., Воеводин В. В., Головченко Е. Н., Фалалеев Р. Т., Духанов А. В., Тарасов А. А., Шамардин Л. В., Моисеенко А. И. Результаты реализации проекта «Мобильность молодых ученых» в 2010 году: развитие функциональных элементов технологии iPSE и расширение состава прикладных сервисов // Известия высших учебных заведений. Приборостроение. 2011. Т. 54. №10. 80 - 86.

4. E.H. Головченко. Разбиение больших сеток // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия «Информационные технологии». Нижний Новгород: Издательство ННГУ. 2012. № 5(2). С. 309-315.

5. Е.Н.Головченко, Е.Ю.Дорофеева, В.А.Гасилов, М.В.Якобовский. Вычислительный эксперимент по оценке качества алгоритмов параллельной декомпозиции больших сеток // Препринты ИПМ им. М.В.Келдыша. 2013. №7. 32 с.

6. E.H. Головченко. Геометрическая декомпозиция сеточных данных // Труды 8-ой Международной Конференции «Высокопроизводительные параллель-

ные вычисления на кластерных системах (НРС-2008)», Казань, Изд. КГТУ 2008. 139.

7. Головченко E.H., Нестеров И.А., Петров Д.В., Якобовский М.В. Параллельные алгоритмы обработки результатов вычислительных экспериментов // Современные проблемы вычислительной математики и математической физики: Международная конференция, Москва, МГУ имени М.В. Ломоносова, 16-18 июня 2009 г.: Тезисы докладов. - М.: Издательский отдел факультета ВМК МГУ имени М.В. Ломоносова; МАКС Пресс. 2009. 316.

8. E.H. Головченко. Комплекс программ параллельной декомпозиции сеток // Труды Международной суперкомпьютерной конференции "Научный сервис в сети ИНТЕРНЕТ: суперкомпьютерные центры и задачи", Изд-во МГУ. 2010. 568-573.

9. E.H. Головченко. Разбиение больших сеток на микро-домены и формирование доменов // Материалы XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах». Нижний Новгород. Издательство Нижегородского госуниверситета. 2011. 87-92.

10. E.H. Головченко. Разбиение больших сеток // Труды Международной суперкомпьютерной конференции "Научный сервис в сети ИНТЕРНЕТ: поиск новых решений", Изд-во МГУ. 2012. 412-420.

11. E.H. Головченко, Е.Ю. Дорофеева, В.А. Гасилов, М.В. Якобовский. Вычислительный эксперимент с алгоритмами параллельной декомпозиции больших сеток // Труды Международной суперкомпьютерной конференции "Научный сервис в сети Интернет: все грани параллелизма" (23-28 сентября 2013г., г. Новороссийск). -М.: Изд-во МГУ. 2013. 82-85.

Подписано в печать 20.03.2014. Формат 60x84/16. Усл. печ. л. 0,9. Тираж 75 экз. Заказ П-60. ИПМ им.М.В.Келдыша РАН. 125047, Москва, Миусская пл., 4

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В.КЕЛДЫША

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

04201457092

Головченко Евдокия Николаевна

ДЕКОМПОЗИЦИЯ РАСЧЕТНЫХ СЕТОК ДЛЯ РЕШЕНИЯ ЗАДАЧ МЕХАНИКИ СПЛОШНЫХ СРЕД НА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

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

ДИССЕРТАЦИЯ

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

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

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

профессор Якобовский М.В.

Москва - 2014

Оглавление

Введение...................................................................................4

Глава 1. Постановка задачи................................................18

1.1 Критерии декомпозиции...........................................................18

1.2 Математические модели...........................................................21

1.3 Моделирование газоплазменных потоков в диверторе токамака.............................................................................................25

1.4 Моделирование воздушных ударных волн..........................28

1.4.1 Моделирование распространения ударной волны от приземного источника энергии взрывного типа..............................................................28

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

1.5 Программный комплекс МАИРЬЕЗБ...................................33

Глава 2. Алгоритмы декомпозиции...................................35

2.1 Модель декомпозиции...............................................................35

2.1.1 Построение графа по сетке...................................................................35

Нодальный граф...............................................................................................................35

Дуальный граф.................................................................................................................35

2.1.2 Модели декомпозиции графов.............................................................36

2.1.3 Модель декомпозиции..........................................................................40

2.2 Обзор и анализ существующих алгоритмов........................41

2.2.1 Простые алгоритмы разбиения сеток..................................................41

2.2.2 Алгоритмы геометрической декомпозиции сеток.............................42

2.2.3 Алгоритмы декомпозиции графов.......................................................44

2.2.3.1 Спектральная бисекция.......................................................................................44

2.2.3.2 Алгоритм локального уточнения.......................................................................45

2.2.3.3 Иерархические алгоритмы..................................................................................49

Огрубление графа........................................................................................................50

Разбиение огрубленного графа..................................................................................52

Восстановление разбиения.........................................................................................53

Локальное уточнение разбиения................................................................................53

Параллельные реализации иерархических алгоритмов...........................................54

2.2.3.4 Диффузионные и генетические алгоритмы......................................................56

Диффузионные алгоритмы.........................................................................................56

Генетические алгоритмы............................................................................................60

2.2.3.5 Оптимизация характеристических отношений доменов.................................62

2.2.3.6 Алгоритмы наращивания доменов....................................................................64

Алгоритм Фархата.......................................................................................................64

Жадный алгоритм с выигрышами..............................................................................64

Алгоритм пузырькового роста...................................................................................65

2.2.3.7 Инкрементный алгоритм декомпозиции графов..............................................66

2.3 Параллельный алгоритм геометрической декомпозиции сеточных данных..............................................................................71

2.3.1 Параллельная сортировка.....................................................................73

2.3.2 Деревья разбиений................................................................................76

2.3.3 Определение количества доменов, формируемых на процессорах. 77

2.3.4 Рекурсивная координатная бисекция вершин по процессорам........79

2.3.5 Локальная рекурсивная координатная бисекция вершин по доменам ..........................................................................................................................82

2.3.6 Принятые решения................................................................................85

2.4 Параллельный инкрементный алгоритм декомпозиции графов.................................................................................................86

2.4.1 Геометрическая декомпозиция............................................................91

2.4.2 Присоединение малых блоков вершин...............................................95

2.4.3 Инициализация доменов и локальное разбиение..............................99

Инициализация доменов...............................................................................................100

Локальное разбиение....................................................................................................101

2.4.4 Перераспределение плохих групп доменов и повторное локальное разбиение.......................................................................................................118

Перераспределение плохих групп доменов................................................................118

2.4.5 Принятые решения..............................................................................123

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

3.1 Комплекс программ параллельной декомпозиции сеток GRIDSPIDERPAR..........................................................................126

3.2 Сравнение параллельного инкрементного алгоритма с последовательным инкрементным алгоритмом.....................127

3.3 Масштабируемость алгоритмов...........................................128

3.4 Разбиения на микродомены...................................................130

3.5 Разбиения на домены..............................................................139

3.6 Результаты тестирования разбиений на физических задачах..............................................................................................144

3.7 Результаты тестирования разбиений на микродомены на физических задачах.......................................................................151

Заключение..........................................................................154

Список литературы

156

Введение

Актуальность.

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

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

В данной работе сделан акцент на статической декомпозиции сеток. Статическая декомпозиция сетки проводится один раз перед началом расчета задачи. В отличие от нее, динамическая декомпозиция выполняется периоди-

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

Задача сбалансированного разбиения сетки на домены сводится к более общей задаче разбиения графа на домены. В этом случае выполняется разбиение графа, аппроксимирующего вычислительные и коммуникационные нагрузки сетки. Существует несколько моделей декомпозиции графов [4], отличающиеся видом графа и критериями сбалансированного разбиения: стандартная модель графа, модель двудольного графа, модель гиперграфа, модель декомпозиции с несколькими ограничениями, модель декомпозиции с несколькими целевыми функциями, модель асимметричного разбиения. В случае разбиения сеток хорошо себя зарекомендовал наиболее распространенный подход, использующий стандартную модель графа. В нем сетка аппроксимируется неориентированным графом С? = (V, Е), где V - множество вершин, Е - множество ребер. И вершины, и ребра, имеют вес. Оптимальным считается разбиение на домены, при котором выровнен суммарный вес вершин в доменах и минимизирован суммарный вес разрезанных ребер (разрезанное ребро - ребро, соединяющее вершины из разных доменов). В данной модели суммарный вес вершин в доменах отвечает за равномерность распределения вычислительной нагрузки по процессорам, которые будут обрабатывать эти домены, а суммарный вес разрезанных ребер - за коммуникационную нагрузку между процессорами. Как известно, поставленная задача декомпозиции графа является КР-полной, поэтому для ее решения используются различные эвристические методы. К геометрическим методам относятся алгоритмы рекурсивных координатной и инерциальной бисекций [5, 6] и декомпозиция с использованием кривой Гильберта [6, 9]. К методам разбиения графов относятся алгоритм спектральной бисекции [7, 8], алгоритм Кегг^Иап-Ып (КЪ) и Р1с1исс1а-МаШ1еу8е8 (БМ) [10], иерархические алгоритмы [10, 11, 12, 13, 6], диффузионные [14, 13] и генетические алгоритмы [15, 16, 17], используемые в рамках иерархического подхода, алгоритмы, оптими-

зирующие характеристические отношения доменов [18, 19], жадные алгоритмы (greedy methods), или алгоритмы наращивания доменов [20, 7, 21], и инкрементный алгоритм декомпозиции графов [22]. Эти алгоритмы, за исключением инкрементного, реализованы в следующих последовательных пакетах декомпозиции графов: METIS, JOSTLE, SCOTCH, CHACO и PARTY. К параллельным пакетам относятся PARMETIS (параллельная версия пакета METIS), JOSTLE, PT-SCOTCH (параллельная версия пакета SCOTCH) и ZOLTAN.

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

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

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

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

о

1.2-10 ячеек, требуется порядка 200 ГБ), поэтому для декомпозиции нужен параллельный алгоритм. Методы разбиения графов параллельных пакетов PARMETIS, JOSTLE, PT-SCOTCH и ZOLTAN основываются на иерархических алгоритмах [25, 26, 13, 27, 6], состоящих из следующих частей: поэтапное огрубление графа, декомпозиция самого маленького из полученных графов и отображение разбиения на предыдущие графы с периодическим локальным уточнением границ доменов. Недостатком таких алгоритмов является образование доменов, границы которых состоят из неоптимальных наборов сегментов [18, 28]. В частности, домены могут оказаться несвязными. Такое ухудшение качества доменов для некоторых задач является критичным. На доменах с длинными границами, или сложной конфигурацией, алгоритмы решения систем линейных уравнений сходятся за большее число итераций. Связность микродоменов важна при хранении больших сеток, поскольку на связных микродоменах коэффициент сжатия информации о сеточных данных, как правило, будет больше. В алгоритме композиции подобластей [24] у несвязных подобластей длиннее приграничные полосы, в которых требуется повторное вычисление значений, а на узких приграничных полосах возникают проблемы с применимостью метода. Несвязные домены с

оторванными ячейками являются неприемлемыми, например, для распараллеливания методики ТИМ-20 решения задач механики сплошной среды [29] на нерегулярных многоугольных сетках произвольной структуры.

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

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

Цели работы.

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

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

• Разработка программного комплекса декомпозиции больших сеток.

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

Научная новизна.

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

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

Теоретическая и практическая значимость.

В диссертационной работе были разработаны два алгоритма: параллельный алгоритм геометрической декомпозиции сеточных данных и параллельный инкрементный алгоритм декомпозиции графов, на основе которых был создан комплекс программ ОШО$РГОЕ11РА11 декомпозиции больших сеток. Разработанные алгоритмы поддерживают два основных этапа декомпозиции больших сеток: предварительную декомпозицию сетки по процессорам и параллельную декомпозицию сетки высокого качества. [103 - 107].

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

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