Кластерная реализация параллельных итерационных методов решения жестких задач Коши

Аннотация

Никишин Р.Ю., Назарова И. А.,Фельдман Л.П. Кластерная реализация параллельных итерационных методов решения жестких задач Коши Рассматриваются параллельные алгоритмы решения нелинейной задачи Коши. Выполняется анализ решения одного дифференциального уравнения и системы таких уравнений большой размерности. Приведены особенности выполнения параллельной реализации алгоритмов. Проанализированы аналитические оценки динамических характеристик и зависимости от топологии. Произведено сравнение аналитических и полученных экспериментально характеристик, а также определена эффективность параллельной реализации.

 

Постановка проблемы.

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

В докладе рассматривается реализация полностью неявных методов типа Рунге-Кутты на кластере.

 

Анализ реализации ПНМРК

Для системы из  обыкновенных дифференциальных уравнений:

                                                                                                           (1)

где ,  - правая часть есть в общем случае нелинейная функция , задающая отображение: .

Одношаговый многостадийный метод для решения нелинейной задачи Коши, описываемой СОДУ (1), имеет вид:

,                                                                                     (2)

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

Применение полностью неявных многостадийных методов (ПНММ) требует для определения коэффициентов  решения системы , в общем случае нелинейных, уравнений:

                                                                            (3)

Решение системы (3) может быть получено с использованием следующей итерационной схемы:

                                                                                               (4)

где

Здесь итерационный процесс, повторенный раз представляет  как тую аппроксимацию для шагового коэффициента .

 

Решение уравнения

Для определения коэффициентов  необходимо решить систему из s, в общем случае нелинейных, уравнений:

                                                                             (5)

Для решения системы выбран метод простой итерации с итерационной схемой, описанной (3).

Вычисление l-й итерации отображено на схеме:

                                                                      (6)

Количество итераций  равняется порядку метода r.

Выполнение нулевой итерации, как и последующих, разбивается на количество процессоров. При этом на каждом из процессоров выполняется расчет s/p коэффициентов k. Где s – порядок метода, а p – количество процессоров.

В параллельном алгоритме, после каждой итерации (как нулевой, так и каждой из  последующих) выполняется множественная пересылка типа «все-всем» между процессорами. Каждый процессор передает коэффициенты, хранящиеся в переменной kproc всем процессорам, кроме себя. После решения системы (4), на каждом процессоре выполняется вычисление  по формуле: .

Аналитические динамические характеристики метода:

                                                (7)

Данные формулы были подтверждены проведенным экспериментом на MPI-кластере. При проведении эксперимента используется топология однонаправленное кольцо.

Экспериментальные значения динамических характеристик последовательного и параллельного алгоритмов приведены в табл.1:

Табл. 1 Экспериментальные значения динамических характеристик последовательного и параллельного алгоритмов

 

Решение системы уравнений

Для определения коэффициентов  необходимо решить систему из , в общем случае нелинейных, уравнений:

                                                                                (8)

Для решения системы выбран метод простой итерации с итерационной схемой, описанной (3).

На нулевой итерации выполняется вычисление функций уравнений с аргументами :

                                                                                               (9)

На последующих  итерациях выполняется вычисление коэффициентов , используя коэффициенты  из предыдущей -й итерации.

Количество процессоров равномерно делится на порядок метода, таким образом составляя s групп. Каждая группа вычисляет m уравнений в каждом векторе . В случае, если процессоров больше, чем порядок метода, уравнения в каждой группе соответственно делятся между процессорами группы. Таким образом, каждый процессор в группе вычисляет d элементов , где  , а  Вычисление  разбивается  на p процессоров. На каждом процессоре вычисляется m/p элементов вектора .

Аналитические динамические характеристики метода:

                                                 (10)                                                            

Данные формулы были подтверждены проведенным экспериментом на MPI-кластере. При проведении эксперимента используется топология однонаправленное кольцо.

Экспериментальные значения динамических характеристик последовательного и параллельного алгоритмов для методов второго порядка представлены в табл. 2:

Экспериментальные значения динамических характеристик последовательного и параллельного алгоритмов для методов четвертого порядка представлены в табл. 3:

Табл. 3 Экспериментальные значения динамических характеристик последовательного и параллельного алгоритмов для методов четвертого порядка

Анализирую полученные в результате эксперимента значения, можно сделать вывод о целесообразности применения параллельных алгоритмов при решении жестких задач Коши ПНМРК.

 

Выводы

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

Оговорены особенности выполнения параллельной реализации алгоритмов. Проанализированы аналитические оценки динамических характеристик.

Проведены эксперименты на MPI-кластере, подтверждающие аналитические оценки и позволяющие наглядно проиллюстрировать эффективность использование параллельных алгоритмов при решении жестких задач Коши.

Список источников

1. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи: Пер. с англ. – М.: Мир, 1990. –  512с.
2. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. – М.: Мир,1999. – 685с.
3. Фельдман Л.П., Назарова И.А. Эффективность параллельных алгоритмов оценки локальной апостериорной погрешности для численного решения задачи Коши // Электронное моделирование, т. 29, № 3, 2007. – С. 11-25.