ВУЗ:
Составители:
57
N и наоборот. При рассмотрении конкретных вычислительных алгоритмов по-
строение функции изоэффективности позволяет выявить пути совершенствова-
ния параллельных алгоритмов.
Для построения этих функций удобно использовать закон Густавсона –
Барсиса. Эффективность использования s процессоров в соответствии с этим
законом выражается в виде
1
`1
s
s
R
E g
s s
.
При заданном фиксированном p
s
=const с использованием этого равенства мож-
но построить аналитическое соотношение для функции изоэффективности в
следующем виде:
,
s
g F E s
.
Такая форма может оказаться более удобной в случае, когда известна доля вре-
мени на проведение последовательных расчетов в выполняемых параллельных
вычислениях.
4.7 Верхняя граница времени выполнения параллельного алгоритма
Для любого количества используемых процессоров – s справедлива сле-
дующая верхняя оценка для времени выполнения параллельного алгоритма
T
s
<T
∞
+T
1
/s. (4.24)
Действительно, пусть H
∞
есть расписание для достижения минимально воз-
можного времени выполнения T
∞
. Для каждой итерации τ, 0<τ<T
∞
выполнения
расписания H
∞
обозначим через n
τ
количество операций, выполняемых в ходе
итерации τ. Расписание выполнения алгоритма с использованием s процессоров
может быть построено следующим образом. Выполнение алгоритма разделим
на T
∞
шагов; на каждом шаге τ следует выполнить все n
τ
операций, которые вы-
полнялись на итерации τ расписания H
∞
. Эти операции могут быть выполнены
не более чем за n
τ
/s итераций при использовании s процессоров. Как резуль-
тат, время выполнения алгоритма T
s
может быть оценено следующим образом:
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
