Составители:
Рубрика:
лярное умножение на вектор временн´ой развертки очевидно дает
разность t
i
0
(j)
− t
i
00
(j)
, так что неравенство (2.1) принимает вид
−(t
i
0
(j)
− t
i
00
(j)
) ≥ h
j
.
Последнее означает, что момент времени начала операции в конце
дуги должен быть больше момента времени начала операции в на-
чале дуги не менее чем на величину времени реализации операции,
указанной в начале дуги.
Замечание. По матрице A, векторам t и h определяются мно-
гие характеристики процесса реализации алгоритма; в частности:
1) время T выполнения алгоритма равно (см. § 8 из первой гла-
вы)
T (t) = max
i
(t
i
+ τ
i
) − min
i
t
i
, (2.2)
где τ
i
— время реализации операции в i-й вершине;
2) порядок выполнения операций алгоритма соответствует упо-
рядочению по возрастанию координат вектора t ;
3) если какие-то координаты вектора t одинаковы, то это озна-
чает, что соответствующие операции выполняются параллельно на
разных функциональных устройствах;
4) если перенумеровать подряд все группы равных координат
вектора t и провести топологическую сортировку вершин графа ал-
горитма, помечая одним индексом вершины, относящиеся к равным
компонентам t
k
, то эта сортировка определит параллельную форму
алгоритма, реализуемую при временном режиме, соответствующем
вектору t;
5) синхронность или асинхронность работы функциональных
устройств связывается с равномерным или неравномерным распре-
делением (различных) координат вектора t.
2.3. Об использовании памяти для хранения
промежуточных результатов
В графе G выделим множество L вершин, L ⊂ V (например, L
может быть множеством вершин, соответствующих операции сло-
жения). Обозначим q
L
(t, τ) число координат t
i
вектора t, равных τ
и таких, что t
i
— момент включения функционального устройства,
реализующего операцию в i-й вершине, лежащей в L. Теперь число
85
Страницы
- « первая
- ‹ предыдущая
- …
- 82
- 83
- 84
- 85
- 86
- …
- следующая ›
- последняя »
