УрФУ (Екатеринбург) Рассматривается уравнение переноса с запаздыванием с одномерной переменной по пространству. В качестве метода для численного решения данного уравнения используется разностная схема ¾правый уголок¿. В работе рассматривается механизм распараллеливания указанной схемы. Для полноты эксперимента рассматриваются различные виды запаздывания: постоянное, переменное и распределенное. Проведен замер эффективности данного метода для последовательной и параллельной версии на разных количествах узлов по пространству и по времени. Предоставлены результаты проведенных экспериментов.
с краевым условием
= f (x; t; u(x; t); ut(x; ));
6 s 6 0:
(1)
(
Дискретизация задачи Пусть шаг h по переменной x такой, что X=h = N , где N – натуральное, тогда обозначим через xi = ih 2 [0; X], i = 0 : : : N . Пусть шаг по переменной t такой, что = = m, где m – натуральное, пусть M = bT = c, обозначим tj = j 2 [ ; T ], j = m : : : M . Сеткой назовем набор пар fxi; tjg. Через uij обозначим приближенное значение u(xi; tj).
При всяком фиксированном i = 0; : : : ; N введем дискретную предысторию к моменту tj; j = 0; : : : ; M : fuikgj = fuik; j m 6 k 6 jg. Оператором интерполяции-экстраполяции назовем оператор, определенный на множестве всех допустимых предысторий и действующий по правилу I: fuikgj ! vji( ) 2 Q[tj ; tj + ]: Здесь Q[ ; ] это набор функций u(s), кусочно-непрерывных на [ ; ] с конечным числом точек разрыва первого рода. В точках разрыва будем считать функцию непрерывной справа. Определим норму Q = Q[ ; ] как
ku( )kQ = sm2[a;x ] ju(s)j: Будем полагать, что, во-первых, оператор интерполяции-экстраполяции липшицев, то есть существует такая константа LI; что для всех предысторий дискретной модели fuikgj и fykigj выполняется tj 6t6tj+ jvji(t) max
wji (t)j 6 LI j mma6xl6j juli yjij; где vji( ) = I(fuikgj); wji ( ) = I(fykigj): Во-вторых, положим, что оператор интерполяции-экстраполяции согласован, то есть vji(tk) = uik; k = j m; : : : ; j: Будем говорить, что оператор интерполяции-экстраполяции имеет порядок p, если существуют константы C1 и C2 такие, что jvji(t) u(xi; t)j 6 C1 maxj m6k6j juik u(xi; tk)j + C2 p для всех i, j и t 2 [tj ; tj+1]: Простейший способ интерполяции кусочно-линейная функция. Простейший способ экстраполяции экстраполяция продолжением (см. [7]). Будем использовать кусочно-линейную интерполяцию с экстраполяцией продолжением, которая является липшицевым оператором (LI = 2), согласована и имеет порядок p = 2 (см. [7]).
Рис. 1: Сетка 3
Схема ¾Правый уголок¿ Рассмотрим метод:
i
uj+1
uij + a uij+1
h
uij+11 = f (xi; tj; uij; ut(x; ))):
(
Обозначим "ij = u(xi; tj) uij, i = 0; : : : ; N , j = 0; : : : ; M . Будем говорить, что метод сходится, если "ij ! 0 при h ! 0 и ! 0 для всех i = 0; : : : ; N и j = 0; : : : ; M . Будем говорить, что метод сходится с порядком hp + q; если существует константа C такая, что j"ijj 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 между потоками. Все вычисление выполнялось пошагово по диагоналям. На каждом шаге выбиралась следующая диагональ, для узлов которой параллельно вычислялись искомые значения. Так как элементы на диагонали не зависят друг от друга, то данный подход является корректным с точки зрения вычислений. На каждом этапе параллельного вычисления искомых значений в узлах диагонали платформа порождает 8 потоков и распределяет узлы между ними по мере возможности. Из-за того, что одновременно вычисляется не более 8 потоков и количество элементов диагонали в большинстве случаев больше 8, эффект ¾узкого фронта распараллеливания¿ был незначительным, поэтому в большинстве примеров мы рассматривали сетки с одинаковым числом узлов по осям. Так как целью данной работы является исследование возможности ускорения путем распараллеливания вычислений, то мы не прибегали к другим приемам программных и алгоритмических оптимизаций (векторизации, кешированию и др.). В итоге, мы оценивали потенциал ускорения при помощи лишь многопоточного программирования. 5
Численные эксперименты с краевым условием: с начальным условием: Точное решение данного уравнения:
N = M = Err T1 T2 40 40 1.31 0 12 с краевым условием: с начальным условием: Точное решение данного уравнения: u(x; t) = x3 + t3 + 3x2 + 3t2; 0 6 x 6 1; 5.3
Пример 3. Распределенное запаздывание с краевым условием: с начальным условием: + = (1 x) sin(t)
u(x; t + )d ;
Z 2 0 6 t 6 4; 0 6 x 6 ; Отметим, что численные эксперименты для примера 3 проводились без использования рекуррентных соотношений между интегралами по пересекающимся интервалам. Сделано это было для большего числа вычислений на каждом шаге и анализа эффективности использования параллелизма для численного решения уравнений рассматриваемых типов. 6 Заключение
Все вычисления выполнялись на ноутбуке с процессором Intel(R) Core i7 4700MQ 2.4GHz x 4, поддерживающем одновременное выполнение 8 потоков. Для чистоты эксперимента все вычисления проводились в максимально ¾стерильных условиях¿ (на компьютере запущены только необходимые приложения), однако операционная система и фоновые процессы в любом случае влияют на время вычислений, поэтому в примерах указано среднее время выполнения среди десяти запусков. Также можно заметить сильное замедление параллельной программы на малом количестве узлов по сравнению с последовательной версией. Это вызвано временем, которое уходит у платформы на подготовку многопоточной экосистемы и переключение между потоками. Последовательная программа лишена данных недостатков. В качестве эффективности в данной работе рассматривается отношение времени выполнения параллельной программы ко времени выполнения последовательной. В дальнейшем планируется более глубокий анализ алгоритмов параллельного вычисления решений описанных выше уравнений: с учетом различных показателей эффективности, таких как слабая и сильная масштабируемость.
Временны´ е результаты вычислений на сетках с небольшим количеством узлов обусловлены тем, что рассмотренная в статье параллельная версия правого уголка тратит много времени на подготовку потоков и переключение между ними. Однако с увеличением количества узлов видно, что параллельный алгоритм становится быстрее последовательного. Так как наибольший интерес с практической точки зрения представляют более точные вычисления на мелкой сетке, то можем сделать вывод, что полученные преимущества при распараллеливании подсчетов можем считать основанием для применения рассмотренного алгоритма на практике и для ускорения аналогичных явных разностных схем. Список литературы
Работа поддержана программой ППК (постановление Правительства РФ № 211 от 16.03.2013). [1] J. Wu. Theory and Application of Partial Functional Differential Equations. Springer-Verlag, New York, 1996. [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.
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)