Составители:
Рубрика:
§ 4. Ускорение при распараллеливании
Пуcть алгоритм реализуется на вычислительной системе за
время T . Рассмотрим гипотетическое "идеальное" простое функ-
циональное устройство, которое имеет возможность выполнять все
операции алгоритма за такие же времена, за которые эти опера-
ции выполняются в системе. Предположим, что время реализации
этого алгоритма на идеальном функциональном устройстве равно
T
0
.
Определение 4.1. Отношение U = T
0
/T называется ускоре-
нием реализации алгоритма на параллельной системе.
Теорема 4.1. Пусть параллельная система состоит из s
независимых функциональных устройств с пиковыми производи-
тельностями p
1(1)
, . . . , p
1(s)
. Предположим, что при реализации
алгоритма загруженность i-го функционального устройства рав-
на z
(i)
, i = 1, . . . , s. Тогда достигаемое ускорение U вычисляется
по формуле
U =
s
X
i=1
p
1(i)
z
(i)
. (4.1)
Д о к а з а т е л ь с т в о. Обозначим T время реализации алгорит-
ма на нашей системе, p
1
— номинальную (пиковую) производитель-
ность системы, z — ее загруженность. Из формулы (3.3) предыду-
щего параграфа имеем
Z · P
1
=
s
X
i=1
p
1(i)
z
(i)
. (4.2)
По определению загруженности Z = R
T
/P
T
, где R
T
— стоимость
обработки алгоритма; она равна T
0
, a P
T
= P
1
· T (так как система
работает стабильно). Итак
Z =
T
0
P
1
· T
,
откуда
Z · P
1
=
T
0
T
.
Подставляя это в (4.2), получаем (4.1).
62
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
