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

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

Особенностью параллельной реализации метода Якоби в отличие от последовательной версии является разбиение преобразованной матрицы А на части, которые передаются процессам-потомкам от родительского. Каждый процесс-потомок производит расчеты лишь со своей частью матрицы, вычисляя часть вектора xk+1, которая затем передается родительскому процессу с целью проверки критерия останова. Если критерий останова не выполнился, то обновленное приближение решения передается всем процессам-потомкам и они выполняют следующую итерацию алгоритма. Такая схема позволяет более эффективно расходовать системную память и уменьшает количество пересылаемых данных.

Демонстрация работы параллельного алгоритма

Выполнение k+1-ой итерации происходит по следующей схеме:

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

Время, затраченное на последовательное выполнение алгоритма, выражается следующей формулой:
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)

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

Эксперименты проводились на следующей конфигурации:
Processor: AMD Turion(tm) X2 Dual-Core Mobile RM-70 2.00GHz
RAM: 3 Gb
OS: Windows 7 Ultimate x86

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

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

Размер матрицы	Количество итераций	Последовательный	Параллельный (2 процесса)	Ускорение (2 процесса)	Параллельный (4 процесcа)	Ускорение (4 процесса)
512 * 512	10000	10.6055	7.71639	1.37	12.0014	0.88
1024 * 1024	10000	41.6292	29.6758	1.4	14.4	2.18
2048 * 2048	10000	179.711	123.396	1.46	152.437	1.18

Из полученных данных видно, что параллельная работа алгоритма дает замедление. Это связано с накладными расходами на передачу данных между процессами. Также при обмене данными требуется синхронизировать работу процессов, что тоже не улучшает производительность.

В таблице 2 приведены теоретическое и экспериментальное время:

Таблица 2. Сравнение теоретических оценок и экспериментальных данных.

Размер матрицы	Теоретическое время (2 процесса)	Экспериментальное время (2 процесса)	Теоретическое время (4 процесса)	Экспериментальное время (4 процесса)
512 * 512	5.3027	7.71639	2.6513	12.0014
1024 * 1024	20.8146	29.6758	10.4073	43.9385
2048 * 2048	89.855	123.396	44.927	152.437

Как видно из приведённых результатов при локальных вычислениях (на одном компьютере) с числом процессов, равным числу ядер ЦП (2 ядра), выигрыш во времени происходит практически сразу и ускорение близко к идеальному (идеальное ускорение на двух ядрах = 2). При вычислениях в 4 процесса получаем замедление. Это связано с дополнительными коммуникационными расходами при передаче данных между большим числом процессов. Из полученных данных видно, что параллельная работа алгоритма дает замедление. Это связано с накладными расходами на передачу данных между процессорами и разделением времени ЦП. Также при обмене данными требуется синхронизировать работу процессоров, что тоже не улучшает производительность.

Об авторах

Заикин А., Роменский С., группа 8410.