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

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
15
Стоимость операции – время её реализации. Максимальная стоимость рабо-
ты, которую можно выполнить за время T , равна T для простого функционального
устройства и nT для конвейерного функционального устройства длины n .
В общем случае структура алгоритма (программы) имеет фрагменты, допус-
кающие одновременное выполнение на нескольких функциональных устройствах –
это параллельная часть программы, а есть фрагменты, которые должны выполняться
последовательно и на одном устройстве – это последовательная часть программы.
Пусть время выполнения алгоритма на последовательной машине 1 T , причем
s T - время выполнения последовательной части алгоритма, а p T - параллельной, тогда
полное время p s T T T + =
1 . Для идеально параллельной машины время выполнения той
же программы для N независимых ветвей параллельной части распределяется по
одной на N процессорах, уменьшается до
N
Tp , а полное время выполнения
программы
N
T
T Tp
s + =
2 .
Коэффициент ускорения, т.е. во сколько раз быстрее на параллельной
машине выполняется программа, чем на последовательной, определяется как
N
P S
N
T
T
T T
T
T K
p
s
p s
+
=
+
+
= = 1
2
1 ,
где
p s
s
T T
T S
+
= ,
p s
p
T T
T
P +
= - относительные доли последовательной и параллельной
частей ) PS( 1 = +.
Степенью параллелизма называют количество процессоров, используемых в
каждый момент времени для выполнения программы.
Зависимость коэффициента ускорения от числа процессоров и степени парал-
лелизма алгоритма (Рис.1.3) (относительной доли параллельной части) носит назва-
ние закона Амдала: «В случае, когда задача разделяется на несколько частей,
суммарное время ее выполнения на параллельной системе не может быть меньше
времени выполнения самого длинного фрагмента».