Рубрика «декомпозиция графов»

Метод рекурсивной координатной бисекции для декомпозиции расчетных сеток - 1

Введение

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

  1. Повысить скорость работы программы.
  2. Работать с сетками такого размера, который не помещается в оперативной памяти одного процессора.

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

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js