(первая глубина
p
= 3
N
) и на сетках первого уровня (вторая глубина
p
= 3
2
N
), т.е.
S
Σ
>
max(
S
0
, S
1
)
и
E
Σ
>
max(
E
0
, E
1
)
.
Влияние обмена данными на эффективность параллелизма.
Обмен данными между процессорами приводит к уменьшению эффек-
тивности параллелизма. Время исполнения многопроцессорной про-
граммы можно представить в виде
T
(
p
) =
T
(1)
p
+
T
o
,
где
T
(1)
есть время, необходимое для выполнения программы на од-
нопроцессорном компьютере, а
T
o
— время, необходимое для обменов
данными. Тогда, согласно (2) и (3), выражения для ускорения и парал-
лелизма принимают вид
S
p
=
p
E
p
=
T
(1)
T
(1)
p
+
T
o
.
Положим, что время, необходимое для обменов данными, пропорцио-
нально времени, необходимому для выполнения программы на одно-
процессорном компьютере, т.е.
T
o
=
αT
(1)
,
где
α
>
0
— коэффициент пропорциональности. Тогда
S
p
=
p
E
p
=
p
1 +
pα
,
т.е. наличие обменов данными (
α
6
= 0
) приводит к снижению ускоре-
ния и эффективности параллелизма. К сожалению, значение коэффи-
циента
α
зависит от программных и аппаратных средств многопроцес-
сорного компьютера и от решаемой задачи, поэтому получить оценку
α
теоретическими методами весьма затруднительно. Проще экспери-
ментально измерить величину эффективности параллелизма и затем
определить значение параметра
α
по формуле
α
=
1
p
1
E
p
−
1
.
В частности, при
E
p
= 50
% величина
α
составит
1
/p
.
В оценках типа (10) или (12) время обмена данными при выпол-
нении сглаживающих итераций на уровнях с мелкими сетками учтено
значениями эффективностей
E
0
и
E
1
. Однако отсутствует учет време-
ни обмена данными при переходе к уровням с числом сеток, меньшим,
чем число процессоров. Поэтому в общем случае оценка (9) принима-
ет вид
78
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2011. № 4
