Алговики - Вклад [ru]

Участник:Andrclive/Уравнения мелкой воды

2016-11-30T21:30:10Z

Andrclive:

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

Ситуации, когда глубина акватории много меньше горизонтальных размеров, достаточно обычна, поэтому уравнения мелкой воды находят широкое применение. Они используются с учётом кориолисовых сил при моделировании атмосферы и океана. Будем рассматривать вид задачи МВ, который используется при моделировании
циркуляции океана в модели INMOM (Institute of Numerical Mathematics Ocean Model).

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> x, y </math> - широта и долгота,
<math> t </math> - время,
<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

К этой задаче также добавляются граничные условия:

<math> (\bar{U}, \bar{n}) = 0 </math>
на границе, где <math> \bar{U} = (u, v) </math> и <math> \bar{n} </math>
- единичная нормаль к границе.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации системы с учетом граничных условий получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

Приведем схему, показывающую структуру последовательного алгоритма.

[[Файл:SW.png|center|200px]]

Систему <math> Ax = b </math> на каждом шаге по времени решаем методом GMRES с помощью PETSc.

== Последовательная сложность алгоритма ==
При решении системы <math> Ax = b </math> методом GMRES, необходимо провести довольно большее количество итераций - это связано со структурой матрицы <math>A</math>, о которой писалось выше. Чтобы на каждом следующем шаге по времени это число итераций уменьшить, можно в методе GMRES использовать начальное приближение не нулевое, а как решение <math>x</math> с предыдущего шага по времени. Тогда число итераций с каждом шагом по времени будет заметно уменьшаться.

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем схему, показывающую структуру работы параллельной версии:

[[Файл:SW_MPI.png|center|500px]]

== Ресурс параллелизма алгоритма ==
При декомпозиции области и решения системы <math> Ax = b </math> параллельным итерационным методом, вообще говоря, число итераций может увеличиться по сравнению с последовательной версией. Для уменьшения количества итераций на каждом шаге по времени можно решать систему с использованием начального приближения не нулевого, а как решения <math>x</math> на предыдущем шаге по времени.

== Входные и выходные данные алгоритма ==
Входные данные алгоритма состоят из:

* Размеров и координат расчетной области.
* Топографии дна (можно просто задать глубину везде постоянной).
* Атмосферного давления на поверхности.
* Средней плотности жидкости.
* Начальных условий скоростей и уровня (обычно задаются просто нулями).

Как писалось выше, матрица <math> A </math> - разряженная 7-диагональная плохо обусловленная матрица. Формируется и подается на вход решателю в формате
CSR (Compressed Sparse Row matrix).

Выходные данные скоростей и уровня записываются в бинарный файл с последующим созданием заголовка .ctl для навигации по нему и работе с ним
в программе GrADS.

== Свойства алгоритма ==

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Некоторое среднее время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc.

[[Файл:SW_local_sys.png|center|600px]]

Не очень хорошая масштабируемость алгоритма связана именно с параллельным решением системы <math> Ax = b </math>. Этот этап требует довольно большое количество пересылок между процессорами. Для достижения наилучшей производительности, сам PETSc рекомендует по 10000 неизвестных на один процессор, а лучше по 20000 ([https://www.mcs.anl.gov/petsc/documentation/faq.html#slowerparallel]).

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

* Н.А. Дианский. Моделирование циркуляции океана.
* К.М. Терехов. Параллельная реализация модели общей циркуляции океана // Сборник тезисов лучших дипломных работ 2010. ВМИК МГУ, Москва.
* PETSc [https://www.mcs.anl.gov/petsc/]

[[en:Description of algorithm properties and structure]]

Участник:Andrclive/Уравнения мелкой воды

2016-11-30T21:29:18Z

Andrclive:

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

Ситуации, когда глубина акватории много меньше горизонтальных размеров, достаточно обычна, поэтому уравнения мелкой воды находят широкое применение. Они используются с учётом кориолисовых сил при моделировании атмосферы и океана. Будем рассматривать вид задачи МВ, который используется при моделировании
циркуляции океана в модели INMOM (Institute of Numerical Mathematics Ocean Model).

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> x, y </math> - широта и долгота,
<math> t </math> - время,
<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

К этой задаче также добавляются граничные условия:

<math> (\bar{U}, \bar{n}) = 0 </math>
на границе, где <math> \bar{U} = (u, v) </math> и <math> \bar{n} </math>
- единичная нормаль к границе.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации системы с учетом граничных условий получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

Приведем схему, показывающую структуру последовательного алгоритма.

[[Файл:SW.png|center|200px]]

Систему <math> Ax = b </math> на каждом шаге по времени решаем методом GMRES с помощью PETSc.

== Последовательная сложность алгоритма ==
При решении системы <math> Ax = b </math> методом GMRES, необходимо провести довольно большее количество итераций - это связано со структурой матрицы <math>A</math>, о которой писалось выше. Чтобы на каждом следующем шаге по времени это число итераций уменьшить, можно в методе GMRES использовать начальное приближение не нулевое, а как решение <math>x</math> с предыдущего шага по времени. Тогда число итераций с каждом шагом по времени будет заметно уменьшаться.

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем схему, показывающую структуру работы параллельной версии:

[[Файл:SW_MPI.png|center|500px]]

== Ресурс параллелизма алгоритма ==
При декомпозиции области и решения системы <math> Ax = b </math> параллельным итерационным методом, вообще говоря, число итераций может увеличиться по сравнению с последовательной версией. Для уменьшения количества итераций на каждом шаге по времени можно решать систему с использованием начального приближения не нулевого, а как решения <math>x</math> на предыдущем шаге по времени.

== Входные и выходные данные алгоритма ==
Входные данные алгоритма состоят из:

* Размеров и координат расчетной области.
* Топографии дна (можно просто задать глубину везде постоянной).
* Атмосферного давления на поверхности.
* Средней плотности жидкости.
* Начальных условий скоростей и уровня (обычно задаются просто нулями).

Как писалось выше, матрица <math> A </math> - разряженная 7-диагональная плохо обусловленная матрица. Формируется и подается на вход решателю в формате
CSR (Compressed Sparse Row matrix).

Выходные данные скоростей и уровня записываются в бинарный файл с последующим созданием заголовка .ctl для навигации по нему и работе с ним
в программе GrADS.

== Свойства алгоритма ==

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Некоторое среднее время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc.

[[Файл:SW_local_sys.png|center|600px]]

Не очень хорошая масштабируемость алгоритма связана именно с параллельным решением системы <math> Ax = b </math>. Этот этап требует довольно большое количество пересылок между процессорами. Для достижения наилучшей производительности, сам PETSc рекомендует по 10000 неизвестных на один процесс, а лучше по 20000 ([https://www.mcs.anl.gov/petsc/documentation/faq.html#slowerparallel]).

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

* Н.А. Дианский. Моделирование циркуляции океана.
* К.М. Терехов. Параллельная реализация модели общей циркуляции океана // Сборник тезисов лучших дипломных работ 2010. ВМИК МГУ, Москва.
* PETSc [https://www.mcs.anl.gov/petsc/]

[[en:Description of algorithm properties and structure]]

Участник:Andrclive/Уравнения мелкой воды

2016-11-30T20:53:11Z

Andrclive:

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

Ситуации, когда глубина акватории много меньше горизонтальных размеров, достаточно обычна, поэтому уравнения мелкой воды находят широкое применение. Они используются с учётом кориолисовых сил при моделировании атмосферы и океана. Будем рассматривать вид задачи МВ, который используется при моделировании
циркуляции океана в модели INMOM (Institute of Numerical Mathematics Ocean Model).

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> x, y </math> - широта и долгота,
<math> t </math> - время,
<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

К этой задаче также добавляются граничные условия:

<math> (\bar{U}, \bar{n}) = 0 </math>
на границе, где <math> \bar{U} = (u, v) </math> и <math> \bar{n} </math>
- единичная нормаль к границе.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации системы с учетом граничных условий получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

Приведем схему, показывающую структуру последовательного алгоритма.

[[Файл:SW.png|center|200px]]

Систему <math> Ax = b </math> на каждом шаге по времени решаем методом GMRES с помощью PETSc.

== Последовательная сложность алгоритма ==
При решении системы <math> Ax = b </math> методом GMRES, необходимо провести довольно большее количество итераций - это связано со структурой матрицы <math>A</math>, о которой писалось выше. Чтобы на каждом следующем шаге по времени это число итераций уменьшить, можно в методе GMRES использовать начальное приближение не нулевое, а как решение <math>x</math> с предыдущего шага по времени. Тогда число итераций с каждом шагом по времени будет заметно уменьшаться.

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем схему, показывающую структуру работы параллельной версии:

[[Файл:SW_MPI.png|center|500px]]

== Ресурс параллелизма алгоритма ==
При декомпозиции области и решения системы <math> Ax = b </math> параллельным итерационным методом, вообще говоря, число итераций может увеличиться по сравнению с последовательной версией. Для уменьшения количества итераций на каждом шаге по времени можно решать систему с использованием начального приближения не нулевого, а как решения <math>x</math> на предыдущем шаге по времени.

== Входные и выходные данные алгоритма ==
Входные данные алгоритма состоят из:

* Размеров и координат расчетной области.
* Топографии дна (можно просто задать глубину везде постоянной).
* Атмосферного давления на поверхности.
* Средней плотности жидкости.
* Начальных условий скоростей и уровня (обычно задаются просто нулями).

Как писалось выше, матрица <math> A </math> - разряженная 7-диагональная плохо обусловленная матрица. Формируется и подается на вход решателю в формате
CSR (Compressed Sparse Row matrix).

Выходные данные скоростей и уровня записываются в бинарный файл с последующим созданием заголовка .ctl для навигации по нему и работе с ним
в программе GrADS.

== Свойства алгоритма ==

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Некоторое среднее время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc.

[[Файл:SW_local_sys.png|center|600px]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

* Н.А. Дианский. Моделирование циркуляции океана.
* К.М. Терехов. Параллельная реализация модели общей циркуляции океана // Сборник тезисов лучших дипломных работ 2010. ВМИК МГУ, Москва.
* PETSc [https://www.mcs.anl.gov/petsc/]

[[en:Description of algorithm properties and structure]]

Участник:Andrclive/Уравнения мелкой воды

2016-11-30T20:51:45Z

Andrclive:

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

Ситуации, когда глубина акватории много меньше горизонтальных размеров, достаточно обычна, поэтому уравнения мелкой воды находят широкое применение. Они используются с учётом кориолисовых сил при моделировании атмосферы и океана. Будем рассматривать вид задачи МВ, который используется при моделировании
циркуляции океана в модели INMOM (Institute of Numerical Mathematics Ocean Model).

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> x, y </math> - широта и долгота,
<math> t </math> - время,
<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

К этой задаче также добавляются граничные условия:

<math> (\bar{U}, \bar{n}) = 0 </math>
на границе, где <math> \bar{U} = (u, v) </math> и <math> \bar{n} </math>
- единичная нормаль к границе.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации системы с учетом граничных условий получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

Приведем схему, показывающую структуру последовательного алгоритма.

[[Файл:SW.png|center]]

Систему <math> Ax = b </math> на каждом шаге по времени решаем методом GMRES с помощью PETSc.

== Последовательная сложность алгоритма ==
При решении системы <math> Ax = b </math> методом GMRES, необходимо провести довольно большее количество итераций - это связано со структурой матрицы <math>A</math>, о которой писалось выше. Чтобы на каждом следующем шаге по времени это число итераций уменьшить, можно в методе GMRES использовать начальное приближение не нулевое, а как решение <math>x</math> с предыдущего шага по времени. Тогда число итераций с каждом шагом по времени будет заметно уменьшаться.

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем схему, показывающую структуру работы параллельной версии:

[[Файл:SW_MPI.png|center|500px]]

== Ресурс параллелизма алгоритма ==
При декомпозиции области и решения системы <math> Ax = b </math> параллельным итерационным методом, вообще говоря, число итераций может увеличиться по сравнению с последовательной версией. Для уменьшения количества итераций на каждом шаге по времени можно решать систему с использованием начального приближения не нулевого, а как решения <math>x</math> на предыдущем шаге по времени.

== Входные и выходные данные алгоритма ==
Входные данные алгоритма состоят из:

* Размеров и координат расчетной области.
* Топографии дна (можно просто задать глубину везде постоянной).
* Атмосферного давления на поверхности.
* Средней плотности жидкости.
* Начальных условий скоростей и уровня (обычно задаются просто нулями).

Как писалось выше, матрица <math> A </math> - разряженная 7-диагональная плохо обусловленная матрица. Формируется и подается на вход решателю в формате
CSR (Compressed Sparse Row matrix).

Выходные данные скоростей и уровня записываются в бинарный файл с последующим созданием заголовка .ctl для навигации по нему и работе с ним
в программе GrADS.

== Свойства алгоритма ==

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Некоторое среднее время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc.

[[Файл:SW_local_sys.png|center|600px]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =

* Н.А. Дианский. Моделирование циркуляции океана.
* К.М. Терехов. Параллельная реализация модели общей циркуляции океана // Сборник тезисов лучших дипломных работ 2010. ВМИК МГУ, Москва.
* PETSc [https://www.mcs.anl.gov/petsc/]

[[en:Description of algorithm properties and structure]]

Участник:Andrclive/Уравнения мелкой воды

2016-11-30T19:21:56Z

Andrclive:

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

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

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

[[Файл:SW.png|center]]

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем схему, показывающая структуру работы параллельной версии:

[[Файл:SW_MPI.png|center|500px]]

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

= Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc для 50 итераций:

[[Файл:SW_local_sys.png|center|600px]]

== Существующие реализации алгоритма ==
Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.

= Литература =
<references />

[[en:Description of algorithm properties and structure]]

Файл:SW MPI.png

2016-11-30T19:21:22Z

Andrclive:

Участник:Andrclive/Уравнения мелкой воды

2016-11-28T00:49:46Z

Andrclive: Новая страница: «Основные авторы описания: А.В.Чаплыгин = Свойства и структура алгоритмо…»

Основные авторы описания: [[Участник:andrclive|А.В.Чаплыгин]]

= Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Уравнения мелкой воды (МВ) представляют собой упрощенную модель полных уравнений Навье-Стокса, описывающих пространственные
нестационарные течения. При выводе системы уравнений МВ предполагается, что среда представляет собой достаточно
тонкий слой, глубина которого много меньше его продольного размера, поэтому вертикальной составляющей скорости в слое можно пренебречь
и полагать, что продольные скорости постоянны по толщине слоя.

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

Уравнения мелкой воды в криволинейной системе координат при предположении <math> \zeta << H </math>, где <math>\zeta</math> - это отклонение уровня,
а <math>H</math> - глубина, имеют вид:

<math>
\left\{
\begin{array}{ccc}
\frac{\partial u}{\partial t} - lv = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{\partial v}{\partial t} + lu = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\partial \zeta}{\partial t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

<math> u, v </math> - зональная и меридиональная компоненты скорости,
<math> l </math> - параметр Кориолиса,
<math> r_x, r_y </math> - метрические коэффициенты,
<math> p_a </math> - атмосферное давление на поверхности,
<math> g </math> - ускорение свободного падения,
<math> \rho_0 </math> - средняя плотность жидкости.

== Математическое описание алгоритма ==

Для решения уравнений применяется техника построения разностных аппроксимаций по пространству второго порядка точности (в случае равномерной сетки)
на разнесенной "C" - сетке классификации Аракавы.
Уравнения требуют совместного решения сразу трех уравнений, записанных с использованием неявной схемы по времени:

<math>
\left\{
\begin{array}{ccc}
\frac{u^{j+1} - u^j}{\delta t} - lv^{j+1} + ru^{j+1} = -\frac{1}{r_x}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial x} - g\frac{\partial \zeta}{\partial x} ) \\
\\
\frac{v^{j+1} - v^j}{\delta t} + lu^{j+1} + rv^{j+1} = -\frac{1}{r_y}( \frac{1}{\rho_0}\frac{\partial p_a}{\partial y} - g\frac{\partial \zeta}{\partial y} ) \\
\\
\frac{\zeta^{j+1} - \zeta^j}{\delta t} = \frac{1}{r_x r_y} ( \frac{\partial r_y u H}{\partial x} + \frac{\partial r_x v H}{\partial y} ) \\
\end{array}
\right.
</math>

Здесь в первые два уравнения дополнительно введены слагаемые, которые можно рассматривать как рэлеевское трение с коэффициентом <math> r </math> для
дополнительного стока импульса. Они необходимы для регуляризации задачи, поскольку система может быть вырожденной.

После дискретизации получаем линейную систему <math> Ax = b </math>, которую решаем итерационным методом GMRES.

== Вычислительное ядро алгоритма ==
Формирование матрицы <math> A </math> занимает довольно много времени и ресурсов при больших размерностях задачи, но матрица генерируется всего один раз в программе, в начале, затем на каждом шаге по времени генерируется правая часть <math> b </math> и решается система <math> Ax = b </math>.
В процессе решения системы <math> Ax = b </math> получается 7-диагональная плохо обусловленная матрица. Решать такую систему на каждом шаге по времени довольно затруднительно, особенно если шагов по времени довольно много, и поэтому основное время алгоритма приходится именно на этот этап.

== Макроструктура алгоритма ==

== Схема реализации последовательного алгоритма ==

[[Файл:SW.png|center]]

== Информационный граф ==
Параллельная реализация алгоритма использует метод двумерной декомпозиции области. При запуске программы из полученного числа процессоров формируется
двумерная сетка, которая накладывается на рабочие массивы (<math> u, v, \zeta </math>) во вертикале и горизонтали, в итоге каждый процессор получает свой блок из общего массива над которым он будет выполнять работу. На рисунке изображен пример разбиения массива по процессорной сетке:

[[Файл:SW_proc_grid.png|center|600px]]

Дополнительные внерасчетные границы добавляются, чтобы производить обмен зависимыми данными между процессорами.

[[Файл:SW_proc_border.png|center|450px]]

Приведем информационный граф работы параллельной версии:

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

= Программная реализация алгоритма =

== Масштабируемость алгоритма и его реализации ==

Задача рассчитывалась на сетке (1, 254)X(1, 128), на 5 дней с шагом по времени 1800 секунд (пол часа).
Матрица <math> A </math> на такой сетке имеет размеры 97920 на 97920.
Все тесты проводились на суперкомпьютере Ломоносов.

Общее время расчета алгоритма:

[[Файл:SW_global.png|center]]

Время решения системы <math> Ax = b </math> методом GMRES с помощью пакета PETSc для 50 итераций:

[[Файл:SW_local_sys.png|center|600px]]

== Существующие реализации алгоритма ==
Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.

= Литература =
<references />

[[en:Description of algorithm properties and structure]]

Файл:SW local sys.png

2016-11-28T00:33:58Z

Andrclive:

Файл:SW global.png

2016-11-28T00:33:46Z

Andrclive:

Файл:SW proc border.png

2016-11-27T23:31:46Z

Andrclive:

Файл:SW proc grid.png

2016-11-27T23:23:34Z

Andrclive:

Файл:SW.png

2016-11-27T23:06:13Z

Andrclive:

Участник:Andrclive

2016-11-27T20:50:00Z

Andrclive:

Чаплыгин Андрей Викторович

ВМК МГУ

Участник:Andrclive

2016-11-27T20:49:29Z

Andrclive:

Чаплыгин Андрей Викторович
ВМК МГУ

Участник:Andrclive

2016-11-27T20:46:55Z

Andrclive: Создана пустая страница