а время параллельного решения задачи — выражением
τ
NN
=
r
j
=1
t
cal
q
(
M
−
j
)(
lC
F
+
C
I
)
≈
t
cal
q
(
lC
F
+
C
I
)
M
2
NN
.
Здесь идалее
t
cal
— время выполнения арифметической операции на
одном процессоре используемой МВС.
Утверждение 1
. Ускорение
S
параллельного метода на основе рав-
номерной декомпозиции точек переключения оценивается величиной
S
≈
NN
2
.
Из утверждения 1 следует, что равномерная декомпозиция точек
переключения не может обеспечить ускорение, превышающее 50%
максимального потенциально возможного ускорения, равного
NN
.
Лучшей балансировкизагрузкиМВС можно добиться за счет нерав-
номерной декомпозиции точек переключения.
Неравномерная декомпозиция точек переключения
. Положим, что
процессор
P
i
выполняет интегрирование системы ОДУ (3) при упра-
влениях
U
Γ
a
, . . . , U
Γ
b
, а процессор
P
i
+1
— приуправлениях
U
Γ
b
+1
, . . . , U
Γ
c
,
1
a < b < c M
. Потребуем, чтобы времена решения задачи про-
цессорами
P
i
,
P
i
+1
былиравны, т.е. чтобы выполнялось равенство
T
i
=
T
i
+1
,
i
∈
[1 : (
NN
−
1)]
. В работе [7] показано, что для этого
величины
a, b, c
должны удовлетворять рекуррентному уравнению
c
2
−
2(
M
+ 1)
c
+
a
2
−
2
b
2
−
2
Ma
+ 2(2
M
+ 1)
b
= 0
.
(4)
Еслидля процессора
P
1
задать величины
a
=
a
1
= 1
,
b
=
b
1
, то
из выражения (4) последовательно легко найти управления, которые
должны обрабатывать процессоры
P
2
, P
3
, . . . , P
NN
.
Рассмотрим для примера ситуацию, когда
M
= 1000
,
b
1
= 100
.
Из уравнения (4) вытекает, что в данном случае можно обеспечить
приблизительно равномерную загрузку шести процессоров (таблица).
Отметим, что для процессора
P
6
число точек переключения вычислено
по остаточному принципу и не удовлетворяет уравнению (4).
Как показано в работе [7], при неравномерной декомпозиции то-
чек переключения время последовательного решения задачи можно
оценить выражением
τ
1
=
t
cal
q
(
lC
F
+
C
I
)
M
−
1 +
M
i
=1
(
M
−
i
) =
=
t
cal
q
(
lC
F
+
C
I
) (
M
−
1) (1 + 0
,
5
M
)
,
а время параллельного решения — выражением
τ
NN
=
t
cal
q
(
lC
F
+
C
I
) (
M
+ 1)
b
1
−
0
,
5
b
2
1
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2010. № 2 9
