Стационарная разметка
Cтраница 2
В § 3.1 и § 3.2 проблема реализуемости недетерминированной модели потоковых вычислений сводится к поиску стационарной и неизбыточной разметки М - сети на верхней полуструктуре ее свойств, не убывающих в процессе решения задачи разметки. Стационарной разметки может и не существовать. Достигнутая стационарная разметка охватывает все допустимые истории процессов, обусловленные информационной структурой программы. [16]
Например, заданы стандартное окружение для анализа G ( V, A), ( L, Л), F, 2V х 2А - F и некоторая начальная разметка графа G. Требуется найти стационарную разметку, при которой свойство любой дуги является наибольшей нижней гранью множества допустимых в соответствии с правилами разметки свойств. Задача анализа называется прямой, когда свойства любой вершины определяются свойствами ее предшественников. Если же свойства вершины зависят только от свойств ее преемников, то имеет место обратная задача анализа. [17]
 |
Алгоритм распознавания недостижимости стационарной разметки. [18] |
Монотонность функции Л позволяет распознавать недостижимость стационарной разметки, не дожидаясь завершения прохода с возвращениями по всем уровням сети. Тогда уровень / препятствует достижимости стационарной разметки. [19]
 |
Алгоритм распознавания недостижимости стационарной разметки. [20] |
При этом проверяется, возрастают ли приведенные свойства вершин уровня. Если нет уровней, препятствующих достижимости стационарной разметки, то она и является результатом работы алгоритма. [21]
 |
Репликация входов гамаков. [22] |
Другой вопрос, который возникает при наличии гамаков, блокирующих вычисления, заключается в следующем. Каким образом, следует преобразовать М - сеть, чтобы стационарная разметка стала достижимой. Ясно, что для этого каким-то способом нужно устранить взаимозависимость путей, ведущих от входов к выходам гамака. [23]
Назовем состояние схемы Янова, при котором выполнена посылка правила вывода П1, стационарной верхней разметкой. Это название, уже употреблявшееся неформально в предыдущем параграфе, оправдано тем, что в условиях стационарной разметки никакое дальнейшее применение аксиом А9 и А10 не изменит верхней разметки дуг схемы. [24]
В § 3.1 и § 3.2 проблема реализуемости недетерминированной модели потоковых вычислений сводится к поиску стационарной и неизбыточной разметки М - сети на верхней полуструктуре ее свойств, не убывающих в процессе решения задачи разметки. Стационарной разметки может и не существовать. Достигнутая стационарная разметка охватывает все допустимые истории процессов, обусловленные информационной структурой программы. [25]
Если его свойство при переразметке строго возрастает, то стационарной разметки не существует. Поэтому можно построить конструктивный прием, который следует использовать для проверки существования стационарной разметки М - сети с гамаками. [26]
Пусть in ( e), out ( e) - метки входной и выходной позиций, которым инцидентна дуга е е Е М - сети. Если начальная разметка каждого уровня минимальна, т.е. ( Ve Е) / i ( е) г [ in ( е), out ( е) ], ( Vv V jj, ( v) - d ( v) 1, за исключением процессов, не участвующих в альтернативах вычислений, то стационарная разметка М - сети является неизбыточной. [27]
Если его свойство при переразметке строго возрастает, то стационарной разметки не существует. Поэтому можно построить конструктивный прием, который следует использовать для проверки существования стационарной разметки М - сети с гамаками. [28]
Объектом анализа будет маркированный потоковый граф с метками дуг и вершин, вид ( семантику) которых мы не конкретизируем. Заметим, что в вводном пункте § 3.1, посвященном основным понятиям разметки и анализа, мы не определяли точно, что представляет собой информация на входе 1и и выходе Ои вершины и графа и каковы параметры Ри, Gu. Можно ли в таких условиях в результате анализа обобщенного маркированного потокового графа установить, достижима ли стационарная разметка. [29]
Страницы: 1 2