Постановка задачи

Необходимо реализовать параллельную программу, которая решает системы линейных алгебраических уравнений (СЛАУ) методом простой итерации (Якоби) с помощью библиотеки MPI. Также нужно провести теоретический анализ эффективности алгоритма, провести эксперименты.

Описание метода

Рассмотрим систему линейных уравнений: Ax=b, где A - матрица размером n*n, x-искомый вектор, b-вектор свободных членов. Алгоритм:
1) задаются: размерность системы n, eps-погрешность решения,начальное приближение: X0=(b1/a11, ..., bn/ann)
2) вычисляются элементы вектора Xk: xi = ( bi/aii - ∑aij*xj/aii )
3) проверяется критерий останова: если ||Xk - Xk-1|| < eps, то стоп, иначе на шаг2)

В общем случае метод не сходится, тем не менее если система обладает строгим диагональным преобладанием,то итерации будут сходится.

Параллельный алгоритм

При распараллеливании алгоритма предполагается, что размерность системы больше числа процессоров. Каждый процессор считает “свои” элементы вектора Х=(x1,x2,x3,...,xn).
Перед началом выполнения метода на каждый процессор рассылаются необходимые данные:
1)размерность системы N
2)начальное приближение X0
3)строки матрицы A
4)элементы вектора свободных членов b.

После получения необходимой информации каждый процессор будет вычислять соответствующие компоненты вектора X и передавать их главному процессору. Главный процессор при получении очередного приближения решения Xk должен сравнить его с предыдущим приближением Xk-1. Если норма разности этих векторов:

||Xk – Xk-1|| = max {|Xk,i – Xk,i-1|, i = 1,1,…n}
окажется меньше или равной заданной точности (eps), то вычисления закончатся. В противном случае вектор Xk поэлементно будет разослан всем процессам и будет вычисляться очередное приближение решения.

Анализ эффективности

Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой:
T(1) = k * (n^2 + n), где k – число выполненных итераций, а n – число уравнений.

Время, затраченное на параллельное выполнение алгоритма на p процессорах без учета затрат на передачу данных, выражается формулой:
T(p) = k * (n^2 + n)/p

Тогда ускорение равно:
S = T(1) / T(p) = p

Эффективность:
E = T(1) / p*T(p) = 1

Определим время, затрачиваемое на передачу данных. Для этого используем модель Хокни.

Первоначальная рассылка данных требует следующее время:
Tcomm1 = (p-1) * (alfa + w*(n^2 / p + n / p + n + 1) / betta), где alfa - латентность, w - размер элемента данных в байтах, betta - пропускная способность сети

Передача данных, выполняемая в итерационном процессе, затрачивает следующее время:
Tcomm2 = k * (p-1) * (alfa + w*n / betta), где k - количество выполненных итераций

В итоге общее время передачи данных выражается формулой:
Tcomm = (p-1) * (alfa + w*(n^2 / p + n / p + n + 1) / betta) + k * (p-1) * (alfa + w*n / betta)

Это время зависит от числа итераций. Как правило, их количество меньше числа уравнений n. Значит время на передачу данных можно оценить величиной:
Tcomm = O(n^2)
В свою очередь и ко времени выполнения алгоритма применима та же оценка:
T = O(n^2)

Если число итераций будет сравнимо с n, то для времени выполнения алгоритма будет справедлива уже другая оценка:
T = O(n^3)

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

Эксперименты проводились на следующей машине:
Intel Core-i5-2410M CPU @ 2.3GHz

Время работы алгортимов и полученные ускорения представлены в таблице1:

Таблица 1. Ускорение вычислений

Размер матрицы	Количество итераций	Последовательный	Параллельный (2 процесса)	Ускорение (2 процесса)	Параллельный (4 процесcа)	Ускорение (4 процесса)
500 * 500	3002	4.1	2.1	1.95	1.8	2.3
1000 * 1000	6800	28.5	14.5	1.96	12.7	2.24
2000 * 2000	10000	180	105	1.7	97	1.85

Об авторах

Мухутдинов Рамиль, Гаврик Дмитрий
группа 8409