Составители:
Рубрика:
4) временн´ая развертка однозначно определяет параллельную
форму алгоритма; для ее построения следует объединить в ярусы
операции, начинающиеся в один и тот же момент, а сами ярусы
упорядочить по возрастанию времени.
Теорема 2.1. Для любого вектора t имеется альтернатива:
либо базовая система G
0
срабатывает и реализует алгоритм G,
либо работа системы G
0
останавливается.
Д о к а з а т е л ь с т в о. Очевидно, что для i-го функционально-
го устройства системы может случиться одно из двух: а) в момент
времени t
i
все данные для его работы поступили; б) в момент t
i
данные не поступили. В первом случае функциональное устрой-
ство срабатывает, во втором случае происходит отказ и система
останавливается.
Теорема 2.2. Для того чтобы программа t по базовой си-
стеме G
0
реализовывала алгоритм G, необходимо и достаточно,
чтобы для любых (i, j), для которых существует дуга, ведущая
из i-й вершины в j-ю, разность t
j
− t
i
была не меньше времени
срабатывания i-го функционального устройства.
Д о к а з а т е л ь с т в о очевидно, ибо к моменту срабатывания j-
го функционального устройства должны быть готовы данные для
него; это означает, что для всех дуг (i, j), ведущих в j-е функцио-
нальное устройство, должно выполняться условие: разность t
j
− t
i
не меньше времени срабатывания i-го функционального устрой-
ства.
Следствие 2.1. Если путь ведет из i-й вершины в j-ю, то
условие теоремы 2.2 эквивалентно тому, чтобы разность t
j
− t
i
была не меньше суммы времен срабатывания всех функциональ-
ных устройств на этом пути, кроме j-го.
Замечание. Совокупность всех базовых программ, реализую-
щих G на системе G
0
, полностью описывается теоремой 2.2.
Развертку t можно корректировать во время ее выполне-
ния. Это происходит весьма эффективно, если эта коррекция вы-
полняется самими функциональными устройствами, начинающи-
ми свою работу только после того, как вычислены все аргумен-
ты. Этим будет достигнуто наиболее эффективное выполнение ал-
горитма (если, конечно, его работу не задерживают входные дан-
ные). Эта ситуация представляет типичный пример, когда резуль-
таты выполнения алгоритма управляют работой вычислительной
системы.
69
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
