Составители:
Рубрика:
π
L
устройств, необходимых для реализации операций, соответству-
ющих множеству L, определится формулой
π
L
= max
τ≥0,t
i
=τ
q
L
(t, τ). (2.3)
Рассмотрим какую-либо строку соотношения (2.1), и пусть эта
строка соответствует дуге, идущей из вершины v
s
в вершину v
r
,
причем в вершине v
s
операция выполняется за время h
(s)
(номер s
здесь, вообще говоря, не означает порядковый номер компоненты
вектора h и связан с номером вершины — начала рассматриваемой
дуги). Если t
r
− t
s
> h
(s)
, то это означает, что в момент времени
t
s
+ h
(s)
операция будет выполнена, и результат ее должен где-то
храниться до момента t
r
прежде, чем он будет использован при
выполнении операции, соответствующей вершине v
r
.
Поэтому вектор h + A
T
t определяет режим использования па-
мяти вычислительной системы для хранения промежуточных ре-
зультатов. В частности, нужное число ψ каналов записи в память
и число θ каналов чтения из памяти находятся по формулам
*
ψ = max
τ≥0, t
r
−t
s
>h
(s)
q
v
(t + h
∗
, τ),
где h
∗
— вектор длительностей h
(i)
операции в i-й вершине, i =
1, 2, . . . , n,
θ = max
t
r
=τ
q
v
(t, τ). (2.4)
В первой формуле вычисляется количество координат вектора
t равных t
s
+ h
(s)
, для которых t
r
− t
s
> h
(s)
(или, иначе, число дуг,
для которых включение очередного устройства задерживается) и
берется максимум по подобным дугам, а во второй — максимальное
число устройств, использующих задержанные результаты по всем
моментам времени.
2.4. Задача отображения алгоритмов на
вычислительные системы
как задача минимизации функционала
Теперь видно, что неравенство (2.1) определяет все ограниче-
ния и требования, проистекающие из-за внутренних особенностей
*
q
v
(t + h
∗
, τ) — число компонент (вершин), для которых t
i
+ h
i
= τ; из них
выделены лишь те вершины, где t
r
− t
s
> h
(s)
. Это можно написать в виде
ψ = max q
v
(t, τ) при условиях t
s
+ h
(s)
= τ, t
r
− t
s
> h
(s)
.
86
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
