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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

107
1
1
1 1
1 1
( ) ( 1)
2
( ) ( 1)
2
( ) ( 1) ( 1) ( 1)
2 2
( ) ( 1) ( 1) ( 1)
2 2
,
,
,
,
l
l
l l
l l
l l
i i
i
l l
i i
i
l l l l
i i i i
i i
l l l l
i i i i
i i
a a
c c
b b c a
f f f f
(6.4)
где
1 1
( 1) ( 1) ( 1) ( 1)
2 2
/ , / 2
i l
l l l l l
i i i i
i i
a b c b i
с шагом
l
до
l
n
с первоначальными значениями
(0) (0) (0) (0)
, , ,
i i i i i i i i
a a b b c c f f
и с последующим нахождением неизвестных
i
x
по формуле
1 1
( 1) ( 1) ( 1) ( 1)
2 2
( ) / ,
l l
l l l l
i i i i i
i i
x f a x c x b
(6.5)
где
1
, 1,...,2,1, 2
l
l q q i
с шагом
1
2
l
до
1
2
l
n
и
0
0
n
x x
.
На каждом уровне редукции по формулам (6.4) и (6.5) произво-
дятся независимые вычисления, которые могут выполняться одно-
временно. Рассмотрим параллельную реализацию метода. Посколь-
ку число уравнений
2 1
q
n
, для равномерной загрузки число
процессорных элементов (ПЭ) будем выбирать как
2
r
size
, где
,
r q
– натуральные числа
(0 )
r q
. Каждый ПЭ ведет расчеты в
своей части системы из
1
n
m
size
уравнений и обменивается рас-
четными данными, которые вычисляются и находятся в адресном
пространстве других ПЭ.
Прямой ход редукции состоит из (
1
q
)-го шага. На первом шаге
циклическая редукция выполняется для m неизвестных на каждом
ПЭ, здесь исключаются неизвестные с нечетными индексами и пе-
ресчитываются коэффициенты с индексами i, кратными 2, но не
кратными 4, затем коэффициенты
(1) (1) (1) (1) (1)
( , , , )
i i i i i
P a b c f
пересы-
лаются: на левый ПЭ – коэффициент с минимальным индексом,
кратным 2, но не кратным 4, а на правый ПЭ – с максимальным
индексом, кратным 2, но не кратным 4. На 2-м, 3-м,…,
( 2)
q
-м ша-
гах пересчитываются и рассылаются по той же схеме коэффициенты
( )
, 2,3,... 2
l
i
P l q
с соответствующими индексами i. При прямом
ходе максимальная степень параллелизма наблюдается до
( )
q r
-го шага, затем она начинает падать. Это связано с останов-
кой ПЭ, на которых новые значения коэффициентов уравнений не

Страницы