Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

LIBRARY PARALLEL ITERATIVE METHODS FOR LINEAR ALGEBRAIC EQUATION SOLVER FOR CONVECTION – DIFFUSION ON THE BASIS OF DECOMPOSITION ONE SPATIAL DIRECTIONS

Chistyakov A.E. 1 Khachunts D.S. 1 Nikitina A.V. 1 Protsenko E.A. 2 Kuznetsova I.Yu. 2
1 GOU VO Public Educational Institution «Scientific Research Institute of Multiprocessor Computer Systems named after Acad. A.V. Kalyaev of Southern Federal University»
2 GOU VO «Engineering and Technological Academy of the Southern Federal University»
In this paper carried out the work on a parallel library implementation of iterative methods solvers of linear In this paper carried out the work on a parallel library implementation of iterative methods solvers of linear algebraic equations (SLAE) convection-diffusion problems based on decomposition one spatial direction. Built library of two-layer iterative methods for the resolution of devyatidiagonalnyh difference equations. Tabulated values obtained the number of iterations for solving grid equations by iterative methods on the time step variable. Developed parallel algorithms for the study of the library, implemented as a set of programs. When parallel implementation used decomposition methods grid areas in one direction for the computational complexity convection-diffusion problems, taking into account the architecture and parameters of multiprocessor computer systems. Obtained by the execution of one iteration of the Jacobi method and MPTM respectively on different grids, as well as the values of acceleration and efficiency of the parallel algorithm, time-dependent arithmetic operation, data transfer time and latency. The efficiency MPTM for solving grid equations with nonselfadjoint operators in a wide range of set parameters.
parallel algorithms
library of iterative methods
problems convection-diffusion

Для решения двумерной задачи диффузии-конвекции,, была построена библиотека двухслойных итерационных методов, предназначенных для решения девятидиагональных сеточных уравнений. Данная библиотека решателей систем линейных алгебраических уравнений (СЛАУ) состоит из:

– метода Якоби [4];

– метода минимальных поправок;

– метода скорейшего спуска;

– метода Зейделя;

– метода верхней релаксации;

– адаптивного МПТМ вариационного типа [1; 2; 6].

Разработанная библиотека итерационных методов была протестирована на модельной задаче диффузии-конвекции-реакции [9; 11]. Задача решена на сетке размером 100×100, шаги по пространственным переменным равны 1 м, коэффициент турбулентного обмена μ=10 м2/с, скорость конвективного переноса равна нулю. Функция, описывающая распределение и интенсивность источников веществ, представлена точечным источником. Для решения модельной задачи использованы схемы с весами, при этом вес схемы задавался равным 0,5. Шаг по временной переменной менялся от 0,001 до 1000 с. Завершение работы решателей СЛАУ происходило при выполнении следующего условия: равномерная норма вектора невязки меньше заданного значения [3].

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

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

Таблица 1

Зависимости количества итераций решения сеточных уравнений итерационными методами от шага по временной переменной

Шаг по временной переменной

Количество итераций

Метод Якоби

Метод минимальных поправок

Метод скорейшего спуска

Метод Зейделя

Метод верхней релаксации

МПТМ

0.001

6

6

6

5

43

5

0.005

8

8

8

8

43

6

0.01

10

10

10

8

45

6

0.05

23

23

23

15

56

10

0.1

37

36

37

22

61

12

0.5

138

134

138

70

60

27

1

256

247

256

126

60

28

5

1138

1077

1138

558

131

50

10

2233

2110

2233

1073

246

72

50

10160

9523

10160

4774

1074

158

100

19966

18625

19966

9320

2096

218

500

99651

92789

99651

46383

10399

1281

1000

199295

185529

199295

92739

20781

4382

Не трудно заметить, что МПТМ является наиболее эффективным из предложенных методов. При больших шагах по временной переменной МПТМ требуется наименьшее количество итераций, по сравнению с остальными методами. Достаточно эффективен и метод верхней релаксации, но при малых шагах по временной переменной его использовать не целесообразно. При решении сеточных уравнений методы Якоби, Зейделя и вариационного типа показали свою эффективность в узком диапазоне задаваемых параметров, однако использовать данные методы при решении плохо обусловленных задач не целесообразно.

Алгоритм параллельной реализации попеременно-треугольного метода

Схему итерационного двухслойного модифицированного попеременно-треугольного метода запишем в виде:

, ,

где xn – вектор решения; – вектор поправки; А – оператор сеточного уравнения; D – диагональная часть оператора A; w – итерационный параметр; R1, R2 – верхняя и нижняя треугольные части оператора A; – вектор невязки; f – правая часть сеточного уравнения.

Для параллельной реализации адаптивного МПТМ использованы методы декомпозиции области по одному направлению. Наиболее трудоемким расчетом с точки зрения построения параллельной программной реализации является расчет вектора поправки, который выполняется в два шага:

1) ,

2) .

На первом шаге рассчитываются элементы вспомогательного вектора снизу вверх, а затем, зная его, на втором шаге находятся элементы вектора поправки сверху вниз. Схемы расчета вспомогательного вектора и вектора поправки представлены на рис. 1 (стрелками показаны направления счета и передачи).

а) б)

Рис. 1. Схемы расчета вспомогательного вектора yn (а) и вектора поправки wn (б).

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

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

Для решения задачи транспорта МВС использован адаптивный модифицированный попеременно-треугольный метод (МПТМ) минимальных поправок. При параллельной реализации использованы методы декомпозиции сеточных областей для вычислительно трудоемких задач диффузии-конвекции, учитывающие архитектуру и параметры многопроцессорной вычислительной системы. Максимальная производительность МВС составляет 18,8 терафлопс. В качестве вычислительных узлов используются 128 однотипных 16-ядерных Blade-серверов HP ProLiant BL685c, каждый из которых оснащен четырьмя четырехъядерными процессорами AMD Opteron 8356 2.3GHz и оперативной памятью в объеме 32 ГБ. В таблицах 2 и 3 приведены временные затраты выполнения одной итерации методом Якоби и МПТМ соответственно на различных сетках, а также значения ускорения и эффективности для различного числа вычислительных ядер.

Таблица 2

Ускорение и эффективность работы параллельного варианта метода Якоби

 

 

100x100

200x200

500x500

1000x1000

2000x2000

5000x5000

1

Время

0.000271

0.00429

0.00846

0.03608

0.138

1.633

Ускорение

1

1

1

1

1

1

Эффективность

1

1

1

1

1

1

2

Время

0.000074

0.00060

0.00866

0.02193

0.08041

0.825

Ускорение

3.662

7.15

0.977

1.645

1.716

1.979

Эффективность

1.831

3.575

0.488

0.823

0.858

0.99

4

Время

0.000052

0.00017

0.00341

0.00978

0.04376

0.533

Ускорение

5.212

25.235

2.481

3.689

3.156

3.064

Эффективность

1.303

6.309

0.62

0.922

0.788

0.766

8

Время

0.000029

0.000089

0.00207

0.00745

0.02924

0.188

Ускорение

9.345

48.202

4.087

4.843

4.72

8.686

Эффективность

1.168

6.025

0.511

0.605

0.59

1.086

16

Время

0.000025

0.000063

0.00054

0.00628

0.01921

0.142

Ускорение

10.84

68.095

15.667

5.745

7.184

11.5

Эффективность

0.677

4.256

0.979

0.359

0.449

0.719

32

Время

0.000060

0.000089

0.00018

0.00247

0.01051

0.078

Ускорение

4.517

48.202

47

14.607

13.13

20.936

Эффективность

0.141

1.506

1.469

0.456

0.41

0.654

64

Время

0.000125

0.000142

0.00016

0.00110

0.00584

0.044

Ускорение

2.168

30.211

52.875

32.8

23.63

37.114

Эффективность

0.034

0.472

0.826

0.513

0.369

0.58

128

Время

-

0.000364

0.00040

0.00048

0.00485

0.017

Ускорение

-

11.786

21.15

75.167

28.454

96.059

Эффективность

-

0.092

0.165

0.587

0.222

0.75

256

Время

-

-

0.000801

0.000653

0.003215

0.00987

Ускорение

-

-

10.562

55.253

42.924

165.434

Эффективность

-

-

0.041

0.216

0.168

0.646

512

Время

-

-

-

0.001294

0.002051

0.00715

Ускорение

-

-

-

27.883

67.284

228.36

Эффективность

-

-

-

0.054

0.131

0.446

Из таблиц 2 и 3 видно, что максимальное значение эффективности достигалось на четырех вычислительных узлах и сетках 200х200. При этом возникает «суперлинейное ускорение». Эта аномалия вызвана следующей причиной. С увеличением количества вычислителей растёт суммарный объём их оперативной и кэш-памяти. Поэтому большая часть данных задачи вмещается в оперативной памяти и не требует подкачки с диска и вмещается в кэше.

Таблица 3

Ускорение и эффективность работы параллельного варианта МПТМ

 

 

100x100

200x200

500x500

1000x1000

2000x2000

5000x5000

1

Время

0.001183

0.010633

0.026031

0.10584

0.381988

3.700073

Ускорение

1

1

1

1

1

1

Эффективность

1

1

1

1

1

1

2

Время

0.000446

0.003435

0.01932

0.05579

0.264114

1.880677

Ускорение

2.652

3.095

1.347

1.897

1.446

1.967

Эффективность

1.326

1.548

0.674

0.949

0.723

0.984

4

Время

0.000232

0.00106

0.005755

0.026683

0.132585

1.2655

Ускорение

5.099

10.031

4.523

3.967

2.881

2.924

Эффективность

1.275

2.508

1.131

0.992

0.72

0.731

8

Время

0.000179

0.000878

0.004379

0.023322

0.092771

0.489768

Ускорение

6.609

12.11

5.945

4.538

4.118

7.555

Эффективность

0.826

1.514

0.743

0.567

0.515

0.944

16

Время

0.000231

0.000407

0.001869

0.013105

0.085056

0.472151

Ускорение

5.121

26.125

13.928

8.076

4.491

7.837

Эффективность

0.32

1.633

0.87

0.505

0.281

0.49

32

Время

0.000365

0.0005

0.001404

0.008871

0.045913

0.318709

Ускорение

3.241

21.266

18.541

11.931

8.32

11.61

Эффективность

0.101

0.665

0.579

0.373

0.26

0.363

64

Время

0.000642

0.000748

0.001557

0.004189

0.026844

0.182296

Ускорение

1.843

14.215

16.719

25.266

14.23

20.297

Эффективность

0.029

0.222

0.261

0.395

0.222

0.317

128

Время

-

0.001612

0.002064

0.003442

0.016437

0.076545

Ускорение

-

6.596

12.612

30.75

23.24

48.338

Эффективность

-

0.052

0.099

0.24

0.182

0.378

256

Время

-

-

0.005434

0.005446

0.012521

0.06318

Ускорение

-

-

4.79

19.434

30.349

58.563

Эффективность

-

-

0.019

0.076

0.119

0.229

512

Время

-

-

-

0.009793

0.012362

0.058805

Ускорение

-

-

-

10.808

30.9

62.921

Эффективность

-

-

-

0.021

0.06

0.123

Из приведенных таблиц также видно, что для каждой из расчетных сеток ускорение принимает наибольшее значение при определенном значении вычислителей, и при дальнейшем увеличении числа вычислительных ядер ускорение только уменьшается. Это связано с временными затратами на обмен данными между вычислителями. Из приведенных результатов расчетов видно, что методы с диагональными предобуславливателями (пример метод Якоби) лучше распараллеливаются, чем методы с треугольными предобуславливателями (пример МПТМ). Несмотря на это, параллельный вариант МПТМ является предпочтительнее метода Якоби для плохообусловленных задач, так как требует значительно меньшего числа итераций. Следует отметить, что адаптивный МПТМ нашел свое применение при решении задач аэродинамики [5; 10; 12] и транспорта донных материалов [7; 8].

Заключение

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

При параллельной реализации использованы методы декомпозиции сеточных областей по одному направлению для вычислительно трудоемких задач диффузии-конвекции, учитывающие архитектуру и параметры многопроцессорной вычислительной системы. Получены времена выполнения одной итерации методом Якоби и МПТМ соответственно на различных сетках, а также значения ускорения и эффективности параллельного алгоритма, зависящие от времени выполнения арифметической операции, времени передачи данных и латентности. Результаты использования многопроцессорных технологий показали, что максимальное значение эффективности достигалось на четырех вычислительных узлах и сетках 200х200 и равнялось 6,309 (метод Якоби) и 2,508 (метод МПТМ), а максимальное ускорение достигалось на 512 узлах и сетках 5000х5000 и равнялось 228,36 (метод Якоби) и 62,921 (метод МПТМ). Данные результаты расчетов говорят о том, что метод Якоби лучше распараллеливается по сравнению с методом МПТМ, однако, несмотря на это, для решения плохообусловленных задач параллельный МПТМ при больших шагах по временной переменной требует наименьшего числа итераций, что говорит о его предпочтении.

Работа выполнена при частичной финансовой поддержке Задания № 2014/174 в рамках базовой части государственного задания Минобрнауки России, а также при частичной финансовой поддержке РФФИ по проектам № 15-01-08619, № 15-07-08626 и № 15-07-08408.

Рецензенты:

Сухинов А.И., д.ф.-м.н., профессор, декан факультета физики, математики и информатики, ТГПИ им. А.П. Чехова (филиал) РИНХ, Таганрог;

Илюхин А.А., д.ф.-м.н., профессор, профессор кафедры математики, ТГПИ им. А.П. Чехова (филиал) РИНХ, Таганрог.