Высокопроизводительные вычисления на кластерах. Беликов Д.А - 99 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

99
виду, а затем решается система с упрощенной матрицей. Наиболее
известной формой гауссова исключения является та, в которой сис-
тема линейных уравнений приводится к верхнетреугольному виду
путём вычитания одних уравнений, умноженных на подходящие
числа из других уравнений. Полученная треугольная система реша-
ется с помощью обратной подстановки.
Приведем псевдокод прямого хода метода Гаусса, где значения
верхнетреугольной матрицы в процессе вычислений переписывают-
ся в соответствующие элементы матрицы
A
:
do k=1,n-1
do i=k+1,n
l
ik
= a
ik
/a
kk
end do
do j=k+1,n+1
do i=k+1,n
a
ij
= a
ij
– l
ik
*a
kj
end do
end do
end do
В цикле
j
производится вычитание
k
-й строки матрицы
A
,
умноженной на соответствующее число, из расположенных ниже
строк. Правая часть системы (6.1)
b
добавлена к матрице
A
(стол-
бец
n
+1) и обрабатывается в ходе приведения к треугольному виду.
Рассмотрим параллельный алгоритм метода Гаусса. Для сбалан-
сированной загрузки процессоров исходная матрица коэффициентов
A
распределяется по p процессорным элементам (ПЭ) циклически,
т.е. первая строка расширенной матрицы помещается в 0-й ПЭ, вто-
рая – в 1-й ПЭ, и т.д., р-я – в (р-1)-й ПЭ. Затем (р+1)-я снова поме-
щается в 0-й ПЭ, (р+2)-я – в 1-й ПЭ и т.д. (рис. 6.1).
Рис. 6.1 Циклическая строчная схема распределения уравнений системы (6.1) по
процессорным элементам.
/
k n p
1
p+1
…
(k-1)p+1
ПЭ 0
2
p+2
…
(k-1)p+2
ПЭ 1
m
p+m
…
(k-1)p+m
ПЭ m-1
p
2p
…
kp
ПЭ p-1
…
…
…
…
…

Страницы