научная статья по теме РЕШЕНИЕ ЗАДАЧ МНОГОКОМПОНЕНТНОЙ ДИФФУЗИИ С ПОМОЩЬЮ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА МАТРИЧНОЙ ПРОГОНКИ Кибернетика

Текст научной статьи на тему «РЕШЕНИЕ ЗАДАЧ МНОГОКОМПОНЕНТНОЙ ДИФФУЗИИ С ПОМОЩЬЮ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА МАТРИЧНОЙ ПРОГОНКИ»

1. Фурсенко

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ 2005 год, том 17, номер 9, стр. 85-92

> эллипти--тнчеетво от--Я эллипса -X 26). Зави-"! показаны

S (а также |ть пара-:-го из этих "ы зависят

граждан-

-ЗЭ01, 705 с. - М.: Выс-

-icis, 2003, A Linear

- -¿.2004.

РЕШЕНИЕ ЗАДАЧ МНОГОКОМПОНЕНТНОЙ ДИФФУЗИИ С ПОМОЩЬЮ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА МАТРИЧНОЙ ПРОГОНКИ

© Е.Н. Акимова1, И.И. Горбачев2, ВВ. Попов2

1 Институт математики и механики УрО РАН, Екатеринбург

2 Институт физики металлов УрО РАН, Екатеринбург

Работа выполнена при поддержке РФФИ (проект № 03-01-00099) и фондов ОАО «ММК», НТЦ «Аусфер» и ФНиО «Интеле» (проект № 11-03-02)

Для решения системы уравнений с блочно - трехдиагонапьными матрицами предложен и реализован на многопроцессорном вычислительном комплексе МВС-1000 параллельный алгоритм матричной прогонки. Данный алгоритм апробирован на решении тестовой задачи о диффузионном насыщении пластины несколькими элементами. Проведены численные эксперименты по исследованию коэффициентов эффективности и ускорения параллельного алгоритма.

SOLVING THE MULTICOMPONENT DIFFUSION PROBLEMS BY PARALLEL MATRIX SWEEP ALGORITHM

E.N. AkimovaI.I. Gorbachev2, V.V. Popov1

1 Institute of mathematics and mechanics Urals Div. of RAS, Ekaterinburg

2 Institute of metal physics Urals Div. of RAS, Ekaterinburg

The parallel matrix sweep algorithm for solving the system of equations with block-diagonal matrices is proposed and realized on the Multiprocessor Computing System MVS-1000. This algorithm is implemented for solving the testing problem of multicomponent diffusion saturation of a plate. The numerical experiments on the investigation of efficiency and speed up coefficients of the parallel algorithm are carried out.

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

где N - число компонентов сплава; г - пространственная координата; С, - концентрация у-го компонента; - парциальные коэффициенты взаимной диффузии; ц - показатель степени, зависящий от симметрии задачи: 0 - для плоской, 1 - для цилиндрической, 2 - для сферической.

1. Введение

/

\

О)

86

Е.Н. Акимова, ИИ. Горбачев, ВВ. Попов

Многокомпонентные диффузионные задачи, как правило, не решаются аналитически, что заставляет использовать численные методы (см. [1-2]). Для решения диффузионных задач наибольшее распространение получил метод конечных разностей [3]. При решении систем уравнений типа (1) целесообразно использовать абсолютно устойчивую неявную разностную схему. В этом случае система дифференциальных уравнений путем разностной аппроксимации дифференциального оператора сводится к системе матричных уравнений, имеющих блочно-трехдиагональную структуру. Для ¡'-го компонента в к-м узле пространственной сетки система уравнений имеет вид

£ [ 4С; (к-1) + 4с;(к) + (к +1)] = 4 , (2)

н

где а\к, Ь/к, с\к, с1'к - коэффициенты, рассчитываемые в зависимости от модели, С ■ {к) - концентрация у'-го компонента в к-м узле сетки.

В случае неподвижных узлов сетки коэффициенты уравнения (2) записываются в следующем виде:

1 2 , ЦАк-1/2,1 + 1)

а' =--------г4 (к -1/2+1)--^-—-—;

гч(к,1 +1) г(к + 1,1 + 1)-г(к-1,1 + 1) г(к,1 + 1)-г(к-1,1 + 1)

„У 1 1 2

Чк И=г

т(/ + 1)-т(/) гч{к,1 + \) г(Л + 1,/+1)-г(А:-1,/ + 1)

йц(к + 1 2,1 + 1) , Д,(*-1/2,/ + 1)

х(гд(к + 1/2,1 + 1)---^-—--— + г4 (к-1/2,1 + 1)--^-—---);

' г{к +1,1 + 1)-г(к,1 +1) г(к,1 +1) — г(к — 1,/ + 1)

¡\ 1 2

с

Г1 (к+ 112,1 + 1)--Ч--:--— + г" (к-112,1 + 1) 4

г(к + 1,1 +1 )-г(к,1 +1) г(к,1 +1) -г(к-1,1 +1)

1 2 , ¿¡Лк+ 1/2,1 + 1)

Ьк =-!------г4 (к+ 1/2,1 + 1)--^-—-—;

гЦк,1 +1) г(к + \,1+1)-г(к-1,1 + 1) г(к + 1,1 + 1)-г(к,1 + 1)

т(/ + 1)-т(/)

Здесь к - номер узла пространственной сетки, / - номер узла сетки по времени. £>^{к-\/2,1) и Г)^(к+ 1/2,1) - коэффициенты диффузии между (А-1)-м и к-м узлами сетки и

между к-м и (£+1)-м узлами сетки, соответственно.

Для реальных диффузионных задач коэффициенты диффузии обычно зависят от концентраций, вследствие чего уравнения системы (2) не являются линейными. Поэтому приходится использовать итерационную процедуру, на каждом шаге которой коэффициенты диффузии предполагаются постоянными и в уравнения подставляются их значения, взятые на предыдущей итерации, а для первой итерации - на предыдущем временном слое [4]. Таким образом, систему (2) на каждом временном шаге приходится решать многократно, что существенно увеличивает затраты машинного времени.

Наиболее эффективным методом решения систем с блочно-трехдиагональными матри-

Решение задач диффузии с помощью параллельного алгоритма матричной прогонки

87

цами является алгоритм матричной прогонки [5]. Классический вариант этого алгоритма является последовательным. В настоящее время достаточно перспективным является ускорение вычислений за счет распараллеливания алгоритмов, поскольку многопроцессорные суперкомпьютеры становятся все более доступны. Для написания эффективной параллельной программы требуется модификация классического алгоритма. Параллельный алгоритм матричной прогонки предложен в работе [6].

Целью данной работы является реализация параллельного алгоритма матричной прогонки на многопроцессорном вычислительном комплексе МВС-1000 с помощью библиотеки MPI [7] на языке Фортран 90. Проведены численные эксперименты на основе решения модельной задачи. Исследована эффективность параллельного алгоритма.

2. Параллельный алгоритм матричной прогонки

Рассмотрим систему уравнений с блочно-трехдиагональными матрицами

.-лр^+ся-вры =F„ « = U-.N-1, . (3)

rANYN.x+CNYN=FN, i = N,

где Yj - искомые векторы размерности n, Fi - заданные векторы размерности n, Ajt В-, С, - матрицы размерности п*п.

При построении параллельного алгоритма векторы YK , К = 0N , N = L M , выбираются в качестве параметрических неизвестных на L интервалах распараллеливания.

Относительно YK строится редуцированная система уравнений. Для этого на интервалах (К,К + М) рассматриваются следующие задачи:

-AtUl[+C,Ul-B,Ulx =0, UlK =

0, U"K

-w-i+ciï-Biï« =0,

~Ау"-1+С,У" -В^", =0,

UI

и"

V к

(4)

V -

V -

V ' г к+м

(5)

WK =

W

Wt

к+м

(6)

где ¡ = К + \,...,К + М

Утверждение. Если и,■',..., и" - решения задач (4), V- - решения задач (5),

IУ( -решения задачи (6), а У: -решения исходной задачи (3) на (К, К + М), то

V, = {и\и}...и?) гк +(У/У12..УГ ) Укш + (V,. (7)

После подстановки соотношений (7) в исходную систему (3) в точках К = 0,Л/,..., /V, по-

88

EH. Акимова, ИИ. Горбачев, В В. Попов

Решение задач ài

лучим систему уравнений относительно параметрических неизвестных Ук. Эта система уравнений по своей структуре аналогична (3), имеет меньшую размерность и следующий вид:

■ВМ.

к-\\Ук-м + [сК ~ aKvк = FK+AKWK_,+BKWK+„

] ^N-U + [Ov A-NVN-1 ] *Л< >

JK"K+l i'K

к = о,

VK+M ~

K = M,2M,...,N-К = М,

M,

(8)

где и к и Ук - матрицы размерности пуп.

Задача (8) решается классическим алгоритмом матричной прогонки на одном процессоре, например, на НоэЬпроцессоре, задачи (4) - (6) решаются независимо на I интервалах распараллеливания на! процессорах.

Матрицы ип и вектор Щ на интервалах {К,К + М) вычисляются независимо на Ь процессорах по следующим формулам, а) Прямой ход прогонки:

¡ = К + 2,...,К + М-\

а, = [С, -Да,._,]"'Я,..

Ук+i ~ ^K-ti^K+i >

-ыГ'ДР,-.,

(9)

м].

в) Обратный ход прогонки:

'К+М-\ ~ Рк+М-1> 'К+М-1 U,=*,VM+ Р/, V,=a,VM,

(10)

~ак+м-\1 ^V+m-I ~YAT+W-P щ = a:fVM + у,., i = К + M - 2,..., К +1.

После вычисления параметров YK остальные искомые неизвестные находятся по формуле (7) также независимо на каждом из L интервалов на L процессорах.

Схема параллельного алгоритма имеет вид: (9) —> ( 10) —> (8) —> (7).

3. Результаты численных экспериментов

Последовательный и параллельный алгоритмы матричной прогонки реализованы на МВС-1000 - российском массивно-параллельном суперкомпьютере третьего поколения. Вычислительная система МВС-1000/16 производства НИИ «Квант» состоит из 16 процессоров Intel Pentium HI-800, 256 Мбайт памяти, 10 Гбайт диска, двух 100 Мбит сетевых плат (Digital DS21143 Tulip и Intel PRO/lOO). Учебный вычислительный кластер состоит из 8 Intel Pentium IH-700, 128 Мбайт памяти, 14 Гбайт диска, 100 Мбит сетевой платы 3Com Зс905В Cyclone. Первые 16 процессоров работают быстрее, остальные 8 процессоров работают более медленно.

Проведено сравнение эффективности и ускорения последовательного и параллельного алгоритма матричной прогонки.

Написано несколько программ с помощью библиотеки MPI на языке Фортран 90: последовательный классический алгоритм матричной прогонки (ПКА), последовательный модифицированный алгоритм матричной прогонки (ПМА) и параллельный алгоритм матричной прогонки. При этом была написана на языке Фортран вспомогательная библиотека для работы с матрицами и векторами, содержащая операции умножения, сложения, вычитания, обращения матриц, сложения и вычитания векторов, умножения матрицы на вектор.

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

где Тт - вреи т (т > 1), Г, -ставляет собо{ ные обмены, т.

В обще! идеальном сл; времени обме за счет наклал

В табл ния системы ; а также пара] размерности

(число п

Резу имеет хоре при сравне цессоров в

4. Тестова

С п диффузио граничны] шалась в чальной » зионной ] стоянные вую пове

Гр

С

Sm=T,/Tm, Em=Sm/rn,

É

■ В Попов

ва уравне-с

(8)

» ..цессо-рас-

« э на £

(9)

(10)

!

эорму-

семы на « Вы-:ров 1п-

I РепПигп Пер-

зго

: восле-|и0дифи-про-

с

гния ко-

Решение задач диффузии с помощью параллельног

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком