Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Пакет параллельной декомпозиции больших сеток GridSpiderPar * Е.Н. Головченко, М.В. Якобовский Институт прикладной математики им. М.В.Келдыша РАН Задача рациональной декомпозиции расчетных сеток возникает при численном моде- лировании на высокопроизводительных вычислительных системах проблем механи- ки сплошных сред, импульсной энергетики, электродинамики и др. Число процессо- ров, на котором будет считаться вычислительная задача, как правило, заранее неиз- вестно. Поэтому имеет смысл предварительно однократно разбить сетку на большое число микродоменов, а потом формировать из них домены. Методы разбиения гра- фов параллельных пакетов ParMETIS, Jostle, PT-Scotch и Zoltan основываются на ие- рархических алгоритмах, недостатком которых является образование несвязных до- менов. Другим недостатком указанных пакетов является получение сильно несбалан- сированных разбиений. Разработан пакет параллельной декомпозиции больших сеток GridSpiderPar. Проведены вычислительные эксперименты по сравнению различных разбиений на микродомены, разбиений графов микродоменов на домены, а также разбиений сразу на домены нескольких сеток (108 вершин, 109 элементов), получен- ных методами созданного комплекса программ GridSpiderPar и пакетов ParMETIS, Zoltan и PT-Scotch. Качество разбиений проверялось по дисбалансу числа вершин в доменах, числу несвязных доменов и числу разрезанных ребер, а также эффективно- сти параллельного счета задач газовой динамики при распределении сеток по ядрам в соответствии с различными разбиениями. Полученные результаты выявили преиму- щества разработанных алгоритмов. 1. Введение Задача рациональной декомпозиции расчетных сеток возникает при численном моделиро- вании на высокопроизводительных вычислительных системах проблем механики сплошных сред, импульсной энергетики, электродинамики и многих других. При распараллеливании по- добных вычислительных приложений используется метод геометрического параллелизма, при котором сетка, аппроксимирующая расчетную область, распределяется между процессорами по геометрическому признаку. В ходе расчета каждый процессор обрабатывает свою часть сетки. Эффективность работы многопроцессорной вычислительной системы определяется тем, на- сколько равномерно распределена сетка по процессорам и насколько минимизированы затраты на передачу данных между процессорами. Объем передаваемых между процессорами данных зависит от числа связей между распределенными по процессорам доменами (частями сеток). Задача сбалансированного разбиения сетки на домены сводится к более общей задаче раз- биения графа на домены. В этом случае выполняется разбиение графа, аппроксимирующего вычислительные и коммуникационные нагрузки сетки. Сетка аппроксимируется неориентиро- ванным графом G = (V, E), где V – множество вершин, E – множество ребер. И вершины, и реб- ра, имеют вес. Оптимальным считается разбиение на домены, при котором выровнен суммар- ный вес вершин в доменах и минимизирован суммарный вес разрезанных ребер (разрезанное ребро – ребро, соединяющее вершины из разных доменов). Поставленная задача декомпозиции графа является NP-полной, поэтому для ее решения используются различные эвристические методы. Число процессоров, на котором будет считаться вычислительная задача, как правило, зара- нее неизвестно. Поэтому имеет смысл предварительно однократно разбить сетку на большое число микродоменов, а потом формировать из них домены. Количество микродоменов на не- * Работа выполнена при поддержке РФФИ (гранты 13-01-12073 офи_м, 14-01-00663 А, 14-07-00712 А и 15-07-04213 А). 303 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org сколько порядков меньше числа вершин, поэтому многократное разбиение микродоменов на домены быстрее многократного разбиения всей сетки. Широко известны методы декомпозиции областей, используемые для решения линейных и нелинейных систем уравнений, возникающих при дискретизации дифференциальных уравне- ний с частными производными, например, метод Шварца [1]. В нем геометрическая область разбивается на множество микродоменов, что позволяет организовать эффективные параллель- ные вычисления. Еще одной областью использования разбиения сеток на микродомены является хранение больших сеток. Разбиение сеток на микродомены позволяет увеличить коэффициент компрес- сии сеточных данных. Областью данного исследования являются нерегулярные сетки, содержащие 109 и более вершин. В настоящее время такие сетки невозможно разместить в памяти одного процессора, поэтому для декомпозиции нужен параллельный алгоритм. Методы разбиения графов парал- лельных пакетов ParMETIS, Jostle, PT-Scotch и Zoltan основываются на иерархических алго- ритмах, состоящих из следующих частей: поэтапное огрубление графа, декомпозиция самого маленького из полученных графов и отображение разбиения на предыдущие графы с периоди- ческим локальным уточнением границ доменов. Недостатком таких алгоритмов является обра- зование доменов, границы которых состоят из неоптимальных наборов сегментов. В частности, домены могут оказаться несвязными. Такое ухудшение качества доменов для некоторых задач является критичным. На доменах с длинными границами или сложной конфигурацией алго- ритмы решения систем линейных уравнений сходятся за большее число итераций. Связность микродоменов важна при хранении больших сеток, поскольку на связных микродоменах коэф- фициент сжатия информации о сеточных данных, как правило, будет больше. В алгоритме композиции подобластей у несвязных подобластей длиннее приграничные полосы, в которых требуется повторное вычисление значений, а на узких приграничных полосах возникают про- блемы с применимостью метода [2]. Несвязные домены с оторванными ячейками являются не- приемлемыми, например, для распараллеливания методики ТИМ-2D решения задач механики сплошной среды на нерегулярных многоугольных сетках произвольной структуры [3]. Другим недостатком указанных пакетов является получение сильно несбалансированных разбиений. В частности, в разбиениях, получаемых пакетом ParMETIS, числа вершин в доменах могут отличаться в два раза. К тому же разбиения больших сеток на большое число микродо- менов не всегда удается получить методами существующих пакетов разбиения графов. Вышесказанное обусловило разработку пакета параллельной декомпозиции больших сеток GridSpiderPar. 2. Алгоритмы параллельной декомпозиции Разработаны два алгоритма: параллельный алгоритм геометрической декомпозиции сеточ- ных данных и параллельный инкрементный алгоритм декомпозиции графов, на основе которых был создан комплекс программ GridSpiderPar декомпозиции больших сеток. Разработанные алгоритмы поддерживают два основных этапа декомпозиции больших сеток: предварительную декомпозицию сетки по процессорам и высокого качества параллельную декомпозицию сетки. Оба алгоритма рассчитаны на нерегулярные сетки, содержащие 109 и более вершин. 2.1 Параллельный инкрементный алгоритм декомпозиции графов Параллельный инкрементный алгоритм декомпозиции графов пакета GridSpiderPar основан на последовательном инкрементном алгоритме декомпозиции графов [4]. Достоинством ин- крементного алгоритма является формирование преимущественно связных доменов. Параллельный инкрементный алгоритм предполагает выполнение следующих этапов:  Геометрическое распределение вершин по процессорам с помощью разработанного параллельного алгоритма геометрической декомпозиции сеточных данных.  Перераспределение малых блоков вершин (Рис. 1). 304 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 1. Фрагменты геометрического распределения вершин по процессорам (слева) и перераспреде- ления малых блоков вершин (справа)  Локальное разбиение вершин на каждом из процессоров на домены последовательным инкрементным алгоритмом декомпозиции графов. На Рис. 2 слева четко выражены границы между процессорами, домены не пересекают эти границы.  Перераспределение плохих групп доменов. Сбор каждой группы плохих доменов на одном процессоре.  Локальное повторное разбиение плохих групп доменов инкрементным алгоритмом де- композиции графов. На Рис. 2 справа видно, что после перераспределения плохих групп доменов и их повторного разбиения домены вышли за границы между процессо- рами. Рис. 2. Локальное разбиение (слева), сбор плохих групп доменов и их повторное разбиение (справа) При выполнении локального разбиения вначале выбираются инициализирующие вершины для доменов. Далее разбиение проводится посредством итерационного процесса, на каждом шаге которого выполняются следующие действия:  Инкрементный рост доменов и диффузное перераспределение вершин между домена- ми (Рис. 3, 4). Рис. 3. Инкрементный рост доменов  Локальное уточнение доменов алгоритмом KL/FM (Рис. 4). Границы доменов стали более гладкими. Однако в разбиении присутствуют несвязные домены (самый светлый домен). 305 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 4. Диффузное перераспределение вершин между доменами (слева) и локальное уточнение (справа)  Проверка качества доменов. Если качество доменов соответствует заданному, разбие- ние считается найденным, и происходит выход из цикла, иначе - переход к следующе- му этапу.  Освобождение части вершин плохих доменов и переход к первому этапу. Плохими до- менами считаются домены, качество которых не соответствует заданному, и соседи та- ких доменов. В плохих доменах часть вершин освобождается, то есть вновь считается нераспределенной (Рис. 5). Освобождается часть внешних оболочек, а затем все ком- поненты связности, кроме той, которая содержит наибольшее число вершин. Рис. 5. Освобождение части вершин плохих доменов (слева) и результирующее разбиение (справа) В результирующем разбиении на Рис. 5 видно, что теперь самый светлый домен является связным. Качество доменов проверяется следующим образом. Все вершины, расположенные на гео- метрической границе графа (вершины, аппроксимирующие границу моделируемой области) и на границах между доменами, считаются принадлежащими первой оболочке своего домена. В каждом домене вершинами второй оболочки считаются соседи вершин из первой оболочки данного домена, которые так же принадлежат этому домену и не попали в первую оболочку. Остальные оболочки вычисляются аналогично. На Рис. 6 представлены оболочки домена при условии, что вся сетка принадлежит одному домену. Проверяется связность оболочек каждого домена и вычисляется номер несвязной оболочки с наименьшим номером (номер первой не- связной оболочки) в каждом домене. Хорошими считаются те домены, номер первой несвязной оболочки в которых не меньше заданного порогового значения. 306 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 6. Оболочки домена 2.2 Параллельный алгоритм геометрической декомпозиции сеточных данных Параллельный алгоритм геометрической декомпозиции сеточных данных пакета GridSpiderPar основывается на методе рекурсивной координатной бисекции [5]. На каждом эта- пе рекурсивной бисекции область разбивается на две части. Полученные подобласти разбива- ются дальше аналогичным образом до тех пор, пока в подобластях не останется по одному до- мену. Основные этапы алгоритма следующие:  Случайное начальное распределение вершин по процессорам. Начальное распределе- ние может быть любым, например, в соответствии с порядковыми номерами вершин.  Рекурсивная координатная бисекция вершин по процессорам (Рис. 7): o Параллелепипед, заключающий в себе сетку, разбивается на две части. Выбирается координатная ось, вдоль которой параллелепипед имеет наибольшую протяжен- ность. Параллелепипед разрезается перпендикулярно выбранной оси. o Группа процессоров делится на две, далее каждая из групп делит свой блок вер- шин аналогичным образом. Для разделения блока вершин используется парал- лельная сортировка [6] по выбранной оси координат (а также по остальным для разрезания секущей плоскости). Рис. 7. Геометрическое разбиение сетки на семь доменов на трех процессорах. Первые два этапа разбиения: распределение вершин по процессорам  Локальная рекурсивная координатная бисекция вершин по доменам. Дальнейшее раз- биение на домены проводится локально на каждом процессоре (Рис. 8). 307 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 8. Результат геометрического разбиения сетки на семь доменов на трех процессорах Достоинством геометрического алгоритма является то, что при разбиении на равные доме- ны числа вершин в получаемых доменах отличаются не больше, чем на единицу. Подобный алгоритм реализован в пакете Zoltan [5]. Отличие рекурсивной координатной бисекции созданного алгоритма от аналогичного алгоритма в пакете Zoltan состоит в том, что в нем секущая плоскость (медиана) при необходимости разрезается по нескольким координатам, что позволяет обрабатывать ситуации наличия на одной плоскости множества вершин с одина- ковым значением координаты (Рис. 9). В пакете Zoltan вершины из медианы распределяются по областям произвольным образом, что увеличивает число разрезанных ребер. Рис. 9. Разрезание секущей плоскости Более подробное описание разработанных алгоритмов можно найти в статье [7]. 3. Результаты 3.1 Разбиение на микродомены и домены Проведены вычислительные эксперименты по сравнению разбиений на микродомены, раз- биений графов микродоменов на домены, а также разбиений сразу на домены нескольких тет- раэдральных сеток (108 ÷ 2.7∙108 вершин, 7∙108 ÷ 1.6∙109 тетраэдров, 8∙108 ÷ 1.9∙109 ребер) (Рис. 10), полученных методами разработанного пакета GridSpiderPar и пакетов ParMETIS, Zoltan и PT-Scotch. Качество разбиений проверялось по дисбалансу числа вершин в доменах, числу не- связных доменов и числу разрезанных ребер. Рис. 10. Тетраэдральные сетки В сравнении участвовали следующие методы: 308 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org  IncrDecomp – параллельный инкрементный алгоритм декомпозиции графов пакета GridSpiderPar.  PartKway – иерархический алгоритм разбиения графов пакета ParMETIS.  PartGeomKway - иерархический алгоритм разбиения графов пакета ParMETIS, выпол- няющий предварительное геометрическое разбиение с использованием кривой Гиль- берта.  PT-Scotch – иерархический диффузионный алгоритм пакета PT-Scotch.  GeomDecomp – параллельный алгоритм геометрической декомпозиции сеточных дан- ных пакета GridSpiderPar.  RCB – алгоритм рекурсивной координатной бисекции пакета Zoltan. Вначале сетки были разбиты на 25600 микродоменов (Таблицы 1 и 2). Результаты Таблицы 1 показывают, что дисбаланс числа вершин в микродоменах в разбиениях, полученных метода- ми пакета ParMETIS, достигает 60%, в разбиениях, сформированных пакетом PT-Scotch – 8%. В то время как почти во всех разбиениях, полученных методом IncrDecomp, дисбаланс меньше 1%. В разбиениях, образованных геометрическими методами, как и предполагалось, числа вершин в микродоменах отличаются не более чем на единицу. Здесь и далее под дисбалансом подразумевается процентное отношение максимального модуля отклонения от среднего ариф- метического числа вершин в микродомене. Таблица 1. Дисбаланс числа вершин в 25600 микродоменах, % Методы Сетка 1 Сетка 2 Сетка 3 Сетка 4 разбиение графов IncrDecomp 3,5 0,1 0,3 0,2 PartKway 53,4 59,8 58,6 64,3 PartGeomKway 48,7 50,4 62,4 56,5 PT-Scotch 8,3 8,3 8,3 8,3 геометрические методы GeomDecomp 0,01 0,01 0,02 0,01 RCB 0,01 0,01 0,02 0,01 Как видно из Таблицы 2, число несвязных микродоменов в разбиениях, полученных мето- дами пакета ParMETIS, достигает 69 из 25600, как и в разбиениях, образованных геометриче- скими методами. Для пакета PT-Scotch это число достигает 7. Обычно в разбиениях, получае- мых пакетом PT-Scotch, почти все микродомены связны, но PT-Scotch не гарантирует связ- ность, формируемых микродоменов. И почти во всех разбиениях, образуемых методом IncrDecomp, все микродомены связны. Таблица 2. Число несвязных микродоменов из 25600 Методы Сетка 1 Сетка 2 Сетка 3 Сетка 4 разбиение графов IncrDecomp 0 0 0 1 PartKway 69 35 37 29 PartGeomKway 67 34 28 37 PT-Scotch 7 0 2 4 геометрические методы GeomDecomp 62 38 16 33 RCB 64 43 14 44 Затем по разбиениям тетраэдральных сеток на 25600 микродоменов, полученных методами пакета ParMETIS и разработанного пакета GridSpiderPar, были составлены графы связей между 309 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org микродоменами с весами вершин, соответствующими количеству вершин в микродоменах. Графы микродоменов были разбиты на 512 доменов методами PartGraphRecursive и PartGraphKway пакета METIS, методом PartKway пакета ParMETIS и методом IncrDecomp па- кета GridSpiderPar, запущенными на одном процессоре. Проведено сравнение различных вари- антов разбиений графов микродоменов на домены между собой и с разбиениями сразу на 512 доменов, полученных методами PartKway и PartGeomKway пакета ParMETIS, диффузионным алгоритмом пакета PT-Scotch и методом GeomDecomp пакета GridSpiderPar. Результаты Таблицы 3 показывают, что дисбаланс числа вершин в доменах в разбиениях, полученных напрямую методами пакета ParMETIS, достигает 50%, в разбиениях, сформиро- ванных пакетом PT-Scotch – 5%. Дисбаланс числа вершин в доменах, сформированных из мик- родоменов, не зависит от дисбаланса числа вершин в микродоменах, и составляет около 5%. Видимо, это связано с малым числом микродоменов в домене (50) и недостаточной чувстви- тельностью алгоритмов разбиения графов к весам вершин. Наименьший дисбаланс числа вер- шин в доменах оказался в разбиениях графов микродоменов, сформированных методами пакета METIS. Таблица 3. Дисбаланс числа вершин в 512 доменах, % Методы Сетка 1 Сетка 2 Сетка 3 Сетка 4 разбиение графов PartKway 12,9 20,6 17,6 28,4 PartGeomKway 31,1 35,7 44,2 51,4 PT-Scotch 4,9 1,7 2,8 2,9 геометрические методы GeomDecomp 0 0 0 0 разбиение графов микродоменов Среднее арифм. 5,3 5,4 3,7 5,1 Время работы алгоритма IncrDecomp в несколько раз больше времен работы остальных ал- горитмов. Время работы алгоритма GeomDecomp не отличается от времен работы других гео- метрических алгоритмов. Однако алгоритмы разрабатывались в качестве инструментов стати- ческой декомпозиции, которая проводится один раз перед расчетом, а времена расчета физиче- ских задач в разы больше, чем времена получения разбиений. Поэтому увеличение времени получения разбиений не является таким существенным. 3.2 Тестирование различных разбиений на задачах газовой динамики На задачах газовой динамики проведено тестирование разбиений, полученных методами разработанного пакета GridSpiderPar и пакетов ParMETIS, Zoltan и PT-Scotch. Первая задача – моделирование газоплазменных потоков в диверторе токамака ITER. То- камак – тороидальная установка для магнитного удержания плазмы с целью достижения усло- вий, необходимых для протекания управляемого термоядерного синтеза. Дивертор является одним из ключевых компонентов токамака ITER (Рис. 11). Он расположен вдоль нижней части вакуумной камеры и служит для приема потоков примесей и излучений из плазмы. 310 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 11. Моделирования газоплазменных течений в диверторе токамака ITER Расчетная область аппроксимировалась тетраэдральной сеткой, содержащей порядка 2.8∙106 ячеек (divertor). Считалась полная система уравнений радиационной магнитной газовой динамики с учетом радиационного и кондуктивного теплопереноса и турбулентной вязкости. Использовались явные и неявные схемы. Вычисления проводились на 256 ядрах. Вторая задача – моделирование распространения ударной волны от приземного источника энергии взрывного типа (Рис. 12). Для моделирования приземного взрыва была выбрана куби- ческая область, которая аппроксимировалась гексаэдральными сетками, содержащими порядка 6.1∙107 (boom) и 1.16∙108 (boomL) ячеек со сгущением в области взрыва. Вычисления проводи- лись на 4096 и 10080 ядрах, соответственно. Считалась полная система уравнений газовой ди- намики с учетом кондуктивного теплопереноса. Турбулентные потоки не учитывались. Ис- пользовались явные и неявные схемы. Рис. 12. Апроксимация изоповерхностей давления на расчетную сетку в момент времени t=1000 мс Для всех расчетных сеток были построены дуальные графы с числом вершин 2.8∙106 ÷ 1.2∙108 и числом ребер 2.3∙107 ÷ 1.0∙109. Разбиения дуальных графов были получены методами пакетов GridSpiderPar, ParMETIS, Zoltan и PT-Scotch. К списку сравниваемых методов были добавлены два метода:  RIB – алгоритм рекурсивной инерциальной бисекции пакета Zoltan.  HSFC – алгоритм пакета Zoltan, выполняющий геометрическое разбиение с использо- ванием кривой Гильберта. Для разборчивости на Рис. 13 – 15 метод IncrDecomp обозначен I, PartKway – PK, PartGeomKway – PGK, PT-Scotch – PTScotch и GeomDecomp – G. Методы IncrDecomp и GeomDecomp окрашены отличающимися цветами, а алгоритмы разбиения графов и геометри- ческие алгоритмы разделены между собой. На Рис. 13, 14 отображен дисбаланс числа вершин в доменах с точки зрения недостатка числа вершин и избытка числа вершин, соответственно. Недостаток числа вершин в доменах в разбиениях, полученных методами пакета ParMETIS, достигает 80%, избыток – 5%. Дисбаланс в разбиениях, сформированных пакетом PT-Scotch, в обоих случаях около 5%, а в разбиениях, образованных методом IncrDecomp, дисбаланс меньше 0,1%. 311 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 13. Дисбаланс числа вершин в доменах: недостаток вершин (boom) Рис. 14. Дисбаланс числа вершин в доменах: избыток вершин (boom) Наименьшее число разрезанных ребер получено методами пакета ParMETIS, или алгорит- мом IncrDecomp разработанного пакета GridSpiderPar. Проведено сравнение эффективности параллельного счета физических задач пакетом MARPLE3D [8] при распределении сеток по ядрам в соответствии с различными разбиениями. Параллельный программный комплекс MARPLE3D создан в ИПМ им. М.В.Келдыша РАН, и его предметной областью являются задачи двухтемпературной радиационной магнитной гид- родинамики. Для расчета каждой физической задачи на всех разбиениях выделялось одинако- вое машинное время. Были получены числа шагов по времени, до которых досчитали задачи. Полученные результаты (Рис. 15) демонстрируют, что по числу шагов по времени метод IncrDecomp опережает остальные методы декомпозиции графов, а метод GeomDecomp не- сколько опережает другие геометрические методы. На разбиениях, полученных методами раз- биения графов, числа шагов по времени больше, чем на разбиениях, полученных геометриче- скими методами, не учитывающими связи между вершинами. 312 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Рис. 15. Число шагов по времени за 1 час (divertor) 3.3 Тестирование разбиений графов микродоменов на задаче приземного взрыва Дуальный граф boomL, содержащий 1.2∙108 вершин и 1.0∙109 ребер, был разбит на различ- ное число микродоменов (от 24576 до 196608) и сразу на 3072 домена алгоритмом IncrDecomp разработанного пакета GridSpiderPar. Составлены графы связей микродоменов с весами вер- шин, соответствующими количеству вершин в микродоменах. Графы микродоменов были раз- биты алгоритмом IncrDecomp на 3072 домена. Для расчета задачи моделирования распространения ударной волны от приземного взрыва на всех разбиениях выделялось одинаковое машинное время (5 часов). Были получены числа шагов по времени, до которых досчитала задача. Таблица 4. Тестирование разбиений графов микродоменов на задаче приземного взрыва Шаги Микро- Соседние Информация Микро- Дисбаланс, Разрезанные по домены домены о сетке домены % ребра време- в домене (макс.) ни имя: 3072 1 9,1 53 140 207 28 1107 BoomL 24576 8 62,5 64 611 859 25 833 49152 16 37,5 66 566 874 25 880 116 214 272 98304 32 18,7 68 841 339 23 949 гексаэдров 196608 64 7,9 68 207 798 21 999 Как видно из Таблицы 4, разбиения содержали от 1 (разбиение сразу на 3072 домена) до 64 микродоменов в домене. Чем больше микродоменов, тем меньше дисбаланс получаемых раз- биений, тем меньше максимальное число соседних доменов, но тем больше общее число разре- занных ребер. Увеличение общего числа разрезанных ребер объясняется тем, что при составле- нии графов микродоменов не учитывались веса ребер между микродоменами. Максимальное число соседних доменов влияет на количество обменов между процессорами, обрабатывающи- 313 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org ми данные домены. С увеличением числа микродоменов, увеличивается также число шагов по времени, полученных на разбиениях. Что говорит о том, что для задачи моделирования при- земного взрыва равномерность распределения вычислительной нагрузки по процессорам и ко- личество обменов между процессорами критичнее, чем объем передаваемых данных. При срав- нении разбиения сразу на 3072 домена и разбиений графов микродоменов заметно, что в раз- биении, составленном из 196608 микродоменов (64 микродомена в домене), дисбаланс числа вершин в доменах меньше, чем в разбиении сразу на домены, и меньше максимальное число соседних доменов. Результат, объясняется тем, что при разбиении на определенное количество доменов не всегда удается получить требуемый дисбаланс. Например, при разбиении данного графа на 4096 доменов получаемый дисбаланс составлял 0.03%, что значительно меньше 9.1%, полученных при разбиении на 3072 домена. Число шагов по времени, полученных на разбие- нии, составленном из 196608 микродоменов, не намного меньше, чем полученных на разбиении сразу на домены. Таким образом, можно сделать вывод, что при достаточном количестве микродоменов в доменах разбиения графов микродоменов не уступают по качеству разбиению сразу на домены, что подтверждается малым уменьшением скорости счета рассматриваемой физической задачи. К тому же на декомпозицию графа микродоменов при массовых расчетах требуется меньше процессоро-часов. 4. Заключение Разработан пакет параллельной декомпозиции больших сеток GridSpiderPar, в который во- шли два алгоритма: параллельный алгоритм геометрической декомпозиции сеточных данных и параллельный инкрементный алгоритм декомпозиции графов. Разработанные алгоритмы под- держивают два основных этапа декомпозиции больших сеток: предварительную декомпозицию сетки по процессорам и высокого качества параллельную декомпозицию сетки. Оба алгоритма рассчитаны на нерегулярные сетки, содержащие 109 и более вершин. Достоинством инкремент- ного алгоритма является формирование преимущественно связных доменов. Проведены вычислительные эксперименты по сравнению различных разбиений на микро- домены, разбиений графов микродоменов на домены, а также разбиений сразу на домены не- скольких сеток (108 вершин, 109 элементов), полученных методами созданного комплекса про- грамм GridSpiderPar и пакетов ParMETIS, Zoltan и PT-Scotch. Качество разбиений проверялось по дисбалансу числа вершин в доменах, числу несвязных доменов и числу разрезанных ребер, а также эффективности параллельного счета задач газовой динамики при распределении сеток по ядрам в соответствии с различными разбиениями. Полученные результаты выявили преимуще- ства разработанных алгоритмов. Вычисления проводились на кластерах МВС-100К, Ломоносов и Helios. Литература 1. Barry Smith, Petter Bjorstad, William Gropp. Domain decomposition: parallel multilevel methods for elliptic partial differential equations // Cambridge University Press. 1996. 225 pp. 2. А. И. Илюшин, А. А. Колмаков, И. С. Меньшов. Построение параллельной вычислительной модели путем композиции вычислительных объектов // Математическое моделирование. 2011. T. 23. № 7. 97-113. 3. А. А. Воропинов. Декомпозиция данных для распараллеливания методики ТИМ-2D и кри- терии оценки ее качества // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование:», вып. 4. 2009. №37(170). 40-50. 4. М. В. Якобовский. Инкрементный алгоритм декомпозиции графов // Вестник Нижегород- ского университета им. Н.И.Лобачевского. Серия «Математическое моделирование и опти- мальное управление». Вып. 1(28). Нижний Новгород: Издательство ННГУ. 2005. 243-250. 5. Boman E., Devine K., Catalyurek U., Bozdag D., Hendrickson B., Mitchell W.F., Teresco J. Zoltan: Parallel Partitioning, Load Balancing and Data-Management Services. Developer’s Guide, 314 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Version 3.3 // Sandia National Laboratories, Copyright © 2000-2010, URL: http://www.cs.sandia.gov/Zoltan/dev_html/dev.html. 6. Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных // В кн.: Фундаментальные физико-математические проблемы и моделирование технико- технологических систем: Сб. науч. тр., Выпуск 7 / Под ред. Л.А. Уваровой. – М.: Издатель- ство "Янус-К". 2004. 235-249. 7. Е.Н. Головченко. Параллельный пакет декомпозиции больших сеток // Математическое мо- делирование. 2011. Т. 23. № 10. 3-18. 8. В.А. Гасилов и др. Пакет прикладных программ MARPLE3D для моделирования на высо- копроизводительных ЭВМ импульсной магнитоускоренной плазмы // Матем. моделирова- ние. 2012. Т.24. №1. 55–87. 315 Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org Parallel partitioning tool GridSpiderPar for large mesh decomposition Evdokia Golovchenko and Mikhail Yakobovskiy Keywords: parallel programming, graph partitioning, mesh decomposition The problem of load balancing arises in parallel mesh-based numerical solution of problems of continuum mechanics, energetics, electrodynamics etc. on high-performance computing systems. The number of processors to run a computational problem is often unknown. It makes sense, therefore, to partition a mesh into a great number of microdomains which then are used to create subdomains. Graph partitioning methods implemented in state-of-the-art parallel partitioning tools ParMETIS, Jostle, PT-Scotch and Zoltan are based on multilevel algorithms. That approach has a shortcoming of forming unconnected subdomains. Another shortcoming of present graph partitioning methods is generation of strongly imbalanced partitions. The program package for parallel large mesh decomposition GridSpiderPar was developed. We compared different partitions into microdomains, microdomain graph partitions and partitions into subdomains of several meshes (10^8 vertices, 10^9 elements) obtained by means of the partitioning tool GridSpiderPar and the packages ParMETIS, Zoltan and PT-Scotch. Balance of the partitions, edge-cut and number of unconnected subdomains in different partitions were compared as well as the computational performance of gas-dynamic problem simulations run on different partitions. The obtained results demonstrate advantages of the devised algorithms.