uzluga.ru
добавить свой файл
1



Локально-перестраиваемые декартовы сетки с динамической адаптацией к решению

  • Локально-перестраиваемые декартовы сетки с динамической адаптацией к решению

  • Проверка разработанных сеток на решении простейшей задачи переноса

  • Параллельная реализация алгоритмов с динамической балансировкой загрузки





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

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

  • Физические явления зачастую имеют разрывы и локализованные области с большими градиентами физических величин

  • Численное моделирование таких задач и распро-странённые подходы (конечные элементы, конеч-ные объёмы, конечные разности, спектральные методы) будут неэффективны на равномерных сетках, когда требуется высокая точность решения



Повышение порядка аппроксимации разностной схемы — немонотонность разностных схем и появление осцилляций

  • Повышение порядка аппроксимации разностной схемы — немонотонность разностных схем и появление осцилляций

  • Уменьшение размеров ячеек во всей области — значительный рост вычислительной сложности задачи

  • Выборочное измельчение элементов сетки (адаптивная сетка) — подход, который исполь-зован в данной работе



Вначале сетка состоит из одной прямоугольной ячейки

  • Вначале сетка состоит из одной прямоугольной ячейки

  • Каждая ячейка может быть разделена на четыре ячейки одинакового размера

  • Если ячейки когда-то составляли одну ячейку, то они могут быть объединены обратно

  • При данных предположениях сетку удобно хранить в виде четверичного дерева:



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

  • Дополнительное ограничение на размер ячеек: в окрестности каждой ячейки не должно быть ячеек, которые отличаются от неё по размерам более чем в два раза

  • Следствия из этого ограничения:

    • Ячейка будет иметь от 6 до 12 соседей
    • Не может быть одновременно больших и маленьких соседних ячеек
  • Преимущества ограничения:

    • Значительно упрощаются алгоритмы поиска соседей и интерполяции
    • Повышается точность аппроксимации уравнений
    • Сетка успевает «подготовиться» к приходу области с большим градиентом (при движении таких областей)
  • Недостаток:

    • Чрезмерное измельчение сетки в некоторых областях


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

  • Каждая ячейка имеет 9 интерполяционных точек, которые хранят значения, аппроксимирующие сеточную функцию и две её частные производные

  • Эти точки вычисляются с использованием значений в ячейке и её соседях

  • Интерполяционные точки содержат достаточно информации для консервативной аппроксимации уравнений в частных производных (до второго порядка включительно)

  • Таким образом, формулы для аппроксимации и алгоритмы расчёта не зависят от локальной структуры сетки



Свойства, которыми должен обладать алгоритм адаптации:

  • Свойства, которыми должен обладать алгоритм адаптации:

  • Сетка измельчается в местах больши́х градиентов решения

  • Максимальное число ячеек фиксировано

  • Можно ограничить минимальный размер ячейки (например, для соблюдения условия Куранта)

  • Можно зафиксировать отдельные ячейки, чтобы они не разбивались и не объединялись (например, для задания граничных условий)



Вариация данных в ячейке — это разница между максимальным и минимальным значениями сеточной функции в пределах ячейки

  • Вариация данных в ячейке — это разница между максимальным и минимальным значениями сеточной функции в пределах ячейки

  • Вариация отражает возможную потерю инфор-мации из-за усреднения сеточной функции по площади ячейки

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



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

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

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

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





Рассмотрим в качестве примера двумерную задачу переноса:

  • Рассмотрим в качестве примера двумерную задачу переноса:

  • где c=c(x,y,t) — некоторая физическая величина, t — время, Vx — скорость переноса величины c вдоль оси x, Vy — скорость переноса величины c вдоль оси y

  • Область решения — единичный квадрат, граничные условия — c=0 на границе области, начальное условие — c(x,y,0)=c0(x,y)



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

  • Несмотря на простоту постановки задачи и известное аналитическое решение, она сложна для численной реализации сеточными методами:

  • Если при разностной аппроксимации задачи не внести искусственную диффузию («схемную вязкость»), то разностная схема будет неустойчива

  • Если же схемную вязкость внести (например, путём использования разностной схемы, ориентированной против потока), то численное решение будет иметь большу́ю погрешность, так как в исходном дифференциальном уравнении  диффузионные члены отсутствуют

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



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

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

  • Количество использованных ячеек одинаково для обеих сеток — 4096 ячеек



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

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







Время решения задачи переноса на адаптивной сетке в 1.5 раза больше времени вычисления на равномерной сетке с тем же числом ячеек

  • Время решения задачи переноса на адаптивной сетке в 1.5 раза больше времени вычисления на равномерной сетке с тем же числом ячеек

  • Но для достижения той же точности на равномерной сетке требуется в 16 раз больше ячеек

  • Таким образом, при той же точности решение на адаптивной сетке может быть получено в 10 раз быстрее, чем на равномерной





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

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

  • Кластеры динамически распределяются между процессорами, как неделимые единицы, для обеспечения балансировки загрузки и мини-мального обмена данными при последующем счёте

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



Противоречащие друг другу требования:

  • Противоречащие друг другу требования:

  • Балансировка загрузки — одинаковое число ячеек на всех процессорах

  • Минимизация обменов при счёте — минимальная длина границы между областями разных процессоров

  • Минимизация накладных расходов — минимальное количество пересылаемых между процессорами ячеек при перераспределении кластеров

  • В качестве критерия распределения кластеров по процессорам берётся суммарное ожидаемое время вычислений:

  • Ni — число ячеек на i-ом процессоре;

  • Li — суммарная длина границы между областью i-го процессора и областями других процессоров (измеряется в ячейках);

  • Di — число ячеек, которые должны быть переданы к/от i-го процессора для достижения требуемого распределения кластеров



64 кластера динамически распределяются по 3-м процессорам. На рисунках показано распределение для различных моментов времени

  • 64 кластера динамически распределяются по 3-м процессорам. На рисунках показано распределение для различных моментов времени

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



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

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

  • Разработаны параллельные алгоритмы с динамической балансировкой загрузки

  • Алгоритмы будут реализованы в виде пакета программ для обеспечения их широкого применения

  • Спасибо за внимание!