Антон Сухинов, Московский физико-технический институт Научный руководитель: Б.Н. Четверушкин, Институт математического моделирования РАН

Локально-перестраиваемые декартовы сетки с динамической адаптацией к решению Проверка разработанных сеток на решении простейшей задачи переноса Параллельная реализация алгоритмов с динамической балансировкой загрузки 2

3

При численном решении задач математической физики обычно используются вычислительные сетки, покрывающие расчётную область. Дискрети- зация уравнений модели выполняется на уровне элементов сетки Физические явления зачастую имеют разрывы и локализованные области с большими градиентами физических величин Численное моделирование таких задач и распро- странённые подходы (конечные элементы, конеч- ные объёмы, конечные разности, спектральные методы) будут неэффективны на равномерных сетках, когда требуется высокая точность решения 4

Повышение порядка аппроксимации разностной схемы немонотонность разностных схем и появление осцилляций Уменьшение размеров ячеек во всей области значительный рост вычислительной сложности задачи Выборочное измельчение элементов сетки (адаптивная сетка) подход, который исполь- зован в данной работе 5

Вначале сетка состоит из одной прямоугольной ячейки Каждая ячейка может быть разделена на четыре ячейки одинакового размера Если ячейки когда-то составляли одну ячейку, то они могут быть объединены обратно При данных предположениях сетку удобно хранить в виде четверичного дерева: 6

Дополнительное ограничение на размер ячеек: в окрестности каждой ячейки не должно быть ячеек, которые отличаются от неё по размерам более чем в два раза Следствия из этого ограничения: Ячейка будет иметь от 6 до 12 соседей Не может быть одновременно больших и маленьких соседних ячеек Преимущества ограничения: Значительно упрощаются алгоритмы поиска соседей и интерполяции Повышается точность аппроксимации уравнений Сетка успевает «подготовиться» к приходу области с большим градиентом (при движении таких областей) Недостаток: Чрезмерное измельчение сетки в некоторых областях 7

Каждая ячейка имеет 9 интерполяционных точек, которые хранят значения, аппроксимирующие сеточную функцию и две её частные производные Эти точки вычисляются с использованием значений в ячейке и её соседях Интерполяционные точки содержат достаточно информации для консервативной аппроксимации уравнений в частных производных (до второго порядка включительно) Таким образом, формулы для аппроксимации и алгоритмы расчёта не зависят от локальной структуры сетки 8

Свойства, которыми должен обладать алгоритм адаптации: Сетка измельчается в местах больших градиентов решения Максимальное число ячеек фиксировано Можно ограничить минимальный размер ячейки (например, для соблюдения условия Куранта) Можно зафиксировать отдельные ячейки, чтобы они не разбивались и не объединялись (например, для задания граничных условий) 9

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

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

12

Рассмотрим в качестве примера двумерную задачу переноса: где c=c(x,y,t) некоторая физическая величина, t время, V x скорость переноса величины c вдоль оси x, V y скорость переноса величины c вдоль оси y Область решения единичный квадрат, граничные условия c=0 на границе области, начальное условие c(x,y,0)=c 0 (x,y) 13

Несмотря на простоту постановки задачи и известное аналитическое решение, она сложна для численной реализации сеточными методами: Если при разностной аппроксимации задачи не внести искусственную диффузию («схемную вязкость»), то разностная схема будет неустойчива Если же схемную вязкость внести (например, путём использования разностной схемы, ориентированной против потока), то численное решение будет иметь большую погрешность, так как в исходном дифференциальном уравнении диффузионные члены отсутствуют В связи с этим было решено использовать линейную комбинацию разностной схемы второго порядка точности и разностной схемы, ориентированной против потока 14

На рисунках показаны начальные условия для равномерной (слева) и адаптивной (справа) сеток Количество использованных ячеек одинаково для обеих сеток 4096 ячеек 15

На рисунках показаны результаты решения задачи переноса для V x =1, V y =1 в момент времени T=0.5 на равномерной (слева) и адаптивной (справа) сетках 16

17

18

Время решения задачи переноса на адаптивной сетке в 1.5 раза больше времени вычисления на равномерной сетке с тем же числом ячеек Но для достижения той же точности на равномерной сетке требуется в 16 раз больше ячеек Таким образом, при той же точности решение на адаптивной сетке может быть получено в 10 раз быстрее, чем на равномерной 19

20

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

Противоречащие друг другу требования: Балансировка загрузки одинаковое число ячеек на всех процессорах Минимизация обменов при счёте минимальная длина границы между областями разных процессоров Минимизация накладных расходов минимальное количество пересылаемых между процессорами ячеек при перераспределении кластеров В качестве критерия распределения кластеров по процессорам берётся суммарное ожидаемое время вычислений: N i число ячеек на i-ом процессоре; L i суммарная длина границы между областью i-го процессора и областями других процессоров (измеряется в ячейках); D i число ячеек, которые должны быть переданы к/от i-го процессора для достижения требуемого распределения кластеров 22

64 кластера динамически распределяются по 3-м процессорам. На рисунках показано распределение для различных моментов времени Из-за малого количества ячеек по сравнению с объёмом передаваемых данных большую часть времени работают только два процессора 23

Разработаны новые алгоритмы иерархических локально-перестраиваемых декартовых сеток с динамической адаптацией к решению. Алгоритмы проверены на задаче переноса Разработаны параллельные алгоритмы с динамической балансировкой загрузки Алгоритмы будут реализованы в виде пакета программ для обеспечения их широкого применения Спасибо за внимание! 24