Стр. 20 - Параллельное программирование
Упрощенная HTML-версия
ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
18
Рис. 2.1. Вычислительная модель алгоритма в виде графа
"операции-операнды"
Описание схемы параллельного выполнения алгоритма
Параллельно могут быть выполнены те операции алгоритма, между которыми
нет пути в рамках выбранной схемы вычислений (для вычислительной схемы
рис. 2.1, например, параллельно могут быть выполнены сначала все операции умно-
жения, а затем первые две операции вычитания).
Пусть
p
- количество процессоров, используемых для выполнения алгоритма,
тогда для параллельного выполнения вычислений необходимо задать множество
(
)
{
}
V i: it,iP,i
pH
∈
=
, в котором для каждой операции
i
∈
V
указывается номер
используемого для выполнения операции процессора
P
i
и время начала выполнения
операции
t
i
. Чтобы множество было реализуемым, необходимо выполнение сле-
дующих требований:
•
jP iP jt it:V j,i
≠⇒= ∈∀
, т.е. один и тот же процессор не должен назна-
чаться разным операциям в один и тот же момент времени;
•
( )
1
+≥⇒∈ ∀
i
j
t
t
R j,i
, т.е. к назначаемому моменту выполнения
операции все необходимые данные уже должны быть вычислены.
Определение времени выполнения параллельного алгоритма
Моделью параллельного алгоритма
(
)
p
p
H,GA
исполняемого с использованием
p
процессоров, будем называть вычислительную схему алгоритма
G
совместно с
множеством
H
p
. Время выполнения параллельного алгоритма определяется макси-
мальным значением времени, используемым во множестве (расписании)
H
p
(
)
(
)
1
max
,
+
=
∈
i
Vi
p
p
t
HGT
.
х
2
y
1
y
2
х
1
х
2
y
2
x
2
y
1
х
1
y
2
х
1
y
1
х
2
y
2
-х
2
y
1
x
1
y
2
-x
1
y
1
(х
2
y
2
- х
2
y
1
)-( x
1
y
2
-x
1
y
1
)
