=Paper=
{{Paper
|id=Vol-1894/num1
|storemode=property
|title=Схема "правый уголок" и ее распараллеливание для численного решения уравнения переноса с запаздыванием(Parallelization of "the right corner" scheme for numerical solution of an advection equation with delay)
|pdfUrl=https://ceur-ws.org/Vol-1894/num1.pdf
|volume=Vol-1894
|authors=Eugene S. Elkin,Sergey V. Sviridov
}}
==Схема "правый уголок" и ее распараллеливание для численного решения уравнения переноса с запаздыванием(Parallelization of "the right corner" scheme for numerical solution of an advection equation with delay)==
https://ceur-ws.org/Vol-1894/num1.pdf
Схема «правый уголок» и ее распараллеливание
для численного решения уравнения переноса
с запаздыванием
Е.С. Елькин С.В. Свиридов
evgeny.elkin@urfu.ru sergey.sviridov@urfu.ru
УрФУ (Екатеринбург)
Аннотация
Рассматривается уравнение переноса с запаздыванием с одномер-
ной переменной по пространству. В качестве метода для численного
решения данного уравнения используется разностная схема «пра-
вый уголок». В работе рассматривается механизм распараллелива-
ния указанной схемы. Для полноты эксперимента рассматривают-
ся различные виды запаздывания: постоянное, переменное и рас-
пределенное. Проведен замер эффективности данного метода для
последовательной и параллельной версии на разных количествах
узлов по пространству и по времени. Предоставлены результаты
проведенных экспериментов.
1 Введение
Уравнение переноса — это уравнение в частных производных первого порядка. В моделях физики такое
уравнение часто называют уравнением конвекции, в моделях биологии — уравнением адвекции. Оно может
осложняться различными видами запаздывания [1]. В силу сложности объектов, на первый план выходит
конструирование численных алгоритмов их решения.
Численные методы решения уравнения переноса без запаздывания достаточно хорошо изучены, напри-
мер, в работах [3, 2, 5]. Вопросы численного решения уравнений переноса с запаздыванием рассматрива-
лись, например, в [8, 9]. Методы распараллеливания рассматривались ранее, например, в [10, 11, 12]. В
данной работе исследуются вопросы распараллеливания для конкретного алгоритма.
Рассмотрим уравнение переноса с эффектом наследственности:
∂u(x, t) ∂u(x, t)
+a = f (x, t, u(x, t), ut (x, ·)), (1)
∂t ∂x
0 6 t 6 T, 0 6 x 6 X,
с краевым условием
u(0, t) = γ(t), 0 6 t 6 T, (2)
и начальным условием
u(x, s) = ϕ(x, s), 0 6 x 6 X, −τ 6 s 6 0. (3)
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
318
Здесь x, t — независимые переменные, u(x, t) — искомая функция, ut (x, ·) = {u(x, t + s), −τ 6 s < 0} –
функция-предыстория искомой функции к моменту t, τ > 0 — величина запаздывания.
Предполагается, что функционал f , функции γ(t), ϕ(x, s) и константа a > 0 таковы, что задача (1)–(3)
имеет единственное решение.
2 Дискретизация задачи
Пусть шаг h по переменной x такой, что X/h = N , где N – натуральное, тогда обозначим через xi =
ih ∈ [0, X], i = 0 . . . N . Пусть шаг ∆ по переменной t такой, что τ /∆ = m, где m – натуральное, пусть
M = bT /∆c, обозначим tj = j∆ ∈ [−τ, T ], j = −m . . . M . Сеткой назовем набор пар {xi , tj }. Через uij
обозначим приближенное значение u(xi , tj ).
При всяком фиксированном i = 0, . . . , N введем дискретную предысторию к моменту tj , j = 0, . . . , M :
{uik }j = {uik , j − m 6 k 6 j}. Оператором интерполяции-экстраполяции назовем оператор, определенный
на множестве всех допустимых предысторий и действующий по правилу I: {uik }j → vji (·) ∈ Q[tj − τ, tj + ∆].
Здесь Q[α, β] — это набор функций u(s), кусочно-непрерывных на [α, β] с конечным числом точек разрыва
первого рода. В точках разрыва будем считать функцию непрерывной справа. Определим норму Q =
Q[α, β] как
ku(·)kQ = max |u(s)|.
s∈[α,β]
Будем полагать, что, во-первых, оператор интерполяции-экстраполяции липшицев, то есть существует
такая константа LI , что для всех предысторий дискретной модели {uik }j и {yki }j выполняется
max |vji (t) − wji (t)| 6 LI max |uil − yji |,
tj −τ 6t6tj +∆ j−m6l6j
где vji (·) = I({uik }j ), wji (·) = I({yki }j ).
Во-вторых, положим, что оператор интерполяции-экстраполяции согласован, то есть
vji (tk ) = uik , k = j − m, . . . , j.
Будем говорить, что оператор интерполяции-экстраполяции имеет порядок p, если существуют констан-
ты C1 и C2 такие, что |vji (t) − u(xi , t)| 6 C1 maxj−m6k6j |uik − u(xi , tk )| + C2 ∆p для всех i, j и t ∈ [tj − τ, tj+1 ].
Простейший способ интерполяции — кусочно-линейная функция. Простейший способ экстраполяции —
экстраполяция продолжением (см. [7]). Будем использовать кусочно-линейную интерполяцию с экстрапо-
ляцией продолжением, которая является липшицевым оператором (LI = 2), согласована и имеет порядок
p = 2 (см. [7]).
Рис. 1: Сетка
319
Рис. 2: Изображение разностной схемы «Правый уголок»
3 Схема «Правый уголок»
Рассмотрим метод:
uij+1 − uij uij+1 − ui−1
j+1
+a = f (xi , tj , uij , ut (x, ·))). (4)
∆ h
Каждая производная в (4) представлена как разность приближенных значений функции в узлах сетки,
показанных на рис. 2. Значение ui−1 j+1 может быть выражено из ранее подсчитанных значений, значит,
рассматриваемый метод «правый уголок» является явным для уравнения (1)–(3).
Обозначим εij = u(xi , tj ) − uij , i = 0, . . . , N , j = 0, . . . , M . Будем говорить, что метод сходится, если
i
εj → 0 при h → 0 и ∆ → 0 для всех i = 0, . . . , N и j = 0, . . . , M . Будем говорить, что метод сходится
с порядком hp + ∆q , если существует константа C такая, что |εij | 6 C(hp + ∆q ) для всех i = 0, . . . , N и
j = 0, . . . , M. В [4] доказано, что рассматриваемый метод сходится с порядком O(∆ + h). Данная схема
входит в семейство методов, рассмотренных в [6].
4 Идея параллельного вычисления
В данной схеме для вычисления очередных неизвестных значений используются значения, стоящие
ниже или левее по x и по t, следовательно, мы можем независимо друг от друга вычислять элементы,
находящиеся на одной диагонали (далее будем называть эти «диагональные» элементы фронтом). Это
дает возможность для параллельного вычисления результирующей функции. Схематичное расположение
«фронтов» для параллельного вычисления показано на рис. 3.
Рис. 3: Схема «Правый уголок»
Для реализации данного подхода использовалось многопоточное программирование. В качестве языка
было решено использовать C# и платформу .Net, включающую примитивы многопоточного программи-
рования. При реализации использовалась сборка System.Threading.Tasks, в частности метод Parallel.For,
позволяющий распараллелить выполнение цикла For между потоками. Все вычисление выполнялось поша-
гово по диагоналям. На каждом шаге выбиралась следующая диагональ, для узлов которой параллельно
вычислялись искомые значения. Так как элементы на диагонали не зависят друг от друга, то данный
подход является корректным с точки зрения вычислений. На каждом этапе параллельного вычисления
320
искомых значений в узлах диагонали платформа порождает 8 потоков и распределяет узлы между ни-
ми по мере возможности. Из-за того, что одновременно вычисляется не более 8 потоков и количество
элементов диагонали в большинстве случаев больше 8, эффект «узкого фронта распараллеливания» был
незначительным, поэтому в большинстве примеров мы рассматривали сетки с одинаковым числом узлов по
осям. Так как целью данной работы является исследование возможности ускорения путем распараллели-
вания вычислений, то мы не прибегали к другим приемам программных и алгоритмических оптимизаций
(векторизации, кешированию и др.). В итоге, мы оценивали потенциал ускорения при помощи лишь мно-
гопоточного программирования.
5 Численные эксперименты
Во всех таблицах с результатами экспериментов используем следующие обозначения:
Err — максимум модуля разности точного и приближенного решений в узлах сетки. T1 — время вы-
полнения последовательной версии (в миллисекундах). T2 — время выполнения параллельной версии (в
миллисекундах).
5.1 Пример 1. Постоянное запаздывание
∂u ∂u
+ = πt cos(πx) + (3 − t) sin(πx)u(x, t − 2),
∂t ∂x
0 6 t 6 4, 0 6 x 6 4,
с краевым условием:
u(0, t) = 0, 0 6 t 6 4,
с начальным условием:
u(x, t) = t sin(πx), 0 6 x 6 4, −2 6 t 6 0.
Точное решение данного уравнения:
u(x, t) = t sin(πx).
Таблица 1: Численные эксперименты для примера 1
N= 40 40 80 80 160 320 640
M= 40 80 40 80 160 320 640
Err 1.31 1.2 1.18 0.65 0.32 0.15 0.08
T1 0 1 1 1 6 31 132
T2 12 8 8 10 12 35 72
5.2 Пример 2. Переменное запаздывание
3
∂u ∂u t 1 t 5
+ = u x, − + 6x + 3t2 + 6t − 3x3 − − ,
∂t ∂x 2 2 2 8
0 6 t 6 1, 0 6 x 6 2,
с краевым условием:
u(0, t) = 3t2 + 6t, 0 6 t 6 4,
с начальным условием:
1
u(x, t) = x3 + t3 + 3x2 + 3t2 , 0 6 x 6 1, − 6 t 6 0.
2
Точное решение данного уравнения:
u(x, t) = x3 + t3 + 3x2 + 3t2 .
321
Таблица 2: Численные эксперименты для примера 2
N= 40 80 160 320 640
M= 40 80 160 320 640
Err 4.15 2.56 1.84 0.98 0.42
T1 4 9 32 196 628
T2 14 19 43 152 439
5.3 Пример 3. Распределенное запаздывание
Z − π2
∂u ∂u
+ = (1 − x) sin(t) − u(x, t + ξ)dξ,
∂t ∂x −π
0 6 t 6 4, 0 6 x 6 π,
с краевым условием:
u(0, t) = 0, 0 6 t 6 π,
с начальным условием:
u(x, t) = x sin(t), 0 6 x 6 4, −π 6 t 6 0.
Точное решение данного уравнения:
u(x, t) = x sin(t).
Таблица 3: Численные эксперименты для примера 3
N= 40 80 160 320 640
M= 40 80 160 320 640
Err 1.68 0.92 0.65 0.34 0.18
T1 1 4 12 122 680
T2 12 16 39 97 421
Отметим, что численные эксперименты для примера 3 проводились без использования рекуррентных
соотношений между интегралами по пересекающимся интервалам. Сделано это было для большего чис-
ла вычислений на каждом шаге и анализа эффективности использования параллелизма для численного
решения уравнений рассматриваемых типов.
6 Заключение
Все вычисления выполнялись на ноутбуке с процессором Intel(R) Core i7 4700MQ 2.4GHz x 4, поддержи-
вающем одновременное выполнение 8 потоков. Для чистоты эксперимента все вычисления проводились в
максимально «стерильных условиях» (на компьютере запущены только необходимые приложения), однако
операционная система и фоновые процессы в любом случае влияют на время вычислений, поэтому в приме-
рах указано среднее время выполнения среди десяти запусков. Также можно заметить сильное замедление
параллельной программы на малом количестве узлов по сравнению с последовательной версией. Это вы-
звано временем, которое уходит у платформы на подготовку многопоточной экосистемы и переключение
между потоками. Последовательная программа лишена данных недостатков. В качестве эффективности
в данной работе рассматривается отношение времени выполнения параллельной программы ко времени
выполнения последовательной. В дальнейшем планируется более глубокий анализ алгоритмов параллель-
ного вычисления решений описанных выше уравнений: с учетом различных показателей эффективности,
таких как слабая и сильная масштабируемость.
Временны́е результаты вычислений на сетках с небольшим количеством узлов обусловлены тем, что
рассмотренная в статье параллельная версия правого уголка тратит много времени на подготовку потоков
и переключение между ними. Однако с увеличением количества узлов видно, что параллельный алго-
ритм становится быстрее последовательного. Так как наибольший интерес с практической точки зрения
представляют более точные вычисления на мелкой сетке, то можем сделать вывод, что полученные пре-
имущества при распараллеливании подсчетов можем считать основанием для применения рассмотренного
алгоритма на практике и для ускорения аналогичных явных разностных схем.
322
Благодарности
Работа поддержана программой ППК (постановление Правительства РФ № 211 от 16.03.2013).
Список литературы
[1] J. Wu. Theory and Application of Partial Functional Differential Equations. Springer-Verlag, New York,
1996.
[2] N. N. Kalitkin. Numerical methods. Second edition. BHV-Peterburg, Sankt-Peterburg, 2011 (in Russian).
= Н. Н. Калиткин. Численные методы. 2-е издание. БХВ-Петербург, Санкт-Петербург, 2011.
[3] A. A. Samarsky. Theory of differencial schemes. Third edition. Nauka, Moscow, 1989 (in Russian). =
А. А. Самарский. Теория разностных схем. 3-е издание. Наука, Москва, 1989.
[4] V. G. Pimenov. Differencial methods for solution of functional equations with delay. Ural State University,
Ekaterinburg, 2014 (in Russian). = В. Г. Пименов. Разностные методы решения уравнений в частных
производных с наследственностью. Издательство уральского университета, Екатеринбург, 2014.
[5] I. B. Petrov, A. I. Lobanov. Lectures on computational mathematics. Binom, Moscow, 2006 (in Russian).
= И. Б. Петров, А. И. Лобанов. Лекции по вычислительной математике. Бином, Москва, 2006.
[6] L. S. Volkanin. Numerical solution of an advection equation with delay. Teoriya upravlenija i
matematicheskoe modelirovanie. Conference proceedings. Izhevsk, 12–13, 2012 (in Russian). = Л. С. Вол-
канин. Численное решение уравнения переноса с эффектом наследственности. Теория управления и
математическое моделирование. Тезисы конференции. Ижевск, 12–13, 2012.
[7] A. V. Kim, V. G. Pimenov. i-smooth analysis and a numerical methods for solving of a functional-differential
equations). RCD, Moscow-Izhevsk, 2004 (in Russian). = А. В. Ким, В. Г. Пименов. i-гладкий анализ
и численные методы решения функционально-дифференциальных уравнений. РХД, Москва-Ижевск,
2004.
[8] V. G. Pimenov, S. V. Sviridov. Grid methods for solving of an advection equation with delay. Vestnik
Udmurtskogo Universiteta. Matematika. Mehanika. Kompyuternye nauki, 3:59–74, 2014 (in Russian). =
В. Г. Пименов, С. В. Свиридов. Сеточные методы решения уравнения переноса с запаздыванием.
Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 3:59–74, 2014.
[9] S.I. Solodushkin. One difference scheme for numerical solving of advection equation with aftereffect.
Proceedings of 8th Conference on Applied Mathematics and Scientific Computing, Sibenik, Croatia, 10-14
June, 54–55, 2013.
[10] S.I. Solodushkin, I.F.Yumanova, R.H. De Staelen. A difference scheme for multidimensional transfer
equations with time delay. Journal of Computational and Applied Mathematics, 318:580–590, 2017.
[11] S.I. Solodushkin, A.A. Sagoyan, I.F. Iumanova. Parallel variant of numerical algorithm for solving a
multidimensional advection equation with time delay. CEUR Workshop Proceedings, 1662:315–325, 2016.
[12] S.I. Solodushkin, A.A. Sagoyan, I.F. Iumanova. One parallel method for solving the multidimensional
transfer equation with aftereffect. Lecture Notes in Computer Science (including subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics), 10187:617–624, 2017.
323
Parallelization of «the right corner» scheme for numerical solution of
an advection equation with delay
Eugene S. Elkin, Sergey V. Sviridov
Ural Federal University (Yekaterinburg, Russia)
Keywords: advection equation, delay, grid schemes, parallelization.
We consider an advection equation with delay and the right corner scheme for numerical solution of the
considered equation. A parallelization method is proposed. Test examples with different types of delay are given.
The considered parallel method is compared with a serial implementation of the right corner method. Results
for all experiments are given.
324