Параллельная реализация итерационного метода решения СЛАУ

1.

Параллельная реализация итерационного метода
решения СЛАУ

2.

Реализация метода Якоби (1 шаг)
for i = 1 : n
x_new(i) = b(i);
for j = 1 : n
if ( j ~= i )
x_new(i) = x_new(i) - a(i,j) * x(j);
end
end
x_new(i) = x_new(i) /a(i,i);

3.

Вычисление невязки
eps = abs(x_new - x)

4.

Необходимо проверить
Сходимость и правильность решения для
произвольной размерности матрицы
И для любого вида матрицы с выраженным
диагональным преобладанием (диагональный элемент
любой строки по модулю больше суммы
недиагональных)
Для проверки задаем решение в виде вектора из 1
и вычисляем для этого решения правую часть
Матрицу задаем в виде диагональной малой

5.

Измерение времени
Два вызова функции gettimeofday
●#include <sys/time.h>
struct timeval tv1,tv2;
gettimeofday(&tv1,NULL);
DoSomeThing();
gettimeofday(&tv2,NULL);
double dt_sec = (tv2.tv_sec – tv1.tv_sec);
double dt_usec = (tv2.tv_usec – tv1.tv_usec);
dt = dt_sec + 1e-6*dt_usec;

6.

Перед тем, как переходить к
распараллеливанию, зафиксируйте (для
размерности 10х10)
Ход сходимости (перенаправлением вывода в
файл):
<Номер итерации> <значение невязки>
Решение, которое получается в итоге (не желаемый
вектор из всех единиц, а именно то, что получается)
Параллельный алгоритм

7.

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

8.

Декомпозиция
(разделение задачи между N параллельными процессами)
Матрица A
Вектора b и x
Процесс 0
0
Процесс 1
1
Процесс 2
2
Процесс N-1
N-1

9.

Распараллеливание.
Что изменяется?
Размерность матрицы и векторов(N строк)
Последовательный вариант:
#define N 10
Параллельный вариант (P процессов)
#define P 2
#define N (10/P)
Размерность матрицы меняется только по строкам
Каждый процесс инициализирует только “свою” часть
матрицы и вектора правой части
Не нужно создавать всю матрицу в одном процессе и
потом рассылать всем прочим

10.

Почему необходимы пересылки,
или зависимость по данным
Вектор
x_new
Для того, чтобы вычислить x_new,
необходимо
Реально в памяти одного процесса
Вектор
Вектор x x_new
Матрица A
0
Процесс 00
0
1
Процесс 1
1
2
N-1
=
Процесс 2
Процесс N-1
*
2
N-1
i
Матрица A
Процесс i
Вектор x
i

11.

Пересылки
Процесс i содержит только часть вектора x
Перед вычислением x_new необходимо переслать
недостающие части с других процессов
Вектор x, процесс 0
Вектор x, процесс i
Вектор x, процесс N-1
0
0
0
i
i
i
N-1
N-1
N-1

12.

Декомпозиция
(разделение задачи между N параллельными процессами)
Матрица A
Вектора b и x
Процесс 0
0
Процесс 1
1
Процесс 2
2
Процесс N-1
N-1

13.

Декомпозиция
(разделение задачи между N параллельными процессами)
Матрица A
Вектора b и x
Процесс 00
0
Процесс 1
1
Процесс 2
2
Процесс N-1
N-1

14.

Параллельная реализация метода Якоби (1 шаг)
for i = 1 : n
x_new(i) = b(i);
for j = 1 : n
if ( j ~= i )
x_new(i) = x_new(i) - a(i,j) * x(j);
end
end
x_new(i) = x_new(i) /a(i,i);