Составители:
Рубрика:
С другой стороны, z
j
=
1
T
P
r
i=1
τ
i
N
ij
, откуда
s
X
j=1
z
j
=
1
T
r
X
i=1
s
X
j=1
τ
i
N
ij
,
что совпадает с доказываемой формулой (2.5).
Теорема 2.4 Пусть s конвейерных функциональных
устройств за время T в общей сложности выполняют N опера-
ций, и каждое из этих функциональных устройств может вы-
полнять лишь операции одной длительности. Пусть z
j
— загру-
женность j-го устройства. Тогда
s
X
j=1
z
j
=
N
T
. (2.6)
Д о к а з а т е л ь с т в о. Обозначим τ
j
длительность операций на
j-м устройстве, а N
j
— их количество.
Стоимость реально выполненной работы на j-м устройстве рав-
на τ
j
N
j
, а максимально возможная стоимость работы, которую
можно осуществить на j-м устройстве, по теореме 2.2 равна τ
j
T .
Поэтому загруженность j-го устройства равна z
j
= (τ
j
N
j
)/(τ
j
T ) =
(N
j
)/T .
Поскольку
P
s
j=1
N
j
= N , то теперь легко получить формулу
(2.6). Теорема доказана.
§ 3. О времени реализации алгоритма
Теорема 3.1. Время реализации алгоритма не меньше, чем
время выполнения операций, находящихся на каждом произвольно
выбранном пути графа алгоритма.
Д о к а з а т е л ь с т в о вытекает из того факта, что операции,
находящиеся на одном пути алгоритма не могут выполняться од-
новременно.
Теорема 3.2. Любой алгоритм при подходящем составе и
количестве функциональных устройств может быть реализован
за время, равное максимальному из времен последовательного вы-
полнения операций, находящихся на отдельных путях графа алго-
ритма.
60
Страницы
- « первая
- ‹ предыдущая
- …
- 57
- 58
- 59
- 60
- 61
- …
- следующая ›
- последняя »
