Учебное пособие Казань 018 удк

3.7. Верхняя граница времени выполнения параллельного алгоритма 
Для любого количества используемых процессоров - 
s 
справедлива 
следующая верхняя оценка для времени выполнения параллельного алгоритма 
𝑇
𝑠
< 𝑇
∞
+ 𝑇
1
/𝑠
(3.24) 
Действительно, пусть 
𝐻
∞
есть расписание для достижения минимально 
возможного времени выполнения 
𝑇
∞
. Для каждой итерации 
𝜏, 0 < 𝜏 < 𝑇
∞
выполнения расписания 
𝐻
∞
обозначим через 
𝑛
𝜏
количество операций, 
выполняемых в ходе итерации 
τ
. Расписание выполнения алгоритма с 

---

36 
использованием 
s
процессоров может быть построено следующим образом. 
Выполнение алгоритма разделим на 
𝑇
∞
шагов; на каждом шаге 
τ
следует 
выполнить все 
𝑛
𝜏
операций, которые выполнялись на итерации 
τ
расписания 
𝐻
∞
. Эти операции могут быть выполнены не более чем за 
n
τ
/s
итераций при 
использовании 
s
процессоров. Как результат, время выполнения алгоритма 
T
s
может быть оценено следующим образом: 
𝑇
𝑠
= ∑
]
𝑛
𝜏
𝑠
[
𝑇
∞
𝑇=𝑇
1
< ∑
]
𝑛
𝜏
𝑠
+ 1[ =
𝑇
1
𝑠
+ 𝑇
∞
𝑇
∞
𝑇=𝑇
1
, 
(3.25) 
где ]*[ - означает операцию округления до целого числа в сторону 
увеличения. 
Приведенная схема рассуждений, по существу, дает практический способ 
построения расписания параллельного алгоритма. Первоначально может быть 
построено расписание без учета ограниченности числа используемых 
процессоров (расписание для 
паракомпьютера
). Затем, в соответствии с 
описанной выше схемой, может быть построено расписание для конкретного 
количества процессоров.