В работе представлено описание методов повышения эффективности вычислительных экспериментов на неструктурированных сетках большого размера. Приводятся результаты тестирования предложенных алгоритмов на примере расчетов с использованием тетраэдральных сеток, содержащих до 1.5 миллиарда элементов. Вычислительная мощность современных суперкомпьютеров позволяет решать актуальные задачи математической физики, связанные с обработкой сверхбольших объемов данных на неструктурированных сетках. Разработанные на основе метода геометрического параллелизма распределенные алгоритмы по определению характеризуются высокой масштабируемостью. Число параллельных процессов приложения здесь, теоретически, ограничивается только числом сеточных элементов. В свою очередь число сеточных элементов среднестатистической расчетной сетки, как минимум, на несколько порядков превосходит число процессорных ядер лидирующих по показателю быстродействия многопроцессорных систем. А, следовательно, есть основания утверждать, что на любом из существующих суперкомпьютеров можно провести расчет, например, задачи газодинамического обтекания на неструктурированной сетке с таким числом элементов, что лимит параллелизма не будет исчерпан. Фактическая производительность распределенных вычислений на неструктурированных сетках определяется эффективностью методов решения следующих прикладных задач: балансировка загрузки процессов; стабилизация производительности вычислений на неструктурированных сетках; распределенная запись данных контрольных точек; распределенное хранение и сжатие больших объемов сеточных данных. Первые два пункта в списке влияют на быстродействие вычислительного ядра. Последующие два определяют эффективность решения не менее важных с точки зрения затрат времени проблем распределенного хранения и обработки данных широкомасштабных вычислительных экспериментов.
Методы повышения эффективности широкомасштабных распределенных вычислительных экспериментов на неструктурированных сетках* Далее топология преобразованной сетки задается ее огрубленным графом - графом доменов и их связей (рис. 1). Огрубленный граф используется на этапе балансировки загрузки. Число вершин графа примерно на два порядка больше максимального числа параллельных процессов приложения, но существенно меньше числа сеточных элементов. Поэтому декомпозиция графа на части, обрабатываемые параллельными процессами приложения, может быть выполнена в последовательном режиме.
Результаты балансировки загрузки для преобразованной к двухуровневому представлению
тетраэдральной сетки (209 028 730 узлов и 1 244 316 672 тетраэдров) показаны на рис. 2.
Значения расчетных параметров определяются в узлах сетки. На графиках отображены
зависимости минимального и максимального числа обрабатываемых процессами сеточных узлов на
фоне равномерного распределения. Дисбаланс (отношение максимального размера подобласти к
осредненной величине) не превосходит 15%. В то же время прямое разбиение сеточного графа
с использованием процедур библиотеки ParMETIS [
Рис. 2. Результаты балансировки загрузки Геометрия неструктурированных сеток задается координатами сеточных узлов и индексами вершин сеточных элементов. Распределенное хранение этих данных может быть организовано в рамках той же двухуровневой схемы. Геометрия сетки записывается на диск как множество файлов, каждый из которых содержит описание одного или нескольких доменов. Аналогичный принцип структурирования данных можно использовать и при записи расчетных параметров.
а) цепочка по сеточным элементам б) преобразование двух элементов последовательно
сти
Рис. 3. Циклический метод сжатия
Для сокращения объема записываемых на диск данных целесообразно использовать
комбинацию стандартного [
а) блок из пяти элементов б) блок из трех элементов
Рис. 4. Блочный метод сжатия При использовании блочного метода сжатия сеточные элементы разбиваются на группы размером от одного до пяти тетраэдров. Каждая группа описывается четверкой индексов вершин центрального элемента, признаками присутствия связей по каждой из граней (четыре бита) и индексами четвертых вершин смежных центральному по соответствующей грани тетраэдров (рис. 4). Сформированные в результате сжатия циклическим или блочным методом структуры данных далее повторно упаковываются с использованием процедур библиотеки GZIP.
Результаты упаковки геометрии трех тетраэдральных сеток циклическим (C) методом, блочным (B) методом, методом GZIP и их комбинацией представлены в таблице 1. Эффективность упаковки данных специализированными методами оказывается выше по сравнению с алгоритмом GZIP, а применение комбинации методов сжатия улучшает коэффициент упаковки более чем в два раза.
Таблица 1. Коэффициент упаковки данных Сетка (число узлов/число тетраэдров) 7320 / 37964 58926 / 363124 455160 / 2647040
B / B + GZIP 2.65 / 5.99 2.69 / 5.04 2.72 / 4.48 Коэффициент сжатия данных
C / C + GZIP 3.09 / 6.65 3.19 / 6.07 3.28 / 5.68
GZIP 2.09 1.74 2.59 Алгоритмы моделирования задач газовой динамики на неструктурированных сетках характеризуются низким соотношением числа арифметических операций на единицу данных. Поэтому быстродействие ядра сильно зависит от метода индексации сеточных элементов, определяющего порядок доступа к данным в оперативной памяти. Исходная индексация сеточных элементов соответствует методу генерации сетки и не всегда оптимальна с точки зрения особенностей программной реализации вычислительного алгоритма. Поэтому производительность вычислений на неструктурированных сетках без оптимизации индексации может быть низкой или нестабильной с ростом числа параллельных процессов.
Для оптимизации индексации сеточных элементов неструктурированных сеток предлагается использовать метод, основанный на идее присвоения индексов в порядке обхода вершин дуального графа. Первый элемент последовательности обхода выбирается произвольным образом. Далее в конец последовательности в произвольном порядке добавляются индексы элементов, имеющих с первым элементом общую грань. Затем в последовательность добавляются элементы, имеющие общую грань со вторым элементом и ранее не вошедшие в последовательность, и так далее до момента обхода всех сеточных элементов. Сравнительные результаты быстродействия модуля по вычислению конвективных потоков на основе метода конечного объема с полиномиальной реконструкцией переменных в ячейках тетраэдральной сетки для различных вариантов индексации элементов приведены в таблице 2. Расчет задачи невязкого обтекания сферы проводился на локально сгущающейся сетке, содержащей 119286 узлов и 679339 тетраэдров. Позитивная индексация соответствует описанному выше методу. Негативная индексация формируется таким образом, чтобы исключить кэширование данных. Представленные результаты демонстрируют существенное влияние метода индексации сеточных элементов на время работы модуля.
Таблица 2. Время работы модуля вычисления конвективных потоков Число процессорных ядер 1 6 1 6 Индексация элементов
Время (секунд) Позитивная Позитивная Негативная Негативная Обобщенное тестирование эффективности методов оптимизации вычислений на неструктурированных сетках большого размера проводилось на примере задачи невязкого обтекания тела сложной формы на тетраэдральной сетке, содержащей 260 517 739 узлов и 1 555 767 296 тетраэдров, с определением значений в узлах. Расчет проводился с использованием ресурсов МВС «Ломоносов». Замерялись время выполнения 500 вычислительных шагов и производительность вычислений при запуске от 1000 до 29600 параллельных процессов (таблица 3).
Таблица 3. Параметры вычислительного эксперимента Число процессов Время (секунд) Ускорение Эффективность
1 1.91 3.55 6.48 9.27 11.85 16.60 18.44 19.56 Methods for increasing optimisation for large scale parallel computing experiments on unstructured grids Sergey Sukov Keywords: parallel algorithms, numerical simulation, unstructured grids Methods are presenting for increasing optimisation for computing experiments on huge unstructured grids. Results of propositional algorhytmes testing are presented by the example of calculations using tetrahedral grids containing to 1.5 billion elements.