Similar presentations:
Параллельная реализация итерационного метода решения СЛАУ. Реализация метода Якоби
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
Процесс 00
0
Процесс 1
1
Процесс 2
2
Процесс N-1
N-1
9.
Распараллеливание.Что изменяется?
Размерность матрицы и векторов(N строк)
Последовательный вариант:
#define N 10
Параллельный вариант (P процессов)
#define P 2
#define N (10/P)
Реальное количество итераций в циклах
(напр., 10/P вместо 10)
Добавляются пересылки данных
после вычисления x_new
Добавляется вычисление максимального
10.
Почему необходимы пересылки,или зависимость по данным
Вектор
x_new
Для того, чтобы вычислить x_new,
необходимо
Реально в памяти одного процесса
Вектор
Вектор x x_new
Матрица A
0
Процесс 0
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
Процесс 00
0
Процесс 1
1
Процесс 2
2
Процесс N-1
N-1
13.
Декомпозиция(разделение задачи между N параллельными процессами)
Матрица A
Вектора b и x
Процесс 0
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);