Стр. 23 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
21
• при выборе вычислительной схемы алгоритма должен использоваться
граф с минимально возможным диаметром (см. теорему 1);
• для параллельного выполнения целесообразное количество процессоров
определяется величиной ∞ TTp / ~
1 (см. теорему 5);
• время выполнения параллельного алгоритма ограничивается сверху ве-
личинами, приведенными в теоремах 4 и 5.
• Для вывода рекомендаций по формированию расписания по параллель-
ному выполнению алгоритма приведем доказательство теоремы 4.
Доказательство теоремы 4 [1]. Пусть H∞ есть расписание для достижения
минимально возможного времени выполнения T∞. Для каждой итерации τ, 0 ≤ τ ≤ T∞,
выполнения расписания H∞ обозначим через nτ количество операций, выполняемых
в ходе итерации τ. Расписание выполнения алгоритма с использованием p процессо-
ров может быть построено следующим образом. Выполнение алгоритма разделим на
T∞ шагов; на каждом шаге τ следует выполнить все операции, которые выполнялись
на итерации τ расписания H∞. Выполнение этих операций может быть выполнено
не более, чем за   p n /
τ итераций при использовании p процессоров. Время
выполнения алгоритма p T может быть оценено следующим образом:
∞
= =
+ =




 + <





= ∑ ∑∞ ∞ T
p
T
p
n
p
n
T
T T
p
1
1 1
1
τ
τ
τ
τ .
Доказательство теоремы дает практический способ построения расписания
параллельного алгоритма. Первоначально может быть построено расписание без
учета ограниченности числа используемых процессоров (расписание для параком-
пьютера). Затем, следуя схеме вывода теоремы, может быть построено расписание
для конкретного количества процессоров.
Показатели эффективности параллельного алгоритма
Ускорение, получаемое при использовании параллельного алгоритма для p
процессоров, по сравнению с последовательным вариантом выполнения вычислений
определяется
( ) ( ) ( )nTnT nS
p p /
1 = ,
т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполне-
ния параллельного алгоритма (величина n используется для параметризации вычис-
лительной сложности решаемой задачи и может пониматься, например, как количе-
ство входных данных задачи).
Эффективность использования параллельным алгоритмом процессоров при
решении задачи определяется соотношением