Решение систем линейных уравнений является важной частью многих алгоритмов. Получение точного решения аналитическими методами является сложной вычислительной задачей, поэтому там где это возможно применяются численные методы. Не всегда необходимо знать точное решение, часто достаточно определить его с заданной точностью. Одним из численных методов решения СЛАУ является метод Якоби. Данный метод будет рассмотрен в данной работе.

Рассмотрим систему линейных уравнений: ,где

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

Сборка всего вектора на каждом узле важна, так как результирующий вектор одной итерации является исходным приближением для другой.

Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой:

T = k * (2*n^2 - n)

, где k – число выполненных итераций, а n – число уравнений.
Время, затраченное на параллельное выполнение алгоритма на p процессорах без учета затрат на передачу данных, выражается формулой:

T(p) = k/p * (2*n^2 - n)

Тогда ускорение равно:

S = T(1) / T(p) = p

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

E = T1 / p*Tp = 1

Разработанный способ параллельных вычислений позволяет достичь идеальных показателей ускорения и эффективности.
Определим время, затрачиваемое на передачу данных. Для этого используем модель Хокни.
Первоначальная рассылка данных требует следующее время:

Tcomm1 = (p-1) * (4*alfa + (n^2 / p + n) / betta)

, где alfa - латентность, betta - пропускная способность сети.
Передача данных, выполняемая в итерационном процессе, затрачивает следующее время:

Tcomm2 = k * (p-1) * (3*alfa + (n / p + n) / betta)

, где k - количество выполненных итераций.
В итоге общее время передачи данных выражается формулой:

Tcomm = (p-1) * (4*alfa + (n^2 / p + n) / betta) + k * (p-1) * (3*alfa + (n / p + n) / betta)

Это время зависит от числа итераций. Как правило, их количество меньше числа уравнений n. Значит время на передачу данных можно оценить величиной:

Tcomm = O(n^2)

В свою очередь и ко времени выполнения алгоритма применима та же оценка:

T = O(n^2)

Если число итераций будет сравнимо с n, то для времени выполнения алгоритма будет справедлива уже другая оценка:

T = O(n^3)

Эксперименты проводились на компьютере на основе двуядерного процессора Core 2 Duo E8400@3.6 GHz, 4Gb RAM@1066MHz под управлением Windows 7 Professional 64-bit. В таблице представлены результаты экспериментов, где T - время выполнения, S* - теоретическая оценка ускорения, S - экспериментальное ускорение.

Размер матрицы	Последоваетльный алгоритм / Параллельный алгоритм в один процесс, мс	Параллельный алгоритм
		2 процесса			4 процесса
		T	S*	S	T	S*	S
300	109/134	94	1,694721	1,425531	107	1,306086	1,252336
500	327/351	202	1,863552	1,737624	221	1,306086	1,252336
700	639/664	375	1,920372	1,770667	392	1,788972	1,693878
1000	1380/1415	890	1,957407	1,589888	804	1,886990	1,759950
1500	3105/3171	1872	1,976579	1,693910	1898	1,940357	1,670706

Работу выполнил Сморкалов Григорий, студент группы 83-03.