Рис. 2. Зависимость ускорения от числа процессоров при выполнении парал-
лельного алгоритма решения СЛАУ
На каждом
k
-м шаге исключения, когда ведущим является
k
-й стол-
бец исходной матрицы, хранящийся в компьютере
p
k
, этот компьютер
определяет номер ведущей строки (из строк с номерами
k . . . N
) и
передает его всем остальным компьютерам. Затем на каждом компью-
тере осуществляется перестановка строк. Эта операция требует край-
не незначительных временн ´ых затрат, так как между компьютерами
пересылается всего одно число, а пересылки переставляемых строк
не требуется. Затем
p
k
-й компьютер вычисляет столбец коэффициен-
тов, с которыми
k
-я строка должна вычитаться из всех остальных,
этот столбец пересылается на все компьютеры, и начинается процесс
вычитания строк, который выполняется на всех компьютерах одновре-
менно. Отметим, что вычитание происходит из всех строк матрицы,
в результате чего матрица сразу приводится к диагональному виду.
Все преобразования вектора правой части выполняются на компью-
тере с номером 0. На него же пересылаются диагональные элементы
преобразованной матрицы, после чего находится решение системы.
Данный алгоритм реализован авторами в виде программы на язы-
ке Fortran-90, расчеты по которой проводились на двух вычислитель-
ных комплексах — сети ПЭВМ и высокопроизводительном кластере
МВС-6000IM.
На рис. 2 представлены графики, характеризующие эффективность
предложенного параллельного алгоритма решения СЛАУ с квадратной
невырожденной матрицей порядка
N
= 5000
. Штриховые линии пока-
зывают максимально возможное (теоретически) ускорение, сплошные
— реальное ускорение, полученное в ходе расчетов.
В табл. 1 приведены значения ускорений, полученные при исполь-
зовании алгоритма на вышеуказанных вычислительных комплексах,
а также отношение, характеризующее эффективность сети ПЭВМ по
сравнению с МВС-6000IM.
Решение систем обыкновенных дифференциальных уравнений
(ОДУ).
При решении плоских задач гидродинамики и аэроупругости
92
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2009. № 1
