Научный журнал

Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955

ИФ РИНЦ = 0,593

• Авторы
• Файлы

Ващенко Г.В.

Статья в формате PDF

768 KB

Для численного решения задачи Коши рассматриваются параллельные аналоги алгорит­мов явных методов типа Рунге-Кутты для систем обыкновенных дифференциальных уравнений первого порядка. Предложены параллельные вы­числительные схемы методов, ориентированных на применение в много процессорных вычисли­тельных системах кластерной архитектуры.

Рассматривается задачи Коши для систем обыкновенных дифференциальных уравнений первого порядка

Для численного решения задачи (1) применя­ется явные s-стадийные методы типа Рунге-Кутты, (n + 1)-й шаг в которых задается формулами

где i=1,2,...,s

Конкретный метод Рунге - Кутты определяется набором коэффициентов b_i, c_i, a_i, 1 ≤ i ≤ s, 2 ≤j ≤ (i - 1) [2-4].                                   

Основной подход при конструировании параллельных методов состоял в распараллелива­нии последовательных численных алгоритмов, использовании декомпозиции и анализе информа­ционных взаимосвязей между подзадачами [1, 5].

1. Последовательная вычислительная схема

Для определенности зададимся некото­рым отрезком [t₀, T], введем равномерную сет­ку w = (t₀, t₁,..., t_s) с величиной шага h_n+1= h и на сетке w_n в начальный момент времени t₀ в качестве начального условия зададим вектор j⁽⁰⁾ = (y⁽⁰⁾₁, y⁽⁰⁾₂,..., y⁽⁰⁾_N). Определение значений компонент вектора приближенного решения осуществляется по формуле (2), записанной для вычисления каж­дой компоненты вектора y⁽ⁿ⁺¹⁾

где 

Формулы (2) и (3) показывают, что определение значения у⁽ⁿ⁺¹⁾ сводится к строго по­следовательному вычислению коэффициентов К₁⁽ⁿ⁾, К₂⁽ⁿ⁾,..., K_s⁽ⁿ⁾ их умножению на коэффици­енты b_i, i = 1, 2, ., s, соответственно, и после­дующему суммированию.

2. Параллельная явная s -стадийная вычислительная схема

Последовательная схема (3) дает основание для организации двух типов параллельных вычислений:

а) вычисление отдельных компонент векторов коэффициентов К₁⁽ⁿ⁾,K₂⁽ⁿ⁾,...,K_s⁽ⁿ⁾ и  вектора численного решения 

б) вычисление отдельных операций внутри одного шага метода.

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

С целью выявления максимального независимого набора операций при вычислении коэффициентов К₁⁽ⁿ⁾ , i=1,2,...,s используется аппарат графов зависимости. Анализ графа за­висимостей, в предположении, что размерность N исходной системы (1) кратна числу компьюте­ров p, N = kp и схема размещения блочная обе­спечивает возможность записи параллельных схем. В каждом компьютере размещено и вы­числяется последовательно по k компонент век­торов коэффициентов, K₁⁽ⁿ⁾, K₂⁽ⁿ⁾,...,К_s⁽ⁿ⁾. Вычисления y⁽ⁿ⁺¹⁾ в n-м узле сетки w_n реализуются по правилу, показанному ниже. 

Вычисление коэффициентов и вектора приближенного решения при N = kp лгоритм. Пусть задана система (1), правая часть которой гладкая по всем аргументам y_i, 1 ≤ i ≤ N и пусть на заданном отрезке [t₀, T] определена равномерная сетка w_n. Тогда для решения задачи Коши вычислительной системе из p = N/k компьютеров, Comp(i), 1 ≤ i ≤ N, и блочной схемой хранения, справедлив параллельный алгоритм.

Шаг 1. Вычислить К⁽ⁿ⁾_1,lz и α⁽ⁿ⁾_2,lz по формулам 

и переслать K⁽ⁿ⁾_1,lz и α⁽ⁿ⁾_2,lz всем (p - 1) компьютерам.

Шаг 2. Вычислить K(n)2,lzи α(n)3,lzпо формулам 

и переслать K⁽ⁿ⁾_2,lz и α⁽ⁿ⁾_3,lz всем (p - 1) компьютерам ....................................................                    

Шаг s. Вычислить K⁽ⁿ⁾_s,lz
Шаг (s + 1). Вычислить    

Шаг (s + 3). Переслать всем (p-1) компьютерам.

пересылок для одного узла сетки w_n составит s(p - 1)²≈O(sp²).  

Параллельный аналог формулы (3) для рав­номерной сетки может быть записан в виде 

где

Заметим, что в отдельных случаях, зави­сящих от типа и вида исходной системы (1), может быть достигнута максимальная степень параллелизма и, соответственно, сокращение временных  затрат  выполнения  вычислений по разработанному алгоритму. Так, например, для двустадийной схемы Рунге-Кутты параллельный алгоритм записывается следующим образом.

Шаг 2. Вычислить   по формулам         

Шаг 3 Вычислить           

Шаг 4. Сохранить  

Шаг 5. Переслать всем (p - 1) компью­терам.

Рассмотренные параллельные схемы явных методов типа Рунге-Кутты ориентированы на реализацию в многопроцессорных вычислительных системах кластерной архитектуры с использованием технологии MPI. MPI имеет в составе коммуникационные операции попарные и коллективные обмены, средства организации виртуальных топологий. Исследования пред­ставленных параллельных схем показали, что для их реализация наиболее подходящими мо­гут быть топологии кольцо, линейка, решетка и гиперкуб. Разработанные схемы могут служить основой для разработки параллельных алгорит­мов решения задачи Коши явными методами с контролем точности и устойчивости, алгорит­мов переменного порядка и шага, а также воз­можной автоматизации построения методов интегрирования с адаптивной областью устой­чивости.

Список литературы

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ - Петербург, 2002. - 806 с.

2. Новиков Е.А. Явные методы для жестких систем. -Новосибирск: Наука, 1997. - 197 с.

3. Хайрер Э., Ваннер Г. Решение обыкновенных диффе­ренциальных уравнений. Жесткие и дифференциально-алге­браические задачи. - М.: Мир, 1999. - 685 с.

4.    Jackson K., Norsett S. The potential for parallelism in Runge -Kutta methods. Part I: RK formulas in standart form // SIAM J. Numer. Anal. - 1996.
- Vol. 32. - P. 49-82.

5.     Hendrickson B., KoldaTamaraG.Graphpartitioningmodels for parallel computing // Parallel Computing.-2002.-Т. 26,№12.-P. 181-197.

Библиографическая ссылка