Лекции по параллельным вычислениям. Гергель В.П - 151 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

151
Анализ эффективности
Пусть n – порядок системы линейных уравнений, а s, s<n – число исполь-
зуемых процессоров, т.е. матрица А имеет размер n×n, а n/s – размер полосы на
каждом процессоре (для простоты полагаем, что n/s – целое число). Определим
сложность параллельного варианта метода Гаусса.
В прямом ходе алгоритма для выбора ведущей строки на каждой итерации
и каждом процессоре должно быть определено максимальное значение в столб-
це с исключаемой неизвестной в пределах закрепленной за ним полосы. По ме-
ре исключения неизвестных количество строк в полосах сокращается. После
сбора полученных максимальных значений, определения и рассылки ведущей
строки на каждом процессоре выполняется вычитание ведущей строки из каж-
дой строки оставшейся части строк своей полосы матрицы A.
Как мы установили выше, общие затраты на выполнение действий в одной
строке на i-й итерации,
2
0
n
i
составляет
12
in операций. Если при-
менена циклическая схема распределения данных между процессорами, то на
i-й итерации каждый процессор будет обрабатывать примерно
s/in
строк.
С учетом сказанного, общее число операций параллельного варианта прямого
хода метода Гаусса определяется выражением
2
1
0
2 1
n
s
i
n i
T n i
s
.
Заметим, что
s/in
, как правило, не будет целым. Для построения прибли-
женных достаточных оценок не будем учитывать операцию округления, но на
каждой итерации введем операции с одной дополнительной строкой:
.122
1
1212
2
0
2
0
2
2
0
2
0
1
n
i
n
i
n
i
n
i
s
ininin
s
inin
s
in
T
(11.7)
На каждой i-й итерации обратного хода после рассылки очередной вычис-
ленной неизвестной на каждом процессоре обновляются значения правых час-

Страницы